§ 4. Пересчет. Перечисление. Классификация. Оптимизация

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

Рис. 1

Рис. 2

Рис. 3

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

подмножество решений, для которого функция величины максимальна (соответственно минимальна), и каков соответствующий максимум (минимум).

Чтобы проиллюстрировать эти различные аспекты в конкретном случае, мы рассмотрим один пример, в котором результаты ясны без доказательства, но читатель найдет в дальнейшем строгие рассуждения и доказательства на эту тему.

Рассмотрим квадрат, разделенный на 25 клеток (рис 1). Предположим, что в эти клетки размещаются пять кружков так, что в каждую строку и каждый столбец попадает в точности по одному кружку.

Рис. 4

Каждой клетке сопоставим двойку , изображаемую стрелкой. Тем самым размещению кружков по клеткам будет соответствовать диаграмма вида рис 3 Первый вопрос сколько различных размещений можно реализовать? Легко доказать, что это число равно числу перестановок из пяти элементов, а именно (рис. 1—3). Задача пересчета решена Выпишем эти 120 решений, используя метод, который будет изложен в дальнейшем Получим

Это и есть перечисление

Предположим теперь, что нас интересует число решений (возможно, и их список), обладающих специальной структурой Рассмотрим, например, рис 3 и назовем контуром замкнутый путь на этой диаграмме Она состоит тогда из двух контуров длин 3 и 2 соответственно (длина — число стрелок, образующих контур). Интересной является задача распределения на классы

контуров, имеющих одинаковую структуру, например, пять контуров длины три контура длины 1 и один контур длины 2 (рис. 4,б) и т. д. Отыскание числа таких классов и их состава — важная комбинаторная задача.

Предположим, далее, что каждой клетке сопоставлена числовая функция, а каждому решению — величина, равная сумме этих чисел; найдем решение с минимальной величиной. Если функция величины задана, как на рис. 2, то решение, указанное на рис. 1 или на рис. 3, имеет величину Отыскивая решение с минимальной величиной, мы приходим к одному из двух решений, представленных на рис. 5, для которых эта величина равна 9.

Рис. 5

Таким образом, читатель уже может получить представление о том, чем мы будем заниматься в этой книге.

В последующих параграфах сначала систематически излагаются методы пересчета. Эти методы, по существу, основаны на понятии производящей функции, и поэтому мы начнем с некоторых классических понятий анализа. Если читатель забыл некоторые понятия (комплексная плоскость, последовательность, голоморфная функция и т. д.), ему следует, не затрачивая излишних усилий, заглядывать время от времени в курс анализа. Математика представляет собой единое целое, и трудно изучать комбинаторные структуры без подходящей базы математики непрерывного.