9. Сочетания без повторений.

Одной из важнейших задач комбинаторики является подсчет числа -подмножеств -множества Такие неупорядоченные подмножества называются сочетаниями без повторений из элементов по а их число обозначают (от французского слова combinaison - сочетание). Например, из элементов -множества можно составить

Рис. 5

следующие подмножества

Число этих подмножеств равно 10. Значит, Отметим, что каждое множество X имеет лишь одно -подмножество, а именно пустое множество. Далее, в -множестве содержится одноэлементных подмножеств, т. е. подмножеств вида

Выведем формулу, выражающую через пят. Пусть из элементов -множества X составлены все -подмножества. Упорядочим всеми способами каждое из этих подмножеств. Мы получим, и притом лишь по одному разу, все упорядоченные -подмножества -множества Их число, как мы знаем, равно Но число -подмножеств в X равно а каждое из них можно упорядочить способами. Значит, имеет место равенство Из него вытекает, что Заменяя в полученной формуле его выражением получаем: