Тема 4.1. Сочетания

Пусть задано конечное множество мощности . Обозначим через множество всех - элементных подмножеств множества .

Теорема: Число всех - элементных подмножеств множества вычисляется по формуле

Доказательство: Будем строить - элементные подмножества множества действием из двух этапов. На первом этапе построим - элементное подмножество, тогда число способов осуществления первого этапа будет равно . На втором этапе к полученному - элементному подмножеству присоединим один из элементов множества , которые не входят в это подмножество; ясно, что . Значит, согласно принципу умножения, в результате описанного действия получим - элементных подмножеств. Но не все они будут разными, так как каждое - элементное подмножество можно так построить способами: присоединением каждого из его элементов к остальным его элементам. Поэтому найденное число в раз больше, чем число - элементных подмножеств множества . Следовательно, Отсюда находим

Но число одноэлементных подмножеств множества равно т.е. . Следовательно,

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

Определение: Произвольное - элементное подмножество множества из элементов в комбинаторике называется сочетанием из элементов по элементов. Порядок элементов в подмножестве не имеет значения, поэтому часто вместо слова «сочетание» употребляется термин комбинация или соединение из элементов по элементов, которые отличаются, по крайней мере одним элементом, но не порядком элементов.

Пример 4.1: Сколькими способами из 7 человек можно выбрать комиссию, состоящую из 3 человек?

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

Пример 4.2: Рассмотрим на плоскости с декартовой прямоугольной системой координат «шахматный город», состоящий из прямоугольных кварталов, границами которых являются части горизонтальных и вертикальных улиц. Требуется определить число различных кратчайших путей в пределах этого города, ведущих из левого нижнего угла (точки ) в правый верхний угол (точку ).

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

Замечание: Заметим, что полученное равенство установлено при решении геометрической задачи. Заметим так же, что рассмотренный пример даёт интересную геометрическую интерпретацию для чисел .

Определение: Сочетаниями с повторениями, содержащими элементов, выбранных из элементов заданного множества, называются всевозможные множества из элементов, отличающиеся хоть одним элементов (порядок не учитывается), при этом допускается неединичное вхождение элементов. Обозначаем .

Теорема: Число

Доказательство: Рассмотрим подробно, чем отличаются друг от друга два разных результата такой схемы выбора. Нам не важен порядок номеров элементов множества, то есть мы учитываем только, сколько раз в нашем наборе из элементов появился элемент номер 1, элемент номер 2, …, элемент номер . То есть результат выбора можно представить набором чисел , в котором – число появлений элемента номер в выборке, и . При этом два результата эксперимента различны, если соответствующие им наборы не совпадают.

Представим себе другой эксперимент, имеющий точно такие же результаты (и, следовательно, их столько же). Есть ящиков, в которых размещается шариков. Нас интересует только количество шариков в каждом ящике. То есть, результатом эксперимента снова является набор чисел , в котором – число шариков в ящике с номером , и . Числа по-прежнему принимают натуральные значения или равны 0.

А теперь изобразим результат такого размещения в виде схемы, в которой вертикальные линии обозначают перегородки между ящиками, а кружки – находящиеся в ящиках шарики:

Мы видим результат размещения 9 шариков по 7 ящикам. Здесь 1-й ящик содержит 3 шарика, 2-й и 6-й ящики пусты, 3-й ящик содержит 1 шарик, и в 4-м и 5-м ящиках есть по 2 шарика. Переложим один шарик из первого ящика во второй и изобразим таким же образом ещё один результат размещения:

И ещё один:

Видим, что все размещения можно получить, меняя между собой шарики и перегородки, или расставляя шариков на месте. Число получается так: у ящиков есть ровно перегородка, считая крайние, или перегородка, если не считать крайние, которые двигать нельзя. И есть шариков. Перебрав все возможные способы расставить шариков на этих местах (и ставя на оставшиеся места перегородки), переберём все нужные размещения.

Но способов расставить шариков на местах ровно – это в точности число способов выбрать из номеров мест номеров мест, на которые нужно поместить шарики. Заметим, что равенство верно в силу того, что можно вместо выбора мест для шариков выбирать место для перегородок ящиков, заполняя шариками оставшиеся места.

Дата добавления: 2015-10-28