Русская Википедия:Правило Паскаля
Шаблон:Distinguish Правило Паскаля — это комбинаторное тождество для биномиальных коэффициентов. Правило утверждает, что для любого натурального числа n мы имеем:
- <math>{n-1\choose k} + {n-1\choose k-1} = {n\choose k}</math> для <math>1 \leqslant k \leqslant n </math>,
где <math>{n\choose k}</math> является биномиальным коэффициентом. Оно также часто записывается в виде
- <math>
{n \choose k} + {n \choose k-1} = {n + 1 \choose k}</math> для <math>1 \leqslant k \leqslant n + 1 </math>
Комбинаторное доказательство
Правило Паскаля имеет интуитивное комбинаторное значение. Напомним, что <math>{a\choose b}</math> подсчитывает, сколькими способами можно выбрать подмножество с b элементами из множества с a элементами. Таким образом, правая часть тождества <math>{n\choose k}</math> подсчитывает, сколькими способами можно получить k-подмножество из множества с n элементами.
Теперь представим, что вы выделяете определённый элемент X из множества с n элементами. Таким образом, каждый раз, когда вы выбираете k элементов из подмножества, имеется две возможности — X принадлежит выбранному подмножеству или нет.
Если X находится в подмножестве, нужно лишь выбрать ещё k − 1 объектов (поскольку известно, что X будет в подмножестве) из оставшихся n − 1 объектов. Это можно сделать <math>n-1\choose k-1</math> способами.
Если X не принадлежит подмножеству, нужно выбрать все k элементов из подмножества, состоящего из n − 1 объектов, не равных X. Это можно сделать <math>n-1\choose k</math> способами.
Мы получаем, что число способов получить k-подмножество из n-элементного множества, которое, как мы знаем, равно <math>{n\choose k}</math>, равно также числу <math>{n-1\choose k-1} + {n-1\choose k}.</math>
См. также Биективное доказательство.
Алгебраическое доказательство
Нужно показать, что
- <math> { n \choose k } + { n \choose k-1 } = { n+1 \choose k }.</math>
- <math>\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>n, k_1, k_2, k_3,\dots ,k_p, p \in \mathbb{N}^* </math> и <math>n=k_1+k_2+k_3+ \cdots +k_p </math>. Тогда
- <math>
\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>
См. также
Примечания
Литература
- Данная статья включает материал из статьи «Pascal's rule» с сайта PlanetMath, опубликованной под лицензией CCA-SA
- Данная статья включает материал из статьи «Pascal's rule proof» с сайта PlanetMath, опубликованной под лицензией CCA-SA
- Шаблон:Книга
