Посмотрим теперь, сколько существует разных подмножеств из 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 имеем
|
|
.