Правило Паскаля (Hjgfnlk Hgvtglx)

Перейти к навигации Перейти к поиску

Правило Паскалякомбинаторное тождество для биномиальных коэффициентов. Правило утверждает, что для любого натурального числа 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, опубликованной под лицензией CCA-SA
  • Данная статья включает материал из статьи «Pascal's rule proof» с сайта PlanetMath, опубликованной под лицензией CCA-SA
  • Russell Merris. Combinatorics. — John Wiley & Sons., 2003. — ISBN 978-0-471-26296-1.