§ 3. Сочетания

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

Всякое подмножество множества содержащее элементов называется сочетанием из данных элементов по элементов.

Из определения понятия сочетания вытекает, что два различных сочетания из данных элементов по элементов отличаются составом элементов, входящих в них, т. е. отличаются одно от другого по крайней мере одним элементом.

Пример. Из множества цифр 1, 2, 3, 4 можно образовать следующие сочетания по два элемента: 1, 2; 1, 3; 1.4, 2, 3; 2, 4; 3, 4.

Число различных сочетаний из элементов по обозначают символом

Известно, что всякое множество имеет два несобственных подмножества. Одним из этих подмножеств является само множество. Это подмножество является единственным сочетанием из элементов по Поэтому

Вторым несобственным подмножеством является пустое подмножество, не имеющее элементов. Поэтому считаем, что

Принято также считать, что

Очевидно, что

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

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

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

Действительно, общий вид сочетания из элементов по элементов следующий:

(каждое из является одним из чисел причем ни одно из этих чисел не повторяется дважды. При описанном процессе образования сочетаний по элементов сочетание мы получили раз:

впервые, когда к сочетанию присоединим

во второй раз, когда к сочетанию присоединим

в -раз, когда к сочетанию присоединим

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

Следовательно,

Эта формула верна при всяком Поэтому, подставляя вместо последовательно , получим соотношения:

Перемножив соответственно левые и правые части этих равенств, получим:

Поделив обе части этого равенства на произведение и приняв во внимание, что будем иметь:

Этим теорема доказана.

Формулу для можно записать иначе. Умножив числитель и знаменатель дроби, стоящей в правой части формулы (1), на произведение получим:

или

Заметим, что формула (2) справедлива и для Действительно, принято считать, что и поэтому

Пример. Найти число диагоналей выпуклого десятиугольника.

Решение. Вершины десятиугольника образуют множество 10 точек плоскости, никакие три из которых не лежат на одной прямой. Соединяя каждую пару этих точек отрезком прямой, получим

отрезков, 10 из которых являются сторонами многоугольника, а другие 35 — его диагоналями.

Теорема 2. Число сочетаний из элементов по элементов равно числу сочетаний из элементов по элементов, т. е.

Действительно, если из данных элементов выберем какие-либо элементов, то они образуют некоторое сочетание из элементов по элементов. Остальные элементов образуют сочетание из элементов по элементов.

Таким образом, каждому сочетанию из элементов по элементов соответствует одно и только одно сочетание из элементов по элементов, и наоборот. Поэтому

Эту теорему можно доказать иначе: по формуле (3)

и, следовательно,

Соотношение позволяет ускорить вычисление числа сочетаний из элементов по элементов, при Например:

Теорема 3. Число сочетаний из элементов по элементов равно числу сочетаний из элементов по элементов, сложенному с числом сочетаний из элементов по элементов:

Доказательство. Разделим все сочетания из элементов по элементов на две группы. К первой группе отнесем все сочетания из элементов по элементов, в которые не входит Это будут сочетания из элементов по элементов, и число их будет Ко второй группе отнесем сочетания из элементов по элементов, в которые входит Сочетания второй группы можно получить, образовав из элементов а» все сочетания по элехментов и присоединив к каждому из них Поэтому число сочетаний во второй группе равно Отсюда вытекает, что

Теорему (3) можно доказать еще и так: по формуле (2)

Отсюда