Сочетания

Определение

Определение:

Сочетанием из [math]\displaystyle{ n }[/math] элементов по [math]\displaystyle{ k }[/math] называется неупорядоченная выборка без повторений объема [math]\displaystyle{ k }[/math] из [math]\displaystyle{ n }[/math]-элементного множества.

Не умаляя общности, можно называть сочетанием из [math]\displaystyle{ n }[/math] элементов по [math]\displaystyle{ k }[/math] неупорядоченный набор из [math]\displaystyle{ k }[/math] различных чисел, принадлежащих множеству [math]\displaystyle{ \{1, ..., n\} }[/math].

Количество различных сочетаний из [math]\displaystyle{ n }[/math] по [math]\displaystyle{ k }[/math] обозначают [math]\displaystyle{ C_n^k }[/math] или [math]\displaystyle{ \binom{n}{k} }[/math].

Пример 1

Предположим, из [math]\displaystyle{ n }[/math] участников спортивного клуба на соревнования должны поехать какие-то [math]\displaystyle{ k }[/math]. Тогда имеется [math]\displaystyle{ C_n^k }[/math] различных возможности собрать команду.

Пример 2

Пусть [math]\displaystyle{ S = \{1,2,3\} }[/math]. Тогда [math]\displaystyle{ \{1,2\} }[/math], [math]\displaystyle{ \{1,3\} }[/math], [math]\displaystyle{ \{2,3\} }[/math] — все возможные cочетания из трех элементов по два.

Утверждение:

Пусть [math]\displaystyle{ k,n\in\mathbb{N} }[/math] и [math]\displaystyle{ 1 \leq k \leq n }[/math]. Тогда [math]\displaystyle{ \binom{n}{k} = \frac{n!}{k!(n-k)!} }[/math].

Доказательство:

Действительно, каждому сочетанию из [math]\displaystyle{ n }[/math] по [math]\displaystyle{ k }[/math] соответствует [math]\displaystyle{ k! }[/math] различных размещений из [math]\displaystyle{ n }[/math] по [math]\displaystyle{ k }[/math] с различным порядком следования элементов. Тогда [math]\displaystyle{ \binom{n}{k} = \frac{A_n^k}{k!} = \frac{n!}{k!(n-k)!} }[/math].

[math]\displaystyle{ \blacksquare }[/math]

Рис. 2. Каждому сочетанию соответствуют [math]\displaystyle{ k! = 2! = 2 }[/math] размещения — все порядки его элементов. Поэтому [math]\displaystyle{ C_3^2 = A_3^2/2! = 6/2 = 3 }[/math].

Очевидным следствием из формулы является равенство [math]\displaystyle{ \binom{n}{k} = \binom{n}{n-k}. }[/math]

Интуитивно эту формулу можно было бы обосновать следующим рассуждением. Выбирая $k$ элементов из $n$, мы тем самым выбираем $n-k$ элементов из $n$, которые не попадают в нашу выборку. Проще говоря, мы разбиваем наше множество мощности $n$ на два подмножества мощностей $k$ и $n-k$ соответственно.

Рис. 3. Выбрать [math]\displaystyle{ k }[/math] элементов из [math]\displaystyle{ n }[/math] — то же, что указать [math]\displaystyle{ n-k }[/math] элементов, которые останутся. Для [math]\displaystyle{ S=\{1,\dots,5\} }[/math] и [math]\displaystyle{ k=3 }[/math]: [math]\displaystyle{ C_5^3 = C_5^2 = 10 }[/math].

Свойства числа сочетаний

[math]\displaystyle{ \binom{n}{k}\cdot\binom{k}{l} = \binom{n}{l}\cdot \binom{n-l}{k-l}. }[/math]

Действительно, [math]\displaystyle{ \binom{n}{k}\cdot\binom{k}{l}= \frac{n!}{k!(n-k)!}\cdot\frac{k!}{l!(k-l)!} \cdot \frac{(n-l)!}{(n-l)!}= \frac{n!}{l!(n-l)!}\cdot\frac{(n-l)!}{(k-l)!(n-k)!} = \binom{n}{l}\cdot \binom{n-l}{k-l}. }[/math]

Интуитивно формулу можно описать как разбиение множества из [math]\displaystyle{ n }[/math] элементов на три подмножества мощностей [math]\displaystyle{ l }[/math], [math]\displaystyle{ k-l }[/math], [math]\displaystyle{ n-k }[/math] соответственно. Левая часть равенства описывает выбор сначала [math]\displaystyle{ k }[/math] элементов из [math]\displaystyle{ n }[/math], а затем [math]\displaystyle{ l }[/math] элементов из выбранных [math]\displaystyle{ k }[/math]. Получим все варианты разбиения исходного множества на три подмножества указанных мощностей.

Правая часть равенства соответствует выбору сначала [math]\displaystyle{ l }[/math] элементов из [math]\displaystyle{ n }[/math], а затем [math]\displaystyle{ k-l }[/math] элементов из оставшихся [math]\displaystyle{ n-l }[/math]. Получим те же варианты подмножеств.

Рис. 4. Разбиение на три части размерами [math]\displaystyle{ l }[/math], [math]\displaystyle{ k-l }[/math] и [math]\displaystyle{ n-k }[/math]. Слева сначала выбирают [math]\displaystyle{ k }[/math], затем [math]\displaystyle{ l }[/math]; справа сначала [math]\displaystyle{ l }[/math], затем [math]\displaystyle{ k-l }[/math] из оставшихся — получаются одни и те же разбиения. Для [math]\displaystyle{ n=5 }[/math], [math]\displaystyle{ k=3 }[/math], [math]\displaystyle{ l=1 }[/math]: [math]\displaystyle{ 10\cdot 3 = 5\cdot 6 = 30 }[/math].

Алгоритм перебора сочетаний

Пусть [math]\displaystyle{ x_1, x_2, ..., x_k }[/math] — числа из множества [math]\displaystyle{ \{1,2,...,n\} }[/math], вошедшие в сочетание, причем [math]\displaystyle{ x_1 \lt x_2 \lt ... \lt x_k }[/math].

Пусть в начальный момент времени сочетание состоит из первых [math]\displaystyle{ k }[/math] чисел: [math]\displaystyle{ x_i = i, i=\overline{1,k} }[/math].

На каждом шаге будем просматривать вектор [math]\displaystyle{ (x_1, x_2, ..., x_k) }[/math], начиная с [math]\displaystyle{ x_k }[/math], и искать первую такую компоненту [math]\displaystyle{ x_i }[/math], которую можно увеличить (нельзя увеличить [math]\displaystyle{ x_k }[/math], если он равен [math]\displaystyle{ n }[/math]; [math]\displaystyle{ x_{k-1} }[/math], если он равен [math]\displaystyle{ n-1 }[/math] и так далее).

Если такой компоненты не найдется, алгоритм завершает свою работу. В противном случае, пусть [math]\displaystyle{ i }[/math] — такое наибольшее число, что [math]\displaystyle{ x_i \lt n-k+i }[/math]. Увеличим [math]\displaystyle{ x_i }[/math] на единицу, а для всех [math]\displaystyle{ x_t, t=\overline{i+1,k} }[/math], присваиваем значения [math]\displaystyle{ x_t = x_i+(t-i) }[/math]. Повторяем процесс нужное число раз.

Рис. 1. Если последний элемент можно увеличить, он увеличивается: [math]\displaystyle{ (1,2,3)\to(1,2,4) }[/math]. Если хвост уже максимален, находится ближайшая слева позиция, которую можно увеличить, а хвост переназначается: [math]\displaystyle{ (1,4,5)\to(2,3,4) }[/math].

Пример

Пример 1

Рассмотрим, как работает алгоритм для [math]\displaystyle{ n=5 }[/math] и [math]\displaystyle{ k=3 }[/math].

1. Сначала [math]\displaystyle{ x = (x_1, x_2, x_3) = (1,2,3) }[/math].
2. Увеличиваем [math]\displaystyle{ x_3 }[/math]: [math]\displaystyle{ x = (1,2,4) }[/math].
3. Увеличиваем [math]\displaystyle{ x_3 }[/math]: [math]\displaystyle{ x = (1,2,5) }[/math].
4. [math]\displaystyle{ x_3 }[/math] больше увеличить нельзя. Увеличиваем [math]\displaystyle{ x_2 }[/math] и переназначаем значение [math]\displaystyle{ x_3 }[/math]: [math]\displaystyle{ x = (1,3,4) }[/math].
5. [math]\displaystyle{ x = (1,3,5) }[/math]
6. [math]\displaystyle{ x = (1,4,5) }[/math]
7. [math]\displaystyle{ x = (2,3,4) }[/math]
8. [math]\displaystyle{ x = (2,3,5) }[/math]
9. [math]\displaystyle{ x = (2,4,5) }[/math]
10. [math]\displaystyle{ x = (3,4,5) }[/math]

Таким образом, мы перебрали все сочетания из 5 по 3.

Связь сочетаний и (0,1)-векторов

С каждым сочетанием из $n$ по $k$ можно связать вектор из нулей и единиц, в котором число единиц равно $k$: позиции единиц указывают числа, которые должны войти в сочетание. Другими словами, установлено взаимооднозначное соответствие между множеством сочетаний из $n$ по $k$ и множеством (0,1)-векторов длины $n$ с $k$ единицами.

В свою очередь, каждый (0,1)-вектор длины $n$ с $k$ единицами соответствует пути на прямоугольной решетке длины $n-k$ и высоты $k$.

Можно сопоставить каждому шагу вниз единицу, а каждому шагу вправо — ноль. Тогда произвольному пути в $n$ шагов из точки $(0,0)$ в точку $(n-k,k)$ взаимно-однозначно соответствует (0,1)-вектор длины $n$ с $k$ единицами. Таким образом, мы получили взаимно-однозначное соответствие между множеством сочетаний из $n$ по $k$ и множеством путей на прямоугольной решетке.

Рис. 1. Сочетанию [math]\displaystyle{ \{1,3,4\} }[/math] соответствует вектор [math]\displaystyle{ (1,0,1,1,0) }[/math], а ему — путь из [math]\displaystyle{ (0,0) }[/math] в [math]\displaystyle{ (2,3) }[/math]: единица — шаг вниз, ноль — шаг вправо. Все три множества равномощны.

Заметим, что все множество путей из точки $(0,0)$ в точку $(n-k,k)$ складывается из множества путей из $(0,0)$ в $(n-k,k-1)$ с последним шагом из $(n-k,k-1)$ в $(n-k,k)$ и множества путей из $(0,0)$ в $(n-k-1,k)$ с последним шагом из $(n-k-1,k)$ в $(n-k,k)$.

Тогда количество путей из $(0,0)$ в $(n-k,k)$, равное $\binom{n}{k}$, совпадает с суммой количеств путей из $(0,0)$ в $(n-k,k-1)$ и из $(0,0)$ в $(n-k-1,k)$, что равно $\binom{n-1}{k-1}+\binom{n-1}{k}$. Таким образом, мы привели еще одно доказательство рекурентной формулы для вычисления $C_n^k$.

Конспект: Дискретная математика