帕斯卡法則

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

重寫左邊為

:
\begin{align}
& {} \frac{(n-1)!}{k!(n-k-1)!} + \frac{(n-1)!}{(k-1)!(n-k)!} \\
& = \frac{(n-k)(n-1)!}{(n-k-1)!k!(n-k)}+\frac{k(n-1)!}{k(k-1)!(n-k)!} \\
& = \frac{(n-k)(n-1)!+k(n-1)!}{k!(n-k)!} \\
& = \frac{(n-1)! \times [(n-k)+k]}{k!(n-k)!} \\
& = \frac{(n-1)! \times n}{k!(n-k)!} \\
& = \frac{n!}{k!(n-k)!} \\
& = { n \choose k }
\end{align}

推广
设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}

参见

• 杨辉三角形

Закон Паскаля