§ 5. Сочетания с повторениями

Рассмотрим задачу: сколько всего букетов можно составить из семи роз, пяти фиалок и трёх тюльпанов, если каждый букет состоит из одной розы, двух фиалок и двух тюльпанов (порядок цветов в букете не важен) ?

Это – простая задача на сочетания и принцип умножения: = = 7103 = 210.

Другая задача: сколько букетов, содержащих 3 цветка, можно составить из роз, фиалок и тюльпанов (цветов достаточное количество и порядок цветков в букете не существенен) ?

Здесь букет можно мыслить как набор , в которых р – розы, ф – фиалки, т – тюльпаны и k₁ + k₂ + k₃ = 3. Поэтому возможны следующие случаи:

роз 3: такой набор единственный (р; р; р);

роз 2: таких наборов два (р; р; ф), (р; р; т);

роз 1: таких наборов три (р; ф; ф), (р; ф; т); (р; т; т);

роз 0: таких наборов четыре (ф; ф; ф), (ф; ф; т), (ф; т; т); (т ; т; т).

Всего, таким образом, получится 10 букетов. Хотя результат и получен, но не вполне понятно, как решать эту задачу для букетов из большего количества k цветов в букете: даже для k = 5 перечислить все букеты затруднительно ! Поэтому надо задуматься об общем методе решения задачи.

Пусть – количество букетов, составляемых из k видов цветов, каждый из которых содержит j цветов. Тогда, нужно найти , и согласно схеме перечисления по количеству роз . Здесь – учитывает единственный набор (р; р; р), – количество “хвостов” (ф) и (т) при двух розах, – количество “хвостов” (ф; ф), (ф; т); (т; т) при одной розе, и – количество букетов (ф; ф; ф), (ф; ф; т), (ф; т; т); (т; т; т) при отсутствии роз. Ясно, что . Аналогично . Так что теперь получим .

Таким образом, найден более перспективный способ подсчёта букетов, основанный на рекуррентном соотношении .

Если A = {a₁ , … , a_n } – конечное множество из n элементов, то сочетанием n элементов с повторениями называется любой упорядоченный набор вида , где k_i  N₀ . Если k_i = 0, то это значит, что в наборе элемент a_i отсутствует. Числа k_i , … , k_n называются кратностями элементов a₁ , … , a_n в сочетании с повторениями. Число сочетаний с повторениями длины k = k₁ + … + k_n будем обозначать через .

Перечислить все сочетания с повторениями длины k можно рекурсивно. Ясно, что существует ровно n различных сочетаний с повторениями длины 1: (a₁), … , (a_n). Если уже умеем перечислять все сочетания с повторениями, но от меньшего чем n количества элементов, то вначале выпишем единственное сочетание кратности k по a₁ : , затем перечислим все сочетания с повторениями кратности k – 1 по a₁ (и кратности 1 по элементам множества A₁ = A \ {a₁}= {a₂ , … , a_n }) – их . Затем – кратности k – 2 по a₁ (и кратности 2 по элементам множества A₁) – их , и т.д., пока не перечислим все сочетания кратности 1 по a₁ (и кратности k – 1 по элементам множества A₁ ) – их , и наконец, все сочетания кратности 0 по a₁ (и кратности k по элементам множества A₁ ) – их .

Пример: Перечислим все сочетания с повторениями длины 4 для трёхэлементного множества A = {1, 2, 3}.

(1; 1; 1; 1),

(1; 1; 1; 2), (1; 1; 1; 3),

(1; 1; 2; 2), (1; 1; 2; 3), (1; 1; 3; 3),

(1; 2; 2; 2), (1; 2; 2; 3), (1; 2; 3; 3); (1; 3; 3; 3),

(2; 2; 2; 2), (2; 2; 2; 3), (2; 2; 3; 3); (2; 3; 3; 3), (3; 3; 3; 3).

Таким образом, = 15. Попутно получаем = 5, = 4, = 3.

Проанализировав приведённый выше алгоритм перечисления всех сочетаний с повторениями длины k, получим рекуррентную формулу:

.

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

s = 1: Ясно, что .

s = 2: Имеем

.

s = 3: Имеем

Возникает гипотеза о том, что . Для её обоснования достаточно проверить выполнение рекуррентного соотношения:

.

Это следует из основного равенства для биномиальных коэффициентов:

– верно.

Другой способ доказательства формулы состоит в том, что каждому сочетанию с повторениями можно биективно сопоставить некоторое сочетание из n+k–1 по k. Именно, сопоставим каждому сочетанию с повторениями обычное сочетание n+k–1 элементов множества = {a₁ , … , a_n , b₁ , … , b_k–1} по k :

{a₁ , … , a_n ; b₁ , … , … , }.

В этом сочетании каждому a_i кратности k_i > 0 соответствует группа элементов количество которых k_i – 1. Если кратность элемента равна 0, то ни он сам, ни соответствующая ему группа во множестве не участвуют. Общее количество элементов в построенном сочетании будет 1+(k₁–1)+1+(k₂–1)+…+1+(k_n–1) = k.

Пример: Сочетаниям с повторениями длины 3 из множества A = {1, 2} сопоставим следующие сочетания элементов множества = {1, 2, b₁ , b₂}: (2; 2; 2)  {2, b₁ , b₂}, (1; 2; 2)  {1, 2, b₂}, (1; 1; 2)  {1, 2, b₁}, (1; 1; 1)  {1, b₁ , b₂}. Видно, что установленное соответствие является в данном примере взаимно однозначным.

Это соответствие взаимно однозначно и в общем случае:

инъективность: если и привели к одному и тому же сочетанию

{a₁ , … , a_n ; b₁ , … , , … , },

то из правила построения этого сочетания сразу следует, что s₁–1 = p₁–1 = t₁–1, т.е. s₁ = t₁ , s₂–1 = p₂–1 = t₂–1, т.е. s₂ = t₂ , … , s_n–1 = p_n–1 = t_n–1, т.е. s_n = t_n , так что рассматриваемые сочетания с повторениями совпадают.

сюръективность: по любому сочетанию

{a₁ , … , a_n ; b₁ , … , … , }

однозначно восстанавливается его прообраз. Действительно, если a₁ не участвует в сочетании, то его кратность в сочетании с повторениями равна 0. Если же a₁ участвует в сочетании, то выделяем максимальный отрезок подряд участвующих в этом сочетании элементов b₁ , … , и записываем в искомом сочетании с повторениями элемент a₁ с кратностью s₁ . При этом ситуация, когда элемент b₁ не входит в сочетание возникнуть не может, т.к. в противном случае элементов из множества {b₁ , … , b_k–1} будет участвовать меньше k–1, а поскольку рассматриваемое сочетание имеет n+k–1 элемент, то количество участвующих в нём элементов из множества A должно быть больше n, что невозможно. Точно так же процесс построения искомого сочетания с повторениями происходит и далее.

Примеры: 1. Сочетанию {a₁ , a₃ , b₁ , b₂} из пяти элементов по четыре соответствует сочетание с повторениями (a₁ ; a₁ ; a₁; a₃) длины 4 элементов множества A = {a₁ , a₂ , a₃}.

2. Сочетанию {a₂ , a₃ , b₁ , b₃ } из пяти элементов по четыре соответствует сочетание с повторениями (a₂ ; a₂ ; a₃ ; a₃ ) длины 4 элементов множества A = {a₁ , a₂ , a₃}.

3. Сочетанию {a₂ , b₁ , b₂ , b₃ } из пяти элементов по четыре соответствует сочетание с повторениями (a₂ ; a₂ ; a₂; a₂) длины 4 элементов множества A = {a₁ , a₂ , a₃}.