Энциклопедический словарь юного математика

По мере развития комбинаторики выяснилось, что, несмотря на внешнее различие изучаемых ею вопросов, многие из них имеют одно и то же математическое содержание и сводятся к задачам о конечных множествах и их подмножествах. Постепенно выявилось несколько основных типов задач, к которым сводится большинство комбинаторных проблем. Важную область комбинаторики составляет теория перечислений. С ее помощью можно подсчитать число решений различных комбинаторных задач. В основе этой теории лежат «правило суммы» и «правило произведения». Они гласят: «если множество 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 и их число обозначают , а во втором – размещениями без повторений, их число обозначают . Формулы для  и  таковы:

, A^m_n = n(n-1)·...·(n-m+1).

«Число, место и комбинация – три взаимно перекрещивающиеся, но отличные сферы мышления, к которым можно отнести все математические идеи». Дж. Сильвестр

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

.

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

.

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

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

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

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

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