Связь комбинаторики с различными разделами математики (стр. 3 из 7)
а) Вокруг каждой из трёх осей, соединяющих центры противоположных граней, имеется три вращения на углы
, 
, 
. Им соответствуют перестановки:1) (1, 5, 8, 4) (2, 6, 7, 3)
2) (1, 8) (2, 7) (3, 6) (4, 5)
3) (1, 4, 8, 5) (2, 3, 7, 6)
4) (1, 4, 3, 2) (5, 8, 7, 6)
5) (1, 3) (2, 4) (5, 7) (6, 8)
6) (1, 2, 3, 4) (5, 6, 7, 8)
7) (1, 5, 6, 2) (3, 4, 8, 7)
8) (1, 6) (2, 5) (3, 8) (4, 7)
9) (1, 2, 6, 5) (3, 7, 8, 4)
б) Вокруг каждой из четырёх диагоналей куба имеется по два вращения. Им соответствуют перестановки:
10) (1) (2, 5, 4) (3, 6, 8) (7)
11) (2) (1, 3, 6) (4, 7, 5) (8)
12) (3) (1, 6, 8) (2, 7, 4) (5)
13) (4) (1, 3, 8) (2, 7, 5) (6)
14) (1) (2, 4, 5) (3, 8, 6) (7)
15) (2) (1, 6, 3) (4, 5, 7) (8)
16) (3) (1, 8, 6) (2, 4, 7) (5)
17) (4) (1, 8, 3) (2, 5, 7) (6)
в) Вокруг каждой из шести осей, соединяющих середины противоположных рёбер куба, имеется одно вращение. Им соответствуют перестановки:
18) (1, 5) (2, 8) (3, 7) (4, 6)
19) (1, 2) (3, 5) (4, 6) (7, 8)
20) (1, 7) (2, 3) (4, 6) (5, 8)
21) (1, 7) (2, 6) (3, 5) (4, 8)
22) (1, 7) (2, 8) (3, 4) (5, 6)
23) (1, 4) (2, 8) (3, 5) (6, 7)
Вместе с тождественной перестановкой (1)(2)(3)(4)(5)(6)(7)(8) получаем 24 перестановки – все элементы группы G. Итак, в группе Gвращений куба имеется:
1 перестановка типа <1, 1, 1, 1, 1, 1, 1, 1>,
6 перестановок типа <4, 4>,
9 перестановок типа <2, 2, 2, 2>,
8 перестановок типа <1, 1, 3, 3>.
Тогда перестановка первого типа имеет 38 неподвижных точек, любая из перестановок второго типа – 32, третьего и четвёртого типов – 34 неподвижных точек (по формуле
nk = nk). Поэтому согласно лемме Бернсайда, имеем 
(38 + 6∙32 + 9∙34 + 8∙34) = 333.Таким образом, число геометрически различимых способов раскраски вершин куба в три цвета равно 333.
Задача 2. Сколько различных ожерелий из семи бусин можно составить из бусин двух цветов – красного и синего?
Решение. Переформулируем эту задачу следующим равносильным образом: сколькими геометрически различными способами можно раскрасить вершины правильного семиугольника в два цвета? Пусть М – множество всевозможных по-разному раскрашенных правильных семиугольников одного размера, положение которых в пространстве фиксировано. Тогда имеется 27 = 128 различных вариантов раскраски вершин семиугольника, так как каждую вершину независимо от других можно раскрасить двумя способами. Здесь два способа раскраски неотличимы, если один из них можно получить из другого, применяя к семиугольнику либо преобразования вращения, либо симметрии относительно осей. Будем описывать раскраски «словами» длины 7, составленными из букв к (вершина окрашена в красный цвет) и с (вершина окрашена в синий цвет). Проделаем те же действия, что и в задаче 1 для применения леммы Бернсайда. Опишем разложения в произведение циклов для всех перестановок из группы G.
а) Тождественному преобразованию соответствует перестановка:
1) (1)(2)(3)(4)(5)(6)(7)
б) Поворотам на углы
соответствуют перестановки:2) (1,2,3,4,5,6,7)
3) (1,3,5,7,2,4,6)
4) (1,4,7,3,6,2,5)
5) (1,5,2,6,3,7,4)
6) (1,6,4,2,7,5,3)
7) (1,7,6,5,4,3,2)
в) Симметриям относительно осей, соединяющих вершины семиугольника с серединами противоположных сторон, соответствуют перестановки:
8) (1) (2,7) (3,6) (4,5)
9) (2) (1,3) (7,4) (5,6)
10) (3) (2,4) (1,5) (6,7)
11) (4) (3,5) (2,6) (7,1)
12) (5) (4,6) (3,7) (2,1)
13) (6) (5,7) (4,1) (2,3)
14) (7) (1,6) (2,5) (3,4),
где 1, 2, 3, 4, 5, 6, 7 – числа, с помощью которых занумерованы вершины семиугольника.
Итак, в группе G имеется:
1 перестановка типа <1, 1, 1, 1, 1, 1, 1>,
6 перестановок типа <7>,
7 перестановок типа <1, 2, 2, 2>.
Слово неподвижно относительно перестановки
тогда и только тогда, когда буквы, стоящие на местах с номерами из одного цикла в перестановке α, совпадают. Поэтому тождественная перестановка имеет 27 неподвижных точек на М, перестановки второго типа – по 2, а перестановки третьего типа – по 24. Применяя лемму Бернсайда, получаем 
(27 + 6∙2 + 7∙24) = 18.
Итак, из бусин двух цветов можно составить 18 семибусенных ожерелий.
Задача 3. Грани куба можно раскрасить: а) все в белый цвет; б) все в чёрный цвет; в) часть в белый, а остальные в чёрный. Сколько имеется разных способов раскраски?
Решение.
Грань (1' 4' 5' 8') – 1
Грань (2' 3' 6' 7') – 2
Грань (3' 4' 7' 8') – 3
Грань (1' 2' 5' 6') – 4
Грань (1' 2' 3' 4') – 5
Грань (5' 6' 7' 8') – 6
Рис. 3
а) Вокруг каждой из трёх осей, соединяющих центры противоположных граней, имеется три вращения на углы
, , . Им соответствуют перестановки:1) (1) (2) (5, 4, 6, 3)
2) (1) (2) (4, 3) (6, 5)
3) (1) (2) (5, 3, 6, 4)
4) (3) (4) (1, 6, 2, 5)
5) (3) (4) (1, 2) (6, 5)
6) (3) (4) (5, 2, 6, 1)
7) (5) (6) (1, 3, 2, 4)
8) (5) (6) (1, 2) (3, 4)
9) (5) (6) (4, 2, 3, 1)
б) Вокруг каждой из четырёх диагоналей куба имеется по два вращения. Им соответствуют перестановки:
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 перестановка типа <1, 1, 1, 1, 1, 1>,
6 перестановок типа <1, 1, 4>,
3 перестановки типа <1, 1, 2, 2>,
8 перестановок типа <3, 3>,
6 перестановок типа <2, 2, 2>.
Поэтому тождественная перестановка имеет 26 неподвижных точек на М, перестановки второго и пятого типов имеют по 23 неподвижных точек на М, перестановки третьего типа – по 24, а перестановки четвёртого типа – по 22. Тогда по лемме Бернсайда получаем
(26 + 6∙23+ 3∙24+ 8∙22 + 6∙23) = 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 перестановка типа <1, 1, 1, 1, 1, 1>,
2 перестановки типа <6>,
2 перестановки типа <3, 3>,
4 перестановки типа <2, 2, 2>,
3 перестановки типа <1, 1, 2, 2>.
Определим количество неподвижных точек для перестановок каждого типа. Так как количество различных цветов, в которые нужно раскрасить шестиугольник, равно трём, то минимальное количество циклов в перестановке должно быть равно трём, чтобы она имела неподвижные точки. То есть перестановки 1), 2), 4), 5) неподвижных точек не имеют. Для перестановки первого типа получим
36 = 
= 90 неподвижных точек. Для каждой перестановки типа <2, 2, 2> по принципу умножения получаем по Р3 =3∙2∙1= 6 неподвижных точек. Для каждой перестановки типа <1, 1, 2, 2> по принципу умножения получим по Р3 =3∙2∙1∙1= 6 неподвижных точек. Применим лемму Бернсайда: 
(1∙90+ 4∙6+ 3∙6) = 11.