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

Материал из Юнциклопедии
(перенаправлено с «КОМБИНАТОРИКА»)
Перейти к: навигация, поиск

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

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

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

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

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

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

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

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

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

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

${{P}_{n}}=A_{n}^{n}=n!.$

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

$C_{n}^{m}=\frac{n!}{m!\left( n-m \right)!}.$

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

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

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

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

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

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