П.5. r -элементные подмножества (r - сочетания)

Определение. Пусть A - конечное множество. r - сочетанием множества A называется любое r - элементное подмножество множества A.

Пример 1. Пусть A = { a , a , a } - 3-х элементное множество. Выпишем все 2- сочетания множества A: { a , a }, { a , a }, { a , a }. n

Теорема 1. Пусть A есть n - элементное множество, n, r Î N . Справедливы утверждения:

1. Число всех r - сочетаний n - элементного множества равно .

2. Число всех r - элементных подмножеств n - элементного множества равно .

Доказательство. Обозначим K - число всех r - сочетаний n - элементного множества A. Каждое r - элементное подмножество n - элементного множества A определяет r! перестановок множества A, при этом разные подмножества определяют разные перестановки. Поэтому K × r! - число всех r - перестановок множества A, равное n . Отсюда следует, что K = n / r! = = . n