В.П. Воронин - Дополнительные главы дискретной математики (1127085), страница 11
Текст из файла (страница 11)
Внутри каждого класса эквивалентности веса элементов одинаковы иравны весу орбиты, но каждый такой элемент участвует в сумме |G| раз, так как (далее a — элемент из первой орбиты,b — из последней)∑ ∑nπ∈G a:a=π(a)ω (a) = ∑∑i=1 π:π(i)=inni=1i=1ω (i) = ∑ ω (i) ] {π ∈ G : π (i) = i} = ∑ ω (i) |Gi | =ω (1) + · · · + ω (1) + ω (2) + · · · + ω (2) + · · · + ω (n) + · · · + ω (n) ={z} |{z}|{z}||G1 ||G2 ||Gn |N(G)W O 1 + · · · +W O 1 + · · · +W O N(G) + · · · +W O N(G) = |G| ∑ W O j{z}|j=1|{z}∑ |Gi |=|O 1 ||Ga |=|G|N(G) ||G |=|G||G|=O∑|ibi∈O 1i∈O N(G)N(G)=⇒∑Wj=11Oj =∑ ∑ ω (a) ,|G| π∈Ga=π(a)что и требовалось доказать.Лемма 1.3.3 (Бернсайд, ограниченная форма).
Пусть N 0 — некоторое подмножество множества N. Еслиопределить эквивалентность в ограниченной форме:a ∼0 b (mod G) ⇐⇒ a ∼ b (mod G) & a, b ∈ N 0 ,то число орбит по группе G на множестве N 0 равно1N G| N 0 =λ1 π | N 0 ,∑|G| π∈Gгде λ1 π | N 0 — число петель перестановки π на множестве N 0 . Док-во. Аналогично основной лемме 1.3.1 с тем лишь отличием, что рассуждения проводятся для части орбит.Теорема Пойа.
Обозначим N = {1, . . . , n} — множество вершин, M = {1, . . . , m} — множество красок. Функции видаf : N → M будем называть раскрасками множества N в цвета из M. Их множество — map (N, M) с числом элементов] map (N, M) = mn . Для некоторой подгруппы G ⊆ Sn будем называть раскраски f и g эквивалентными и обозначатьf ∼ g (mod G) ⇐⇒ ∃ π ∈ G : ∀x ∈ N ⇒ f (π (x)) = g (x) .Определение 1.3.4. Цикловым индексом группы перестановок G будем называть многочленZ (G; x1 , . .
. , xn ) =1λ (π) λ (π)λ (π)∑ x11 x22 · · · xnn ,|G| π∈Gгде λ (π) = (λ1 (π) , λ2 (π) , . . . , λn (π)) — тип перестановки π.В примере 5 рассмотрено значение Z (G; k, . . . , k) циклового индекса групп вращений и вращений с отражениями дляпростого p. В общем виде они выглядят для простых p следующим образом:1 px1 + (p − 1) x p ,pp−11p2Z (G; x1 , . . .
, x p ) =x + (p − 1) x p + px1 x2,p 1Z (G; x1 , . . . , x p ) =для группы вращений;для группы вращений с отражениями.Установим изоморфизм между элементами π ∈ G и перестановками Smn . Определим для начала раскраске f и перестановке π функцию f π по следующему правилу: ∀ j = π (i) ⇒ f π ( j) = f (i). Легко убедиться, что такое соответствиеинъективно: действительно, еслиf1 → f1π , f2 → f2πиf1π ( j) = f2π ( j) ∀ j = 1, n =⇒ f1 (i) = f2 (i) ∀ i = π −1 ( j) .Так поставим в соответствие группе G некоторое множество раскрасок { f π }.
При этом перестановке π ставится вb Легко видеть, что это соответствие изоморфно (поэтомусоответствие некоторая другая перестановка раскрасок πb ∈ G.38ГЛАВА 1. КОМБИНАТОРИКА−1 , eb симметрической группы Smn ), так как (πb)−1 = πdb аb — единичный элемент в G,можно говорить о подгруппе Gπ\2 · π1 = πb2 · πb1 . Осталось показать, что это соответствие взаимно однозначно: пусть G 3 π1 6= π2 ∈ G, а π1 , π2 порождаютсоответственно πb1 , πb2 . Тогда ∃ i : j = π1 (i) 6= π2 (i) = k. Рассмотрим раскраску, окрашивающую i-ый элемент в первыйцвет, а все остальные во второй. Тогда πb1 окрасит все элементы, кроме j-го в первый цвет, а j-ый элемент во второй,а πb2 все элементы, кроме k-го окрасит в первый цвет, а k-ый элемент во второй.
Следовательно, πb1 , πb2 — разныеb установлен изоморфизм.перестановки раскрасок. Таким образом, можно окончательно утверждать, что между G и GТеорема 1.8 (Пойа, упрощенный вид). Число орбит раскрасок по группе G (подгруппе Sn ) равно значениюциклового индекса Z (G; m, m, · · · , m). Док-во. Заметим предварительно, что в силу изоморфизмаf1 ∼ f2b ⇐⇒ f1 ∼ f2(mod G)(mod G).bПусть F = {F1 , . . . , Ft } — множество орбит. Тогда по лемме Бернсайда 1.3.1 и в силу изоморфизма групп G и G11t = ∑ ∑ 1 =∑ mλ1 (π) mλ2 (π) · · · mλn (π) = Z (G; m, m, .
. . , m) .|G|bπ∈GG πb∈Gb f =bπ ( f )Последнее равенство вытекает из того, что петля в перестановке группы G при изоморфно переходит в окрашиваниеbвсех циклов в один цвет раскраской группы GПусть W = {w1 , . . . , wr } — множество цветов. Введем все окрасок ω : M → K (W ), то есть ω (i) = wi . Весом раскраскибудем называть произведение весов ее цветов:ω ( f ) = ∏ ω ( f (i)) .i∈NОчевидно, что f1 ∼ f2 (mod G) ⇒ ω ( f1 ) = ω ( f2 ):ω ( f2 ) = ∏ ω ( f2 (i)) = ∏ ω ( f1 (π (i))) = ∏ ω ( f1 (i)) = ω ( f1 ) .i∈Ni∈Ni∈NПо аналогии с обычными группами перестановок, весом орбиты назовем вес любой ее раскраски: W (Fi ) = ω ( f ) ∀ f ∈ Fi .Теорема 1.9 (Пойа).∑F∈Fmmmi=1i=1i=1!W (F) = Z G; ∑ ω (i) , ∑ ω 2 (i) , .
. . , ∑ ω n (i) . Док-во. Пусть W = {W1 , . . . ,Wr } — множество всех возможных весов раскрасок (весов орбит), r 6 mn . Тогда∑F∈FrW (F) = ∑ Wii=1∑F∈FW (F)=Wir11 = ∑ Wi · ∑b πb∈Gbi=1G∑1F∈FW (F)=Wiλ1= ∑ (ω (1) + · · · + ω (m))λ1 ω 2 (1) + · · · + ω 2 (m) 2 · · · (ω n (1) + · · · + ω n (m))λnb π∈GGmmmi=1i=1i=1!= Z G; ∑ ω (i) , ∑ ω 2 (i) , . . . , ∑ ω n (i) .Последнее равенство вытекает из того, что петля в перестановке группы G при изоморфно переходит в окрашиваниеbвсех циклов в один цвет раскраской группы GВ дальнейшем под витражом будем понимать прозрачную прямоугольник, разлинованный квадратами, которыемогут быть окрашены в цвета.
При этом окраска квадрата с двух сторон одинаковая. По пластиной будем пониматьнепрозрачный (двусторонний) прямоугольник, разлинованный квадратами, которые могут быть окрашены в цвета собеих сторон независимо друг от друга.Примеры.1. Найти число орбит на множестве S = {a, b, c, d} по группеG = aa bb cc dd , ab ba cc dd ,ab c dabd c,ab c dbad c.391.3. ПРОСТЕЙШИЕ ПЕРЕЧИСЛИТЕЛЬНЫЕ ЗАДАЧИ Решение. Нетрудно проверить, что G — группа. Действительно, первый ее элемент является единицей, оставшиеся три являются сами себе обратными, композицией второго и третьего является четвертый, второго и четвертого — третий, третьего и четвертого — второй. Легко видеть, что орбитами здесь являются лишь два множества:{a, b} и {c, d}. Согласно лемме 1.3.1 число орбит равноN (G) =1(4 + 2 + 2 + 0) = 2.42.
Найти число орбит на множестве {a, b, c, d, e, f , g, h} по группе.nG = eb = aa bb cc dd ee ff gg hh , π = π −1 = ab ba dc Решение. По лемме 1.3.1, очевидно,N (G) =d e f ghc f e gho.1(8 + 4) = 623. Найти число различных вершинных раскрасок треугольников в два цвета (используется модель "ожерелья", тоесть орбиты определяются по группе вращений). Решение. Здесь легко представить себе все эти раскраски:12a345a67a8aAAAAAAAA A A Aa a A Aa a Aa a A a Aa(обведены вершины, раскрашенные в один цвет, отличный от цвета необведенных). Группа вращений в данномслучае содержит три перестановки: тождественную и вращения на углы 2pi/3 и 4π/3:G = eb = 11 22 33 44 55 66 77 88 = [1] [2] · · · [8] ,π = 11 23 34 42 56 67 75 88 = [234] [567] [1] [8] ,π −1 = π 2 = 11 24 32 43 57 65 76 88 = [423] [756] [1] [8] .Таким образом, по лемме 1.3.11(8 + 2 + 2) = 4.3Действительно, неэквивалентными раскрасками являются, например, раскраски 1, 2, 5, 8.N (G) =4.
Найти число различных вершинных раскрасок правильного пятиугольника в три цвета по группе вращений и погруппе вращений и симметрий. Док-во. Группа вращений в данном случае состоит из пяти перестановок: тождественной, которая оставляетвсе раскраски неподвижными, и поворотов на π · n/5, где n = 2, 4, 6, 8, которые оставляют неподвижными лишьодноцветные раскраски (потому что 5 — простое число). Тогда по лемме 1.3.1N (G) = 2551 53 +3+3+3+3 == 51.55Добавляя также симметрии, имеем еще пять перестановок, соответствующих каждой из пяти осей симметрии,каждая из которых сохраняет 33 раскрасок.1`#c##c#5#`LLLL`4cc` 2`340ГЛАВА 1. КОМБИНАТОРИКАДействительно, можно выбрать любой цвет для вершины, через которую проходит ось, а также два любых цветадля вершин, лежащих по одну сторону от оси.
В этом случаеN (G) = 3901 53 + 3 + 3 + 3 + 3 + 33 + 33 + 33 + 33 + 33 == 39.10105. Найти число различных вершинных раскрасок правильного p-угольника, где p — простое в k цветов, отождествляя раскраски, получающиеся друг из друга вращениями и вращениями с симметриями. Решение.
Группа вращений будет состоять из p перестановок, из которых одна (единичная) сохраняет все k pраскрасок, а остальные (p − 1 различных поворотов, совмещающих вершины) в силу простоты p сохраняют лишьодноцветные раскраски. Таким образом, число раскрасок по группе вращений равно для простого числа вершинN (G) =1 p(k + (p − 1) k) .pГруппа симметрий будет содержать p перестановок (для начал пусть p — нечетное), каждая из которых соответствует оси, проходящей через выделенную вершину (в силу простоты p все оси различны). Каждая симметриясохраняет раскраски, у которых выделенная вершина имеет произвольный цвет, а оставшиеся p−12 вершин, ле,лежащихподругуюсторонужащих по одну сторону от оси определяют однозначно раскраску оставшихся p−12оси, то есть в этом случаеp+11 pk + (p − 1) k + p · k 2 .N (G) =2pВ случае четного простого p = 2 симметрий наблюдаться не будет, поэтомуN (G) =1 k (k + 1)=,22также, как и по группе вращений.6.
Найти число различных вершинных раскрасок правильного шестиугольника в 2 цвета, отождествляя раскраски,получающиеся друг из друга сначала только вращениями, а затем вращениями с симметриями. Решение. Группа вращений будет содержать 6 перестановок, где единичная сохраняет все 26 раскрасок, повороты на π/3 и 5π/3 сохраняют только одноцветные раскраски (так как 1 и 5 взаимно просты с числом вершин 6),повороты на 2π/3 и 4π/3 сохраняет четыре раскраски (четные вершины раскрашены в один цвет, а нечетные —в другой), поворот на π сохраняет восемь раскрасок (противоположные вершины окрашены в один цвет).
Такимобразом, в случае группы вращенийN (G) = 841 62 + 2 · 2 + 2 · 22 + 23 == 14.66Группа симметрий содержит шесть перестановок (3 оси, проходящие через две противоположные вершины и 3оси через середины противоположных ребер). Симметрии, соответствующие осям, проходящим через вершины,сохраняют 24 раскрасок (две вершины на оси и две вершины по одну сторону оси произвольны), а симметрии, соответствующие осям, проходящим через середины ребер, сохраняют 23 раскрасок (три вершины по одну сторонуоси определяют однозначно остальные).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
