Быстрый поиск

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

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

Переформулируем теперь эту задачу так, чтобы стала понятной её связь с леммой Бернсайда. Пусть М – множество всевозможных по-разному раскрашенных кубов одного размера, положение которых в пространстве фиксировано (|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 вращений куба.

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

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.

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

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

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

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 перестановка типа <1, 1, 1, 1, 1>,

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

5 перестановок типа <1, 2, 2>.

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