帕斯卡法則

帕斯卡法則是組合數學上的一個關於二項式係數的恆等式。它說明對於正整數$n$,$k$（$k \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}$

参见

• 杨辉三角形