PA_full (1127144), страница 20
Текст из файла (страница 20)
. . + ⌫N штук.Каждая перестановка g 2 с типом h ⌫1 , . . . , ⌫N i будетиметь rC(g) неподвижных точек.Следовательно, по лемме Бёрсайда, число полученных классовэквивалентности, т.е. неэквивалентных раскрасок(приписываний) естьТеоремаC( : T ) = P ( : T, x1 , .
. . , xN )↵↵x1 =...=xN =r= P (r, . . . , r).Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задач276 / 432Вычисление C( ) через цикловой индексКаждый класс эквивалентности это g-цикл; ихC(g) = ⌫1 + . . . + ⌫N штук.Каждая перестановка g 2 с типом h ⌫1 , . . .
, ⌫N i будетиметь rC(g) неподвижных точек.Следовательно, по лемме Бёрсайда, число полученных классовэквивалентности, т.е. неэквивалентных раскрасок(приписываний) естьТеоремаC( : T ) = P ( : T, x1 , . . . , xN )↵↵x1 =...=xN =r= P (r, . . . , r).Например, P (1, . . .
, 1) = 1: если все элементы покрасить водин цвет, то таких раскрасок одна.Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задачЗадача (про слова)Составляются слова длины l > 2 из алфавитаA = { a1 , . . . , am }. Слова считаются эквивалентными, еслиони получаются одно из другого перестановкой крайних букв.Определить число S неэквивалентных слов.277 / 432Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задачЗадача (про слова)Составляются слова длины l > 2 из алфавитаA = { a1 , . . . , am }.
Слова считаются эквивалентными, еслиони получаются одно из другого перестановкой крайних букв.Определить число S неэквивалентных слов.Было решение: S =ml +ml21.277 / 432Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задач277 / 432Задача (про слова)Составляются слова длины l > 2 из алфавитаA = { a1 , . . .
, am }. Слова считаются эквивалентными, еслиони получаются одно из другого перестановкой крайних букв.Определить число S неэквивалентных слов.Было решение: S =Другое решение:ml +ml21.l 2z }| {= { e, g } ⇠....= 2; T :|{z}lПрикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задач277 / 432Задача (про слова)Составляются слова длины l > 2 из алфавитаA = { a1 , . . . , am }. Слова считаются эквивалентными, еслиони получаются одно из другого перестановкой крайних букв.Определить число S неэквивалентных слов.Было решение: S =Другое решение:ml +ml21.l 2z }| {= { e, g } ⇠....= 2; 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.lxl1 +x1l2w(g)xl1xl1 2 x122 1x2.#мономов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 � вершины правильного пятиугольника.
#Col(3) =?1Ожерелья одинаковы, если одно получается из другого поворотом.Решение⇠= 5 = hti, t5 = e, n = 5.Элемент группы gT ype(g)eh 5, 0, 0, 0, 0 it, t2 , t3 , t4h 0, 0, 0, 0, 1 iw(g)x51x5Цикловой индекс: P (x1 , x2 , x3 , x4 , x5 ) =#Col(3) = P (3, . . .
, 3) =35 +4·35=# мономов14155 [x1 + 4x5 ].3·855 = 3 · 17= 51.Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задачЗадача Олимпиады �Покори Воробьёвы горы – 2009�Для 50 детей детского сада закуплены 50 одинаковых тарелок.По краю каждой тарелки равномерно расположено 5 белыхкружочков. Воспитатели хотят перекрасить какие-либо из этихкружочков в другой цвет так, чтобы все тарелки сталиразличными. Какое наименьшее число дополнительных цветовпотребуется им для этого?280 / 432Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задачКак должны были решать детиРешениеПусть требуется r цветов.
Отбросим r вариантов раскраски водин цвет. Число остальных вариантов без учёта возможности5поворота тарелки � r5 r; с учётом поворота � r 5 r (каждыйвариант повторятся 5 раз).r5 rr5 + 4rИтого: #Col(r) =+r =;55При 2-х дополнительных цветах #Col(3) = 51.281 / 432Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задачЗадача об ожерельях: N = 5, r = 3, 2-й вариант2Ожерелья одинаковы, если одно получается из другогоповоротом или переворотом.282 / 432Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задач282 / 432Задача об ожерельях: N = 5, r = 3, 2-й вариант2Ожерелья одинаковы, если одно получается из другогоповоротом или переворотом.Решение⇠= D5 = ht, f i, t5 = f 2 = e, n = |D5 | = 10.Элемент группы gT ype(g)w(g) # мономовeh 5, 0, 0, 0, 0 i x511234t, t , t , th 0, 0, 0, 0, 1 i x54f, tf, .
. . , t4 fh 1, 2, 0, 0, 0 i x1 x225Всего10⇥ 5⇤12Цикловой индекс: P = 10 x1 + 4x5 + 5x1 x2 .� группа диэдра:#Col(3) = P (x1 , . . . , x5 )|x1 =...=x5 =3 =Запомним этот ответ.35 +4·3+5·3310= 39.Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задачЗадача о раскраске кубаЗадача (раскраска куба в два цвета)Грани куба раскрашивают в 2 цвета.Сколько существует различно окрашенных кубов?283 / 432Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задачЗадача о раскраске кубаЗадача (раскраска куба в два цвета)Грани куба раскрашивают в 2 цвета.Сколько существует различно окрашенных кубов?Решение= O = h t, f, r i, t4 = f 2 = r3 = e, |O| = 24.t � вращение на 90 вокруг оси,проходящей через середины двухпротивоположных граней (2�2, 3 оси);f � вращение на 180 вокруг оси,проходящей через середины двухпротивоположных рёбер ( � , 6 осей);r � вращение на 120 вокруг оси,проходящей через две противоположныевершины (M�M, 4 оси).283 / 432Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задачЗадача о раскраске куба в два цвета...T � множество граней куба, N = 6.Элемент группы gT ype(g)w(g) # мономовeh 6, 0, 0, 0, 0, 0 ix6113t, th 2, 0, 0, 1, 0, 0 i x21 x43·2=6t2h 2, 2, 0, 0, 0, 0 i x21 x223fh 0, 3, 0, 0, 0, 0 ix32622r, rh 0, 0, 2, 0, 0, 0 ix34·2=8Всего24⇥⇤1P =· x61 + 6x21 x4 + 3x21 x22 + 6x32 + 8x23 .2426 + 12 · 23 + 3 · 24 + 8 · 22#Col(2) == 10.24284 / 432Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задачЗадача (Перечисление графов)Сколько имеется неориентированных непомеченных графов (безпетель и кратных рёбер) с тремя вершинами?285 / 432Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задачЗадача (Перечисление графов)Сколько имеется неориентированных непомеченных графов (безпетель и кратных рёбер) с тремя вершинами?РешениеT � стороны треугольника, N = 3.⇠= S3 � все перестановки трёх вершин,n = 3! = 6.: T � действие перестановоквершин на стороны.↵Графы неориентированные �r = 2 � пометки �есть ребро/нет ребра�S3 = { e, 2 ⇤ (ABC), 3 ⇤ ((A)(BC)) }.285 / 432Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задач286 / 432Перечисление графов...S3 = { e, 2 ⇤ (ABC), 3 ⇤ ((A)(BC)) }.| {z }| {z }g1g2Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задач286 / 432Перечисление графов...S3 = { e, 2 ⇤ (ABC), 3 ⇤ ((A)(BC)) }.| {z }| {z }g1Элемент группы ge = (a)(b)(c)g1 = (abc)g2 = (a)(bc)ВсегоT ype(g)h 3, 0, 0 ih 0, 0, 1 ih 1, 1, 0 ig2w(g)x31x13x11 x12# мономов1236Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задач286 / 432Перечисление графов...S3 = { e, 2 ⇤ (ABC), 3 ⇤ ((A)(BC)) }.| {z }| {z }g1g2Элемент группы g T ype(g) w(g) # мономовe = (a)(b)(c)h 3, 0, 0 i x3111g1 = (abc)h 0, 0, 1 i x32g2 = (a)(bc)h 1, 1, 0 i x11 x123Всего6⇥⇤P1 (x1 , x2 , x3 ) = 16 x31 + 2x13 + 3x11 x12 , P1 (2, 2, 2) = 4.Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задачПеречислим ориентированные: пустой граф и графы� всего 7 графов неориентированных � 4.287 / 432Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задачЦикловые индексы самодействия идействия O на элементы кубаP (Sn ) =X(j1 ,...,jn )2 n01j1 +2j2 +...+njn =nxj11 xj22 .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
