Связь комбинаторики с различными разделами математики (стр. 4 из 7)
Итак, 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.Итак, двумя геометрически различными способами три одинаковые мухи могут усесться в вершинах правильного пятиугольника.
Задача 6. Сколькими способами можно раскрасить вершины куба в два цвета (красный и синий) так, чтобы вершин каждого цвета было поровну?
Решение. Для решения этой задачи воспользуемся задачей 1. Пусть М – множество всевозможных по-разному раскрашенных кубов одного размера, положение которых в пространстве фиксировано. Тогда по формуле
nk(k1, k2, …, kn) = 
получим |M| = 28(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> имеет
28(4,4) = = 70 неподвижных точек. Каждая перестановка типа <4, 4> имеет (по принципу умножения Р2 =2∙1= 2 неподвижные точки. Для каждой перестановки типа <2, 2, 2, 2> имеется 24(2, 2) = 
= 6 неподвижных точек. Каждая перестановка типа <1, 1, 3, 3> имеет (по принципу умножения) Р2 =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 = 4∙3∙2∙1∙4∙4 = 384 неподвижные точки. Для каждой перестановки типа <1, 1, 2, 2> по принципу умножения имеется Р4 = 4∙3∙2∙1 = 24 неподвижные точки. По лемме Бернсайда получаем
(1∙384+3∙24) = 19. Итак, существует 19 различных способов раскраски граней куба в 4 цвета так, чтобы все 4 цвета присутствовали в раскраске каждого куба.
§ 2. «Метод просеивания» [4]
Познакомимся с наиболее общим методом пересчёта, который можно назвать «методом просеивания» или «комбинаторным просеиванием»: с любым свойством P можно связать его расщепление на некотором множестве A, в соответствии с которым A разбивается на две части: подмножество А1, образованное элементами, обладающими свойством Р, и А2, образованное элементами, не обладающими свойством Р, т. е. обладающими свойством
. Выбирая свойства подходящим образом, можно последовательным просеиванием пересчитать подмножества с наложенными на них теми или иными ограничениями.2.1. Формула включения и исключения
Пусть А – конечное множество и
. Будем обозначать через 
дополнение А1 по отношению к А, а через CardA – число элементов в А.Тогда
.Если
и 
, то 
(1) 
.Покажем, что формула (1) обобщается на случай nподмножеств
, i=1, 2, ... n: 
(2)Действуем по индукции. Имеем
(3)Предположим, что (2) выполняется для случая n-1 подмножеств Ai, i=1, 2,…,n-1:
(4)Рассмотрим следующие подмножества множества An:
Применяя (4) с A=An, имеем
(5)Подставляя (5) и (4) в (3), получаем (2). Таким образом, с учётом (1) формула (2) доказана по индукции. Эту формулу называют формулой включения и исключения. Часто её представляют в таком виде:
(6)Формулы (2) и (6) играют основную роль в перечислении подмножеств, обладающих заданными свойствами. Посмотрим на эти формулы с другой точки зрения. Пусть элементы
обладают свойством Pi, i=1, 2, …,n. Тогда мы скажем, что подмножество 
обладает свойством 
. Таким образом, если элементы А могут обладать n различными свойствами, то число элементов А, обладающих k указанными свойствами и не обладающих n-k остальными, дается формулой (6).