Научная библиотека

§ 13. КОМБИНАТОРНЫЕ ЗАДАЧИ

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

1. Раскраска вершин куба.

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

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

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

Ситуация существенно меняется, если мы откажемся от предположения о том, что кубы жестко закреплены, так как по-разному окрашенные кубы можно повернуть так, что в новом положении их окраски совпадут (рис. 33).

Рис. 33

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

Сколькими геометрически различными способами можно раскрасить вершины куба в три цвета.

Переформулируем теперь эту задачу так, чтобы стала понятной ее связь с леммой Бернсайда. Пусть М — множество всевозможных по-разному раскрашенных кубов одного размера, положение которых в пространстве фиксировано, , G — группа всех вращений куба, состоящая из 24 перестановок. Группа G естественным образом определяет группу перестановок на множестве М. Именно: если а — некоторое вращение, то каждому кубу из М можно сопоставить некоторый, вообще говоря, другой куб, который получается из первого при вращении а. Это соответствие является, очевидно, перестановкой на множестве которую будем обозначать а. Группу всех таких перестановок множества М, определяемых перестановками из G, мы будем обозначать G. Ясно, что

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

Считая вершины кубов занумерованными числами 1,2, 3, 4, 5, 6, 7, 8, раскраску каждого из 38 кубов можно однозначно охарактеризовать «словом» из 8 букв, каждая из которых есть либо к, либо с, либо з. То, что i-я буква слова равна к (или с, или з), означает; что i-я вершина при выбранной нумерации окрашена в красный цвет (или в сцний, или в зеленый соответственно). Например, для куббв, изображенных на рис. 33, имеем соответственно последовательности . Перестановки из группы G переставляют такие последовательности. Например, если то перестановка а слово переводит в , слово ссззсскк переводит в слова оставляет неизменными и т. д. Выписать всю таблицу значений для перестановки а затруднительно, поскольку она состоит из строк!

Для того чтобы применить лемму Бернсайда, необходимо определить число неподвижных точек каждой перестановки из G. Последовательность букв будет неподвижной для перестановки тогда и только тогда, когда при разложении соответствующей перестановки в произведение "Циклов вершины куба, номера которых входят один и тот же цикл, окрашены одним цветом. Например, если , то неподвижными относительно а будут слова, составленные целиком из одной буквы, и слова, составленные из двух разных букв, причем одна из них стоит на первых четырех местах в слове, а вторая — из четырех последующих. Поэтому имеется 9 неподвижных точек перестановки на множестве М. Уже на этом примере видно, что подсчет числа неподвижных точек перестановок из G сильно упрощается, если извесгны разложения в произведение циклов соответствующих перестановок из G. Если перестановка разложена в произведение циклов, то число ее неподвижных точек равно

Поэтому сначала мы опишем разложения в произведение циклов для всех перестановок из группы G вращений куба.

а) Вокруг каждой из трех осей, соединяющих центры противоположных граней, имеется три нетождественных вращения. Им соответствуют перестановки

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

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

Вместе с тождественной получаем 24 перестановки. Итак, в группе G вращений куба имеется

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

Таким образом, число геометрически различимых способов раскраски вершин куба в три цвета равно 333.

2. Составление ожерелий.

Сколько различных ожерелий из семи бусин можно составить из бусин двух цветов — красного и синего?

Для того чтобы стала понятной аналогия этой задачи с предыдущей, переформулируем ее следующим равносильным образом:

Сколькими геометрически различными способами можно раскрасить вершины правильного семиугольника в два цвета?

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

Снова будем описывать раскраски словами длины 7, составленными из букв к (вершина окрашена в красный цвет) и с (вершина окрашена в синий цвет). На множестве N всех таких слов действует группа перестановок, задаваемых перестановками из Например, если, , то перестановка а последнюю букву каждого слова переставляет в его начало, а остальные буквы не изменяет. Для того чтобы определить число орбит группы на множестве N, необходимо найти типы перестановок из Эта задача гораздо проще аналогичного вопроса для группы G из примера 1.

Группа состоит из 14 перестановок множества которые распределены по возможным типам так:

Слово неподвижно относительно перестановки тогда и только тогда, когда буквы, стоящие на местах с номерами из одного цикла в перестановке а, совпадают. Поэтому тождественная перестановка имеет 27 неподвижных точек на N, перестановки второго типа — по 2, а перестановки третьего типа — по 24. Применяя лемму Бернсайда, получаем

Итак, из бусин двух цветов можно составить 18 семибусенных ожерелий.

Упражнения

1. Грани куба можно раскрасить: а) все в белый цвет; б) все в черный цвет; в) часть в белый, а остальные в черный. Сколько имеется разных способов раскраски?

2. Сколько различных ожерелий можно составить из двух синих, двух белых и двух красных бусин?

3. Сколькими геометрически различными способами три абсолютно одинаковые мухи могут усесться в вершинах правильного пятиугольника?

4. Сколько существует различных ориентированных графов с тремя вершинами?

5. Сколько существует различных неориентированных графов с четырьмя вершинами?

6. Сколькими способами можно раскрасить вершины куба в два цвета так, чтобы вершин каждого цвета было поровну?

7. Сколькими различными способами можно грани куба раскрасить в четыре цвета?