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

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

( n − 1 k ) + ( n − 1 k − 1 ) = ( n k ) {displaystyle {n-1 choose k}+{n-1 choose k-1}={n choose k}} для 1 ⩽ k ⩽ n {displaystyle 1leqslant kleqslant n} ,

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

( n k ) + ( n k − 1 ) = ( n + 1 k ) {displaystyle {n choose k}+{n choose k-1}={n+1 choose k}} для 1 ⩽ k ⩽ n + 1 {displaystyle 1leqslant kleqslant n+1}

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

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

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

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

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

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

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

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

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

( n k ) + ( n k − 1 ) = ( n + 1 k ) . {displaystyle {n choose k}+{n choose k-1}={n+1 choose k}.}

( n k ) + ( n k − 1 ) = n ! k ! ( n − k ) ! + n ! ( k − 1 ) ! ( n − k + 1 ) ! = n ! [ n − k + 1 k ! ( n − k + 1 ) ! + k k ! ( n − k + 1 ) ! ] = n ! ( n + 1 ) k ! ( n − k + 1 ) ! = ( n + 1 k ) {displaystyle {egin{aligned}{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)!}} ight]&={frac {n!(n+1)}{k!(n-k+1)!}}={inom {n+1}{k}}end{aligned}}}

Обобщение

Пусть n , k 1 , k 2 , k 3 , … , k p , p ∈ N ∗ {displaystyle n,k_{1},k_{2},k_{3},dots ,k_{p},pin mathbb {N} ^{*}} и n = k 1 + k 2 + k 3 + ⋯ + k p {displaystyle n=k_{1}+k_{2}+k_{3}+cdots +k_{p}} . Тогда

( n − 1 k 1 − 1 , k 2 , k 3 , … , k p ) + ( n − 1 k 1 , k 2 − 1 , k 3 , … , k p ) + ⋯ + ( n − 1 k 1 , k 2 , k 3 , … , k p − 1 ) = ( n − 1 ) ! ( k 1 − 1 ) ! k 2 ! k 3 ! ⋯ k p ! + ( n − 1 ) ! k 1 ! ( k 2 − 1 ) ! k 3 ! ⋯ k p ! + ⋯ + ( n − 1 ) ! k 1 ! k 2 ! k 3 ! ⋯ ( k p − 1 ) ! = k 1 ( n − 1 ) ! k 1 ! k 2 ! k 3 ! ⋯ k p ! + k 2 ( n − 1 ) ! k 1 ! k 2 ! k 3 ! ⋯ k p ! + ⋯ + k p ( n − 1 ) ! k 1 ! k 2 ! k 3 ! ⋯ k p ! = ( k 1 + k 2 + ⋯ + k p ) ( n − 1 ) ! k 1 ! k 2 ! k 3 ! ⋯ k p ! = n ( n − 1 ) ! k 1 ! k 2 ! k 3 ! ⋯ k p ! = n ! k 1 ! k 2 ! k 3 ! ⋯ k p ! = ( n k 1 , k 2 , k 3 , … , k p ) . {displaystyle {egin{aligned}&{}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{aligned}}}