Правило Паскаля — комбинаторное тождество для биномиальных коэффициентов. Правило утверждает, что для любого натурального числа n мы имеем:
- для ,
где является биномиальным коэффициентом. Оно также часто записывается в виде
- для
Комбинаторное доказательство
Правило Паскаля имеет интуитивное комбинаторное значение. Напомним, что подсчитывает, сколькими способами можно выбрать подмножество с b элементами из множества с a элементами. Таким образом, правая часть тождества подсчитывает, сколькими способами можно получить k-подмножество из множества с n элементами.
Теперь представим, что вы выделяете определённый элемент X из множества с n элементами. Таким образом, каждый раз, когда вы выбираете k элементов из подмножества, имеется две возможности — X принадлежит выбранному подмножеству или нет.
Если X находится в подмножестве, нужно лишь выбрать ещё k − 1 объектов (поскольку известно, что X будет в подмножестве) из оставшихся n − 1 объектов. Это можно сделать способами.
Если X не принадлежит подмножеству, нужно выбрать все k элементов из подмножества, состоящего из n − 1 объектов, не равных X. Это можно сделать способами.
Мы получаем, что число способов получить k-подмножество из n-элементного множества, которое, как мы знаем, равно , равно также числу
См. также Биективное доказательство.
Алгебраическое доказательство
Нужно показать, что
Обобщение
Пусть и . Тогда
См. также
Примечания
Литература
- Данная статья включает материал из статьи «Pascal's rule» с сайта PlanetMath, опубликованной под лицензией
- Данная статья включает материал из статьи «Pascal's rule proof» с сайта PlanetMath, опубликованной под лицензией
- Russell Merris. Combinatorics. — John Wiley & Sons., 2003. — ISBN 978-0-471-26296-1.