帕斯卡法則

Template:Unreferenced Template:Distinguish 帕斯卡法則是組合數學上的一個關於二項式係數的恆等式。它說明對於正整數 $n$ , $k$ （ $k \leq n$ ），

(\binom{n - 1}{k}) + (\binom{n - 1}{k - 1}) = (\binom{n}{k})

。

組合數學上的意義和證明

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

(\binom{n - 1}{k}) + (\binom{n - 1}{k - 1}) = (\binom{n}{k})

重寫左邊為

\begin{matrix} \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)!} \\ = (\binom{n}{k}) \end{matrix}

设 $n, k_{1}, k_{2}, k_{3}, \dots, k_{p}, p \in ℕ^{*}$ 及 $n = k_{1} + k_{2} + k_{3} + \dots + k_{p}$ 。那么：

\begin{matrix} (\binom{n - 1}{k_{1} - 1, k_{2}, k_{3}, \dots, k_{p}}) + (\binom{n - 1}{k_{1}, k_{2} - 1, k_{3}, \dots, k_{p}}) + \dots + (\binom{n - 1}{k_{1}, k_{2}, k_{3}, \dots, k_{p} - 1}) \\ = \frac{(n - 1)!}{(k_{1} - 1)! k_{2}! k_{3}! \dots k_{p}!} + \frac{(n - 1)!}{k_{1}! (k_{2} - 1)! k_{3}! \dots k_{p}!} + \dots + \frac{(n - 1)!}{k_{1}! k_{2}! k_{3}! \dots (k_{p} - 1)!} \\ = \frac{k_{1} (n - 1)!}{k_{1}! k_{2}! k_{3}! \dots k_{p}!} + \frac{k_{2} (n - 1)!}{k_{1}! k_{2}! k_{3}! \dots k_{p}!} + \dots + \frac{k_{p} (n - 1)!}{k_{1}! k_{2}! k_{3}! \dots k_{p}!} \\ = \frac{(k_{1} + k_{2} + \dots + k_{p}) (n - 1)!}{k_{1}! k_{2}! k_{3}! \dots k_{p}!} \\ = \frac{n (n - 1)!}{k_{1}! k_{2}! k_{3}! \dots k_{p}!} \\ = \frac{n!}{k_{1}! k_{2}! k_{3}! \dots k_{p}!} \\ = (\binom{n}{k_{1}, k_{2}, k_{3}, \dots, k_{p}}) \end{matrix}