帕斯卡法則

维基百科,自由的百科全书
跳转至: 导航搜索
Confusion grey.svg
提示:本条目的主题不是帕斯卡定律

帕斯卡法則組合數學上的一個關於二項式係數恆等式。它說明對於正整數n,kk \le n),

{n-1\choose k} + {n-1\choose k-1} = {n\choose k}

組合數學上的意義和證明[编辑]

{n\choose k}表示在有n個元素的集內,有k個元素的子集的數目。其實這些子集之中,可分為包含第一個元素的和不含第一個元素的。包含第一個元素的子集有{n-1\choose k-1}個,不含的有{n-1\choose k}個。

代數證明[编辑]

 { n \choose k } + { n \choose k-1 }  =  { n+1 \choose k }

重寫左邊為

 \frac{n!}{k!(n-k)!} + \frac{n!}{(k-1)!(n-(k-1))!}
 =  \frac{(n-k+1)n!}{(n-k+1)k!(n-k)!}+\frac{kn!}{k(k-1)!(n-k+1)!}
 =  \frac{(n-k+1)n!+kn!}{k!(n-k+1)!}
 =  \frac{(n+1)n!}{k!((n+1)-k)!}
 =  \frac{(n+1)!}{k!((n+1)-k)!}
 =  { n+1 \choose k }

推广[编辑]

n, k_1, k_2, k_3,\dots ,k_p, p \in \mathbb{N}^* \,\!n=k_1+k_2+k_3+ \cdots +k_p \,\!。那么:


\begin{align}
& {} \quad {n-1\choose k_1-1,k_2,k_3, \dots, k_p}+{n-1\choose k_1,k_2-1,k_3,\dots, k_p}+\cdots+{n-1\choose k_1,k_2,k_3,\dots,k_p-1} \\
& = \frac{(n-1)!}{(k_1-1)!k_2!k_3! \cdots k_p!} + \frac{(n-1)!}{k_1!(k_2-1)!k_3!\cdots k_p!} + \cdots + \frac{(n-1)!}{k_1!k_2!k_3! \cdots (k_p-1)!} \\
& = \frac{k_1(n-1)!}{k_1!k_2!k_3! \cdots k_p!} + \frac{k_2(n-1)!}{k_1!k_2!k_3! \cdots k_p!} + \cdots + \frac{k_p(n-1)!}{k_1!k_2!k_3! \cdots k_p!} = \frac{(k_1+k_2+\cdots+k_p) (n-1)!}{k_1!k_2!k_3!\cdots k_p!}  \\
& = \frac{n(n-1)!}{k_1!k_2!k_3! \cdots k_p!} = \frac{n!}{k_1!k_2!k_3! \cdots k_p!}
= {n\choose k_1, k_2, k_3, \dots , k_p}.
\end{align}

参见[编辑]