КОМБИНАТО́РНЫЙ АНА́ЛИЗ
-
Рубрика: Математика
-
-
Скопировать библиографическую ссылку:
КОМБИНАТО́РНЫЙ АНА́ЛИЗ (комбинаторная математика, комбинаторика), раздел математики, посвящённый решению задач о выборе и расположении в соответствии с заданными правилами элементов некоторого, обычно конечного, множества. Каждое такое правило определяет способ построения некоторой конструкции, состоящей из элементов исходного множества, которая называется комбинаторной конфигурацией. Можно сказать, что целью К. а. является изучение комбинаторных конфигураций, в частности изучаются вопросы их существования, алгоритмы построения, решаются задачи на перечисление. Примерами комбинаторных конфигураций являются перестановки, размещения, сочетания (см. Комбинаторные числа и многочлены), блок-схемы и латинские квадраты.
Развитие К. а. шло параллельно с развитием др. разделов математики, таких как алгебра, теория чисел, теория вероятностей, с которыми К. а. тесно связан. Ещё математики Древнего Востока знали формулу, выражающую число сочетаний через биномиальные коэффициенты, и формулу Ньютона бинома с натуральным показателем $n$. С мистич. целями изучались магич. квадраты 3-го порядка. Становление К. а. как раздела математики связано с работами Б. Паскаля и П. Ферма по азартным играм. Эти работы, заложившие основы элементарной теории вероятностей, содержали принципы определения числа комбинаций элементов конечного множества. Большой вклад в развитие комбинаторных методов был сделан Г. В. Лейбницем, Я. Бернулли, Л. Эйлером. С 1950-х гг. интерес к К. а. возродился в связи с бурным развитием дискретной математики, информатики, информации теории, кибернетики и планирования эксперимента. На формирование направлений исследований в К. а. оказывают влияние как выбор объектов исследований, так и цели исследования, зависящие от сложности изучаемых объектов. Для сложных комбинаторных конфигураций осн. целями исследований являются выяснение условий их существования и разработка алгоритмов построения. Ещё одно направление исследований в К. а. связано с теоремами выбора. В основе мн. результатов этого направления лежит теорема Холла о существовании систем разл. представителей (трансверсалей) семейства подмножеств некоторого множества, которые определяются следующим образом. Пусть $T=\left\{t_1,t_2,…, t_m\right\}$ – некоторое множество и $S=\left\{S_1,S_2,…, S_n\right\}$ – некоторое семейство его подмножеств. Набор $R=\left\{t_{i_1},t_{i_2},…, t_{i_n}\right\}$ разл. элементов множества $T$ называется системой разл. представителей (с. р. п.) семейства $S$, если $t_{i_j}\in S_j$; элемент называется представителем множества $S_j, j=1,2,…, n$. Теорема Холла о с. р. п. состоит в том, что семейство $S$ имеет с. р. п. тогда и только тогда, когда объединение каждых $k$ множеств из $S$ содержит, по крайней мере, $k$ разл. элементов, $k=1,2,…, n. $
Пусть
$$T=A_1\cup A_2 \cup\ldots \cup A_l,\tag 1 $$
$$T=B_1 \cup B_2 \cup \ldots \cup B_l \tag 2 $$— два разбиения множества $T$, в которых ни одно из подмножеств $T$ не пусто. Набор $R=\left\{t_{i_1}, t_{i_2}, …,t_{i_l}\right\}$ называется системой общих представителей (с. о. п.) разбиений (1) и (2), если $R$ есть с. р. п. как для семейства $A=\left\{A_1,A_2,…, A_l\right\}$, так и для семейства $B=\left\{B_1,B_2,…, B_l\right\}$. Теорема о с. о. п. состоит в том, что разбиения (1) и (2) имеют с. о. п. тогда и только тогда, когда объединение каждых $k $ множеств из семейства $A$ содержит не более $k$ множеств из семейства $B, k=1,2,…, l. $ Теореме Холла о с. р. п. эквивалентна теорема Кёнига о $(0,1)$-матрице, которая утверждает, что миним. число линий (строк и столбцов), содержащих все единицы, равно макс. числу единиц, которые могут быть выбраны так, что среди них нет двух единиц, расположенных на одной и той же линии.
Значит. часть К. а. составляют перечислительные задачи, решением которых является метод перебора комбинаторных конфигураций из данного класса и определение их числа. Примерами решения перечислительных задач являются следующие результаты. Число подстановок степени $n$ с $k$ циклами равно $\big|S (n, k)\big|, $ где $S (n, k)$ – числа Стирлинга 1-го рода, определяемые равенствами$$x (x-1)\dots (x-n+1)= \sum_{k-0}^n S (n, k)x^k; $$ число разбиений множества из $n$ элементов на $k$ подмножеств равно числу Стирлинга 2-рода $$\sigma (n, k)=\frac{1}{k! }\sum_{j=0}^k (-1)^jC_i^j (k-j)^n, $$где $C_i^j$— число сочетаний из $i$ по $j$; число размещений $m$ разл. предметов по $n$ разл. ячейкам при условии, что пустых ячеек нет, равно $n!\sigma(m,n)$. Для решения некоторых перечислительных задач используется перманент матрицы, который для матрицы $A=\parallel a_{ij}\parallel, i= 1,…,n, j= 1,…,m, n\leq m$, определяется равенством$$\text{per} A=\sum_\sigma a_{1\sigma (1)}\dots a_{n\sigma (n)},$$ где суммирование производится по всем инъективным отображениям $\sigma$ множества $\left\{{1,…,n}\right\}$ в множества $\left\{{1,…,m}\right\}$, т. е. таким отображениям, при которых разл. элементы из $\left\{{1,…,n}\right\}$ имеют разл. образы в $\left\{{1,…,m}\right\}$. Так, число трансверсалей некоторого семейства из $n$ подмножеств конечного множества, состоящего из $m$ элементов, равно перманенту соответствующей матрицы инцидентности (см., напр., Графов теория).
При решении перечислительных задач К. а. существенную роль играет формализация понятия неразличимости объектов. Использование для этих целей понятия эквивалентности объектов относительно некоторой группы подстановок в сочетании с применением метода производящих функций положено в основу т. н. теории перечисления Пойа.