Лекции по прикладной алгебре. v2.0 (1127112), страница 22
Текст из файла (страница 22)
. . , 3) = 39 (только поворот — 51).x1 = y1 + y2 + y3 , x2 = y12 + y22 + y32 , . . . , xk = y1k + y2k + y3k .294 / 432Прикладная алгебраТеория перечисления ПойаПрименение теоремы Пойа для решения комбинаторных задачУсложним задачу об ожерельях N = 5, r = 3Задача (об ожерельях: 5 бусин 3 цветов —)— красный, синий, зелёный. Ожерелья одинаковы, если однополучается из другого поворотом и/или переворотом.Сколько имеется ожерелий, имеющих ровно 2 красные бусины?Решение 51x1 + 4x5 + 5x1 x22 .Было: G = D5 , цикловой индекс P = 10Всего ожерелий P (3, . .
. , 3) = 39 (только поворот — 51).x1 = y1 + y2 + y3 , x2 = y12 + y22 + y32 , . . . , xk = y1k + y2k + y3k .x1 = y + 2, w(красный) = y1 ,y1 = y,x2 = y 2 + 2,w(синий)= y2 , ⇒⇒y2 = y3 = 1,...w(зелёный) = y3 ,x5 = y 5 + 2.294 / 432Прикладная алгебраТеория перечисления ПойаПрименение теоремы Пойа для решения комбинаторных задач110295 / 432x51 + 4x5 + 5x1 x225Xkui y i .xk →7 y + 2, k = 1, 5; P (y) =P (x1 , . . . , x5 ) =i=1Прикладная алгебраТеория перечисления ПойаПрименение теоремы Пойа для решения комбинаторных задач110295 / 432x51 + 4x5 + 5x1 x225Xkui y i .xk →7 y + 2, k = 1, 5; P (y) =P (x1 , .
. . , x5 ) =i=11 u0 + u1 y + u2 y 2 + . . . + u5 y 5 =101 =(y + 2)5 + 4(y 5 + 2) + 5(y + 2)(y 2 + 2)2 =101 . . . + C52 23 y 2 + . . . + 5(y + 2)(y 4 + 4y 2 + 4) ==101 . . . + (10 · 8 + 5 · 2 · 4)y 2 + . . . .=10P (y) =u2 =80 + 40= 12.10Прикладная алгебраТеория перечисления ПойаПрименение теоремы Пойа для решения комбинаторных задачЗадачаВершины куба помечают красными и синим цветами.Сколько существует123разнопомеченных кубов;кубов, у которых половина вершины красные;кубов, у которых не более 2-х красных вершин?296 / 432Прикладная алгебраТеория перечисления ПойаПрименение теоремы Пойа для решения комбинаторных задачЗадачаВершины куба помечают красными и синим цветами.Сколько существует123разнопомеченных кубов;кубов, у которых половина вершины красные;кубов, у которых не более 2-х красных вершин?РешениеЦикловой индекс действия группы O на вершины куба1 8P (O : V ) =x1 + 6x24 + 9x42 + 8x21 x23 .α24296 / 432Прикладная алгебраТеория перечисления ПойаПрименение теоремы Пойа для решения комбинаторных задач296 / 432ЗадачаВершины куба помечают красными и синим цветами.Сколько существует123разнопомеченных кубов;кубов, у которых половина вершины красные;кубов, у которых не более 2-х красных вершин?РешениеЦикловой индекс действия группы O на вершины куба1 8P (O : V ) =x1 + 6x24 + 9x42 + 8x21 x23 .α241Число разнопомеченных кубов —#Col(3) = P |x1 =...=x8 =2 =552= 23 .24Прикладная алгебраТеория перечисления ПойаПрименение теоремы Пойа для решения комбинаторных задач2w(красный) = y, w(синий) = 1, xk = y k + 1, k = 1, 8:1(y + 1)8 + 9 · (y 2 + 1)4 + 6 · (y 4 + 1)2 +#Col(4, 4) =24+ 8 · (y + 1)2 (y 3 + 1)2 =1=.
. . + 28y 2 + C84 y 4 + . . . + 9(. . . 4y 2 + 6y 4 + . . .)+24. . . + 6 · 2y 4 . . . + 8(. . . + 2y + y 2 + . . .)(. . . + 2y 3 + . . .) .168170 + 9 · 6 + 6 · 2 + 8 · 2 · 2 == 7.u4 =2424297 / 432Прикладная алгебраТеория перечисления ПойаПрименение теоремы Пойа для решения комбинаторных задач23297 / 432w(красный) = y, w(синий) = 1, xk = y k + 1, k = 1, 8:1(y + 1)8 + 9 · (y 2 + 1)4 + 6 · (y 4 + 1)2 +#Col(4, 4) =24+ 8 · (y + 1)2 (y 3 + 1)2 =1=. . .
+ 28y 2 + C84 y 4 + . . . + 9(. . . 4y 2 + 6y 4 + . . .)+24. . . + 6 · 2y 4 . . . + 8(. . . + 2y + y 2 + . . .)(. . . + 2y 3 + . . .) .168170 + 9 · 6 + 6 · 2 + 8 · 2 · 2 == 7.u4 =2424#Col(6 2, ∗) = u0 + u1 + u2 . u0 = u1 = 1.1u2 =. . .+28y 2 +. . .+9(. . .+4y 2 . . .)+8(. . .+y 2 +. . .) =2428 + 36 + 872=== 3. #Col(6 2, ∗) = 1+1+3 = 5.2424Прикладная алгебраТеория перечисления ПойаПрименение теоремы Пойа для решения комбинаторных задач298 / 432ЗадачаРассматриваются молекулы 4-х валентного углерода C:××C×CH3×ClCCH3Clгде на на месте × могут находится CH3 (метил), C2 H5 (этил),H (водород) или Cl (хлор).
Например — дихлорбутан.Прикладная алгебраТеория перечисления ПойаПрименение теоремы Пойа для решения комбинаторных задачЗадача (продолжение)Найти1общее число M всех молекул;2число молекул с H = 0, 1, 2, 3, 4 атомами водорода.299 / 432Прикладная алгебраТеория перечисления ПойаПрименение теоремы Пойа для решения комбинаторных задачРешениеКакая группа действует на каком множестве?300 / 432Прикладная алгебраТеория перечисления ПойаПрименение теоремы Пойа для решения комбинаторных задач300 / 432РешениеКакая группа действует на каком множестве?T = h t, f i , t3 = f 2 = e, гдеt — вращение на 120◦ вокруг оси,проходящей через вершинуи центр тетраэдра (M—M);f — вращение на 180◦ вокруг оси,проходящей через центры двухпротивоположных рёбер (—).P (T : V ) =α112x41 + 8x1 x3 + 3x22 .Прикладная алгебраТеория перечисления ПойаПрименение теоремы Пойа для решения комбинаторных задач300 / 432РешениеКакая группа действует на каком множестве?T = h t, f i , t3 = f 2 = e, гдеt — вращение на 120◦ вокруг оси,проходящей через вершинуи центр тетраэдра (M—M);f — вращение на 180◦ вокруг оси,проходящей через центры двухпротивоположных рёбер (—).P (T : V ) =α112x41 + 8x1 x3 + 3x22 .Почему перед x1 x3 коэффициент 8, ведь осей M—M всего 4?Прикладная алгебраТеория перечисления ПойаПрименение теоремы Пойа для решения комбинаторных задач(продолжение)1Имеем N = 4,G — группа вращения тетраэдра:P (T : V ) =α1 4x1 + 8x1 x3 + 3x22 .12Всего молекул (4 радикала) —1 416 · 27M = P (4, .
. . , 4) =4 +8·4·4+3·42 == 36 .12122Веса: y1 = H, y2 = y3 = y4 = 1.Подстановка в P : xk = Hk + 3, k = 1, 4.301 / 432Прикладная алгебраТеория перечисления ПойаПрименение теоремы Пойа для решения комбинаторных задачP (x1 , x2 , x3 ) =112x41 + 8x1 x3 + 3x22 .Проводим подстаковку — xk 7→ H k + 3, k = 1, 2, 30.1 (H + 3)4 + 8(H + 3)(H3 + 3) + 3(H2 + 3)2 =121 4=(H + 4 · H3 · 3 + 6 · H2 · 9 + 4 · H · 27 + 81)+12+ 8(H4 + 3H3 + 3H + 9) + 3(H4 + 6H2 + 9) =P (H) == 1H4 + 3H3 + 6H2 + 11H + 15.Итого имеется молекул с числом атома водорода:с 4-мя — 1 шт., с 3-мя — 3 шт., с 2-мя — 6 шт., с 1-м — 11 шт.,без атомов водорода — 15 шт.,всего — 1 + 3 + 6 + 11 + 15 = 36.302 / 432Прикладная алгебраТеория перечисления ПойаЗадачиРаздел I1Конечные поля или поля ГалуаПоля вычетов по модулю простого числаВычисление элементов в конечных поляхЛинейная алгебра над конечным полемКорни многочленов над конечным полемСуществование и единственность поля Галуа из pnэлементовЦиклические подпространстваЗадачиЧто надо знать2Коды, исправляющие ошибкиПонятие помехоустойчивого кодирования.
Коды ХэммингаГрупповые (линейные) коды303 / 432Прикладная алгебраТеория перечисления ПойаЗадачиРаздел IIЦиклические кодыКоды БЧХЗадачиЧто надо знать3Теория перечисления ПойаДействие группы на множествеПрименение леммы Бёрнсайда для решениякомбинаторных задачПрименение теоремы Пойа для решения комбинаторныхзадачЗадачиЧто надо знать4Некоторые вопросы теории частично упорядоченныхмножеств304 / 432Прикладная алгебраТеория перечисления ПойаЗадачиРаздел IIIОсновные понятия теории ч.у. множествОперации над ч.у. множествамиЛинеаризацияЧто надо знать5Алгебраические решёткиРешётки: определение, основные свойстваМодулярные и дистрибутивные решёткиПрименение теории решёток к задаче классификацииЧто надо знать305 / 432Прикладная алгебраТеория перечисления ПойаЗадачиЗадача (ТП-1)Найти цикловой индекс группы симметрии правильноготреугольника.306 / 432Прикладная алгебраТеория перечисления ПойаЗадачи306 / 432Задача (ТП-1)Найти цикловой индекс группы симметрии правильноготреугольника.РешениеГруппа симметрии правильного треугольника — группа диэдраD3 ∼= S3 .
D3 = h t, s i, t3 = s2 = e, t2 s = st, |D3 | = 6.Элемент группы ge = (1)(2)(3)t = (123), t2 = (132)s = (1)(23), st, st2T ype(g)h 3, 0, 0 ih 0, 0, 1 ih 1, 1, 0 iw(g)x31x3x1 x2Цикловой индекс —PS3 =1 3· x1 + 2x3 + 3x1 x2 .6Прикладная алгебраТеория перечисления ПойаЗадачиЗадача (ТП-2)Найти цикловой индекс транзитивного самодействия группы Z6 .307 / 432Прикладная алгебраТеория перечисления ПойаЗадачи307 / 432Задача (ТП-2)Найти цикловой индекс транзитивного самодействия группы Z6 .РешениеZ6 = hgi , действие g — циклическаяперестановка элементов Z6 .Элемент группы ge = (1) .
. . (6)g = (123456)g 2 = (135)(246)g 3 = (14)(25)(36)g 4 = (153)(264)g = (165432)T ype(g)h 6, 0, . . . ih 0, 0, 0, 0, 0, 1 ih 0, 0, 2, 0, . . . ih 0, 3, 0, . . . ih 0, 0, 2, 0, . . . ih 0, 0, 0, 0, 0, 1 iPZ6 =w(g)x61x6x23x23x23x61 6· x1 + x32 + 2x6 + 2x23 .6Прикладная алгебраТеория перечисления ПойаЗадачиЗадача (ТП-3)Определить число различных раскрасок правильной 4-х угольнойпирамиды П в 3 цвета.308 / 432Прикладная алгебраТеория перечисления ПойаЗадачи308 / 432Задача (ТП-3)Определить число различных раскрасок правильной 4-х угольнойпирамиды П в 3 цвета.РешениеT — множество граней П, нумерация граней: боковые грани — с1 по 4 по часовой стрелке, основание — 5.Группа вращений П: G ∼= Z4 = h t i, t — вращение на 90◦ по4часовой стрелке t = e.Элемент группы gT ype(g)e = (1)(2)(3)(4)(5) h 5, 0, 0, 0, 0 ih 1, 0, 0, 1, 0 ir = (1234)(5)r2 = (12)(34)(5)h 1, 2, 0, 1, 0 ir3 = (1432)(5)h 1, 0, 0, 1, 0 i1 5PG =x1 + x1 x4 + x1 x22 + x1 x4 , P (2)4w(g)x51x1 x4x1 x22x1 x4136== 34.4Прикладная алгебраТеория перечисления ПойаЗадачиЗадача (ТП-4)Найти число раскрасок усечённой правильной 4-х угольнойпирамиды в 2 цвета.309 / 432Прикладная алгебраТеория перечисления ПойаЗадачи309 / 432Задача (ТП-4)Найти число раскрасок усечённой правильной 4-х угольнойпирамиды в 2 цвета.РешениеT — множество граней пирамиды П; |T | = N = 6.Пронумеруем грани П следующим образом: боковые грани — с1 по 4 по часовой стрелки, основания — 5 и 6.G∼= Z4 = h t i , t4 = e, t — 90◦ по часовой стрелке.Элемент группы ge = (1) .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
