§ 2. КОМБИНАТОРИКА

1. Комбинаторные задачи.

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

Поскольку в таких задачах речь идет о тех или иных комбинациях объектов, их называют комбинаторными задачами. Область математики, в которой изучаются комбинаторные задачи, называют комбинаторикой. Комбинаторику можно рассматривать как часть теории множеств — любую комбинаторную задачу можно свести к задаче о конечных множествах и их отображениях.

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

Пусть, например, путешественник хочет выехать из города А,

Рис. 1

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

(см. скан)

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

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

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