AA3-3(PET) (1127141), страница 2
Текст из файла (страница 2)
. . , r).Например, PG (1, . . . , 1) = 1: если все элементы покрасить водин цвет, то таких раскрасок одна.ПРИКЛАДНАЯ АЛГЕБРА. Часть III: Теория перечисления Пойа28 / 70Применение леммы Бёрнсайда для решения комбинаторных задачЗадача (про слова)Составляются слова длины l > 2 из алфавита { a1 , . . . , am }.Слова считаются эквивалентными, если они получаются одноиз другого перестановкой крайних букв.Определить число S неэквивалентных слов.Было решение: S =ml +ml−1.2l−2z }| {Другое решение: G = { e, g } ∼= Z2 ; T : .
. . .|{z}lЭлемент группы gegT ype(g)w(g)#мономовh l, 0, . . . , 0 ixl11l−2 1h l − 2, 1, 0, . . . , 0 i x1 x21hi1 lЦикловой индекс: P (x1 , . . . , xl ) =x + x1l−2 x12 .2 1P (x1 , . . . , xl )x1 =...=x =m = S.lПРИКЛАДНАЯ АЛГЕБРА. Часть III: Теория перечисления Пойа29 / 70Применение леммы Бёрнсайда для решения комбинаторных задачКлассическая комбинаторная задача об ожерельяхОжерелье — окружность, на которой на равных расстояниях подуге располагаются «бусины» (бусины располагаются ввершинах правильного многоугольника).Задача (об ожерельях). Сколько различных ожерелий можносоставить из N бусин r цветов?Варианты. Ожерелья равны iff одно получаетсяиз другого (симметрия в плоскости или в пространстве):12поворотом (бусины плоские,окрашены с одной стороны);поворотом и осевой симметрией(бусины круглые).ПРИКЛАДНАЯ АЛГЕБРА.
Часть III: Теория перечисления Пойа30 / 70Применение леммы Бёрнсайда для решения комбинаторных задачЗадача об ожерельях: N = 5, r = 3Сколько разных ожерелий можно составить из 5 бусин 3цветов?T — вершины правильного пятиугольника. #Col(3) =?¶ Ожерелья одинаковы, если одно получается из другого поворотом.Решение. G ∼= Z5 = hti, t5 = e, n = 5.Элемент группы get, t2 , t3 , t4T ype(g)h 5, 0, 0, 0, 0 ih 0, 0, 0, 0, 1 iw(g)x51x5Цикловой индекс: P (x1 , x2 , x3 , x4 , x5 ) =#Col(3) = P (3, . .
. , 3) =35 +4·35=15# мономов14 5x1 + 4x5 .3·855= 3 · 17 = 51.ПРИКЛАДНАЯ АЛГЕБРА. Часть III: Теория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задачЗадача Олимпиады «Покори Воробьёвы горы – 2009»Для 50 детей детского сада закуплены 50 одинаковыхтарелок. По краю каждой тарелки равномерно расположено 5белых кружочков. Воспитатели хотят перекрасить какие-либоиз этих кружочков в другой цвет так, чтобы все тарелки сталиразличными. Какое наименьшее число дополнительных цветовпотребуется им для этого?31 / 70ПРИКЛАДНАЯ АЛГЕБРА.
Часть III: Теория перечисления Пойа32 / 70Применение леммы Бёрнсайда для решения комбинаторных задачКак должны были решать школьникиРешение.Пусть требуется r цветов.Отбросим r вариантов раскраски в один цвет.Число остальных вариантов без учёта возможности поворотатарелки — r5 − r;5с учётом поворота — r 5−r (каждый вариант повторятся 5 раз).Итого: #Col(r) =r5 − rr5 + 4r+r =;55При 2-х дополнительных цветах #Col(3) = 51.ПРИКЛАДНАЯ АЛГЕБРА.
Часть III: Теория перечисления Пойа33 / 70Применение леммы Бёрнсайда для решения комбинаторных задачЗадача об ожерельях: N = 5, r = 3, 2-й вариант· Ожерелья одинаковы, если одно получается из другогоповоротом или переворотом.G — группа диэдра:G∼= D5 = ht, f i, t5 = f 2 = e, n = |D5 | = 10.Элемент группы get, t2 , t3 , t4f, tf, . . . , t4 fВсего# мономов14510 5x1 + 4x5 + 5x1 x22 .T ype(g)h 5, 0, 0, 0, 0 ih 0, 0, 0, 0, 1 ih 1, 2, 0, 0, 0 iЦикловой индекс: P =110w(g)x51x5x1 x22#Col(3) = P (x1 , .
. . , x5 )|x1 =...=x5 =3 =Запомним этот ответ.35 +4·3+5·3310= 39.ПРИКЛАДНАЯ АЛГЕБРА. Часть III: Теория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задачЗадача о раскраске кубаЗадача (раскраска граней куба в два цвета).Грани куба раскрашивают в 2 и 3 цвета.Сколько существует различно окрашенных кубов?Решение. Напоминание: G = O = h t, f, r i, |O| = 24.t — вращение на 90◦ вокруг оси,проходящей через середины двухпротивоположных граней (2—2, 3 оси);f — вращение на 180◦ вокруг оси,проходящей через середины двухпротивоположных рёбер (◦—◦, 6 осей);r — вращение на 120◦ вокруг оси, проходящей через двепротивоположные вершины (M—M, 4 оси).34 / 70ПРИКЛАДНАЯ АЛГЕБРА. Часть III: Теория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задачЗадача о раскраске куба: обозначения элементовОбозначим через F множество граней куба; |F | = N = 6.Выберем некоторую грань куба (квадрат) и обозначим её ¬,а параллельную ей — .Перенумеруем последовательно вершины грани ¬ числами1, .
. . , 4, а вершины грани — числами 5, . . . , 8 так, чтовершина с номером i смежна с вершиной с номеромi + 4, i = 1, 2, 3, 4.Перестановки далее указаны для случая, когда ось вращенияhti проходит через середины граней ¬ и ,hf i проходит через середины рёбер ( 3-7 ) и ( 1-5 ),hsi проходит через вершины (1) и (7),а грани обозначены:(1-2-6-5) через ®, параллельная ей грань — °,грань (2-3-7-6) — через ¯, параллельная ей грань — ±.35 / 70ПРИКЛАДНАЯ АЛГЕБРА. Часть III: Теория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задачЗадача о раскраске куба: обозначения вершин и граней36 / 70ПРИКЛАДНАЯ АЛГЕБРА. Часть III: Теория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задачЗадача о раскраске куба: обозначения осей37 / 70ПРИКЛАДНАЯ АЛГЕБРА.
Часть III: Теория перечисления Пойа38 / 70Применение леммы Бёрнсайда для решения комбинаторных задачЗадача о раскраске куба...g∈Oet, t3t2fr, r2Всегоперестановка(¬). . . (±)(¬)()(®¯°±)(¬)()(®°)(¯±)(¬)(®±)(¯°)(¬®±)(¯°)T ype(g)h 6, 0, . . . ih 2, 0, 0, 1, 0, ih 2, 2, 0, . . . ih 0, 3, 0, . . . ih 0, 0, 2, 0, . . . iw(g)x61x21 x4x21 x22x32x23#w(g)13·2=6364·2=8241 6x1 + 6x21 x4 + 3x21 x22 + 6x32 + 8x23 .241 6#Col(2) = P (2, . . .
, 2) =2 + 12 · 23 + 3 · 24 + 8 · 22 = 10,241 6#Col(3) = P (3, . . . , 3) =3 + 12 · 33 + 3 · 34 + 8 · 32 = 48.24P (x1 , . . . , x6 ) =ПРИКЛАДНАЯ АЛГЕБРА. Часть III: Теория перечисления Пойа39 / 70Применение леммы Бёрнсайда для решения комбинаторных задачЦикловой индекс действия группы октаэдра —— на множество R рёбер куба ( |R| = N = 12):g∈Oet, t3t2fr, r2ВсегоT ype(g)h 12, 0, . . .
ih 0, 0, 0, 3, 0, 0 ih 0, 6, 0, . . . ih 2, 5, 0, . . . ih 0, 0, 4, 0, . . . iw(g)x121x34x62x21 x52x43#w(g)13·2=6364·2=824Цикловой индекс:P (O : R) =α1 12x1 + 6x34 + 3x62 + 6x21 x52 + 8x43 .24ПРИКЛАДНАЯ АЛГЕБРА. Часть III: Теория перечисления Пойа40 / 70Применение леммы Бёрнсайда для решения комбинаторных задачЦикловой индекс действия группы октаэдра —— на множество V вершин куба ( |V | = N = 8):g∈Oet, t3t2fr, r2ВсегоT ype(g)h 8, 0, . . .
ih 0, 0, 0, 2, 0, 0 ih 0, 4, 0, . . . ih 0, 4, 0, . . . ih 2, 0, 2, 0, . . . iw(g)x81x24x42x42x21 x23#w(g)13·2=6364·2=824Цикловой индекс:P (O : V ) =α1 8x1 + 6x24 + 9x42 + 8x21 x23 .24ПРИКЛАДНАЯ АЛГЕБРА. Часть III: Теория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задачЗадача (перечисление графов).Сколько имеется неориентированных непомеченных графов (безпетель и кратных рёбер) с тремя вершинами?Решение. T — стороны треугольника, N = 3.∼ S3 — все перестановки трёх вершин,G=n = 3! = 6.G : T — действие перестановокαвершин на стороны.Графы неориентированные —r = 2 — пометки «есть ребро/нет ребра»S3 = { e, 2 ∗ (ABC), 3 ∗ ((A)(BC)) }41 / 70ПРИКЛАДНАЯ АЛГЕБРА.
Часть III: Теория перечисления Пойа42 / 70Применение леммы Бёрнсайда для решения комбинаторных задачПеречисление графов...S3 =e, 2 ∗ (ABC), 3 ∗ ((A)(BC)) .| {z }| {z }g1Элемент группы ge = (a)(b)(c)g1 = (abc)g2 = (a)(bc)ВсегоP (x1 , x2 , x3 ) =16T ype(g)h 3, 0, 0 ih 0, 0, 1 ih 1, 1, 0 ig2w(g)x31x13x11 x12#w(g)1236x31 + 2x13 + 3x11 x12 , P (2, 2, 2) = 4.ПРИКЛАДНАЯ АЛГЕБРА. Часть III: Теория перечисления Пойа43 / 70Применение леммы Бёрнсайда для решения комбинаторных задачПеречисление графов...Перечислим ориентированные: пустой граф и графы◦[[]◦◦◦u◦w ◦◦ [[]◦◦◦ [[]◦ u◦◦ [[]◦ u◦◦◦[[]◦[[]— всего 7 графов неориентированных — 4.ПРИКЛАДНАЯ АЛГЕБРА.
Часть III: Теория перечисления Пойа44 / 70Применение леммы Бёрнсайда для решения комбинаторных задачЦикловые индексы самодействия идействия O на элементы кубаP (Sn ) =XN(j1 ,...,jn )∈ n01j1 +2j2 +...+njn =nxj11 xj22 . . . xjnn,(1j1 j1 !)(2j2 j2 !) . . . (njn jn !)1Xn/dϕ(d)xd , ϕ — функция Эйлера,nd|n((n−1)/21,11 x22x если n нечётно,P (Dn ) = P (Zn ) +n/2(n−2)/2122+ x1 x2, если n чётно,4 x2P (Zn ) =1 8x1 + 9x42 + 6x24 + 6x24 + 8x21 x23 (на вершины),α241 12P (O : E) =x1 + 3x62 + 8x43 + 6x24 + 8x21 x52 + 6x34 (на рёбра),α241 6P (O : F ) =x1 + 3x21 x22 + 6x21 x4 + 6x32 + 8x23 (на грани).α24P (O : V ) =ПРИКЛАДНАЯ АЛГЕБРА.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
