Лекции по прикладной алгебре. v2.0 (1127112), страница 19
Текст из файла (страница 19)
. , νN или ν1 (g), ν2 (g), . . . , νN (g).Их упорядоченную совокупность, записанную какT ype(g) = h ν1 , ν2 , . . . , νN iилиh 1 ν1 , 2 ν2 , . . . , N νN iназывают типом перестановки g.NNPPПонятно, что C(g) =νk (g) иk · νk (g) = N .k=1k=1Прикладная алгебраТеория перечисления ПойаДействие группы на множествеПримерПустьT = { 1, . .
. , 10 },1 2 3 4 5 6 7 8 9 10g ==9 6 1 8 5 2 7 10 3 4= (1, 9, 3)(2, 6)(4, 8, 10)(5)(7)ТогдаT ype(g) = h 12 , 21 , 32 , 40 , . . . , 100 i = h 2, 1, 2, 0, . . . , 0 iи C(g) = 5.256 / 432Прикладная алгебраТеория перечисления ПойаДействие группы на множествеПо всей группе257 / 432G:Отношение эквивалентности ∼G на T —deft ∼G t 0 = ∃ g g(t) = t0 .GКлассы этой эквивалентности называют орбитами.Прикладная алгебраТеория перечисления ПойаДействие группы на множествеПо всей группе257 / 432G:Отношение эквивалентности ∼G на T —deft ∼G t 0 = ∃ g g(t) = t0 .GКлассы этой эквивалентности называют орбитами.Число орбит (классов эквивалентности) — C(G).Прикладная алгебраТеория перечисления ПойаДействие группы на множествеПо всей группе257 / 432G:Отношение эквивалентности ∼G на T —deft ∼G t 0 = ∃ g g(t) = t0 .GКлассы этой эквивалентности называют орбитами.Число орбит (классов эквивалентности) — C(G).Если C(G) = 1 (любой элемент T может быть переведён влюбой), то действие G : T называют транзитивным.αКласс эквивалентности, в которую попадает элемент t будемобозначать Orb (t).Прикладная алгебраТеория перечисления ПойаДействие группы на множестве258 / 432Неподвижные точки группы преобразованийG: g(t)= tПри выполнении этого равенства можно фиксировать t или g.1Фиксируем g, т.е.
находим все элементы множества T ,которые перестановка g оставляет на месте (фиксатор):def{ t ∈ T | g(t) = t } = Fix (g) ⊆ T .Прикладная алгебраТеория перечисления ПойаДействие группы на множестве258 / 432Неподвижные точки группы преобразованийG: g(t)= tПри выполнении этого равенства можно фиксировать t или g.1Фиксируем g, т.е. находим все элементы множества T ,которые перестановка g оставляет на месте (фиксатор):def{ t ∈ T | g(t) = t } = Fix (g) ⊆ T .2Фиксируем t, т.е. находим все перестановки g, которыеоставляют данный элемент неподвижным (стабилизатор):def{ g ∈ G | g(t) = t } = Stab (t) ⊆ G.Прикладная алгебраТеория перечисления ПойаДействие группы на множестве258 / 432Неподвижные точки группы преобразованийG: g(t)= tПри выполнении этого равенства можно фиксировать t или g.1Фиксируем g, т.е. находим все элементы множества T ,которые перестановка g оставляет на месте (фиксатор):def{ t ∈ T | g(t) = t } = Fix (g) ⊆ T .2Фиксируем t, т.е. находим все перестановки g, которыеоставляют данный элемент неподвижным (стабилизатор):def{ g ∈ G | g(t) = t } = Stab (t) ⊆ G.Справедливы равенстваC(G) =1 X 1 X Fix (g) = Stab (t) ;|G||G|g∈Gt∈TПрикладная алгебраТеория перечисления ПойаДействие группы на множестве258 / 432Неподвижные точки группы преобразованийG: g(t)= tПри выполнении этого равенства можно фиксировать t или g.1Фиксируем g, т.е.
находим все элементы множества T ,которые перестановка g оставляет на месте (фиксатор):def{ t ∈ T | g(t) = t } = Fix (g) ⊆ T .2Фиксируем t, т.е. находим все перестановки g, которыеоставляют данный элемент неподвижным (стабилизатор):def{ g ∈ G | g(t) = t } = Stab (t) ⊆ G.Справедливы равенстваC(G) =1 X 1 X Fix (g) = Stab (t) ;|G||G|g∈Gt∈Tпервое называется леммой Бёрнсайда (W.Burnside, 1911).Прикладная алгебраТеория перечисления ПойаДействие группы на множестве259 / 432Стабилизатор есть подгруппа12Fix (g) — фиксатор перестановки g;Stab (t) — стабилизатор элемента t.ЛеммаStab (t) 6G.Прикладная алгебраТеория перечисления ПойаДействие группы на множестве259 / 432Стабилизатор есть подгруппа12Fix (g) — фиксатор перестановки g;Stab (t) — стабилизатор элемента t.ЛеммаStab (t) 6G.ДоказательствоЗафиксируем t ∈ T и рассмотрим g, h ∈ Stab (t).
Тогдаg(t) = h(t) = t и h−1 (t) = t. Следовательно,(g ◦ h−1 ) ∗ t = t ⇒ g ◦ h−1 ∈ Stab (t) .Прикладная алгебраТеория перечисления ПойаДействие группы на множестве259 / 432Стабилизатор есть подгруппа12Fix (g) — фиксатор перестановки g;Stab (t) — стабилизатор элемента t.ЛеммаStab (t) 6G.ДоказательствоЗафиксируем t ∈ T и рассмотрим g, h ∈ Stab (t). Тогдаg(t) = h(t) = t и h−1 (t) = t. Следовательно,(g ◦ h−1 ) ∗ t = t ⇒ g ◦ h−1 ∈ Stab (t) .| Stab (t)| > 1, поскольку всегда e ∈ Stab (t).Прикладная алгебраТеория перечисления ПойаДействие группы на множестве260 / 432СтабилизаторЛеммаДлина орбиты Orb (t) равна индексу Stab (t) в группеG, т.е.| Orb (t)| = |G| : | Stab (t)|.ПримерO — группа вращений куба (группа октаэдра) и t — некотораяего вершина.
Найти Stab (t).Прикладная алгебраТеория перечисления ПойаДействие группы на множестве260 / 432СтабилизаторЛеммаДлина орбиты Orb (t) равна индексу Stab (t) в группеG, т.е.| Orb (t)| = |G| : | Stab (t)|.ПримерO — группа вращений куба (группа октаэдра) и t — некотораяего вершина. Найти Stab (t).Решение: Stab (t) ∼= Z3 — группа вращений на 120◦ вокругдиагонали куба, проходящей через данную вершину.Прикладная алгебраТеория перечисления ПойаДействие группы на множестве260 / 432СтабилизаторЛеммаДлина орбиты Orb (t) равна индексу Stab (t) в группеG, т.е.| Orb (t)| = |G| : | Stab (t)|.ПримерO — группа вращений куба (группа октаэдра) и t — некотораяего вершина.
Найти Stab (t).Решение: Stab (t) ∼= Z3 — группа вращений на 120◦ вокругдиагонали куба, проходящей через данную вершину.УтверждениеЧисло элементов в группе вращения правильногомногогранника есть |V | · |E0 |, где |V | — число вершин, а|E0 | — число рёбер, выходящих из одной вершины.Прикладная алгебраТеория перечисления ПойаДействие группы на множествеЭто тетраэдр261 / 432А это — кубикОктаэдр двойственен кубуПрикладная алгебраТеория перечисления ПойаДействие группы на множестве262 / 432Платоновы тела — правильные 3-х мерные многогранникиПлатоновы телатетраэдркуб и октаэдрикосаэдр и додекаэдрОктаэдрГруппа симметрииTOYИкосаэдрПорядок группы4 · 3 = 128 · 3 = 2412 · 5 = 60ДодекаэдрПрикладная алгебраТеория перечисления ПойаДействие группы на множестве263 / 432ПримерДействие группы V4 на множестве T =◦eab abg ∗ t t1eeab abet1aae ab bat2bb ab eabt3ab ab baeabt4{ t1 ,t2t2t1t4t3...,t3t3t4t1t2t6 }t4t4t3t2t1t5t5t6t5t6t6t6t5t6t5Прикладная алгебраТеория перечисления ПойаДействие группы на множестве264 / 432T ype(e) = h 6, 0, 0, 0, 0, 0 i ,T ype(a) = h 0, 3, 0, 0, 0, 0 i ,T ype(b) = h 2, 2, 0, 0, 0, 0 i ,T ype(ab) = h 0, 3, 0, 0, 0, 0 i .C(e) = 6 , C(a) = C(ab) = 3 , C(b) = 4 .Stab (t1 ) = Stab (t2 ) = Stab (t3 ) = Stab (t4 ) = e 6 V4 ,Stab (t5 ) = Stab (t6 ) = h e, b i 6 V4 .Fix (a) = Fix (ab) = ∅ , Fix (b) = { t5 , t6 } , Fix (e) = T .44= 4 , | Orb (t5 )| == 2.| Orb (t1 )| =121X6+2| Fix (g)| == 2,44g∈G1X4t∈T| Stab (t)| =4·1+2·2= 2.4Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задачРаздел I1Конечные поля или поля ГалуаПоля вычетов по модулю простого числаВычисление элементов в конечных поляхЛинейная алгебра над конечным полемКорни многочленов над конечным полемСуществование и единственность поля Галуа из pnэлементовЦиклические подпространстваЗадачиЧто надо знать2Коды, исправляющие ошибкиПонятие помехоустойчивого кодирования.
Коды ХэммингаГрупповые (линейные) коды265 / 432Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задачРаздел IIЦиклические кодыКоды БЧХЗадачиЧто надо знать3Теория перечисления ПойаДействие группы на множествеПрименение леммы Бёрнсайда для решениякомбинаторных задачПрименение теоремы Пойа для решения комбинаторныхзадачЗадачиЧто надо знать4Некоторые вопросы теории частично упорядоченныхмножеств266 / 432Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задачРаздел IIIОсновные понятия теории ч.у. множествОперации над ч.у.
множествамиЛинеаризацияЧто надо знать5Алгебраические решёткиРешётки: определение, основные свойстваМодулярные и дистрибутивные решёткиПрименение теории решёток к задаче классификацииЧто надо знать267 / 432Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задачПростая задачаЗадача (про слова)Составляются слова длины l > 2 из алфавитаA = { a1 , .
. . , am }. Слова считаются эквивалентными, еслиони получаются одно из другого перестановкой крайних букв.Определить число S неэквивалентных слов.268 / 432Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задачПростая задачаЗадача (про слова)Составляются слова длины l > 2 из алфавитаA = { a1 , . .
. , am }. Слова считаются эквивалентными, еслиони получаются одно из другого перестановкой крайних букв.Определить число S неэквивалентных слов.РешениеT — множество слов длины l в алфавите A, N = |T | = ml .Надо представить эквивалентности как орбиты некоторогодействия подходящей группы G на T .Очевидно, g 2 = e и поэтому подходит G ∼= Z2 = { e, g }.Действие: g переставляет в слове крайние буквы.268 / 432Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задачПродолжение 1Число S неэквивалентных слов есть число классовэквивалентности C(G) действия Z2 : T —α|Fix (e)| = |T | = ml ,|Fix (g)| = ml−2 · m = ml−1 .1Xml + ml−1ml−1 (m + 1)S = C(Z2 ) =|Fix (g)| ==.222g∈GДля l = 3, m = 2 ⇒ S =4·32= 6 (из всего 8)269 / 432Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задачПродолжение 1Число S неэквивалентных слов есть число классовэквивалентности C(G) действия Z2 : T —α|Fix (e)| = |T | = ml ,|Fix (g)| = ml−2 · m = ml−1 .1Xml + ml−1ml−1 (m + 1)S = C(Z2 ) =|Fix (g)| ==.222g∈GДля l = 3, m = 2 ⇒ S = 4·32 = 6 (из всего 8)Пусть A = {a, b}.
Показаны слова и классы.aaaaababaabbbaababbbabbb269 / 432Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задач270 / 432Стабилизаторы сопряжённых элементов группы совпадаютЗадачаПоказать, что если элементы g и h группы G сопряжены, тоStab (g) = Stab (h).Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задач270 / 432Стабилизаторы сопряжённых элементов группы совпадаютЗадачаПоказать, что если элементы g и h группы G сопряжены, тоStab (g) = Stab (h).Решениеgf = f h ⇒ Stab (gf ) = Stab (g) ∩ Stab (f ) = Stab (f h) == Stab (f ) ∩ Stab (h) ⇒ Stab (g) = Stab (h).Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задачДействие группы O на вершины кубаЗадачаГруппа вращений куба действует на множество его вершин.Определить типы всех перестановок этой группы.271 / 432Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задачДействие группы O на вершины кубаЗадачаГруппа вращений куба действует на множество его вершин.Определить типы всех перестановок этой группы.РешениеO = h t, f, r i , t4 = f 2 = r3 = e, гдеt — вращение на 90◦ вокруг оси,проходящей через середины двухпротивоположных граней (2—2);f — вращение на 180◦ вокруг оси,проходящей через середины двухпротивоположных рёбер (◦—◦);r — вращение на 120◦ вокруг оси,проходящей через две противоположныевершины (M—M).271 / 432Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задач272 / 432Действие группы O на вершины куба: продолжение решения2 : T ype(t) == T ype(t3 ) = h0, 0, 0, 2, 0, .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
