КОМБИНАТОРНЫЙ АНАЛИЗ

— часть математики, объектом исследований в которой являются множества, состоящие из дискретных (обособленных) элементов. Мн-ва могут быть различными: конечными, бесконечными, допускающими всюду упорядоченность элементов или имеющими более сложную структуру. Специфика методов К. а. состоит в применении двух видов операций: отбора подмножеств (называемых выборками) и операции упорядочения. Эти операции наз. комбинаторными. Задачи К. а., в основном, делятся на три типа. В задачах 1-го типа решается вопрос о числе возможных решений, т. е. требуемых выборок или расположений (конфигураций). В задачах 2-го типа — о существовании решений, их возможности. В задачах 3-го типа — о способах отыскания оптим. решений, т. е. таких, которые обладают экстремальностью относительно заданного свойства. На развитие К. а. большое влияние оказывают приложения математики, напр., матем. обработка результатов экспериментов. К. а. составляет общую теор. основу т. н. дискретной математики (многих матем. методов кибернетики, графов теории, программирования целочисленного, конечных групп и др.). Оперативную часть К. а. составляют следующие методы: метод непосредственного подсчета числа выборок, метод производящих функций, логические, экстремальные, геометрические и др. методы.

Методы непосредственного подсчета числа выборок известны издавна. Они составляют содержание т. н. элементарной комбинаторики. Этими методами находят числа -выборок, получаемых из элементов соответствующего мн-ва. Выборки делят на -сочетания, когда принимают во внимание лишь элементы, составляющие выборку, безотносительно их взаимного расположения, и -перестановки, когда учитывают и порядок следования элементов. Методы непосредственного подсчета разнообразны. Вывод соответствующих формул базируется в основном на двух логич. правилах: а) правило суммы: пусть из -мн-ва S выборка А может быть получена способами, а выборка способами. Выборки А и В не могут быть получены одновременно. В такой ситуации выборку А или выборку В можно получить способами; б) правило произведения: если из -мн-ва S выборку А можно получить способами, а после нее q способами получена выборка В, то выбор А и В в указанном порядке можно осуществить способами.

Среди формул элементарной комбинаторики основными являются: число -перестановок без повторения элементов); (число -перестановок с повторениями элементов); (число -сочетаний); (число -сочетаний при допущении повторения элементов); упорядоченных разбиений -мн-ва на непересекающиеся подмножества, состоящие соответственно из элементов). Число формул элементарной комбинаторики и разнообразие приемов получения их очень велико.

Метод производящих функций сформировался в работах Л. Эйлера и П. Лапласа. Применяют его не только в К. а., но и в теории чисел, вероятностей теории и алгебре. С его помощью изучают последовательности объектов, напр., -выборок из данного -мн-ва, или их чисел. Значение метода состоит в том, что он дает возможность оперировать не с отдельными комбинаторными объектами, а с их классами, а это дает определенные практические преимущества. Производящая ф-ция для чисел -сочетаний

производящая ф-ция для класса самих -сочетаний элементов, обозначаемых здесь имеет вид

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

полиномами, составленными из тех членов стандартного полинома в которых степени параметра t равны числу (или числам) повторений. Производящую функцию для числа -перестановок получают в виде

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

Существует большое разнообразие видов производящих ф-ций, обусловливаемое разнообразием классов выборок. Аппарат оперирования с производящими ф-циями оказывается в большинстве случаев очень громоздким. Для придания ему большей алгоритмичности к настоящему времени накоплено сравнительно много средств: спец. операторы, символические исчисления, спец. числа и спец. ф-ции. Степень общности, достигнутой методом производящих ф-ций в К. а., характеризуется тем, что сейчас удается строить производящие ф-ции для неэквивалентных комбинаторных объектов (теория Пойа и ее обобщения). Эти объекты можно наделять «весами», т. е. численными характеристиками, определяемыми условиями задачи, а понятие эквивалентности можно вводить через группу подстановок. Логические методы К. а. служат для анализа структуры конечных дискретных мн-в и для решения вопроса о существовании (или несуществовании) решения комбинаторных задач. Характеризуются тем, что в них перечислительный аспект уступает место логическому анализу, не всегда еще приводящему к регулярным алгоритмам.

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

Эта ф-ла показывает, что для того, чтобы получить мн-во элементов, указанное в левой части равенства, необходимо из всего -мн-ва исключить элементы, обладающие хотя бы одним из заданных свойств. Однако, при этом элементы, обладающие двумя свойствами, оказываются исключенными дважды. Поэтому их надо возвратить и т. д. Метод, т. о., состоит в попеременном отбрасывании и возвращении подмножеств, что и отражено в его названии. Метод обобщен на случаи, когда речь идет о любых выборках свойств и на случай, когда элементы снабжены весами.

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

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

Экстремальные методы К. а. Пусть задано -мн-во элементов. На нем определено мн-во Р комбинаторных объектов: -перестановок, -сочетаний, конечных последовательностей и т. п. На этом мн-ве задана ф-ция F. Требуется найти экстремум этой ф-ции или же отыскать те элементы (или тот элемент) мн-ва Р, на которых этот экстремум достигается. Напр., имеется мн-во населенных пунктов, расстояние между каждой парой которых известно. Требуется среди всех возможных маршрутов для почтальона найти минимальный.

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

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

Таблично-схемные методы К. а. применяют для исследования комбинаторных расположений. В основе представления об этих расположениях лежит общее понятие системы инцидентностей. Два мн-ва образуют такую систему, если между их элементами установлено соотношение инцидентности, выражаемое понятиями: через...» в зависимости от интерпретации. Изображают системы инцидентности двумерными расположениями — таблицами. В К. а. изучают свойства все более широкого класса таблиц, являющихся интерпретациями комбинаторных задач.

В исследованиях комбинаторных расположений большую роль играет аппарат спец. матриц. Пусть дано и -выборка его подмножеств: Построим , в которой

Полученная бинарная матрица дает полное описание системы инцидентности. С помощью таких матриц часто не только интерпретируют, но и доказывают теоремы и решают задачи К. а. В зависимости от типа комбинаторных задач при их решении используют различные типы матриц: перестановочные, попарных сравнений, матрицы Адамара, стохастические и др. Современные обобщения этой теории включают изучение классов спец. матриц и инвариантов. Существует много типов комбинаторных таблиц и схем большого практ. и теор. значения, напр., латинские прямоугольники и квадраты, системы троек Штейнера и Киркмана. Большой, активно исследуемый класс таблиц составляют блок-схемы.

Блок-схемы вводятся следующим образом: пусть имеется v -мн-во элементов данных эксперимента): Элементы этого мн-ва расположены в b столбиках-блоках, которые являются подмножествами исходного мн-ва. Их перечисления не обязательно пусты. Число элементов в блоке назовем его объемом и обозначим Каждый элемент может состоять в нескольких блоках. Пусть число блоков, содержащих элемент число блоков, в которых появляется неупорядоченная пара элементов. Т. о., блок-схема есть комбинаторное расположение, параметрами которого являются Если вместо пар рассматривают тройки или др. выборки элементов, то такие расположения наз. тактическими конфигурациями. Существует большое разнообразие видов блок-схем. Латинские квадраты — пример полных блок-схем, т. е. таких, в которых в каждом блоке содержатся все элементы мн-ва Системы троек Штейнера частные виды неполных уравновешенных блок-схем, для которых Исследования в области блок-схем сосредоточиваются в настоящее время вокруг проблемы существования (или несуществования) отдельных видов блок-схем, изучения их свойств, нахождения эффективных методов их построения. При исследовании этих таблиц используют результаты теории чисел, групп теории, теории матриц, выпуклых тел и др. При этом выявляется общность теоретических, по существу комбинаторных, основ ряда разделов современной математики.

Геометрические методы К. а. происходят из геом. интерпретаций комбинаторных ситуаций посредством мн-в точек, отрезков и др. При последовательном применении в К. а. подобных интерпретаций выделяют спец. виды геом. систем инцидентностей. Элементы, принятые за первичные, неопределяемые, получили названия: «точки» Р и «линии» L. Отношение инцидентности Р е. L получило конкретизацию как: «точка Р лежит на линии или «линия L содержит точку Р». Эти системы, наконец, были подчинены системам аксиом типа аксиом геометрии. Уточнения и дополнительные разъяснения, либо видоизменения исходных утверждений, приводят к различным видам конечных геометрий, к проблемам комбинаторной топологии, дискретной геометрии, проективной геометрии, геометрической теории чисел, теории графов и комбинаторной геометрии. Простейшими геом. комбинаторными системами являются конечные плоскости, т. е. системы инцидентности двух конечных и линий), подчиненных системе аксиом проективной геометрии. Однако теория и этих комбинаторных систем еще не разработана, в частности, нет условий существования конечных плоскостей. Среди многообразных систем геом. инцидентностей большое внимание привлекают те системы, где инцидентность вводится между мн-вом элементов и некоторыми мн-вами пар этих элементов.

Большая часть Наложенных выше методов К. а. была разработана для тех задач, объекты которых допускали линейную упорядоченность своих элементов. Общая комбинаторная теория, однако, не предполагает необходимости такого ограничения. Последовательное, систематическое развитие комбинаторных методов для мн-в более общей природы — одна из главных задач современного К. а. Отношение порядка (символ: ) в мн-вах вводится формально посредством аксиом: а) рефлективности;

для любого , б) равенства: если , то а = b; в) транзитивности: если , то . Добавление четвертой аксиомы об отсутствии несравнимых элементов: для всяких , либо а либо , определяет уже мн-во, упорядоченное всюду, или цепь.

Тремя первыми аксиомами определяются частично упорядоченные множества; к-во таких мн-в , а среди них неизоморфных: Для результатов еще не получено.

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

Лит.: Рыбников К. А. Введение в комбинаторный анализ. М., 1972 [библиогр. с. 249-250]; Kaulmann A. Introduction & la combinatorique en vue des applications. Paris, 1968; Холл М. Комбинаторика. Пер. с англ. М. 1970 [библиогр. с. 413—418].

К. А. Рыбников.