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

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

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

для

1 ⩽ k ⩽ n

,

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

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

для

1 ⩽ k ⩽ n + 1

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

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

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

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

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

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

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

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

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

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

\begin{matrix} (\binom{n}{k}) + (\binom{n}{k - 1}) & = \frac{n!}{k! (n - k)!} + \frac{n!}{(k - 1)! (n - k + 1)!} \\ = n! [\frac{n - k + 1}{k! (n - k + 1)!} + \frac{k}{k! (n - k + 1)!}] \\ = \frac{n! (n + 1)}{k! (n - k + 1)!} = (\binom{n + 1}{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}

См. также

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

Примечания

Шаблон:Примечания

Литература

Шаблон:Refbegin

Данная статья включает материал из статьи «Pascal's rule» с сайта PlanetMath, опубликованной под лицензией CCA-SA
Данная статья включает материал из статьи «Pascal's rule proof» с сайта PlanetMath, опубликованной под лицензией CCA-SA
Шаблон:Книга

Шаблон:Refend

Шаблон:Rq

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

Содержание

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

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

Обобщение

См. также

Примечания

Литература

Навигация

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

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

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

Обобщение

См. также

Примечания

Литература

Навигация

Поиск