AA3-3(PET) (1127141), страница 3
Текст из файла (страница 3)
Часть III: Теория перечисления ПойаПрименение теоремы Пойа для решения комбинаторных задачРазделыДействие группы на множествеПрименение леммы Бёрнсайда для решениякомбинаторных задачПрименение теоремы Пойа для решения комбинаторныхзадачЗадачи с решениямиЧто надо знать45 / 70ПРИКЛАДНАЯ АЛГЕБРА. Часть III: Теория перечисления Пойа46 / 70Применение теоремы Пойа для решения комбинаторных задачТеорема ПойаК множеству 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.Теорема (Редфилда-Пойа; 1927, 1937)Цикловой индекс действия группы G на RT естьP (G : RT ) = P (G : T, x1 , . . . , xN )ααxk =y1k +...+yrk , k=1,NПРИКЛАДНАЯ АЛГЕБРА. Часть III: Теория перечисления Пойа47 / 70Применение теоремы Пойа для решения комбинаторных задачТеорема Пойа...СледствиеЕсли все веса выбраны одинаковыми (y1 = .
. . yr = 1), тоx1 = . . . xN = r и W (F ) — число классов эквивалентностиC(G : RT ) = C(G : T ) = P (G : T, r, . . . , r) .ααα— лемма Бёрнсайда.Что можно определить (подсчитать) с помощью:леммы Бёрнсайда — общее число неэквивалентныхразметок (раскрасок);теорема Редфилда-Пойа — число разметок данного типа,т.е. содержащих данное количество элементовконкретного цвета.ПРИКЛАДНАЯ АЛГЕБРА. Часть III: Теория перечисления Пойа48 / 70Применение теоремы Пойа для решения комбинаторных задачД. ПойаДьёрдь Пойа (Pólya György, 1887–1985)— венгерский, швейцарскийи американский математик.После окончания Будапештскогоуниверситета работал вВысшей технической школе в Цюрихе,а с 1940 г.
— в Стэнфордскомуниверситете (США).Внёс заметный вклад в теорию чисел, функциональный анализ,математическую статистику (распределение Пойа) икомбинаторику (теорема Редфилда–Пойа).Пойа много работал со школьными учителями математики ивнёс большой вклад в популяризацию науки.ПРИКЛАДНАЯ АЛГЕБРА. Часть III: Теория перечисления Пойа49 / 70Применение теоремы Пойа для решения комбинаторных задачУсложним задачу об ожерельях N = 5, r = 3Задача (об ожерельях: 5 бусин 3-х цветов).Цвета — красный, синий, зелёный. Ожерелья одинаковы, еслиодно получается из другого поворотом и/или переворотом.Сколько имеется ожерелий, имеющих ровно 2 красные бусины?Решение. Было: G = D5 ,1цикловой индекс P = 10x51 + 4x5 + 5x1 x22 ,всего ожерелий P (3, .
. . , 3) = 39 (только поворот — 51).x1 = y1 + y2 + y3 , x2 = y12 + y22 + y32 , . . . , x5 = y15 + y25 + y35 .x1 = y + 2, w(красный) = y1 ,y1 = y,x2 = y 2 + 2,w(синий)= y2 , ⇒⇒y2 = y3 = 1,...w(зелёный) = y3 ,x5 = y 5 + 2.ПРИКЛАДНАЯ АЛГЕБРА. Часть III: Теория перечисления Пойа50 / 70Применение теоремы Пойа для решения комбинаторных задачЗадача об ожерельях: 5 бусин 3-х цветов...1 5x1 + 4x5 + 5x1 x22105Xxk →7 y k + 2, k = 1, 5; P (y) =ui y i , u2 = ?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ПРИКЛАДНАЯ АЛГЕБРА. Часть III: Теория перечисления Пойа51 / 70Применение теоремы Пойа для решения комбинаторных задачЗадача о раскраске кубаВершины куба помечают красными и синим цветами.Сколько существует123разнопомеченных кубов;кубов, у которых половина вершины красные;кубов, у которых не более 2-х красных вершин?Решение.
Цикловой индекс действия группы O на вершиныкуба1 8P (O : V ) =x1 + 6x24 + 9x42 + 8x21 x23 .α241Число разнопомеченных кубов —#Col(3) = P |x1 =...=x8 =2 =552= 23 .24ПРИКЛАДНАЯ АЛГЕБРА. Часть III: Теория перечисления ПойаПрименение теоремы Пойа для решения комбинаторных задачЗадача о раскраске куба...23 81( 24x1 + 6x24 + 9x42 + 8x21 x23 )w(красный) = 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 + . . .) .1168u4 =[ 70 + 9 · 6 + 6 · 2 + 8 · 2 · 2 ] == 7.2424#Col(6 2, ∗) = u0 + u1 + u2 . u0 = u1 = 1.1u2 =. . .+28y 2 +. . .+9(. . .+4y 2 .
. .)+8(. . .+y 2 +. . .) =2428 + 36 + 872=== 3.2424#Col(6 2, ∗) = 1 + 1 + 3 = 5.52 / 70ПРИКЛАДНАЯ АЛГЕБРА. Часть III: Теория перечисления Пойа53 / 70Применение теоремы Пойа для решения комбинаторных задачВращение тетраэдраЗадача. Рассмотрим молекулы 4-х валентного углерода C:××C×CH3×ClCCH3Clгде на на месте × могут находится CH3 (метил), C2 H5 (этил),H (водород) или Cl (хлор). Например — дихлорбутан.ПРИКЛАДНАЯ АЛГЕБРА. Часть III: Теория перечисления ПойаПрименение теоремы Пойа для решения комбинаторных задачВращение тетраэдра...(продолжение)Найти1общее число M всех молекул;2число молекул с H = 0, 1, 2, 3, 4 атомами водорода.54 / 70ПРИКЛАДНАЯ АЛГЕБРА.
Часть III: Теория перечисления Пойа55 / 70Применение теоремы Пойа для решения комбинаторных задачГруппа вращения тетраэдраРешение. Какая группа действует и на каком множестве?T = h t, f i , t3 = f 2 = e, гдеt — вращение на 120◦ вокруг оси,проходящей через вершинуи центр тетраэдра (M—M);f — вращение на 180◦ вокруг оси,проходящей через центры двухпротивоположных рёбер (—).P (T : V ) =α1 4x1 + 8x1 x3 + 3x22 .12Почему перед x1 x3 коэффициент 8, ведь осей M—M всего 4?ПРИКЛАДНАЯ АЛГЕБРА. Часть III: Теория перечисления Пойа56 / 70Применение теоремы Пойа для решения комбинаторных задачГруппа вращения тетраэдра...Цикловой индекс действия группы T на вершины тетраэдра —get, t2fT ype(g)h 4, 0, 0, 0 ih 1, 0, 1, 0 ih 0, 2, 0, 0 iP (x1 , . .
. , x4 ) =w(g)x41x1 x3x22Кол-во14·2=831 4x1 + 8x1 x3 + 3x2212ПРИКЛАДНАЯ АЛГЕБРА. Часть III: Теория перечисления Пойа57 / 70Применение теоремы Пойа для решения комбинаторных задачВращение тетраэдра1Имеем N = 4, действие T на вершины тетраэдра:1 4P (x1 , . . . , x4 ) =x1 + 8x1 x3 + 3x22 .12Всего молекул ( 4 радикала) —1 416 · 27= 36 .M = P (4, . . . , 4) =4 + 8 · 4 · 4 + 3 · 42 =12122Веса: y1 = H, y2 = y3 = y4 = 1.Подстановка в P : xk = Hk + 3, k = 1, 4.ПРИКЛАДНАЯ АЛГЕБРА.
Часть III: Теория перечисления Пойа58 / 70Применение теоремы Пойа для решения комбинаторных задачВращение тетраэдра...P (x1 , x2 , x3 ) =112x41 + 8x1 x3 + 3x22 .Проводим подстаковку — xk 7→ H k + 3, k = 1, 2, 3.2 i1 hP (H) =(H + 3)4 + 8 (H + 3) H3 + 3 + 3 H2 + 3=121 4H + 4 · H3 · 3 + 6 · H2 · 9 + 4 · H · 27 + 81 +=12+8 H4 + 3H3 + 3H + 9 + 3 H4 + 6H2 + 9 == 1 · H4 + 3 · H3 + 6 · H2 + 11 · H + 15.Итого имеется молекул с числом атома водорода:с 4-мя — 1 шт., с 3-мя — 3 шт., с 2-мя — 6 шт.,с 1-м — 11 шт., без атомов водорода — 15 шт.,всего — 1 + 3 + 6 + 11 + 15 = 36.ПРИКЛАДНАЯ АЛГЕБРА.
Часть III: Теория перечисления ПойаЗадачи с решениямиРазделыДействие группы на множествеПрименение леммы Бёрнсайда для решениякомбинаторных задачПрименение теоремы Пойа для решения комбинаторныхзадачЗадачи с решениямиЧто надо знать59 / 70ПРИКЛАДНАЯ АЛГЕБРА. Часть III: Теория перечисления ПойаЗадачи с решениямиЗадача ТП-1Каждое вращение куба переставляет его грани, т.е. задаётгруппу перестановок.Определить стабилизатор некоторой грани в этой группе.Решение.Пусть a — грань куба.Перестановки, оставляющие неподвижной грань сутьe, t, t2 , t3 , где t — вращение на 90◦ вокруг оси, проходящейчерез две противоположные грани.Таким образом, Stab (a) = h t i ∼= Z4 .60 / 70ПРИКЛАДНАЯ АЛГЕБРА. Часть III: Теория перечисления Пойа61 / 70Задачи с решениямиЗадача ТП-2Найти цикловой индекс самодействия группы симметрииправильного треугольника.Решение. Группа симметрии правильного треугольника =группа диэдра D3 ∼= S3 , |D3 | = 6.3D3 = h t, s i, t = s2 = e, t2 s = st,t — вращение на 120◦ вокруг центра,s — отражение относительно оси симметрии.Элемент группы ge = (1)(2)(3)t = (123), t2 = (132)s = (1)(23), st, st2Цикловой индекс PS3 =16T ype(g)h 3, 0, 0 ih 0, 0, 1 ih 1, 1, 0 iw(g)x31x3x1 x2x31 + 2x3 + 3x1 x2 .кол-во123ПРИКЛАДНАЯ АЛГЕБРА.
Часть III: Теория перечисления Пойа62 / 70Задачи с решениямиЗадача ТП-3Найти цикловой индекс транзитивного самодействия группы Z6 .Решение. Обозначим последовательно вершины правильногошестиугольника буквами I, A, S, E, C, R.Z6 = hti, t6 = e, t — поворот на 60◦ .Элемент g группы Z6e = (I)(A) . .
. (R)g = (IASECR)g 2 = (ISC)(AER)g 3 = (IE)(AC)(SR)g 4 = (ICS)(ARE)g 5 = (IRCESA)PZ6 =T ype(g)h 6, 0, 0,h 0, 0, 0,h 0, 0, 2,h 0, 3, 0,h 0, 0, 2,h 0, 0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0i1i0i0i0i1iw(g)x61x6x23x32x23x61 61X6/dx1 + x32 + 2x23 + 2x6 =ϕ(d)xd .66d|6ПРИКЛАДНАЯ АЛГЕБРА. Часть III: Теория перечисления ПойаЗадачи с решениямиЗадача ТП-4Определить число различных раскрасок правильнойчетырёхугольной пирамиды П в 3 цвета.Решение.
Занумеруем последовательно боковые грани Пчислами 1, . . . 4, а основание — 5.G ∼= Z4 = h t i, t — вращение на 90◦ .Элемент группы gT ype(g)w(g)e = (1)(2)(3)(4)(5) h 5, 0, 0, 0, 0 i x51r = (1234)(5)h 1, 0, 0, 1, 0 i x1 x42r = (12)(34)(5)h 1, 2, 0, 0, 0 i x1 x223h 1, 0, 0, 1, 0 i x1 x4r = (1432)(5)1 5x1 + 2x1 x4 + x1 x22 ,P (x1 , .
. . , x5 ) =435 + 2 · 32 + 339 · (27 + 2 + 3)9 · 32P (3, . . . , 3) ==== 72.44463 / 70ПРИКЛАДНАЯ АЛГЕБРА. Часть III: Теория перечисления Пойа64 / 70Задачи с решениямиЗадача ТП-5Сколькими геометрически различными способами три абсолютноодинаковые мухи могут усесться в вершинах правильногосемиугольника, нарисованного на листе бумаги?Решение. Множество T — вершины семиугольника, на которыедействует группа Z7 = h t i, t7 = e.Элемент g ∈ Z7et, t2 , .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
