КОМБИНАТОРИКА

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

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

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

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

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

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

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

С помощью правила суммы легко сосчитать и число элементов в , когда  и  имеют общие элементы. Если обозначить через  множество всех общих элементов у множеств  и , то оно равно , где  - число элементов в множестве . Это утверждение – частный случай так называемой формулы перекрытий.

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

, .

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

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

.

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

.

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

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

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

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

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

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

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

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

Рис. 1

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

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

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

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

Рис. 2

2. Для разворачивания применяется операция ; в результате на своих местах поворачиваются два кубичка ( и  на рис. 2).

2-й этап. Сборка угловых кубичков.

1. Для расстановки угловых кубичков применяется операция , действие которой показано стрелками на рис. 3, и обратная операция @, переставляющая те же кубички в обратном порядке.

Рис. 3

2. Для разворачивания угловых кубичков применяется операция , действие которой показано на рис. 4, и обратная к ней операция , поворачивающая те же три кубичка в противоположном направлении.

Рис. 4

Указанные операции можно использовать и в рамках других общих схем. Например, нетрудно правильно собрать все реберные кубички, кроме четырех, лежащих в одной грани, после чего можно перейти к выполнению первого этапа алгоритма. Общее число ходов при этом заметно сокращается, но остается все еще большим. Дальнейшее сокращение можно получить, в частности, за счет расширения набора стандартных операций. Имеются и принципиально другие схемы сборки. Лучшие из них позволяют обойтись примерно 50 ходами-поворотами, но теоретически из любого состояния кубика можно вернуться в исходное не более чем за 23 хода. Лучшее время, показанное на чемпионате мира 1982 г. по скоростной сборке кубика Рубика, составило всего 22,95 с.

Задача поиска оптимального (по числу ходов) алгоритма является самой сложной и не решенной пока математической задачей, связанной с кубиком Рубика. Представляет интерес также изучение группы, порожденной поворотами граней, и др. Кубик Рубика служит не только развлечением, но и прекрасным наглядным пособием по алгебре, комбинаторике, программированию.