Комбинаторика

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

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

<addc>G</addc>

С аналогичными задачами, получившими название комбинаторных, люди столкнулись в глубокой древности. Уже несколько тысячелетий назад в Древнем Китае увлекались составлением магических квадратов (см. Магические и латинские квадраты), в которых заданные числа располагали так, что их сумма по всем горизонталям, вертикалям и главным диагоналям была одной и той же. В Древней Греции подсчитывали число различных комбинаций длинных и коротких слогов в стихотворных размерах, занимались теорией фигурных чисел, изучали фигуры, которые можно составить из частей особым образом разрезанного квадрата, и т. д.

Комбинаторные задачи возникали и в связи с такими играми, как шашки, шахматы, домино, карты, кости и т. д. (Например, задача о расстановке восьми ферзей на шахматной доске так, чтобы ни один из них не оказался под боем, об обходе всех полей доски шахматным конем и т. д. (см. Математика на шахматной доске).

Комбинаторика становится наукой лишь в XVII в. — в период, когда возникла теория вероятностей. Чтобы решать теоретико-вероятностные задачи, нужно было уметь подсчитывать число различных комбинаций, подчиненных тем или иным условиям. После первых работ, выполненных в XVI в. итальянскими учеными Дж. Кардано, Н. Тартальей и Г. Галилеем, такие задачи изучали французские математики Б. Паскаль и П. Ферма. Первым рассматривал комбинаторику как самостоятельную ветвь науки немецкий философ и математик Г. Лейбниц, опубликовавший в 1666 г. работу «Об искусстве комбинаторики», в которой впервые появляется сам термин «комбинаторный». Замечательные достижения в области комбинаторики принадлежат Л. Эйлеру. Комбинаторными задачами интересовались и математики, занимавшиеся составлением и разгадыванием шифров, изучением древних письменностей. Теперь комбинаторика находит приложения во многих областях науки: в биологии, где она применяется для изучения состава белков и ДНК, в химии, механике сложных сооружений и т. д.

По мере развития комбинаторики выяснилось, что, несмотря на внешнее различие изучаемых ею вопросов, многие из них имеют одно и то же математическое содержание и сводятся к задачам о конечных множествах и их подмножествах. Постепенно выявилось несколько основных типов задач, к которым сводится большинство комбинаторных проблем. Важную область комбинаторики составляет теория перечислений. С её помощью можно подсчитать число решений различных комбинаторных задач. В основе этой теории лежат «правило суммы» и «правило произведения». Они гласят: «если множество [math]A[/math] состоит из [math]m[/math] элементов, а множество [math]B[/math] — из [math]n[/math] элементов, причем эти множества не имеют общих элементов, то их объединение [math]A⋃B[/math], т. е. совокупность всех элементов из [math]A[/math] и [math]B[/math], содержит [math]m+n[/math] элементов; множество [math]A×B[/math], состоящее из всевозможных пар [math](a,b)[/math], где элемент [math]a[/math] принадлежит множеству [math]A[/math], а элемент [math]b[/math] принадлежит множеству [math]B[/math], содержит [math]mn[/math] элементов».

С помощью правила суммы легко сосчитать и число элементов в [math]A⋃B[/math], когда [math]A[/math] и [math]B[/math] имеют общие элементы. Если обозначить через [math]A⋂B[/math] множество всех общих элементов у множеств [math]A[/math] и [math]B[/math], то оно равно [math]n(A)+n(B)−n(A⋂B)[/math], где [math]n(A)[/math] — число элементов в множестве [math]A[/math]. Это утверждение — частный случай так называемой формулы перекрытий.

Часто приходится считать число последовательностей длины [math]m[/math], составленных из элементов некоторого множества [math]A[/math], состоящего из [math]n[/math] элементов, как в случае, когда среди элементов последовательности могут быть повторяющиеся, так и в случае, когда все эти элементы должны быть различными. В первом случае последовательности называют размещениями с повторениями из [math]n[/math] элементов по [math]m[/math] и их число обозначают [math]\bar{A}_{n}^{m}[/math], а во втором — размещениями без повторений, их число обозначают [math]A_{n}^{m}[/math]. Формулы для [math]\bar{A}_{n}^{m}[/math] и [math]A_{n}^{m}[/math] таковы:

[math]\bar{A}_{n}^{m}={{n}^{m}},[/math] [math]A_{n}^{m}=n(n−1)\cdot \ldots \cdot (n−m+1).[/math]

Рассмотрим различные размещения без повторений из [math]n[/math] элементов по [math]n[/math], очевидно, что они отличаются друг от друга лишь порядком элементов; их называют перестановками из [math]n[/math] элементов. Число [math]{{P}_{n}}[/math] таких перестановок равно [math]n![/math] (см. Факториал):

[math]{{P}_{n}}=A_{n}^{n}=n!.[/math]

Если отвлечься от порядка элементов, то возникает задача: сколько подмножеств, содержащих [math]m[/math] элементов и отличающихся одно от другого хотя бы одним элементом, можно извлечь из множества [math]A[/math], содержащего [math]n[/math] элементов. В комбинаторике такие подмножества называют сочетаниями из [math]n[/math] элементов по [math]m[/math], их число обозначают [math]C_{n}^{m}[/math]. Можно доказать, что

[math]C_{n}^{m}=\frac{n!}{m!\left( n-m \right)!}.[/math]

Целый ряд комбинаторных задач возникает при разбиении множеств на части: найти число таких разбиений, если число частей равно [math]k[/math]; найти, сколькими способами можно число [math]n[/math] записать в виде суммы [math]k[/math] слагаемых; найти, сколькими способами можно разложить [math]n[/math] предметов по [math]k[/math] ящикам, и т. д. Обычно задачи теории разбиений и раскладок сводятся к формуле перекрытий и разобранным выше основным задачам комбинаторики. Такими же способами решаются комбинаторные задачи с ограничениями, например подсчет числа размещений с повторениями, в которых ни один элемент не стоит два раза подряд, и т. д.

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

Комбинаторика не сводится только к подсчету количества тех или иных подмножеств или последовательностей. При решении комбинаторных проблем иногда нужно лишь доказать, что данная проблема имеет решение, или убедиться в отсутствии его. Например, доказано следующее утверждение: для любых чисел [math]m[/math] и [math]n[/math] найдется такое число [math]N[/math], что любой граф, состоящий из [math]N[/math] точек и всех соединяющих эти точки отрезков (они раскрашены в [math]m[/math] цветов), содержит часть, состоящую из [math]n[/math] точек и соединяющих их отрезков, такую, что все отрезки имеют один и тот же цвет (теорема Рамсея).

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

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

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