Лекции по прикладной алгебре. v2.0 (1127112), страница 20
Текст из файла (страница 20)
. .i,T ype(t2 ) = h0, 4, 0, . . .i;◦ : T ype(f ) = h0, 4, 0, . . .i;M: T ype(r) = T ype(r2 ) = h2, 0, 2, 0, . . .i.Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задач273 / 432Цикловой индексСуществуетуниверсальныйспособ вычисления числа1 P Fix (g) = C(G) классов эквивалентности (орбит).|G|g∈GСопоставим каждой перестановке g ∈ G вес w(g) по правилу:T ype(g) = hν1 , . . . , νN i ⇒ w(g) = xν11 · . . . · xνNN .|{z}мономПрикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задач273 / 432Цикловой индексСуществуетуниверсальныйспособ вычисления числа1 P Fix (g) = C(G) классов эквивалентности (орбит).|G|g∈GСопоставим каждой перестановке g ∈ G вес w(g) по правилу:T ype(g) = hν1 , . .
. , νN i ⇒ w(g) = xν11 · . . . · xνNN .|{z}мономОпределениеСредний вес подстановок в группе называетсяцикловым индексом действия G : T :α1 X1 X ν1w(g) =x1 · . . . · xNνN .P (G : T, x1 , . . . , xN ) =α|G||G|g∈Gg∈GПрикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задач273 / 432Цикловой индексСуществуетуниверсальныйспособ вычисления числа1 P Fix (g) = C(G) классов эквивалентности (орбит).|G|g∈GСопоставим каждой перестановке g ∈ G вес w(g) по правилу:T ype(g) = hν1 , . .
. , νN i ⇒ w(g) = xν11 · . . . · xνNN .|{z}мономОпределениеСредний вес подстановок в группе называетсяцикловым индексом действия G : T :α1 X1 X ν1w(g) =x1 · . . . · xNνN .P (G : T, x1 , . . . , xN ) =α|G||G|g∈Gg∈GДля продвинутых: это производящий полином.Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задачЦикловой индекс: обозначения и свойстаДругие обозначения: PG (x1 , . . . , xN ) и PG , P (G).G∼= G 0 ⇒ PG = PG 0 — да, если действия определеныодинаково (согласовано)PG = PG 0 6⇒G∼=G0— нет, есть контрпример274 / 432Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задачЦикловой индекс: обозначения и свойстаДругие обозначения: PG (x1 , .
. . , xN ) и PG , P (G).G∼= G 0 ⇒ PG = PG 0 — да, если действия определеныодинаково (согласовано)PG = PG 0 6⇒G∼=G0— нет, есть контрпримерКак применять лемму «не-Бёрнсайда?»Для применения универсального способа вычисления C(G)надо представить эквивалентные элементы множества какклассы эквивалентности действия некоторой группы на этоммножестве.274 / 432Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задачЧисло неэквивалентных раскрасокПусть задано действиеG α: TгруппыG на множестве T .275 / 432Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задачЧисло неэквивалентных раскрасокПусть задано действиеG α: TгруппыG на множестве T .Припишем каждому элементу T одно из r значений(неформально: покрасим в один из r цветов).
Всегоимеется rN раскрасок.275 / 432Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задач275 / 432Число неэквивалентных раскрасокПусть задано действиеG α: TгруппыG на множестве T .Припишем каждому элементу T одно из r значений(неформально: покрасим в один из r цветов). Всегоимеется rN раскрасок.Не будем различать раскраски, если при преобразованииg : t → t0 элемент сохраняет цвет (t раскрашен также какt0 , и каждый g-цикл раскрашен одним своим цветом).••◦••••••Рис. 3. Поворот на 90 (такая перестановка) не даёт новогораскрашивания вершин квадратаПрикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задач275 / 432Число неэквивалентных раскрасокПусть задано действиеG α: TгруппыG на множестве T .Припишем каждому элементу T одно из r значений(неформально: покрасим в один из r цветов).
Всегоимеется rN раскрасок.Не будем различать раскраски, если при преобразованииg : t → t0 элемент сохраняет цвет (t раскрашен также какt0 , и каждый g-цикл раскрашен одним своим цветом).••••••••◦Рис. 3. Поворот на 90 (такая перестановка) не даёт новогораскрашивания вершин квадратаВопрос: Сколько существует неэквивалентных раскрасок —классов эквивалентности C(G)?Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задачВычисление C(G) через цикловой индексКаждый класс эквивалентности это g-цикл; ихC(g) = ν1 + . . .
+ νN штук.Каждая перестановка g ∈ G с типом h ν1 , . . . , νN i будетиметь rC(g) неподвижных точек.276 / 432Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задач276 / 432Вычисление C(G) через цикловой индексКаждый класс эквивалентности это g-цикл; ихC(g) = ν1 + . . . + νN штук.Каждая перестановка g ∈ G с типом h ν1 , . . . , νN i будетиметь rC(g) неподвижных точек.Следовательно, по лемме Бёрсайда, число полученных классовэквивалентности, т.е.
неэквивалентных раскрасок(приписываний) естьТеоремаC(G : T ) = P (G : T, x1 , . . . , xN )ααx1 =...=xN =r= PG (r, . . . , r).Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задач276 / 432Вычисление C(G) через цикловой индексКаждый класс эквивалентности это g-цикл; ихC(g) = ν1 + .
. . + νN штук.Каждая перестановка g ∈ G с типом h ν1 , . . . , νN i будетиметь rC(g) неподвижных точек.Следовательно, по лемме Бёрсайда, число полученных классовэквивалентности, т.е. неэквивалентных раскрасок(приписываний) естьТеоремаC(G : T ) = P (G : T, x1 , . . . , xN )ααx1 =...=xN =r= PG (r, .
. . , r).Например, PG (1, . . . , 1) = 1: если все элементы покрасить водин цвет, то таких раскрасок одна.Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задачЗадача (про слова)Составляются слова длины l > 2 из алфавитаA = { a1 , . . . , am }. Слова считаются эквивалентными, еслиони получаются одно из другого перестановкой крайних букв.Определить число S неэквивалентных слов.277 / 432Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задачЗадача (про слова)Составляются слова длины l > 2 из алфавитаA = { a1 , . .
. , am }. Слова считаются эквивалентными, еслиони получаются одно из другого перестановкой крайних букв.Определить число S неэквивалентных слов.Было решение: S =ml +ml−1.2277 / 432Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задач277 / 432Задача (про слова)Составляются слова длины l > 2 из алфавитаA = { a1 , . . . , am }.
Слова считаются эквивалентными, еслиони получаются одно из другого перестановкой крайних букв.Определить число S неэквивалентных слов.Было решение: S =ml +ml−1.2l−2z }| {Другое решение: G = { e, g } ∼= Z2 ; T : . . . .|{z}lПрикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задач277 / 432Задача (про слова)Составляются слова длины l > 2 из алфавитаA = { a1 , . . . , am }. Слова считаются эквивалентными, еслиони получаются одно из другого перестановкой крайних букв.Определить число S неэквивалентных слов.Было решение: S =ml +ml−1.2l−2z }| {Другое решение: G = { e, g } ∼= Z2 ; T : .
. . .|{z}lЭлемент группы gegT ype(g)h l, 0, . . . , 0 ih l − 2, 1, 0, . . . , 0 iЦикловой индекс:P (x1 , . . . , xl ) =P (x1 , . . . , xl )x1 =...=x =m = S.lw(g)xl11xl−21 x2xl1 +x1l−2 x12.2#мономов11Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задачКлассическая комбинаторная задача об ожерельяхОжерелье — окружность, на которой на равных расстояниях подуге располагаются «бусины» (бусины располагаются ввершинах правильного многоугольника).278 / 432Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задачКлассическая комбинаторная задача об ожерельяхОжерелье — окружность, на которой на равных расстояниях подуге располагаются «бусины» (бусины располагаются ввершинах правильного многоугольника).Задача (об ожерельях)Сколько различных ожерелий можно составить из N бусин rцветов?278 / 432Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задачКлассическая комбинаторная задача об ожерельяхОжерелье — окружность, на которой на равных расстояниях подуге располагаются «бусины» (бусины располагаются ввершинах правильного многоугольника).Задача (об ожерельях)Сколько различных ожерелий можно составить из N бусин rцветов?Варианты.
Ожерелья равны iff одно получаетсяиз другого (симметрия в плоскости или в пространстве):12поворотом (бусины плоские,окрашены с одной стороны);поворотом и осевой симметрией(бусины круглые);278 / 432Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задачЗадача об ожерельях: N = 5, r = 3ЗадачаСколько разных ожерелий можно составить из 5 бусин 3 цветов?279 / 432Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задач279 / 432Задача об ожерельях: N = 5, r = 3ЗадачаСколько разных ожерелий можно составить из 5 бусин 3 цветов?T — вершины правильного пятиугольника. #Col(3) =?1Ожерелья одинаковы, если одно получается из другого поворотом.Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задач279 / 432Задача об ожерельях: N = 5, r = 3ЗадачаСколько разных ожерелий можно составить из 5 бусин 3 цветов?T — вершины правильного пятиугольника.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
