Основы теории перечисления Пойа. Лемма Бернсайда

Пример. Какое число ожерелий из 3-х бусин можно составить из бусин 2-х

цветов: красного (к) и синего (с).

Решение. Здесь два ожерелья неотличимы, если одно из другого мож­но получить преобразованием вращения или , как называют, циклической перестановкой на множестве 3-х элементов из множества {к, с}.

Например, ожерелье к с с эквивалентно ожерелью с к с, так как второе можно получить из первого при циклической перестановке, когда первый элемент переходит на второе ме­сто, второй на третье, а третий на первое. Рассмотрим все циклические перестановки трех элементов G:

Первая перестановка – тождественная; вторая-вращение против часовой стрелки, когда первый элемент переходит на второе место, второй, на третье, третий на первое; третья-вращение по часовой стрелке. Рассмотрим все слова из алфавита 0-к, 1-с длинны три:

000, 001, 010, 011, 100, 101, 110, 111

Некоторые из рассматриваемых ожерелий, как мы выяснили, эквивалентны, т.е. все множество ожерелий разбивается на классы эквивалентных ожерелий: любая пара ожерелий в одном классе эквивалентна между собой, а пара из разных - неэквивалентна. Поэтому число классов и есть требуемое число.

Чтобы получить класс, в котором лежит некоторое ожерелье, например 001, нужно к нему применить все перестановки G .В данном случае

001 .

Общее разбиение ожерелий имеет вид:

{000}{001, 100, 010}{011, 101, 110}{111}.

Т.е. число различных ожерелий равно 4.

В задачах такого рода имеется множество объектов (всевозможные слова алфавита {к, с}); множество преобразований одного объекта в другой, что означает неотличимость объектов (все циклические перестановки трех элементов).

Тогда множество преобразований будет разбивать множество объектов на классы эквивалентных объектов.

Утверждение 1. Множество преобразований, нами рассматриваемое, будет группой перестановок (т.е. каждое преобразование слова заключается в перестановке его букв).

Дадим строгое определение группы перестановок.

Перестановкой слова , называют преобразованием слова длинны n, при котором первая буква переходит на ое место, вторая на ое место, ая на ое.

Например, (2 1 4 3) (к с к к)=с к к к.

Произведением двух перестановок называют преобразование, полученное в результате последовательного применения преобразования , потом преобразования .

Утверждение 2 . Произведение перестановок является перестановкой.

Пример.(2 1 4 3) (3 2 4 1)=(2 3 1 4).

Утверждение 3.Произведение перестановок обладает свойством ассоциативности:

Определим место, на которое перейдет s-ый элемент от перестановки в левой и правой частях равенства

,

т.е. один и тот же элемент.

Тождественной или единичной перестановкой e называют перестановку, оставляющую все буквы на месте (1 2 n).

Утверждение 4. перестановки .

Обратной к перестановке называют перестановку , такую что .

Утверждение 5.Обратная к любой существует единственна, и .

Доказательство. Докажем утверждение на примере. Пусть :(2 4 3 1).

При преобразовании каждый элемент должен остаться на своем месте. значит т. е. (4 1 3 2 ).

Множество элементов с бинарной, ассоциативной операцией , единичным элементом e и обратным для каждого называется группой.

Подгруппой группы называют подмножество элементов группы, которое само является группой.

Утверждение 6.Чтобы подмножество конечной группы являлась группой необходимо и достаточно, чтобы оно было замкнуто относительно групповой операции

Доказательство. Необходимость очевидна.

Достаточность: Пусть множество замкнутое относительно операции . Возьмем произвольный элемент и будем брать степени

до тех пор пока не получим элемент который был в этом ряду ранее: Тогда и если не единица, т.е. k 2, то есть обратный к . Т.е. подмножество есть группа.

Примеры подгрупп.

1.Группа вращений правильного треугольника:

1 2 3 – тождественная перестановка;

2 3 1 – вращение по часовой стрелке;

3 1 2 – вращение против часовой стрелки.

32

Нетрудно проверить, что произведение любых двух перестановок нашей группы есть перестановка нашей группы, есть перестановка нашей группы.

Данная группа является подгруппой группы всех 3!=6 перестановок трех элементов.

2.Группа всех вращений тетраэдра:

1) Вращения относительно высоты 10 тетраэдра на 120 по часовой и против часовой стрелки:

(10) 1 3 4 2 1 4 2 3

(2) 4 2 1 3 3 2 4 1

(3) 2 4 3 1 4 1 3 2

(4) 3 1 2 4 2 3 1 4

2)Вращения относительно осей LM проходящих через середины противоположных сторон на 180

2 1 4 3 4 3 2 1 3 4 1 2.

3)Тождественная - 1 2 3 4.

Всего 12 перестановок. Эта группа является подгруппой группы всех 4!=24 перестановок четырех элементов. В обоих примерах порядок подгруппы (т.е. число элементов в ней ) делит порядок группы.

Имеет место

Теорема Лагранжа.Порядок подгруппы делит порядок группы.

Доказательство. Пусть имеется группа G и ее подгруппа H. На множестве элементов группы зададим следующее отношение: скажем, что два элемента a и b группы эквивалентны, если найдется элемент что . Это отношение обладает тремя свойствами:

1. Оно рефлексивно, т.е. ~ a для любого а. Это верно, так как , где (Н-подгруппа).
2. Оно симметрично, т.е. если а~b, то b~a. Это верно, так как из первой эквивалентности следует, что и поэтому ( так как Н подгруппа, здесь мы так же использовали ассоциативность умножения в группе).
3. Оно транзитивно, т. е. если a ~ b и b ~ c,то a ~ c. Этоверно, так как из первой эквивалентности следует, что из второй следует тогда так как Н подгруппа.

Тогда нетрудно видеть, что данное отношение эквивалентности разобьет все множество G на левые классы эквивалентных непересекающихся множеств, называемых левыми смежными классами группы G по подгруппе Н. (В одном классе эквивалентные между собой элементы, в разных неэквивалентные).

Причем в каждом классе содержится ровно элементов. ( Класс, содержащий некоторый элемент а, содержит элементы где h пробегает группу Н, а их ровно ). Классы не пересекаются, и поэтому порядок подгруппы Н делит порядок группы G.

Данное утверждение можно доказать также используя разложение на правые классы смежности группы G по подгруппе Н.

Пример.Группа вращений треугольника Н является подгруппой группы G всех перестановок трех элементов.

Н: 1 2 3 2 3 1 3 1 2

G: 1 2 3 1 3 2 3 2 1 2 1 3 2 3 1 3 1 2

Разложение на классы эквивалентных элементов имеет вид:

1 2 3, 2 3 1, 3 2 1 2 1 3, 1 3 2, 3 2 1.

Первый класс есть (1 2 3 ) , второй (1 3 2 ) .

Теперь займемся следующей задачей:

1. Имеется множество объектов Х :слова длинны п в алфавите .
2. Имеется группа перестановок G в алфавите букв длинны п. Два слова назовем эквивалентными , если для некоторой перестановки , имеем: слово совпадает со словом .

Утверждение 7.Введенное отношение является отношением эквивалентности.

1. Оно симметрично. Если , то = , тогда .

2. Оно рефлексивно , так как

3. Оно транзитивно: если , то = , = ,

тогда , где (здесь мы также использовали ассоциативность преобразования букв слова).

Таким образом, данное отношение разбивает множество слов на классы эквивалентных слов или, как будем называть в дальнейшем, на орбиты. Наша основная цель - найти число орбит.

Для некоторого слова х рассмотрим множество перестановок N(x): ,

т.е. это перестановки, которые оставляют на месте данный объект. (Например, для слова 010 такой перестановкой служит слово 321, когда первая и третья буквы слова меняются местами, а также тождественная 123).

Утверждение 8. Множество N(x) является группой.

Действительно это верно, так как, если принадлежат N, то . В силу Утверждения 7. и следует требуемое.

Теперь сформулируем основное утверждение параграфа.

Лемма 1. Бернсайда. Число орбит элементов множества Х относитель­но группы перестановок G равно . (Здесь п(а) число слов х,

которые не изменяются при перестановке а.)

Для доказательства рассмотрим таблицу: ее строки — это элементы группы G, а столбцы — это слова х;на пересечении строки а и столбца х ставим 1, если а(х) = х..

Тогда число единиц в таблице можно получить, суммируя их по строкам или, суммируя их по столбцам, т.е.

. (1)

Наша цель — преобразовать сумму в правой части к нужному виду. Сумму в правой части удобно посчитать, разбив элементы на орбиты

Рассмотрим некоторую орбиту О и два элемента из этой орбиты. Покажем справедливость утверждений.

Утверждение 9.

Утверждение 10. Число слов в орбите О равно (в силу пре­дыдущего утверждения, число слов в орбите не зависит от выбора предста­вителя орбиты.)

Доказательство. ( Утверждение 9.)

означает, что при некоторой перестановке . - это перестановки

Рассмотрим перестановки (N обозначает N( )). Нетрудно видеть, что Действительно,

Причем, если , то , поэтому

В силу эквивалентностислов следует и обратное неравенство

,что и дает требуемое.

Доказательство. ( Утверждение10.)

Пусть х некоторый элемент орбиты О. Чтобы найти число элементов в орбите О, нужно к элементу х применить все перестановки группы G, и тогда все полученные различные элементы и будет орбита О.

Разобьем все перестановки из G на правые классы смежности по под­группе N(х). Покажем, что для любых перестановок из одного класса будем иметь , а из разных классов . Это и означает, что число элементов в орбите равно числу классов смежности группы G по подгруппе N(х), т.е. числу . Действительно, если , то , где N(х}. Тогда

Пусть теперь неэквивалентна . Покажем, что

Действительно, если это не так, т.е. , то

Таким образом , т.е. пере­становки эквивалентны. Противоречие. Утверждение 10 доказано.

Теперьможно доказать Лемму Бернсайда. Доказательство. Имеем равенство (1).

Здесь — есть не что иное, как число орбит, обозначено какR,

число N(х) не зависит от представителя , обозначим его —

N(0). Тогда, деля левую часть равенства на получаем требуе­мую формулу.

Осталось показать, как вычислять п(а) — число слов в алфавите из s символов, которые не изменяются при перестановке а. Нетрудно показать, что любую перестановку можно представить в виде произведения циклов.

Например, 21453 есть произведение 12 345, цикл 345 означает, что третья буква переходит на четвертое место, четвертая на пятое, а пятая на третье, т.е. буквы третья, четвертая и пятая сдвигаются по циклу, а все остальные остаются на месте. Цикл 12 определяется аналогично. Тогда слова, которые не изменяются при перестановке 21453 — это слова, у которых на первом и втором месте стоит одна и та же буква, и на третьем, четвертом и пятом месте стоит одна и та же буква. В данном случае число слов равно . В общем случае, если перестановка а раскладывается в k циклов, то

Пример. Каким числом способов можно раскрасить вершины тетраэдра

в три цвета. Два тетраэдра различно раскрашены,если их нельзя перевести

друг в друга вращениями в пространстве.

Решение. Рассмотрим множество объектов Х — слова длины 4 в ал­фавите из трех элементов. Это все окрашенные тетраэдры, включая эквивалентные (т.е. зафиксировали тетраэдр и все­возможными способами раскрасили его вершины, при этом не­которые раскраски естественно оказываются эквивалентными, т.е. одну из другой можно получить поворотами в простран­стве).

Наша задача посчитать число неэквивалентных раскрасок. Рассмотрим группу вращений тетраэдра Н относительно ко­торой и рассматриваем неэквивалентность раскрасок. Тогда число различных раскрашенных тетраэдров есть число орбит Х относительно Н. Найдем числа

1. 1342 = 1 234, п = = 9 и таких перестановок в первой группе 8.

2. 2143 == 12 34; п = = 9 и таких перестановок три.

3. 1234 =1 ; п = 3⁴ = 64.

По лемме Бернсайда искомое число есть =15. Здесь 12 число элементов в группе вращений тетраэдра.

Упражнения.

1. Найти число ожерелий из пяти бусин трех цветов. Два ожерелья оди­наковы, если одно на другого можно получить циклической переста­новкой в плоскости.

2. Найти число раскрасок граней тетраэдра в четыре цвета. Два тетра­эдра одинаковы, если один иа них можно получить из другого враще­нием в пространстве.

3. Найти число раскрасок ребер тетраэдра в четыре цвета. Два тетра­эдра одинаковы, если один из другого можно получить вращениями в пространстве.

4. Найти число существенно различных булевых функций от трех пере­менных. Две функции одинаковы, если одну из другой можно получить переименованием переменных.

Ответы

К главе 1.

1) 2) 3) 4) . 5) . 6) 7) 8)8!=40320. 9) 5!=120. 10) 3 11)

12) 13) 14) =252.

15) 16) 17) .

18) . 19) . 20) .

21) 22) 23) 24) 25) 26) 27) . 28) Порядок существенен: 5! ; порядок не существенен: . 29) 30)

31) . 32) . 33) 34) 35)66660:3 (1111+2222+3333+4444). 36)33330. 37)11110. 38) 16665. 39) 12. 40) 864. 41) 2220. 42) 43) 44) 45)

46) 47) а)

Разное.

1.

2.

3.

4. (6).

5.

6.

7.

8.

9.

10.

11. Ответ нужно поделить на 2.

К главе 2.

1.

2.

3.

4.

5.

К главе 4.

1.

2.

3.

4.