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

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

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>,

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