Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 138
Текст из файла (страница 138)
Если а Е Сгг, то а(С) = С и, следовательно, а '(С) = С, т.к. С = 1(С) = а ' о сг(С) = о '(о(С)) = о. '(С). Следовательно, т ' Е Сс. Отсюда Сс — группа. Пусть С и С' принадлежат одному классу эквивалентности. Количество перестаиовок в С, которые отображают С в С', равно (Сс). Для доказательства положим оо(С) = С' и гт(С) = С. Тогда «го о а(С) .= сто(а(С)) — «то(С) = С'. Таким образом, при фиксированном ао для каждой перестановки а такой, что а(С) = С, имеется перестановка ао о а, которая переводит С в С'.
Для каждой а такой, что а(С) = С, положим 1(а) = о.о о а. Тогда 1 отображает каждую перестановку, переводящую С в саму себя, в перестановку, которая переводит С в С'. Более того, если а, и аз — две перестановки, которые переводят С в себя, и аооа1 = ассами, то о«г о («то о с«1) = оо о («то «г о2) . Поэтому («т, о «то) о стт = (ст, ~ о сто) о аз, что дает 1осгт =1оаз аг = сгз. Следовательно, функция 1 ииъективиа. Пусть а переводит С в С'.
Тогда 1(ао ' о а) = ос о (сто ' о о.) = (ос о ао ) о «т = 1 о «т = сг, так что 1 — сюръекция. Следовательно, 1 — взаимно однозначное соответствие, поэтому существует одинаковое количество перестановок, которые переводят С в С', и тех, которые отображают С в себя. Следовательно, если Ст и Сз принадлежат Е, тому же классу эквивалентности, что и С, то количество перестановок, которые переводят С в Сы равно количеству перестановок, которые переводят С в Сз, а именно, (Са!. Это число называется кратностью класса эквивалентности Е.
Отсюда следует, что (С), количество перестановок в С, равно (Сс). )Е(, где ~Е~ — количество раскрасок в Е, или )Сс(. )Е! = (С!. 780 ГПАВА Г9. Перечосленое цветов Последнее соотношение можно также переписать в виде ~С! = Е ~СС~, СЕЕ и тогда, если Ф вЂ” количество классов эквивалентности, Ю !С1 = Е Е 1Сс! = Е!Сс!, СЕ К Е СЕЕ где К вЂ” множество раскрасок. Следовательно, количество различных раскрасок, т.е, число )т' классов эквивалентности, дает следующая формула Для каждой перестановки о пусть у(о) равно количеству раскрасок, которые о не изменяют.
Заметим, что если для каждой раскраски найти число перестановок, не изменяющих ее, и просуммировать эти числа по всем раскраскам, то получим тот же результат, как если бы мы находили количество раскрасок, которые не изменяет каждая перестановка. Поэтому, суммируя по перестановкам, получаем Е ~Сс~ = Е у(о) СЕ К <ге С Х = С ,'У. ~Сс~ = С Е р(о) 1 1 Подведем итог в приведенной ниже теореме. ТЕОРЕМА 19.3. (Лемма Бернсайда о подсчете) Если К вЂ” число раскрасок над множеством о, С вЂ” группа перестановок на множестве о и 1У вЂ” число классов эквивалентности (т.е, различных раскрасок), то 1 1 А'= С,Е, ~Сс~= С Е р(о) ° УПРАЖНЕНИЯ 1.
Определите группу симметрий равностороннего треугольника. 2. Определите группу симметрий правильного пятиугольника. 3. Определите группу симметрий правильного восьмиугольника. 4. Определите группу симметрий тетраэдра. Ь. Если стержень украшен пятью полосками, каждая из которых может быть одного из двух цветов, то сколькими способами можно раскрасить стержень? (Напомним, что стержень можно перевернуть.) 6. Сколькими способами можно раскрасить равносторонний треугольник, используя два цвета? 7.
Сколькими способами, используя два цвета, можно раскрасить прямоугольник, который не является квадратом? РАЗДЕЛ 19.2. Теорема Лова 781 19.2. ТЕОРЕМА ПОЙА Сделав первый шаг, будем развивать дальше теорию подсчета числа раскрасок. С этой целью рассмотрим теорему Пойа, которая дает производящую функцию для нахождения числа раскрасок неориентированной фигуры с использованием заданного количества цветов. При этом нам будет особенно полезна последняя часть уравнения Бернсайда.
Если удастся найти простой способ определения количества раскрасок, которые остаются неизменными при каждой перестановке, то мы сможем просуммировать эти числа и разделить сумму на число перестановок. В разделе 9.5 показано, что каждую перестановку можно представить как произведение непересекающихся циклов. Если вернуться к двухцветной раскраске квадрата, то 4 3 2 1 (14)(23) .
можно выразить как Перестановка Цикловая структура мг Инвариантные раскраски 1д2 С1С2 2 41 = (13)(2)(4) Сг, С4, Св, Сз, Сд, Сго, С11С12 8 С,С2 2 бг = (1)(3)(24) С1, Сз, Сз, Ст, Сд, Сго, С11С12 8 с2 2 ф1 = (14)(23) фг = (12)(34) Сд, С10, С14С16 Сд, Сго, С12Сгз р1 = (1234) сг 2 рг = (13)(24) рз = (1432) С, Спь С,С, С,С с4 1 1 = (1)(2)(3)(4) 4 С1,С2,Сз,С4,...,С1д 16 с1 Е 2сгсг + Зсг Е 2с4 4 г г Всего 48 В цикле раскраска будет оставаться неизменной, если цвет каждой вершины будет совпадать с цветом той вершины, в которую она переходит. Поэтому все вершины в цикле должны быть одного цвета.
Если ф1 должна оставить раскраску неизменной, то вершины 1 и 4 должны быть одного цвета и вершины 2 и 3 должны быть одного цвета. Следовательно, вершины 1 и 4 могут быть красными или синими, и вершины 2 и 3 могут быть красными или синими. Это значит, что есть четыре раскраски, которые остаются неизменными при перестановке ф1. Это раскраски Сд, С,о, С,4 и Сш. Поскольку для каждого цикла есть выбор из двух цветов, то в общем случае число раскрасок, которые не меняются при перестановке а, равно 2~"1 1, где Су(а) — количество циклов в перестановке а, включая циклы длины 1. Тождественную перестановку 1 можно представить в виде (1)(2)(3)(4). Она имеет четыре цикла, поэтому оставляет неизменными 24 раскрасок.
В приведенной ниже таблице указана каждая перестановка, ее выражение через циклы, ее цикловая структура, количество циклов (гт1), раскраски, которые она не меняет (инвариантные раскраски), и количество таких раскрасок (гггг). Для записи цикловой структуры будем использовать обозначение с'„'„где и — число циклов длины т в перестановке. Таким образом, цикловая структура для ф1 имеет вид сг, т.е. ф1 выражается через два цикла длины 2. г82 ГлЯВА тв, перечисление иеелгае Как отмечалось ранее, для определения количества раскрасок, инвариантных относительно перестановки сг, достаточно найти 2сиг г, где Су(сг) — количество циклов в перестановке сг. Затем нужно просуммировать по всем перестановкам и найти 2 дЭ2(сг).
Другой метод — взять цикловую форму и присвоить каждому циклу значение 2. Например, бг = сгсг оставляет неизменными 22. 2 = 8 раскрасок. Затем нужно найти сумму 2 дгг(сг). Третий метод — сложить вместе все цикловые формы. Согласно таблице имеем с41+ 2с~гсг+ Зс»+ 2с4. Если теперь присвоить каждому циклу значение 2, то получим 24+2 2г 2+3 2 +2 2 48 Итак, всего имеется 48 раскрасок, которые не меняются при перестановках. Если теперь это число разделить на 8, количество перестановок, то получим 1 48 — у(сг) = — = 6 (С) 8 различных раскрасок. Далее предположим, что имеется три цвета. Используя аналогичные рассуждения и таблицу, можно вычислить 3 "< г, где Су(сг) — количество циклов в перестановке сг, чтобы найти количество раскрасок, которые остаются неизменными при перестановке сг, а затем просуммировать эти числа и найти 2 гр(гг).
Затем снова можно разделить на 8 и получить количество различных раскрасок. Второй метод; учитывая, что уже имеется сг + 2сгсг + Зсг + 2с4, присвоим каждому циклу значение 3, так что сумма всех раскрасок, которые не меняются при перестановках, равна 34 + 2 . 32 . 3 + 3 . 32 + 2 . 3 = 168 Разделив теперь на 8, получаем 1 168 — гг(сг) = — = 21 )С! 8 различную раскраску. Пусть имеется гп цветов, тогда 1 с т4+2 тг т+3 тг+2 т — 2 Ф'")— ггЕО Поскольку в обшем случае нам нужна величина )~Т 2; р(сг), которую можно гг Е С получить из — (сг + 2сгсг + Зсг + 2с4), 4 2 2 !С! РАЗДЕГГ 29.2.
Теорема Пойа ?83 то положим Рс (сы сз, сз, с4) = — (с + 2с с2 + Зсз + 2с4), 4 2 2 где с, — цикл длины 4, и назовем Рс(с„сз, сз, с4) циклоеым индексом. ПРИМЕР 19.4. Ранее отмечалось, что для двухцветных раскрасок квадрата достаточно одних вращений. Предположим, что С = (1, ры р2, рз). В таком случае получим таблицу. (Здесь Хг — количество циклов, Ф2 — количество инвариантных раскрасок.) Тогда 1 24 — у ~о(<г) = — = 6, оеС и, как и ранее, получаем шесть различных раскрасок. Опять, если присвоить каждому циклу значение 2 в выражении 1 Рс (сы сз, сз, с4) = — (сг + сз + 2с4), 4 2 то получим (24 + 22 + 2 2) и снова получаем шесть различных раскрасок.
Рассмотрим общий случай, когда группа перестановок С содержит ~С~ элементов раскрашивание проводится с помощью т красок, и сумма циклов равна а1с1' + азс2' + азс" ,+ .. + а„с'„". Цикловой индекс в этом случае равен 1 Рс(сысз,сз,...,с„) = — (а,с" ,+азс",+азс1'+. +а„с'„"), а количество различных раскрасок равно Рс(т,гп,т,...,т), Теперь перейдем от подсчета структур к рассмотрению структуры раскрасок, сохраняющихся при конкретных перестановках.
Опять начнем с двухцветной раскраски квадрата. Рассмотрим цикловую стркутуру сзс2 перестановки Ю, = (13)(2)(4). Сначала посмотрим на элемент структуры сз, который представляет два цикла длины 1. Для двух циклов имеется четыре способа выбора цветов, при которых раскраска не будет меняться: вершины в обоих циклах могут быть окрашены только в красный или только в синий цвет, вершины в одном цикле могут быть окрашены в 784 ГЛЯВА 19. Перечисление пестов Перечень инвариантных раскрасок Перестановка Цикловая структура сгсг г (т + 6)г(тг + Ьг) 61 = (13)(2)(4) (т,'- 6)г(тг -,- Ьг) (тг + Ьг)г с,сг г бг = (1)(3)(24) фг = (14)(23) сг г (тг + Ьг)г сг г = (12)(34) (,.4 + 64) (т' + Ьг)г рг = (1234) р = (13)(24) с4 сг г (т4 + Ь4) рз = (1432) с4 1 (т + 6)4 1 = (1)(2)(3)(4) 8т4 + 8тз6 + 16т'Ь' + 8тЬ' + 864 с4 + 2сг~сг + Зсг г+ 2с4 Всего Последняя строка в столбце перечней раскрасок получается, если раскрыть скобки в выражениях для всех перечней и результаты сложить.
Ранее было показано, что для раскраски С количество перестановок в С, обозначенное )С~, равно )Сс( ~Е), где (Е~ — количество раскрасок в классе эквивалентности Е, содержащем С, и ~Сс~ — количество перестановок, которые не красный, а в другом — в синий, и наоборот. Очевидно, существует только один способ раскраски вершин в обоих циклах красным и один способ раскрасить их в обоих циклах синим.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
