47. Некоторые свойства сочетаний

Поскольку числа показывают, сколько K-Подмножеств содержится в данном N-множестве, то между ними есть целый ряд зависимостей, отражающих различНЫе зависимости между подмножествами. Эти зависимости можно доказывать по-разному. В некоторых случаях удобнее всего прямо воспользоваться формулой (7) для числа сочетаний. Однако более красивым И содержательным является иной способ, основанный на комбинаторных соображениях. Мы подсчитываем число подмножеств некоТОрого вида и разбиваем совокуПНость всех таких подмножеств на классы так, чтобы ни оДНо поДМНОжество нЕ попало в два различных класса. После ЭТого нАХодим, сколько подмножеств входит в каждый класс. СКлАдываЯ Полученные числа, снова получаем количество поДМНОжеств выбранного вида. Это и дает искомое соотношЕНие. Самым простым является соотношение

(9)

Выражающее, что число K-Подмножеств в N-множестве Совпадает с числом -Подмножеств того же Множества. Чтобы доказать это равенство, надо установИТь КаКую-то связь между K-Подмножествами и -подмножествами. Но если удалить из N-множества Х K-подмножество Y, то останется -Подмножество Y', которое называют Дополнением к Y в X. Ясно, что Y В свою очередь является дополнением к Y', . ПоэтоМУ из K-подмножеств и их дополнений можно Устроить ПАры, такие, что каждое K-Подмножество и каждое -Подмножество попадут лишь в одну пару. А это и Значит, что таких подмножеств одинаковое количество, т. Е.

Зафиксируем теперь какой-нибудь из П элементОВ, например А, и разобьем все сочетания из N элементов по K На два класса — содержащие элемент А и не содерЖАщИЕ ЭТого ЭЛЕМента. Число сочетаний первого класса раВНо — надо из оставшихся элементов выбрать еще элементов. А число сочетаний второго класса равно — надо выбрать K из всех элемеНТов, исключая А. Но любое сочетание относится или к первому, ИЛи ко второму классу. Поэтому

(10)

< Предыдущая		Следующая >