Связь комбинаторики с различными разделами математики

Доказательство. Рассмотрим отношение «перестановка α сохраняет неподвижным элемент m» между перестановками группы G и элементами множества М. Сопоставим парам (α, m), αG, mM, вершины прямоугольной сети и отметим те из них, для которых соответств

ующая пара (α, m) находится в указанном отношении, то есть α(m)=m (рис. 1).

Иными словами, построим график указанного отношения.

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

λ(α0) + λ(α1) + … +λ(αk-1)= λ(α), где αG.

С другой стороны, на каждой горизонтали отмечаются все перестановки, сохраняющие элемент mM, отвечающий этой горизонтали. А такие перестановки образуют группу Gm – стабилизатор элемента m, - и их число, по теореме, доказанной ранее, равно |Gm|=|G|:|O(m)|. Поэтому при втором способе подсчёта числа отмеченных точек графика рассматриваемого отношения получаем выражение |G1| + |G2| + … + |Gn| = |Gm |(mM).

Однако, если элементы i, j M содержатся в одной орбите, то О(i)=O(j), и поэтому |Gi|=|G|:|O(i)|=|G|:|O(j)|=|Gj|. Пусть О1, О2, …, Оt – все орбиты группы G такие, что , и слагаемые в этом объединении не пересекаются. Разобьём |Gm | (где mM) на части так, чтобы внутри каждой из этих частей суммирование шло по элементам некоторой орбиты:

m| =m| + m| + … +m|.

Каждое из t слагаемых в правой части этого равенства можно преобразовать следующим образом:

m| = = = = |G|.

Поэтому m| = |G| + … +|G| = t∙|G|.

Таким образом, при втором способе подсчёта мы получили t∙|G| отмеченных точек графика. Приравнивая величины, полученные при первом и втором способах, получим

t|G| = ,

то есть t = t(G) = .

Лемма доказана.

1.3. Комбинаторные задачи

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

Задача 1. Сколькими способами можно раскрасить вершины куба в три цвета (например, красный, синий и зелёный)?

Решение. (В остальных задачах будем использовать обозначения, аналогичные обозначениям в этой задаче). Поскольку каждую из восьми вершин куба можно раскрасить тремя способами, причём независимо от того, как раскрашены другие вершины, то множество всех вершин куба можно раскрасить 38=6561 различными способами (по формуле ). Однако при таком подходе к решению задачи молчаливо предполагается, что мы умеем различать вершины куба перед окраской, то есть, скажем, куб жёстко закреплён или его вершины занумерованы. При этом полученный ответ можно интерпретировать следующим образом: можно так раскрасить 38 абсолютно одинаковых, жёстко закреплённых кубов, что все они будут различаться. Для 38+1 кубов этого сделать уже нельзя. Ситуация существенно меняется, если мы откажемся от предположения о том, что кубы жёстко закреплены, так как по-разному окрашенные кубы можно повернуть так, что в новом положении их окраски совпадут (рис.2).

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

Переформулируем теперь эту задачу так, чтобы стала понятной её связь с леммой Бернсайда. Пусть М – множество всевозможных по-разному раскрашенных кубов одного размера, положение которых в пространстве фиксировано (|M|=38), G – группа всех вращений куба. Группа G естественным образом определяет группу перестановок на множестве М. Именно, если αG – некоторое вращение, то каждому кубу из М можно сопоставить некоторый другой куб, который получается из первого при вращении α. Это соответствие является перестановкой на М, которую будем обозначать . Группу всех таких перестановок множества М, определяемых перестановками из G будем обозначать . Ясно, что || = |G|. То, что два куба К1 и К2 из М раскрашены геометрически одинаково, означает, что один из них можно перевести вращением в такое положение, в котором они неразличимы. Иными словами, существует такая перестановка , что (К1) = К2, то есть К1 и К2 содержатся в одной орбите группы , действующей на множестве М. Таким образом, для того чтобы определить число геометрически различимых способов раскраски вершин куба, нужно найти количество орбит группы на множестве М. Считая вершины кубов занумерованными числами 1, 2, 3, 4, 5, 6, 7, 8, раскраску каждого из 38 кубов можно однозначно охарактеризовать «словом» из восьми букв, каждая из которых есть либо к, либо с, либо з. То, что i-тая буква слова равна к (или с, или з) означает, что i-тая вершина при выбранной нумерации окрашена в красный цвет (или в синий, или в зелёный соответственно). Перестановки из группы переставляют последовательности букв к, с, з. Для того чтобы применить лемму Бернсайда, необходимо определить число неподвижных точек каждой перестановки из . Последовательность букв к, с, з будет неподвижной для перестановки тогда и только тогда, когда при разложении соответствующей перестановки αG в произведение циклов вершины куба, номера которых входят в один и тот же цикл, окрашены одним цветом. Если перестановка αG разложена в произведение kциклов, то число её неподвижных точек равно 3k, где , так как вершины куба, номера которых входят в один цикл, можно раскрасить тремя способами. Опишем разложения в произведение циклов для всех перестановок из группы G вращений куба.

 Скачать реферат