Глава ιι. Комбинаторный анализ

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

1. Задачи на размещения – задачи о расположении, например, на плоскости предметов, обладающих свойствами дальнодействия.

2. Задачи о покрытиях и заполнениях – например, задачи о заполнении заданных тел меньшими телами заданных форм и размеров.

3. Задачи о маршрутах – задачи оптимального плана, например задачи на нахождение кратчайшего пути и т.п.

4. Комбинаторные задачи теории графов – задачи сетевого планирования, например, задачи транспортных и электрических сетей, задачи об окрашивании графов, задачи о перечислении вершин и т.п.

5. Перечислительные задачи, в которых речь идет о числе предметов, составляемых из данного набора элементов при соблюдении определенных правил.