Лекции по прикладной алгебре. v2.0 (1127112), страница 21
Текст из файла (страница 21)
#Col(3) =?1Ожерелья одинаковы, если одно получается из другого поворотом.РешениеG∼= Z5 = hti, t5 = e, n = 5.Элемент группы gT ype(g)eh 5, 0, 0, 0, 0 ih 0, 0, 0, 0, 1 it, t2 , t3 , t4w(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Ожерелья одинаковы, если одно получается из другогоповоротом или переворотом.РешениеG — группа диэдра: G ∼= D5 = ht, f i, t5 = f 2 = e, n = |D5 | = 10.Элемент группы get, t2 , t3 , t4f, tf, .
. . , t4 fВсего# мономов14510 52x1 + 4x5 + 5x1 x2 .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.Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задачЗадача о раскраске кубаЗадача (раскраска куба в два цвета)Грани куба раскрашивают в 2 цвета.Сколько существует различно окрашенных кубов?283 / 432Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задачЗадача о раскраске кубаЗадача (раскраска куба в два цвета)Грани куба раскрашивают в 2 цвета.Сколько существует различно окрашенных кубов?РешениеG = 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=6h 2, 2, 0, 0, 0, 0 i x21 x223t2fh 0, 3, 0, 0, 0, 0 ix32622r, rh 0, 0, 2, 0, 0, 0 ix34·2=8Всего241P =· x61 + 6x21 x4 + 3x21 x22 + 6x32 + 8x23 .2426 + 12 · 23 + 3 · 24 + 8 · 22#Col(2) == 10.24284 / 432Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задачЗадача (Перечисление графов)Сколько имеется неориентированных непомеченных графов (безпетель и кратных рёбер) с тремя вершинами?285 / 432Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задачЗадача (Перечисление графов)Сколько имеется неориентированных непомеченных графов (безпетель и кратных рёбер) с тремя вершинами?РешениеT — стороны треугольника, N = 3.G∼= S3 — все перестановки трёх вершин,n = 3! = 6.G α: 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 x32h 1, 1, 0 i x11 x123g2 = (a)(bc)Всего6P1 (x1 , x2 , x3 ) = 16 x31 + 2x13 + 3x11 x12 , P1 (2, 2, 2) = 4.Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задач287 / 432Перечислим ориентированные: пустой граф и графы◦◦[[]◦◦◦u[[]◦[[]w◦[[]◦◦[[]◦ u◦[[]◦ u◦◦◦◦◦— всего 7 графов неориентированных — 4.◦Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задачЦикловые индексы самодействия идействия 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,12x1 x2 если n нечётно,P (Dn ) = P (Zn ) +n/2(n−2)/2122+ x1 x2, если n чётно,4 x2P (Zn ) =1x81 + 9x42 + 6x24 + 6x24 + 8x21 x23 ,241P (O : E) =x12+ 3x62 + 8x43 + 6x24 + 8x21 x52 + 6x34 ,1α241P (O : F ) =x61 + 3x21 x22 + 6x21 x4 + 6x32 + 8x23 .α24P (O : V ) =α288 / 432Прикладная алгебраТеория перечисления ПойаПрименение теоремы Пойа для решения комбинаторных задачРаздел I1Конечные поля или поля ГалуаПоля вычетов по модулю простого числаВычисление элементов в конечных поляхЛинейная алгебра над конечным полемКорни многочленов над конечным полемСуществование и единственность поля Галуа из pnэлементовЦиклические подпространстваЗадачиЧто надо знать2Коды, исправляющие ошибкиПонятие помехоустойчивого кодирования. Коды ХэммингаГрупповые (линейные) коды289 / 432Прикладная алгебраТеория перечисления ПойаПрименение теоремы Пойа для решения комбинаторных задачРаздел IIЦиклические кодыКоды БЧХЗадачиЧто надо знать3Теория перечисления ПойаДействие группы на множествеПрименение леммы Бёрнсайда для решениякомбинаторных задачПрименение теоремы Пойа для решения комбинаторныхзадачЗадачиЧто надо знать4Некоторые вопросы теории частично упорядоченныхмножеств290 / 432Прикладная алгебраТеория перечисления ПойаПрименение теоремы Пойа для решения комбинаторных задачРаздел IIIОсновные понятия теории ч.у.
множествОперации над ч.у. множествамиЛинеаризацияЧто надо знать5Алгебраические решёткиРешётки: определение, основные свойстваМодулярные и дистрибутивные решёткиПрименение теории решёток к задаче классификацииЧто надо знать291 / 432Прикладная алгебраТеория перечисления ПойаПрименение теоремы Пойа для решения комбинаторных задач292 / 432Теорема ПойаК множеству T , |T | = N , группе G, |G| = n и действиюG α: Tдобавим множество R = {c1 , .
. . , cr }, меток («красок»), исовокупность функций F = RT — приписывания меток(раскрашиваний) элементам T .Прикладная алгебраТеория перечисления ПойаПрименение теоремы Пойа для решения комбинаторных задач292 / 432Теорема ПойаК множеству T , |T | = N , группе G, |G| = n и действиюG α: Tдобавим множество R = {c1 , . . . , cr }, меток («красок»), исовокупность функций F = RT — приписывания меток(раскрашиваний) элементам T . G, действуя на T , действует и◦на RT — ◦ : RT × G = RT .Прикладная алгебраТеория перечисления ПойаПрименение теоремы Пойа для решения комбинаторных задач292 / 432Теорема ПойаК множеству T , |T | = N , группе G, |G| = n и действиюG α: Tдобавим множество R = {c1 , .
. . , cr }, меток («красок»), исовокупность функций F = RT — приписывания меток(раскрашиваний) элементам T . G, действуя на T , действует и◦на RT — ◦ : RT × G = RT . Дадим вес элементам R :w(ci ) = yi , i = 1, r.Прикладная алгебраТеория перечисления ПойаПрименение теоремы Пойа для решения комбинаторных задач292 / 432Теорема ПойаК множеству T , |T | = N , группе G, |G| = n и действиюG α: Tдобавим множество R = {c1 , . .
. , cr }, меток («красок»), исовокупность функций F = RT — приписывания меток(раскрашиваний) элементам T . G, действуя на T , действует и◦на RT — ◦ : RT × G = RT . Дадим вес элементам R :w(ci ) = yi , i = 1, r.Теорема (Редфилда-Пойа)Цикловой индекс действия группыG наRT естьW (F ) = P (G : R ) = P (G : T, x1 , . . . , xN )ααTxk =y1k +...+yrkПрикладная алгебраТеория перечисления ПойаПрименение теоремы Пойа для решения комбинаторных задач293 / 432СледствиеЕсли все веса выбраны одинаковыми (y1 = . .
. yr = 1), тоx1 = . . . xN = r и W (F ) — число классов эквивалентностиC(G : RT ) = C(G : T ) = P (G : T, r, . . . , r) .α— лемма Бёрнсайда.ααПрикладная алгебраТеория перечисления ПойаПрименение теоремы Пойа для решения комбинаторных задач293 / 432СледствиеЕсли все веса выбраны одинаковыми (y1 = . . .
yr = 1), тоx1 = . . . xN = r и W (F ) — число классов эквивалентностиC(G : RT ) = C(G : T ) = P (G : T, r, . . . , r) .ααα— лемма Бёрнсайда.Что можно определить (подсчитать) с помощью:леммы Бёрнсайда — общее число неэквивалентныхразметок (раскрасок);теорема Редфилда-Пойа — число разметок данного типа,(содержащих данное количество элементовконкретного цвета).Прикладная алгебраТеория перечисления ПойаПрименение теоремы Пойа для решения комбинаторных задачУсложним задачу об ожерельях N = 5, r = 3Задача (об ожерельях: 5 бусин 3 цветов —)— красный, синий, зелёный. Ожерелья одинаковы, если однополучается из другого поворотом и/или переворотом.Сколько имеется ожерелий, имеющих ровно 2 красные бусины?294 / 432Прикладная алгебраТеория перечисления ПойаПрименение теоремы Пойа для решения комбинаторных задачУсложним задачу об ожерельях N = 5, r = 3Задача (об ожерельях: 5 бусин 3 цветов —)— красный, синий, зелёный.
Ожерелья одинаковы, если однополучается из другого поворотом и/или переворотом.Сколько имеется ожерелий, имеющих ровно 2 красные бусины?Решение 51x1 + 4x5 + 5x1 x22 .Было: G = D5 , цикловой индекс P = 10Всего ожерелий P (3, . . . , 3) = 39 (только поворот — 51).294 / 432Прикладная алгебраТеория перечисления ПойаПрименение теоремы Пойа для решения комбинаторных задачУсложним задачу об ожерельях N = 5, r = 3Задача (об ожерельях: 5 бусин 3 цветов —)— красный, синий, зелёный. Ожерелья одинаковы, если однополучается из другого поворотом и/или переворотом.Сколько имеется ожерелий, имеющих ровно 2 красные бусины?Решение 51x1 + 4x5 + 5x1 x22 .Было: G = D5 , цикловой индекс P = 10Всего ожерелий P (3, .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
