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

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

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

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

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

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

Тогда перестановка типа <1, 1, 1, 1, 1, 1, 1, 1> имеет ₂ ⁸ (4,4) = = 70 неподвижных точек. Каждая перестановка типа <4, 4> имеет (по принципу умножения Р ₂ =2∙1= 2 неподвижные точки. Для каждой перестановки типа <2, 2, 2, 2> имеется ₂ ⁴ (2, 2) = = 6 неподвижных точек. Каждая перестановка типа <1, 1, 3, 3> имеет (по принципу умножения) Р ₂ =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, 1, 2, 2> и 1 перестановку типа <1, 1, 1, 1, 1, 1>. Определим количество неподвижных точек для перестановок каждого типа. Для перестановки типа <1, 1, 1, 1, 1, 1> имеем по принципу умножения Р₄ = 4∙3∙2∙1∙4∙4 = 384 неподвижные точки. Для каждой перестановки типа <1, 1, 2, 2> по принципу умножения имеется Р₄ = 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) доказана по индукции. Эту формулу называют формулой включения и исключения. Часто её представляют в таком виде: