Приветствую.
В статье пойдёт речь о числе сочетаний. На моём канале есть и другие статьи о комбинаторике (комбинаторное правило умножения, перестановки, размещения), которые могут быть полезными для более полного понимания способа подсчёта числа сочетаний.
Определения
- Сочетание из k элементов – группа, состоящая из данных k элементов. Для группы неважен порядок расположения элементов. К примеру, группа из двух элементов независимо от порядка расположения (ab и ba) – одна и та же.
- Числом сочетаний из n по k называют количество групп, содержащих k элементов, составленных* из данных n элементов. Число сочетаний равно количеству соответствующих размещений, делённому на k!, так как размещения чувствительны к порядку элементов и потому их в k! раз больше.
*слово "составленных" относится к слову "групп".
Сочетания VS Размещения: подробнее
- В случае сочетаний группы из трёх элементов: abc, acb, bac, bca, cab, cba – все одни и те же, и любую из 3! записей выше можно использоваться для обращения к сочетанию abc. А в случае размещений – это шесть различных размещений.
- Действительно, выбирая, например, трёх учеников (a,b,c) в качестве дежурных из класса с 15 учениками, нам безынтересно, в каком порядке мы их выберем, нам лишь интересно, кого именно (какую группу) мы выберем. В этом случае ученики a,b,c независимо от порядка их расположения – одна и та же группа (т.е. одно и то же сочетание).
- А вот если мы рассматриваем способы расположения данных 15 учеников на трёх стульях, то порядок их расположения имеет значение, и здесь речь идёт о размещениях, которые чувствительны к порядку расположения элементов (например, abc и bac – не одно и то же, а два разных размещения).
Задача о рукопожатиях
N человек обменялись рукопожатиями (каждый поздоровался со всеми остальными). Сколько было рукопожатий?
Решение
- Каждый поздоровался единожды со всеми остальными. Это значит, что каждый человек из группы из N человек поздоровался с N-1 людьми. Значит, общее число рукопожатий равно N*(N-1), но отметим, что при таком подсчёте число рукопожатий вдвое больше искомого, ведь рукопожатие между людьми А и Б и людьми Б и А одно и то же. Значит N*(N-1) делим на 2 и получаем ответ.
- Видим, что это число действительно совпадает с числом сочетаний из N по два.
- Данная задача имеет красивую иллюстрацию. Изобразим людей в виде вершин на окружности, а их рукопожатия рёбрами (хордами). Получим следующие иллюстрации (графы) для N=6 и N=9.
Подсчитаем, наконец, число рукопожатий для случая, указанного в заголовке.
Число людей N=15; а k по-прежнему равно 2. Число рукопожатий будет равно 15*14/2=105. Достаточно много. Хотя так не кажется, ведь при встречах каждый думает преимущественно лишь о своих рукопожатиях.
Изобразим рукопожатия на окружности, построив соответствующий полный граф. Придём к простому выводу: обмен рукопожатиями между людьми куда сложнее и интереснее, чем может показаться на первый взгляд.
- Существуют и другие задачи, которые приводят к тем же соображениям: например, задача о количестве партий, сыгранных шахматистами, если каждый сыграл со всеми остальными.
- Также есть задача об эффективной политике: страны наиболее эффективны (при прочих равных) в том случае, когда каждая из них отладила взаимодействие (отношения) со всеми остальными. Общее количество отношений в данном случае также можно подсчитать по выведенной выше формуле (N*(N-1)/2).