Игра в шахматы есть как бы насвистывание математических мелодий. Г. Харди

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

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

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

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

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

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

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

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

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

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

ВЕНГЕРСКИЙ ШАРНИРНЫЙ КУБИК

Необыкновенно популярной головоломкой стал кубик Рубика (рис. 1), изобретенный в 1975 г. преподавателем архитектуры из Будапешта Эрне Рубиком для развития пространственного воображения у студентов. Кубик Рубика – это куб, как бы разрезанный на 27 одинаковых кубичков. В исходном положении каждая грань куба окрашена в один из 6 цветов. Остроумный механизм позволяет поворачивать любой слой из 9 кубичков, примыкающих к одной грани куба, вокруг ее центра (на рис. 1 слегка повернут верхний слой); при этом цвета граней смешиваются. Задача состоит в том, чтобы вернуть разноцветные грани кубика в исходное положение.

Рис. 1

Приведем один из многочисленных алгоритмов решения этой задачи. Он включает два этапа: на первом собираются кубички, располагающиеся в серединах ребер куба (реберные), на втором – угловые. Каждый кубичек может находиться на одном и том же месте в нескольких положениях (реберный – в двух, угловой – в трех). В соответствии с этим каждый этап делится на два шага: на первом кубички только расставляются на нужные места, а на втором они, если это необходимо, разворачиваются на своих местах так, чтобы их цвета совпали с «правильными» цветами граней. Ориентирами при определении правильных положений реберных и угловых кубичков служат квадраты в центрах граней: их взаимное расположение не меняется при вращении граней, а их цвета задают будущие цвета граней куба.

Записывать последовательности ходов (операции) будем, пользуясь обозначениями рис. 1; например, ΦΠ' – это последовательность из двух поворотов: фасадной (передней) грани на 90° по часовой стрелке и правой – на 90° против часовой стрелки. Весь процесс сборки основан на операции F = ПВФВ'Ф'П'Ф и обратной к ней операции F = Ф'ПФВФ'В'П'.

1-й этап. Сборка реберных кубичков.

1. Для расстановки реберных кубичков применяется операция F (или F'), меняющая местами ровно два из них. (Действие операции на реберных кубичках показано на рис. 2.)