WikiSort.ru - Не сортированное

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

${\displaystyle {n-1 \choose k}+{n-1 \choose k-1}={n \choose k}}$ для ${\displaystyle 1\leqslant k\leqslant n}$ ,

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

${\displaystyle {n \choose k}+{n \choose k-1}={n+1 \choose k}}$ для ${\displaystyle 1\leqslant k\leqslant n+1}$

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

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

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

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

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

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

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

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

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

${\displaystyle {n \choose k}+{n \choose k-1}={n+1 \choose k}.}$

${\displaystyle {\begin{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)!}}\right]\\&={\frac {n!(n+1)}{k!(n-k+1)!}}={\binom {n+1}{k}}\end{aligned}}}$

Обобщение

Пусть ${\displaystyle n,k_{1},k_{2},k_{3},\dots ,k_{p},p\in \mathbb {N} ^{*}}$ и ${\displaystyle n=k_{1}+k_{2}+k_{3}+\cdots +k_{p}}$ . Тогда

${\displaystyle {\begin{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}}}$

См. также

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

Примечания

Литература

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка. Исправить статью согласно стилистическим правилам Википедии.