Сочетания

---

Теорема. Число сочетаний из n элементов по k вычисляется следующим образом:

(1)

Доказательство.

Пусть А — множество из n элементов. Чтобы построить его подмножество, состоящее из k элементов, нужно к подмножеству из (k–1) элементов присоединить любой из оставшихся элементов. Поскольку таких подмножеств (содержащих k–1 элемент) имеется и каждое из них можно сделать состоящим из k элементов n–k+1 способами, то, таким образом мы получим (n–k+1)• подмножеств. Но не все они будут различными, так как любое множество из k элементов может быть построено из (k–1)–элементного k способами присоединением первого элемента, второго и т.д. k–го. Как уже отмечалось, порядок элементов в подмножестве не имеет значения, поэтому вычисленное нами число в k раз больше, чем , т.е. k•=(n-k+1)•. Отсюда:

Получили формулу (1).