Комбинаторный анализ (комбинаторика)

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

Перестановкой n-элементного множества называется любой упорядоченный набор , состоящий из элементов множества A, в котором каждый элемент из A встречается ровно один раз. Нетрудно видеть, что число перестановок n-элементного множества равно .

Размещением из n элементов по k называется произвольная перестановка k-элементного подмножества n-элементного множества. Число размещений из n элементов по k равно .

Сочетанием из n элементов по k называется произвольное k-элементное подмножество n-элементного множества. Число сочетаний из n элементов по k равно .

Перестановки, размещения и сочетания естественным образом возникают при решении многих комбинаторных задач, при этом часто найденные решения выражаются через величины и , называемые комбинаторными числами. В качестве простого примера такой задачи можно привести задачу о числе сочетаний с повторениями. Сочетанием с повторениями из n элементов по k называется неупорядоченный k-элементный набор, состоящий из элементов n-элементного множества. Каждое сочетание с повторениями из n элементов по k однозначно определяется тем, сколько раз каждый элемент множества входит в рассматриваемое сочетание. Пусть в некоторое такое сочетание элемент входит раз, где . Этому сочетанию поставим в соответствие набор из k единиц, сгруппированных в n блоков, и нулей, разделяющих эти блоки. В этом наборе первый блок из единиц соответствует элементу , второй блок из единиц — элементу , и т. д. Очевидно, что набор такого вида однозначно определяет соответствующее ему сочетание с повторениями. Поэтому число сочетаний с повторениями из n элементов по k равно числу наборов из k единиц и нулей. Каждый такой набор можно рассматривать как набор значений характеристической функции k-элементного подмножества -элементного множества. Следовательно, число сочетаний с повторениями из n элементов по k равно .

К комбинаторным числам также относятся числа Стирлинга первого и второго рода. Эти числа определяются как коэффициенты в равенствах

,

и имеют простой комбинаторный смысл — равно числу элементов группы подстановок являющихся произведениями ровно k непересекающихся циклов, а равно числу разбиений n-элементного множества на k непустых подмножеств. Очевидно, что . Аналогичная сумма чисел Стирлинга второго рода называется n-м числом Белла и равна числу всех разбиений n-элементного множества. Для чисел Белла справедлива рекуррентная формула .

При решении комбинаторных задач часто оказывается полезна формула включений—исключений

,

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

.

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

.

Мощным средством решения перечислительных комбинаторных задач является метод производящих функций. Производящей функцией последовательности , где , называется ряд

.

Если ряд сходится абсолютно в какой-либо окрестности нуля, то его можно умножить на другой ряд, возвести его в степень, продифференцировать и т. д. Используя такие действия, можно попытаться найти явный вид функции в случае, когда последовательность неизвестна и описывается только какими-нибудь своими свойствами. Если явную формулу для удается найти, то далее можно попытаться найти явную формулу и для — общего члена последовательности. Сделать это можно, вычислив n-ю производную функции или разложив эту функцию в ряд каким-либо иным способом. В качестве примера использования метода производящих функций рассмотрим задачу нахождения явной формулы для n-го члена последовательности Фибоначчи. Члены этой последовательности 1,1,2,3,5,8,….. удовлетворяют рекуррентному соотношению

при . Правую и левую части рекуррентного соотношения умножим на и просуммируем по всем целым n от 2 до . В результате получим равенство

которое после несложных преобразований превращается в равенство для производящих функций

Откуда, в свою очередь, для легко находится явная формула

которая далее представляется в виде суммы простейших дробей

Раскладывая получившиеся дроби в ряды, видим, что

Таким образом

Совместное использование производящих функций и алгебраических методов позволяет решать задачи, в которых требуется перечислять не отдельные элементы, а классы эквивалентности. Простым примером задачи такого типа является задача о числе способов, которыми можно раскрасить грани трехмерного кубика. В этой задаче два раскрашенных кубика считаются эквивалентными, если один кубик можно повернуть так, что после поворота одинаково ориентированные грани кубиков будут окрашены одним и тем же цветом. Дополнительным условием в этой задаче может быть условие на число граней, покрашенных определенным цветом. Например, задача может состоять в том, чтобы найти число различных кубиков, у каждого из которых три белых и три черных грани. Техника решения подобных задач была разработана венгерским математиком Д. Пойа в конце тридцатых годов двадцатого века для решения ряда перечислительных задач теории графов, где в качестве классов эквивалентности рассматривались классы изоморфных графов. Используя эту технику, нетрудно показать, что число неизоморфных графов без кратных ребер и петель на n вершинах асимптотически равно .

Заметное место в комбинаторном анализе занимают задачи связанные с изучением экстремальных элементов различных множеств. К числу самых известных задач такого типа относится задача нахождения чисел Рамсея. Число Рамсея определяется как наименьшее целое n такое, что в любом полном графе с n вершинами, ребра которого раскрашены в красный и синий цвета, найдется либо подграф с k вершинами, все ребра которого окрашены в красный цвет, либо подграф с m вершинами, все ребра которого окрашены в синий цвет. Точные значения чисел Рамсея известны только при небольших значениях m и k, например, , и в случае, когда меньший из аргументов не превосходит двух — легко видеть, что и . В остальных случаях для чисел Рамсея известны только оценки, например, , где c — константа.

Рекомендуемая литература

1. Гульден Я., Джексон Д. Перечислительная комбинаторика. — М.: Наука, 1990.

2. Ежов И. И., Скороход А. В., Ядренко М. И. Элементы комбинаторики. — М.: Наука, 1977.

3. Стенли Р. Перечислительная комбинаторика. — М.: Мир. 1990.

4. Стенли Р. Перечислительная комбинаторика: Деревья, производящие функции и симметрические функции. — М.: Мир, 2005.

5. Харари Ф., Палмер Э. Перечисление графов. — М.: Мир. 1977.

6. Эрдеш П., Спенсер Дж. Вероятностные методы в комбинаторике. — М.: Мир. 1976.