10) (2, 6, 3) (1, 5, 4)

11) (3, 6, 2) (4, 5, 1)

12) (6, 4, 2) (1, 5, 3)

13) (2, 4, 6) (3, 5, 1)

14) (1, 3, 6) (2, 4, 5)

15) (6, 3, 1) (5, 4, 2)

16) (1, 4, 6) (2, 3, 5)

17) (6, 4, 1) (5, 3, 2)

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

18) (2, 3) (1, 4) (5, 6)

19) (1, 3) (4, 2) (5, 6)

20) (1, 6) (5, 2) (3, 4)

21) (1, 5) (6, 2) (3, 4)

22) (4, 6) (3, 5) (1, 2)

23) (6, 3) (5, 4) (1, 2)

Вместе с тождественной перестановкой (1)(2)(3)(4)(5)(6) получаем 24 перестановки – все элементы группы G. Итак, в группе G вращений куба имеется:

1 перестановка типа ,

6 перестановок типа ,

3 перестановки типа ,

8 перестановок типа ,

6 перестановок типа .

Поэтому тождественная перестановка имеет 2⁶ неподвижных точек на М, перестановки второго и пятого типов имеют по 2³ неподвижных точек на М, перестановки третьего типа – по 2⁴, а перестановки четвёртого типа – по 2². Тогда по лемме Бернсайда получаем (2⁶ + 6∙2³+ 3∙2⁴+ 8∙2² + 6∙2³) = 10.

Итак, число геометрически различных способов раскраски граней куба в два цвета равно 10.

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

Решение. Переформулируем задачу так: сколькими геометрически различными способами можно раскрасить вершины правильного шестиугольника так, чтобы две были синего цвета, две – белого, две – красного? а) Вокруг центра шестиугольника имеется пять поворотов на углы . Им соответствуют перестановки:

1) (1, 2, 3, 4, 5, 6)

2) (1, 3, 5) (2, 4, 6)

3) (1, 4) (2, 5) (3, 6)

4) (1, 5, 3) (2, 6, 4)

5) (1, 6, 5, 4, 3, 2)

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

6) (1) (4) (2, 6) (3, 5)

7) (2) (5) (3, 1) (4, 6)

8) (3) (6) (2, 4) (1, 5)

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

9) (1, 2) (6, 3) (5, 4)

10) (1, 6) (2, 5) (3, 4)

11) (2, 3) (1, 4) (6, 5)

Вместе с тождественной перестановкой (1) (2) (3) (4) (5) (6) получаем 12 перестановок – все элементы группы G. Итак, в группе G имеется:

1 перестановка типа ,

2 перестановки типа ,

2 перестановки типа ,

4 перестановки типа ,

3 перестановки типа .

Определим количество неподвижных точек для перестановок каждого типа. Так как количество различных цветов, в которые нужно раскрасить шестиугольник, равно трём, то минимальное количество циклов в перестановке должно быть равно трём, чтобы она имела неподвижные точки. То есть перестановки 1), 2), 4), 5) неподвижных точек не имеют. Для перестановки первого типа получим ₃⁶ = = 90 неподвижных точек. Для каждой перестановки типа по принципу умножения получаем по Р₃ =3∙2∙1= 6 неподвижных точек. Для каждой перестановки типа по принципу умножения получим по Р₃ =3∙2∙1∙1= 6 неподвижных точек. Применим лемму Бернсайда: (1∙90+ 4∙6+ 3∙6) = 11.

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

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

Решение. Обозначим М – множество различных способов расположения трёх одинаковых мух в вершинах пятиугольника, если вершины занумерованы. Тогда |M| = ₂⁵ (3, 2)= =10 способов расположения мух, где 2 – количество элементов множества М₁ = {м, с} (где м – муха, с – свободная вершина),

3, 2 – кратности соответственно м и с.

а) Вокруг центра пятиугольника имеется четыре поворота на углы . Им соответствуют перестановки:

1) (1, 2, 3, 4, 5)

2) (1, 3, 5, 2, 4)

3) (1, 4, 2, 5, 3)

4) (1, 5, 4, 3, 2)

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

5) (1) (2, 5) (3, 4)

6) (2) (1, 3) (5, 4)

7) (3) (2, 4) (1, 5)

8) (4) (3, 5) (2, 1)

9) (5) (1, 4) (2, 3),

где 1, 2, 3, 4, 5 – числа, с помощью которых занумерованы вершины пятиугольника. Вместе с тождественной перестановкой (1)(2)(3)(4)(5) имеем 10 элементов группы G. Итак, в группе G имеется:

1 перестановка типа ,

4 перестановки типа ,

5 перестановок типа .

Определим количество неподвижных точек для перестановок каждого типа. Чтобы перестановка имела неподвижные точки, минимальное количество циклов в перестановке должно быть равно двум, так как множество М₁ состоит из двух элементов м и с. Поэтому перестановки 1) – 4) не имеют неподвижных точек. Тогда для перестановки типа имеем по формуле: ₂⁵ (3, 2) = = 10 неподвижных точек. Для каждой перестановки типа получим по принципу умножения по Р₂ =2∙1∙1= 2 неподвижные точки. По лемме Бернсайда получаем (1∙10+ 5∙2) = 2.

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

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

Решение. Для решения этой задачи воспользуемся задачей 1. Пусть М – множество всевозможных по-разному раскрашенных кубов одного размера, положение которых в пространстве фиксировано. Тогда по формуле _n^k (k₁, k₂, …, k_n) = получим |M| = ₂⁸ (4,4) = = 70 по-разному раскрашенных кубов. Так как нам нужно раскрасить вершины в два цвета (4 - в красный, 4 - в синий), то минимальное количество циклов в перестановке должно быть равно двум. Поэтому все перестановки 1) – 24) (задача 1) имеют неподвижные точки. В результате в группе G имеется:

1 перестановка типа ,

6 перестановок типа ,

9 перестановок типа ,

8 перестановок типа .

Тогда перестановка типа имеет ₂⁸ (4,4) = = 70 неподвижных точек. Каждая перестановка типа имеет (по принципу умножения Р₂ =2∙1= 2 неподвижные точки. Для каждой перестановки типа имеется ₂⁴ (2, 2) = = 6 неподвижных точек. Каждая перестановка типа имеет (по принципу умножения) Р₂ =2∙1∙2∙1= 4 неподвижные точки. По лемме Бернсайда получаем (1∙70+ 6∙2 + 9∙6 + 8∙4) = 7.

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

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

Решение. Для решения этой задачи воспользуемся задачей 3. Пусть М – множество всевозможных по-разному раскрашенных кубов одного размера, положение которых в пространстве фиксировано. Тогда по принципу умножения: первую грань можно раскрасить 4 способами, вторую – тремя, третью – двумя, четвёртую – одним способом, пятую – четырьмя, шестую – четырьмя способами. Получим |M| = 4∙3∙2∙1∙4∙4 = 384. Найдём геометрически различные способы раскраски. Для этого используем описанные в задаче 3 разложения в произведение циклов всех перестановок из группы G вращений куба. Так как в раскраске куба должны присутствовать четыре разных цвета, то минимальное количество циклов в перестановке должно быть равно четырём. Поэтому перестановки 1), 3), 4), 6), 7), 9) – 23) в задаче 3 неподвижных точек не имеют. Таким образом, неподвижные точки имеют 3 перестановки типа и 1 перестановку типа . Определим количество неподвижных точек для перестановок каждого типа. Для перестановки типа имеем по принципу умножения Р₄ = 4∙3∙2∙1∙4∙4 = 384 неподвижные точки. Для каждой перестановки типа по принципу умножения имеется Р₄ = 4∙3∙2∙1 = 24 неподвижные точки. По лемме Бернсайда получаем (1∙384+3∙24) = 19.

Итак, существует 19 различных способов раскраски граней куба в 4 цвета так, чтобы все 4 цвета присутствовали в раскраске каждого куба.

§ 2. «Метод просеивания» [4]

Познакомимся с наиболее общим методом пересчёта, который можно назвать «методом просеивания» или «комбинаторным просеиванием»: с любым свойством P можно связать его расщепление на некотором множестве A, в соответствии с которым A разбивается на две части: подмножество А₁, образованное элементами, обладающими свойством Р, и А₂, образованное элементами, не обладающими свойством Р, т. е. обладающими свойством . Выбирая свойства подходящим образом, можно последовательным просеиванием пересчитать подмножества с наложенными на них теми или иными ограничениями.

2.1. Формула включения и исключения

Пусть А – конечное множество и . Будем обозначать через дополнение А₁ по отношению к А, а через Card A – число элементов в А.

Тогда

.

Если и , то

(1)

.

Покажем, что формула (1) обобщается на случай n подмножеств , i=1, 2, ... n:

(2)

Действуем по индукции. Имеем

(3)

Предположим, что (2) выполняется для случая n-1 подмножеств A_i, i=1, 2,…,n-1:

(4)

Рассмотрим следующие подмножества множества A_n:

Применяя (4) с A=A_n, имеем

(5)

Подставляя (5) и (4) в (3), получаем (2). Таким образом, с учётом (1) формула (2) доказана по индукции. Эту формулу называют формулой включения и исключения. Часто её представляют в таком виде:

(6)

Формулы (2) и (6) играют основную роль в перечислении подмножеств, обладающих заданными свойствами. Посмотрим на эти формулы с другой точки зрения. Пусть элементы обладают свойством P_i, i=1, 2, …,n. Тогда мы скажем, что подмножество обладает свойством . Таким образом, если элементы А могут обладать n различными свойствами, то число элементов А, обладающих k указанными свойствами и не обладающих n-k остальными, дается формулой (6).

2.2. Общий метод «просеивания» или «пропускания через решето». Решето Сильва – Сильвестра

Формула (6) описывает последовательный процесс пересчёта, называемый решетом Сильва – Сильвестра.

Пример. Рассмотрим множество