Математическая энциклопедия - комбинаторный анализ

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

Множество Xиз пэлементов наз. n-м ножеством; любое его m-подмножество,наз. сочетанием объема т. Число сочетаний объема тиз празличных элементов равно

Имеет место формула:

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

При т= п размещение представляет собой перестановку элементов множества X, причем число таких перестановок равно Р(п) = п!

Возникновение основных понятий и развитие К. а. шло параллельно с развитием других разделов математики, таких, как алгебра, теория чисел, теория вероятностей, с к-рыми К. а. тесно связан. Еще математикам Древнего Востока были известны формула, выражающая число сочетаний через биномиальные коэффициенты, и формула бинома Ньютона с натуральным показателем п. С мистическими целями изучались магические квадраты3-го порядка. Рождение К. а. как раздела математики связано с трудами Б. Паскаля (В. Pascal) и П. Ферма (P. Fermat) по теории азартных игр. Этн труды, составившие основу теории вероятностей, одновременно содержали принципы определения числа комбинаций элементов конечного множества, устанавливая тем самым ставшую затем традиционной связь К. а. с теорией вероятностей.

Большой вклад в систематическое развитие комбинаторных методов был сделан Г. Лейбницем (G. Leibniz) в его диссертации "Ars Combinatoria" ("Комбинаторное искусство"), где, по-видимому, впервые появился термин "комбинаторный". Большое значение для становления К. а. имела работа Я. Бернулли (J. Bernoulli) "Ars conjectandi" ("Искусство предположений"), посвященная основным понятиям теории вероятностей, где обстоятельно изложен ряд комбинаторных понятий и указаны их применения для вычисления вероятностей. Можно считать, что с появлением работ Г. Лейбница и Я. Бернулли комбинаторные методы выделились в самостоятельную часть математики.

Большой вклад в развитие комбинаторных методов сделал Л. Эйлер (L. Euler). В его работах по разбиениям и композициям натуральных чисел на слагаемые было положено начало одному из основных методов перечисления комбинаторных конфигураций методу производящих функций.

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

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

Большой развивающийся раздел К. а. составляет теория блок-схем (см. также [2], [3], [10]); основные проблемы этого раздела связаны с вопросами классификации, условиями существования и методами построения нек-рых классов блок-схем. Частным случаем блок-схем являются так наз. уравновешенные неполные блок-схемы, или (b, v, r, k,l)-конфигурации, к-рые определяются как совокупности из bk-подмножеств нек-рого v-множества, называемых блоками, с условием, что каждый элемент появляется в r блоках, а каждая пара элементов в l блоках. При b=vи, следовательно, r=k(b, v, r, k,l)-конфигурацня наз. (v, k,l)-конфигурацией, или симметричной уравновешенной неполной блок-схемой. Даже для (v, k,l)-конфигураций вопрос о необходимых и достаточных условиях их существования остается пока (1978) открытым. Для существования (v, k,l)-конфигураций необходимо, чтобы при vчетном k-l было квадратом, а при vнечетном уравнение

имело решение в целых числах х, у, z, одновременно не равных нулю.

При v=n²+n+1, k=n+1, l=1 (v, k,l)-конфигурация представляет собой проективную плоскость порядка и, являющуюся частным случаем конечной геометрии, содержащей конечное число точек и прямых с заданными условиями их инцидентности. Каждой проективной плоскости порядка п-1 можно поставить во взаимно однозначное соответствие полное множество из п-1 попарно ортогональных латинских квадратов порядка п. Для существования проективной плоскости порядка и необходимо, чтобы при n=1, 2 (mod 4) существовали целые числа аи b, удовлетворяющие равенству n=а ²+b².

Вопрос о существовании проективных плоскостей порядка прешен положительно только для п=р^a, где рпростое, а a натуральное числа. Даже для n=10 этот вопрос является открытым (1978). К этому кругу вопросов относится результат, связанный с опровержением гипотезы Эйлера о несуществовании пары ортогональных латинских квадратов порядка n=4k+2, k=1, 2, ... (см. Комбинаторные задачи).

Другое направление К. а. связано с выбора теоремами. В основе целого ряда результатов этого направления лежит теорема Ф. Холла о существовании системы различных представителей (трансверсали) семейства подмножеств (Х 1, ..., Х n )множества X, т. е. системы элементов ( х 1,..., х п )такой, что х i О Х и х i неравно х j при i неравно j:трансверсаль существует тогда и только тогда, когда для любых i1, ... , ik таких, что справедливо неравенство где |Y|число элементов в множестве Y. Из теоремы Ф. Холла вытекает теорема о существовании латинского квадрата, состоящая в том, что любой латинский прямоугольник размера можно дополнить до латинского квадрата порядка п. Другое следствие теоремы Ф. Холла: любую неотрицательную матрицу А= ||aij||, i, j=1, ..., п, такую, что

можно представить в виде

где П 1, ..., П s матрицы подстановки порядка пи Из теоремы Ф. Холла следует также теорема о том, что минимальное число строк и столбцов неотрицательной матрицы, содержащих все положительные элементы, равно максимальному числу элементов, попарно не расположенных в одной и той же строке или в одном и том же столбце. Экстремальное свойство частично упорядоченных множеств, аналогичное этой теореме, устанавливает теорема, утверждающая, что минимальное число непересекающихся цепей совпадает с объемом максимального подмножества, состоящего из попарно несравнимых элементов. Экстремальный характер носит и следующая теорема: если для n-множества X составить все (ⁿr )сочетаний по r элементов и разбить их на кнепересекающихся классов, то для целого тсуществует число п 0=п 0( т, r, k )такое, что при найдется подмножество из тэлементов для к-рого все (^mr )сочетаний принадлежат одному классу.

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

Значительную часть К. а. составляют перечислительные задачи. При их решении либо указывается метод перебора комбинаторных конфигураций из данного класса, либо определяется их число, либо делается то и другое. Типичные результаты перечислительных задач: число подстановок степени пc k циклами равно |S(n, к)|, где S(n, к)числа Стирлинга 1-го рода, определяемые равенством

число разбиений множества из пэлементов на кподмножеств равно числу Стирлинга 2-го рода

число размещений тразличных предметов в празличных ячейках, когда пустых ячеек нет, равно п!s( т, п). Полезным инструментом для решений перечислительных задач является пер.