1. Сочетания

1.1 Числа С^k_n

Пусть X - множество, состоящее из n элементов. Любое подмножество Y множества X, содержащее k элементов, называется сочетанием k элементов из n; при этом, разумеется, k ? n.

Число различных сочетаний k элементов из n обозначается С_n^k . Одной из важнейших формул комбинаторики является следующая формула для числа С_n^k :

Её можно записать после очевидных сокращений следующим образом:

В частности,

Это вполне согласуется с тем, что в множестве X имеется только одно подмножество из 0 элементов - пустое подмножество.

Приведём доказательство формулы (2). Пусть Y - какое-либо подмножество множества X , содержащее k элементов. Составив всевозможные перестановки из этих элементов, получим k! различных строк длинной k. Если указанную операцию проделать с каждым подмножеством Y, содержащим k элементов, то получим всего C_n^k · k! различных строк длинной k . Но очевидно, что таким путём должны получиться все без исключения строки длиной k без повторений, которые можно составить из элементов множества X. поскольку число таких строк равно A_n^k , то имеем соотношение C_n^k · k! = A_n , из которого следует C_n^k =A^k_n, т.е. формула (2).