AA3-3(PET) (1127141)
Текст из файла
ПРИКЛАДНАЯ АЛГЕБРА. Часть III: Теория перечисления ПойаТема IIIТеория перечисления Пойа1 / 70ПРИКЛАДНАЯ АЛГЕБРА. Часть III: Теория перечисления ПойаДействие группы на множествеРазделыДействие группы на множествеПрименение леммы Бёрнсайда для решениякомбинаторных задачПрименение теоремы Пойа для решения комбинаторныхзадачЗадачи с решениямиЧто надо знать2 / 70ПРИКЛАДНАЯ АЛГЕБРА. Часть III: Теория перечисления ПойаДействие группы на множествеДействие группы на множестве: два определенияГруппа G = h G, ◦, e i, |G| = n.Множество T , |T | = N .Bij(T ) — множество всех биекций (перестановок)элементов T .Symm(T ) — симметрическая группа множества T :Symm(T ) = h Bij(T ), ∗, 1T i ,Определение (I)α ∈ Hom ( G, Symm(T ) ).Действие α группы G на множестве T : символически —G : T.α3 / 70ПРИКЛАДНАЯ АЛГЕБРА.
Часть III: Теория перечисления ПойаДействие группы на множествеДействие группы на множестве: два определения...Определение (II)α = h G, T ; ◦, ?, e i ,где◦G × G → G — групповая операция;?G × T → T — новая операция.Аксиомы для операций:e ? t = t;(g ◦ h) ? t = h ∗ (g ? t).Запись операции ?: g(t) = t 0 .Аксиомы: e(t) = t и (g ◦ h)(t) = h(g(t)).Т.е. элементы g группы G порождают перестановки на T ,обладающие вышеуказанными свойствами.4 / 70ПРИКЛАДНАЯ АЛГЕБРА. Часть III: Теория перечисления ПойаДействие группы на множествеДействие группы на множестве: схема5 / 70ПРИКЛАДНАЯ АЛГЕБРА. Часть III: Теория перечисления Пойа6 / 70Действие группы на множествеДля данной перестановки g:Введём отношение эквивалентности ∼g на T —deft ∼g t 0 = ∃ k g k (t) = t 0Смежные классы эквивалентности ∼g называютg-циклами.Число всех смежных классов обозначим C(g).Количества циклов длины 1, 2, .
. . , N обозначаютν1 , ν2 , . . . , νN или ν1 (g), ν2 (g), . . . , νN (g).Упорядоченную совокупность количеств цикловh ν1 , ν2 , . . . , νN i называют типом перестановки g иобозначают T ype(g).Понятно, что C(g) =NPk=1νk (g) иNPk=1k · νk (g) = N .ПРИКЛАДНАЯ АЛГЕБРА. Часть III: Теория перечисления Пойа7 / 70Действие группы на множествеТип перестановки: примерПустьT = { 1, . . . , 10 },g =1 2 3 4 5 6 7 8 9 109 6 1 8 5 2 7 10 3 4== (1, 9, 3)(2, 6)(4, 8, 10)(5)(7)ТогдаT ype(g) = h 2, 1, 2, 0, . .
. , 0 i,C(g) = 2 + 1 + 2 = 5,|T | = 2 · 1 + 1 · 2 + 2 · 3 = 10.ПРИКЛАДНАЯ АЛГЕБРА. Часть III: Теория перечисления Пойа8 / 70Действие группы на множествеПлатоновы тела — правильные 3-х мерные многогранникиЭто тетраэдрА это — кубикОктаэдр двойственен кубуПРИКЛАДНАЯ АЛГЕБРА. Часть III: Теория перечисления Пойа9 / 70Действие группы на множествеПлатоновы тела — правильные 3-х мерные многогранникиПлатоновы телатетраэдркуб и октаэдрикосаэдр и додекаэдрОктаэдрГруппа вращенияT (тетраэдра)O (октаэдра)Y (икосаэдра)ИкосаэдрПорядок группы4 · 3 = 128 · 3 = 2412 · 5 = 60ДодекаэдрПРИКЛАДНАЯ АЛГЕБРА. Часть III: Теория перечисления Пойа10 / 70Действие группы на множествеT — группа вращения тетраэдраT = h t, f i, t3 = f 2 = e, где:t — вращение на 120◦ вокруг оси,проходящей через вершинуи центр тетраэдра (M—M);таких осей 4.f — вращение на 180◦ вокруг оси,проходящей через центры двухпротивоположных рёбер (—);таких осей 3.|T | = (3 − 1) · 4 + (2 − 1) · 3 + 1 = 12.Тетраэдр двойственен самому себе ⇒ действие на грани =действие на вершины.ПРИКЛАДНАЯ АЛГЕБРА.
Часть III: Теория перечисления Пойа11 / 70Действие группы на множествеДействие T на грани (или вершины) тетраэдра: типыперестановок2 : T ype(t) = T ype(t2 ) = h1, 0, 1, 0i;M: T ype(f ) = h0, 2, 0, 0i.|T | = 2 · 4 + 1 · 3 + 1 = 12.Тетраэдр двойственен самому себе ⇒действие на грани =действие на вершины.ПРИКЛАДНАЯ АЛГЕБРА. Часть III: Теория перечисления Пойа12 / 70Действие группы на множествеO — группа вращения кубаO = h t, f, r i , t4 = f 2 = r3 = e, гдеt — вращение на 90◦ вокруг оси,проходящей через середины двухпротивоположных граней (2—2),f — вращение на 180◦ вокруг оси,проходящей через середины двухпротивоположных рёбер (◦—◦),r — вращение на 120◦ вокруг оси,проходящей через две противоположныевершины (M—M)Сколько осей каждого типа? 3, 6 и 4 соответственно.|O| = 3 · 3 + 1 · 6 + 2 · 4 + 1 = 24.ПРИКЛАДНАЯ АЛГЕБРА.
Часть III: Теория перечисления ПойаДействие группы на множествеДействие O на вершины куба: типы перестановок2 : T ype(t) = T ype(t3 ) == h0, 0, 0, 2, 0, . . .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.13 / 70ПРИКЛАДНАЯ АЛГЕБРА. Часть III: Теория перечисления ПойаДействие группы на множествеПо всей группе G:Отношение эквивалентности ∼G на T —deft ∼G t 0 = ∃ g g(t) = t0 .GКлассы этой эквивалентности называют орбитами.Число орбит (классов эквивалентности) — C(G).Если C(G) = 1 (любой элемент T может быть переведён влюбой), то действие G : T называют транзитивным.αКласс эквивалентности, в которую попадает элемент t будемобозначать Orb (t).14 / 70ПРИКЛАДНАЯ АЛГЕБРА.
Часть III: Теория перечисления Пойа15 / 70Действие группы на множествеФиксатор и стабилизатор. Лемма БёрнсайдаБудем решать уравнение 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.Справедливы равенства1 X 1 X Fix(g)=Stab(t)C(G) =;|G||G|g∈Gпервое называется леммой Бёрнсайда.t∈TПРИКЛАДНАЯ АЛГЕБРА. Часть III: Теория перечисления Пойа16 / 70Действие группы на множествеУ.
БёрнсайдУильям Бёрнсайд(William Burnside, 1852–1927)— английский математик-алгебраист.«Написал первый трактат о группахна английском языке и был первым,кто разработал теорию групп ссовременной абстрактной точки зрения».Также знаменит формулированиемпроблемы Бёрнсайда (1902):Будет ли конечно порождённая группа, в которой каждыйэлемент имеет конечный порядок, обязательно конечной?ПРИКЛАДНАЯ АЛГЕБРА. Часть III: Теория перечисления ПойаДействие группы на множествеСтабилизатор есть подгруппа группы G12Fix (g) — фиксатор перестановки g элемента группы G;Stab (t) — стабилизатор элемента t множества T .ЛеммаStab (t) 6 G.ДоказательствоЗафиксируем 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).17 / 70ПРИКЛАДНАЯ АЛГЕБРА. Часть III: Теория перечисления ПойаДействие группы на множествеЭлемент множества: длина орбиты и стабилизаторЛеммаДлина орбиты Orb (t) равна индексу Stab (t) в группе G, т.е. Orb (t) = G : Stab (t).ПримерПусть V — множество вершин куба. Найти стабилизаторвершины куба при действии группы O на V .Решение: Stab (v) ∼= Z3 — группа вращений на 120◦ вокругдиагонали куба, проходящей через данную вершину.Утверждение (следствие леммы)Число элементов в группе вращения правильногоV · E0 , где V — число вершин, амногогранникаесть E0 — число рёбер, выходящих из одной вершины.18 / 70ПРИКЛАДНАЯ АЛГЕБРА.
Часть III: Теория перечисления Пойа19 / 70Действие группы на множествеДействие группы на множестве: примерДействие группы V4 на множестве T = { t1 , . . . , t6 }◦eababeeababaaeabbbbabeaababbaeg∗teababt1t1t2t3t4t2t2t1t4t3t3t3t4t1t2t4t4t3t2t1t5t5t6t5t6t6t6t5t6t5ПРИКЛАДНАЯ АЛГЕБРА. Часть III: Теория перечисления ПойаДействие группы на множествеДействие группы на множестве: пример...T 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 . Orb (t1 ) = 4 = 4 , Orb (t5 ) = 4 = 2 .121 X 6+2Fix (g) == 2,44g∈G1 X 4·1+2·2Stab (t) == 2.44t∈T20 / 70ПРИКЛАДНАЯ АЛГЕБРА.
Часть III: Теория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задачРазделыДействие группы на множествеПрименение леммы Бёрнсайда для решениякомбинаторных задачПрименение теоремы Пойа для решения комбинаторныхзадачЗадачи с решениямиЧто надо знать21 / 70ПРИКЛАДНАЯ АЛГЕБРА. Часть III: Теория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задачПример применения леммы БёрнсайдаЗадача (про слова). Составляются слова длины l > 2 изалфавита A = { a1 , .
. . , am }.Слова считаются эквивалентными, если они получаются одноиз другого перестановкой крайних букв. Определить число Sнеэквивалентных слов.Решение. T — множество слов длины l в алфавите A,N = |T | = ml .Надо представить эквивалентности как орбиты некоторогодействия подходящей группы G на T .Очевидно, g 2 = e и поэтому подходит G ∼= Z2 = { e, g }.Действие: g переставляет в слове крайние буквы.22 / 70ПРИКЛАДНАЯ АЛГЕБРА.
Часть III: Теория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задачПример применения леммы Бёрнсайда...Число S неэквивалентных слов есть число классовэквивалентности C(G) действия Z2 : T —α Fix (e) = T = ml , Fix (g) = ml−2 · m = ml−1 .ml + ml−1ml−1 (m + 1)1 X Fix (g) ==.S = C(Z2 ) =222g∈GДля l = 3, m = 2 ⇒ S = 4·32 = 6 (из всего 8)Пусть A = {a, b}. Показаны слова и классы.aaaaababaabbbaababbbabbb23 / 70ПРИКЛАДНАЯ АЛГЕБРА. Часть III: Теория перечисления Пойа24 / 70Применение леммы Бёрнсайда для решения комбинаторных задачЦикловой индексСуществуетуниверсальныйспособ вычисления числа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 ν1P (G : T, x1 , . . . , xN ) =w(g) =x1 · . . . · xNνN .α|G||G|g∈Gg∈GДля продвинутых: это производящий полином от многихпеременных.ПРИКЛАДНАЯ АЛГЕБРА. Часть III: Теория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задачЦикловой индекс: обозначения и свойстваДругие обозначения: PG (x1 , . .
. , xN ) и PG , P (G).G ∼= G 0 ⇒ PG = PG 0 — да, если действия определеныодинаково (согласовано)PG = PG 0 6⇒ G ∼= G 0 — нет, есть контрпримерКак применять лемму «не-Бёрнсайда?»Для применения универсального способа вычисления C(G)надо представить эквивалентные элементы множества какклассы эквивалентности действия некоторой группы на этоммножестве.25 / 70ПРИКЛАДНАЯ АЛГЕБРА. Часть III: Теория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задачЧисло неэквивалентных раскрасокПусть задано действие G : T группы G на множестве T .αПрипишем каждому элементу T одно из r значений(неформально: покрасим в один из r цветов).Всего, очевидно, имеется rN раскрасок.Не будем различать раскраски, если при преобразованииg : t → t0 элемент сохраняет цвет. Например, поворот на90◦ —••••••••не даёт нового раскрашивания вершин квадрата.Вопрос: Сколько существует неэквивалентных раскрасок =классов эквивалентности C(G)?26 / 70ПРИКЛАДНАЯ АЛГЕБРА.
Часть III: Теория перечисления Пойа27 / 70Применение леммы Бёрнсайда для решения комбинаторных задачВычисление 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, .
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
