1.3.3. Сочетания

Сочетанием Из N Элементов по M называется всякий неупорядоченный набор M элементов, выбранных из данных N элементов (всякое M-элементное подмножество данного N-элементного множества). Как и в случае размещений сочетания можно представлять в виде таких же наборов натуральных чисел, имея в виду, что расположение этих чисел теперь (в отличие от размещений) не важно. Например, наборы и -- различные размещения, но одно и то же сочетание. Легко видеть, что из одного итого же сочетания (из N Элементов по M) можно путем перестановки элементов получить различных размещений. Поэтому число различных размещений из N элементов по M , где через обозначается число сочетаний N элементов по M. Отсюда с учетом теоремы 2 о числе размещений, получим следующее утверждение.

Теорема 1. .

Из теоремы вытекает очевидное равенство: . Кроме того, с помощью теоремы нетрудно убедиться и в справедливости следующего соотношения: . Последнюю формулу можно использовать как рекурентное соотношение для подсчета числа сочетаний из элементов, если предварительно уже вычислены для различных M. Результаты становятся очень удобными, если их представить в виде следующего треугольника.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Такой треугольник носит название Треугольника Паскаля. Элементы каждой строчки треугольника Паскаля представляют собой сочетания при фиксированном N И меняющемся от 0 до N значении M И вычисляются как суммы ближайших элементов вышестоящей строчки.

Сочетанием C повторениями Из N Элементов по M называется всякий неупорядоченный набор M элементов, выбранных из данных N элементов, в котором допускаются повторения элементов. Два сочетания с повторениями из N Элементов по M Равны, только если они составлены из одних и тех же элементов, взятых с одной и той же кратностью. Под кратностью элемента в сочетании понимают количество раз, которое данный элемент встречается в данном сочетании. Число различных сочетаний с повторениями из N элементов по M обозначается . Можно, доказать, что справедлива следующая

Теорема 2. .

Доказательство. Каждому сочетанию с повторениями из N по M Поставим в соответствие вектор длины , состоящий из нулей и единиц, такой, что число нулей между (I-1)-ой и I-ой единицами равно кратности элемента I в данном сочетании для , а число нулей, стоящих перед первой единицей (после последней -ой единицы) равно кратности элемента 1 (элемента N). Легко видеть что такое отображение обратимо и, значит, биективно. Поэтому число сочетаний с повторениями из N по M Равно количеству векторов указанного вида. С другой стороны каждому такому вектору можно поставить в соответствие сочетание из по M --- номеров нулевых компонент данного вектора, которое также является биекцией. Таким образом, требуемое равенство доказано.

< Предыдущая		Следующая >