Число различных k-элементарных подмножеств n-элементарного множества

Посмотрим теперь, сколько существует разных подмножеств из k элементов в множестве, состоящем из п элементов (k < п).

ТеоремаЧисло различных k-элементных подмножеств n-элементарного множества равно

,

где сокращение п! = п * (п - 1) * ... * 3 * 2 * 1 называется факториалом числа n (читается n-факториал). Причем 0! = 1. А сокращение .

Доказательство.Чтобы построить k-элементное подмножество множества А, необходимо к (k - 1)-элементному множеству присоединить один из п - k + 1 элементов, которые не входят в это подмножество. Поскольку число (k - 1)­элементных подмножеств равно , И каждое из этих подмножеств можно сделать k-элементным п - k + 1 способами, по основному правилу комбина­торики получаем число * (n - k + 1) подмножеств. Однако не все эти подмножества будут различными, поскольку любое k-элементарное подмножество можно также построить k способами. Следовательно,

 

Поскольку – число одноэлементных подмножеств множества А – равно n, то

 

Теорема доказана.

 

Произвольное k-элементное подмножество множества А называется комбинацией, или выборкой, а число числом комбинаций или сочетаний из n элементов по k элементов.

Рис. 5.2.

 

Биномиальные коэффициенты имеют интересную геометрическую интерпре­тацию. Пусть имеем прямоугольную шахматную доску размером m на n, раз­мещенную на координатной плоскости. Эта доска состоит из m*n элементарных квадратов, разделенных n - 1 горизон­тальной линией и m - 1 вертикальной. Определим, сколькими разными самыми короткими путями можно попасть из точки (0, 0) в точку (m, n)на этой доске.

Каждый самый короткий путь, ведущий из точки (0, 0) в точку (m,n), состоит, очевидно, из m + n сторон элементарных квадратов, среди которых m гори­зонтальных и n вертикальных. Эти пути отличаются между собой только 1 числом вертикальных и горизонтальных сторон. Значит, общее количество путей равно числу способов, какими из т + n сторон можно выбрать n верти­кальных, т.е. это число равно .

Заметим, что можно было бы вести подсчет не по вертикальным сторонам,

а по горизонтальным. То есть, существует различных самых коротких путей и, следовательно, справедливо равенство:

.

Данное равенство имеет название «формула симметрии».

Из этой формулы имеем следствие:

,

имеющее название «формула сложения». Докажем данное следствие.

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

следствие доказано.

Пример:

Сборная команда университета по волейболу насчитывает 15 человек. Сколько разных вариантов должен рассмотреть тренер перед игрой, чтобы заявить список игроков на игру?

Решение:Число игроков волейбольной команды равно шести. Значит, число всех возможных вариантов - это число различных подмножеств, состоящих из шести элементов в множестве из пятнадцати элементов. Следовательно, по теореме 2 имеем

.