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

Решим задачу: сколькими способами из множества можно составить всевозможные подмножества по k элементов каждое?

Число таких подмножеств будем называть числом сочетаний без повторений из m элементов по k и обозначать . Решить ее проще всего тоже исходя из понятия вектора. Если бы мы искали число упорядоченных k - подмножеств без повторений, составленных из множества Х в m элементов, то оно было бы равно

.

Но нас не интересует порядок элементов, выбранный в вектор длины k, а интересует лишь состав. Тогда среди различных векторов k! штук имеют одинаковые компоненты и отличаются лишь их порядком. Таким образом, сочетаний будет в k! раз меньше, чем размещений

.

Число сочетаний без повторений обладает следующими свойствами:

; ;

; ;

.

Удобно, также помнить, что .

Дата добавления: 2015-07-26