Правило Паскаля

Не следует путать с Закон Паскаля.

Правило Паскаля — это комбинаторное тождество для биномиальных коэффициентов. Правило утверждает, что для любого натурального числа n мы имеем

[math]\displaystyle{ {n-1\choose k} + {n-1\choose k-1} = {n\choose k} }[/math] для [math]\displaystyle{ 1 \leqslant k \leqslant n }[/math],

где [math]\displaystyle{ {n\choose k} }[/math] является биномиальным коэффициентом. Оно также часто записывается в виде

[math]\displaystyle{ {n \choose k} + {n \choose k-1} = {n + 1 \choose k} }[/math] для [math]\displaystyle{ 1 \leqslant k \leqslant n + 1 }[/math]

Комбинаторное доказательство

Правило Паскаля имеет интуитивное комбинаторное значение. Напомним, что [math]\displaystyle{ {a\choose b} }[/math] подсчитывает, сколькими способами можно выбрать подмножество с b элементами из множества с a элементами. Таким образом, правая часть тождества [math]\displaystyle{ {n\choose k} }[/math] подсчитывает, сколькими способами можно получить k-подмножество из множества с n элементами.

Теперь представим, что вы выделяете определённый элемент X из множества с n элементами. Таким образом, каждый раз, когда вы выбираете k элементов из подмножества, имеется две возможности — X принадлежит выбранному подмножеству или нет.

Если X находится в подмножестве, нужно лишь выбрать ещё k − 1 объектов (поскольку известно, что X будет в подмножестве) из оставшихся n − 1 объектов. Это можно сделать [math]\displaystyle{ n-1\choose k-1 }[/math] способами.

Если X не принадлежит подмножеству, нужно выбрать все k элементов из подмножества, состоящего из n − 1 объектов, не равных X. Это можно сделать [math]\displaystyle{ n-1\choose k }[/math] способами.

Мы получаем, что число способов получить k-подмножество из n-элементного множества, которое, как мы знаем, равно [math]\displaystyle{ {n\choose k} }[/math], равно также числу [math]\displaystyle{ {n-1\choose k-1} + {n-1\choose k}. }[/math]

См. также Биективное доказательство.

Алгебраическое доказательство

Нужно показать, что

[math]\displaystyle{ { n \choose k } + { n \choose k-1 } = { n+1 \choose k }. }[/math]

[math]\displaystyle{ \begin{align} { n \choose k } + { n \choose k-1} & = \frac{n!}{k! (n - k)!} + \frac{n!}{(k - 1)!(n - k + 1)!} \\ & = n! \left[ \frac{n -k + 1}{k!(n -k + 1)!} + \frac{k}{k!(n -k + 1)!}\right] \\ & = \frac{n!(n+1)}{k!(n -k + 1)!} = \binom{n+1}{k} \end{align} }[/math]

Обобщение

Пусть [math]\displaystyle{ n, k_1, k_2, k_3,\dots ,k_p, p \in \mathbb{N}^* }[/math] и [math]\displaystyle{ n=k_1+k_2+k_3+ \cdots +k_p }[/math]. Тогда

[math]\displaystyle{ \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} }[/math]

См. также

• Треугольник Паскаля