PA_full (1127144), страница 21
Текст из файла (страница 21)
. . xjnn,(1j1 j1 !)(2j2 j2 !) . . . (njn jn !)1Xn/d'(d)xd , ' � функция Эйлера,nd|n((n 1)/21,12x⇣1 x2⌘ если n нечётно,P (Dn ) = P ( n ) +n/2(n 2)/2122+ x1 x2, если n чётно,4 x2P(n)=1x8 + 9x42 + 6x24 + 6x24 + 8x21 x23 ,24 11P (O : E) =x12 + 3x62 + 8x43 + 6x24 + 8x21 x52 + 6x34 ,↵24 11P (O : F ) =x6 + 3x21 x22 + 6x21 x4 + 6x32 + 8x23 .↵24 1P (O : V ) =↵288 / 432Прикладная алгебраТеория перечисления ПойаПрименение теоремы Пойа для решения комбинаторных задачРаздел I1Конечные поля или поля ГалуаПоля вычетов по модулю простого числаВычисление элементов в конечных поляхЛинейная алгебра над конечным полемКорни многочленов над конечным полемСуществование и единственность поля Галуа из pnэлементовЦиклические подпространстваЗадачиЧто надо знать2Коды, исправляющие ошибкиПонятие помехоустойчивого кодирования.
Коды ХэммингаГрупповые (линейные) коды289 / 432Прикладная алгебраТеория перечисления ПойаПрименение теоремы Пойа для решения комбинаторных задачРаздел IIЦиклические кодыКоды БЧХЗадачиЧто надо знать3Теория перечисления ПойаДействие группы на множествеПрименение леммы Бёрнсайда для решениякомбинаторных задачПрименение теоремы Пойа для решения комбинаторныхзадачЗадачиЧто надо знать4Некоторые вопросы теории частично упорядоченныхмножеств290 / 432Прикладная алгебраТеория перечисления ПойаПрименение теоремы Пойа для решения комбинаторных задачРаздел IIIОсновные понятия теории ч.у.
множествОперации над ч.у. множествамиЛинеаризацияЧто надо знать5Алгебраические решёткиРешётки: определение, основные свойстваМодулярные и дистрибутивные решёткиПрименение теории решёток к задаче классификацииЧто надо знать291 / 432Прикладная алгебраТеория перечисления ПойаПрименение теоремы Пойа для решения комбинаторных задач292 / 432Теорема ПойаК множеству T , |T | = N , группе , |G| = n и действию:T↵добавим множество R = {c1 , . . . , cr }, меток (�красок�), исовокупность функций F = RT � приписывания меток(раскрашиваний) элементам T .Прикладная алгебраТеория перечисления ПойаПрименение теоремы Пойа для решения комбинаторных задач292 / 432Теорема ПойаК множеству T , |T | = N , группе , |G| = n и действию:T↵добавим множество R = {c1 , . . .
, cr }, меток (�красок�), исовокупность функций F = RT � приписывания меток(раскрашиваний) элементам T . , действуя на T , действует ина RT � : RT ⇥ G = RT .Прикладная алгебраТеория перечисления ПойаПрименение теоремы Пойа для решения комбинаторных задач292 / 432Теорема ПойаК множеству T , |T | = N , группе , |G| = n и действию:T↵добавим множество R = {c1 , .
. . , cr }, меток (�красок�), исовокупность функций F = RT � приписывания меток(раскрашиваний) элементам T . , действуя на T , действует ина RT � : RT ⇥ G = RT . Дадим вес элементам R :w(ci ) = yi , i = 1, r.Прикладная алгебраТеория перечисления ПойаПрименение теоремы Пойа для решения комбинаторных задач292 / 432Теорема ПойаК множеству T , |T | = N , группе , |G| = n и действию:T↵добавим множество R = {c1 , . . .
, cr }, меток (�красок�), исовокупность функций F = RT � приписывания меток(раскрашиваний) элементам T . , действуя на T , действует ина RT � : RT ⇥ G = RT . Дадим вес элементам R :w(ci ) = yi , i = 1, r.Теорема (Редфилда-Пойа)Цикловой индекс действия группына RT естьW (F ) = P ( : RT ) = P ( : T, x1 , . . . , xN )↵↵xk =y1k +...+yrkПрикладная алгебраТеория перечисления ПойаПрименение теоремы Пойа для решения комбинаторных задач293 / 432СледствиеЕсли все веса выбраны одинаковыми (y1 = .
. . yr = 1), тоx1 = . . . xN = r и W (F ) � число классов эквивалентностиC( : RT ) = C( : T ) = P ( : T, r, . . . , r) .↵� лемма Бёрнсайда.↵↵Прикладная алгебраТеория перечисления ПойаПрименение теоремы Пойа для решения комбинаторных задач293 / 432СледствиеЕсли все веса выбраны одинаковыми (y1 = . . . yr = 1), тоx1 = . . .
xN = r и W (F ) � число классов эквивалентностиC( : RT ) = C( : T ) = P ( : T, r, . . . , r) .↵↵↵� лемма Бёрнсайда.Что можно определить (подсчитать) с помощью:леммы Бёрнсайда � общее число неэквивалентныхразметок (раскрасок);теорема Редфилда-Пойа � число разметок данного типа,(содержащих данное количество элементовконкретного цвета).Прикладная алгебраТеория перечисления ПойаПрименение теоремы Пойа для решения комбинаторных задачУсложним задачу об ожерельях N = 5, r = 3Задача (об ожерельях: 5 бусин 3 цветов �)� красный, синий, зелёный.
Ожерелья одинаковы, если однополучается из другого поворотом и/или переворотом.Сколько имеется ожерелий, имеющих ровно 2 красные бусины?294 / 432Прикладная алгебраТеория перечисления ПойаПрименение теоремы Пойа для решения комбинаторных задачУсложним задачу об ожерельях N = 5, r = 3Задача (об ожерельях: 5 бусин 3 цветов �)� красный, синий, зелёный. Ожерелья одинаковы, если однополучается из другого поворотом и/или переворотом.Сколько имеется ожерелий, имеющих ровно 2 красные бусины?Решение⇥ 5⇤1x1 + 4x5 + 5x1 x22 .Было: = D5 , цикловой индекс P = 10Всего ожерелий P (3, . .
. , 3) = 39 (только поворот � 51).294 / 432Прикладная алгебраТеория перечисления ПойаПрименение теоремы Пойа для решения комбинаторных задачУсложним задачу об ожерельях N = 5, r = 3Задача (об ожерельях: 5 бусин 3 цветов �)� красный, синий, зелёный.
Ожерелья одинаковы, если однополучается из другого поворотом и/или переворотом.Сколько имеется ожерелий, имеющих ровно 2 красные бусины?Решение⇥ 5⇤1x1 + 4x5 + 5x1 x22 .Было: = D5 , цикловой индекс P = 10Всего ожерелий P (3, . . . , 3) = 39 (только поворот � 51).x1 = y1 + y2 + y3 , x2 = y12 + y22 + y32 , . . .
, xk = y1k + y2k + y3k .294 / 432Прикладная алгебраТеория перечисления ПойаПрименение теоремы Пойа для решения комбинаторных задачУсложним задачу об ожерельях N = 5, r = 3Задача (об ожерельях: 5 бусин 3 цветов �)� красный, синий, зелёный. Ожерелья одинаковы, если однополучается из другого поворотом и/или переворотом.Сколько имеется ожерелий, имеющих ровно 2 красные бусины?Решение⇥ 5⇤1x1 + 4x5 + 5x1 x22 .Было: = D5 , цикловой индекс P = 10Всего ожерелий P (3, . . .
, 3) = 39 (только поворот � 51).x1 = y1 + y2 + y3 , x2 = y12 + y22 + y32 , . . . , xk = y1k + y2k + y3k .88x1 = y + 2,>>⇢< w(красный) = y1 ,<y1 = y,x2 = y 2 + 2,w(синий)= y2 , ))y2 = y3 = 1,...:>>w(зелёный) = y3 ,:x5 = y 5 + 2.294 / 432Прикладная алгебраТеория перечисления ПойаПрименение теоремы Пойа для решения комбинаторных задач295 / 432⇤x51 + 4x5 + 5x1 x225Xkxk !7 y + 2, k = 1, 5; P (y) =ui y i .P (x1 , .
. . , x5 ) =110⇥i=1Прикладная алгебраТеория перечисления ПойаПрименение теоремы Пойа для решения комбинаторных задач295 / 432⇤x51 + 4x5 + 5x1 x225Xkxk !7 y + 2, k = 1, 5; P (y) =ui y i .P (x1 , . . . , x5 ) =110⇥i=1⇤1 ⇥u0 + u1 y + u2 y 2 + . . . + u5 y 5 =10⇤1 ⇥=(y + 2)5 + 4(y 5 + 2) + 5(y + 2)(y 2 + 2)2 =10⇤1 ⇥=. . . + C52 23 y 2 + . . . + 5(y + 2)(y 4 + 4y 2 + 4) =10⇤1 ⇥. .
. + (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⇥#Col(4, 4) =(y + 1)8 + 9 · (y 2 + 1)4 + 6 · (y 4 + 1)2 +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 + . . .) .⇤1⇥168u4 =70 + 9 · 6 + 6 · 2 + 8 · 2 · 2 == 7.2424297 / 432Прикладная алгебраТеория перечисления ПойаПрименение теоремы Пойа для решения комбинаторных задач297 / 4322w(красный) = y, w(синий) = 1, xk = y k + 1, k = 1, 8:1⇥#Col(4, 4) =(y + 1)8 + 9 · (y 2 + 1)4 + 6 · (y 4 + 1)2 +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 + . . .) .⇤1⇥168u4 =70 + 9 · 6 + 6 · 2 + 8 · 2 · 2 == 7.24243#Col(6 2, ⇤) = u0 + u1 + u2 . u0 = u1 = 1.⇤1⇥u2 =. . .+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 ) =↵112⇥⇤x41 + 8x1 x3 + 3x22 .Прикладная алгебраТеория перечисления ПойаПрименение теоремы Пойа для решения комбинаторных задач300 / 432РешениеКакая группа действует на каком множестве?T = h t, f i , t3 = f 2 = e, гдеt � вращение на 120 вокруг оси,проходящей через вершинуи центр тетраэдра (M�M);f � вращение на 180 вокруг оси,проходящей через центры двухпротивоположных рёбер (⇤�⇤).P (T : V ) =↵112⇥⇤x41 + 8x1 x3 + 3x22 .Почему перед x1 x3 коэффициент 8, ведь осей M�M всего 4?Прикладная алгебраТеория перечисления ПойаПрименение теоремы Пойа для решения комбинаторных задач(продолжение)12Имеем N = 4,� группа вращения тетраэдра:⇤1⇥ 4P (T : V ) =x1 + 8x1 x3 + 3x22 .↵12Всего молекул (4 радикала) �⇤1⇥ 416 · 27M = P (4, .
. . , 4) =4 +8·4·4+3·42 == 36 .1212Веса: y1 = H, y2 = y3 = y4 = 1.Подстановка в P : xk = Hk + 3, k = 1, 4.301 / 432Прикладная алгебраТеория перечисления ПойаПрименение теоремы Пойа для решения комбинаторных задачP (x1 , x2 , x3 ) =112⇥⇤x41 + 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Коды, исправляющие ошибкиПонятие помехоустойчивого кодирования.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
