- •Глава I. Азы комбинаторики
- •§ 1. Основные принципы комбинаторики
- •§ 2. Размещения и перестановки без повторений
- •§ 3. Размещения и перестановки с повторениями
- •§ 4. Подмножества конечных множеств и сочетания
- •§ 5. Сочетания с повторениями
- •§ 6. Принцип включения-исключения
- •§ 7. Примеры решения простейших комбинаторных задач
- •§ 8. Примеры других комбинаторных объектов и сводка некоторых результатов
- •Биномиальные коэффициенты
- •Числа Стирлинга
- •Глава II. Рекуррентные соотношения
- •§ 1. Определение и примеры рекуррентных соотношений
- •Основы метода конечных разностей
- •§ 2. Метод производящих функций для нахождения общего решения линейного однородного рекуррентного соотношения второго порядка
- •Алгоритм нахождения общего решения
- •§ 3. Решение линейных неоднородных рекуррентных соотношений с постоянными коэффициентами и специальной правой частью
- •§ 4. Метод производящих функций для решения общего линейного однородного рекуррентного соотношения с постоянными коэффициентами
- •Алгоритм нахождения общего решения
- •§ 5. Частные решения линейных неоднородных рекуррентных соотношений с постоянными коэффициентами и специальной правой частью
- •§ 6. Некоторые примеры применения производящих функций
§ 5. Сочетания с повторениями
Рассмотрим задачу: сколько всего букетов можно составить из семи роз, пяти фиалок и трёх тюльпанов, если каждый букет состоит из одной розы, двух фиалок и двух тюльпанов (порядок цветов в букете не важен) ?
Это – простая задача на сочетания и принцип умножения: = = 7103 = 210.
Другая задача: сколько букетов, содержащих 3 цветка, можно составить из роз, фиалок и тюльпанов (цветов достаточное количество и порядок цветков в букете не существенен) ?
Здесь букет можно мыслить как набор , в которых р – розы, ф – фиалки, т – тюльпаны и k1 + k2 + k3 = 3. Поэтому возможны следующие случаи:
роз 3: такой набор единственный (р; р; р);
роз 2: таких наборов два (р; р; ф), (р; р; т);
роз 1: таких наборов три (р; ф; ф), (р; ф; т); (р; т; т);
роз 0: таких наборов четыре (ф; ф; ф), (ф; ф; т), (ф; т; т); (т ; т; т).
Всего, таким образом, получится 10 букетов. Хотя результат и получен, но не вполне понятно, как решать эту задачу для букетов из большего количества k цветов в букете: даже для k = 5 перечислить все букеты затруднительно ! Поэтому надо задуматься об общем методе решения задачи.
Пусть – количество букетов, составляемых из k видов цветов, каждый из которых содержит j цветов. Тогда, нужно найти , и согласно схеме перечисления по количеству роз . Здесь – учитывает единственный набор (р; р; р), – количество “хвостов” (ф) и (т) при двух розах, – количество “хвостов” (ф; ф), (ф; т); (т; т) при одной розе, и – количество букетов (ф; ф; ф), (ф; ф; т), (ф; т; т); (т; т; т) при отсутствии роз. Ясно, что . Аналогично . Так что теперь получим .
Таким образом, найден более перспективный способ подсчёта букетов, основанный на рекуррентном соотношении .
Если A = {a1 , … , an } – конечное множество из n элементов, то сочетанием n элементов с повторениями называется любой упорядоченный набор вида , где ki N0 . Если ki = 0, то это значит, что в наборе элемент ai отсутствует. Числа ki , … , kn называются кратностями элементов a1 , … , an в сочетании с повторениями. Число сочетаний с повторениями длины k = k1 + … + kn будем обозначать через .
Перечислить все сочетания с повторениями длины k можно рекурсивно. Ясно, что существует ровно n различных сочетаний с повторениями длины 1: (a1), … , (an). Если уже умеем перечислять все сочетания с повторениями, но от меньшего чем n количества элементов, то вначале выпишем единственное сочетание кратности k по a1 : , затем перечислим все сочетания с повторениями кратности k – 1 по a1 (и кратности 1 по элементам множества A1 = A \ {a1}= {a2 , … , an }) – их . Затем – кратности k – 2 по a1 (и кратности 2 по элементам множества A1) – их , и т.д., пока не перечислим все сочетания кратности 1 по a1 (и кратности k – 1 по элементам множества A1 ) – их , и наконец, все сочетания кратности 0 по a1 (и кратности k по элементам множества A1 ) – их .
Пример: Перечислим все сочетания с повторениями длины 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 элементов множества = {a1 , … , an , b1 , … , bk–1} по k :
{a1 , … , an ; b1 , … , … , }.
В этом сочетании каждому ai кратности ki > 0 соответствует группа элементов количество которых ki – 1. Если кратность элемента равна 0, то ни он сам, ни соответствующая ему группа во множестве не участвуют. Общее количество элементов в построенном сочетании будет 1+(k1–1)+1+(k2–1)+…+1+(kn–1) = k.
Пример: Сочетаниям с повторениями длины 3 из множества A = {1, 2} сопоставим следующие сочетания элементов множества = {1, 2, b1 , b2}: (2; 2; 2) {2, b1 , b2}, (1; 2; 2) {1, 2, b2}, (1; 1; 2) {1, 2, b1}, (1; 1; 1) {1, b1 , b2}. Видно, что установленное соответствие является в данном примере взаимно однозначным.
Это соответствие взаимно однозначно и в общем случае:
инъективность: если и привели к одному и тому же сочетанию
{a1 , … , an ; b1 , … , , … , },
то из правила построения этого сочетания сразу следует, что s1–1 = p1–1 = t1–1, т.е. s1 = t1 , s2–1 = p2–1 = t2–1, т.е. s2 = t2 , … , sn–1 = pn–1 = tn–1, т.е. sn = tn , так что рассматриваемые сочетания с повторениями совпадают.
сюръективность: по любому сочетанию
{a1 , … , an ; b1 , … , … , }
однозначно восстанавливается его прообраз. Действительно, если a1 не участвует в сочетании, то его кратность в сочетании с повторениями равна 0. Если же a1 участвует в сочетании, то выделяем максимальный отрезок подряд участвующих в этом сочетании элементов b1 , … , и записываем в искомом сочетании с повторениями элемент a1 с кратностью s1 . При этом ситуация, когда элемент b1 не входит в сочетание возникнуть не может, т.к. в противном случае элементов из множества {b1 , … , bk–1} будет участвовать меньше k–1, а поскольку рассматриваемое сочетание имеет n+k–1 элемент, то количество участвующих в нём элементов из множества A должно быть больше n, что невозможно. Точно так же процесс построения искомого сочетания с повторениями происходит и далее.
Примеры: 1. Сочетанию {a1 , a3 , b1 , b2} из пяти элементов по четыре соответствует сочетание с повторениями (a1 ; a1 ; a1; a3) длины 4 элементов множества A = {a1 , a2 , a3}.
2. Сочетанию {a2 , a3 , b1 , b3 } из пяти элементов по четыре соответствует сочетание с повторениями (a2 ; a2 ; a3 ; a3 ) длины 4 элементов множества A = {a1 , a2 , a3}.
3. Сочетанию {a2 , b1 , b2 , b3 } из пяти элементов по четыре соответствует сочетание с повторениями (a2 ; a2 ; a2; a2) длины 4 элементов множества A = {a1 , a2 , a3}.