В.П. Воронин - Дополнительные главы дискретной математики (1127085), страница 12
Текст из файла (страница 12)
В случае вращений с симметриямиN (G) = 1561 62 + 2 · 2 + 2 · 22 + 23 + 3 · 24 + 3 · 23 == 13.12127. Найти цикловой индекс групп вращений вершин и ребер тетраэдра. Решение. Группы вращений вершин и ребер тетраэдра содержат по 12 перестановок: тождественную, восемьперестановок, отвечающих выбору одной из четырех осей, проходящих через одну из вершин и середину противоположной грани, а затем вращения вершин тетраэдра на 2π/3 и 4π/3, а также три перестановки, отвечающие1.3. ПРОСТЕЙШИЕ ПЕРЕЧИСЛИТЕЛЬНЫЕ ЗАДАЧИ41выбору одной из трех осей, проходящих через середины противоположных ребер, а затем вращения вершин тетраэдра на π.A AAAAHA`HHHРассмотрим случай вращения вершин. Тождественная перестановка образует 4 цикла единичной длины.
Каждоевращение вокруг оси, проходящей через вершину, образует одну петлю и один цикл длины 3, а вращения вокругреберных осей образуют два цикла длины 2. Таким образом,1 4Z (GV ; x1 , x2 , x3 , x4 ) =x1 + 8x1 x3 + 3x22 .12В случае вращения ребер тождественная перестановка образует шесть петель, вращения вокруг вершинных осейобразуют по два цикла длины 3, а вращения вокруг реберных осей — две петли и два цикла длины 2.
Такимобразом,1 6Z (GE ; x1 , x2 , x3 , x4 , x5 , x6 ) =x1 + 8x32 + 3x12 x22 .128. Найти вес орбит раскрасок граней куба по группе вращений в два цвета с весами 1, x. Решение. Группа вращений и симметрий состоит из 24 перестановок: тождественной, трех поворотов на πвокруг прямых, соединяющих центры противоположных граней, шести поворотов на π/2 вокруг прямых, соединяющих центры противоположных граней, шести поворотов на π вокруг прямых, соединяющих середины противоположных ребер и восьми поворотов на 2π/3 вокруг прямых, соединяющих противоположные вершины. Ониобразуют соответственное число циклов: восемь петель, две петли и два цикла длины 2, две петли и один циклдлины 4, три цикла длины 2 и два цикла длины 3. Соответственно цикловой индекс группы вращений равен1 6Z (G; x1 , x2 , x3 , x4 , x5 , x6 ) =x1 + 3x12 x22 + 6x12 x4 + 6x23 + 8x32 .24Вес раскраски по теореме Пойа 1.9 равенZ G; 1 + x, 1 + x2 , 1 + x3 , 1 + x4232 1 =(1 + x)6 + 3 (1 + x)2 1 + x2 + 6 (1 + x)2 1 + x4 + 6 1 + x2 + 8 1 + x324= 1 + x + 2x2 + 2x3 + 2x4 + x5 + x6 .9.
Найти вес раскрасок пирамиды из 10 шариков (основание составляют шесть шариков, сложенных в виде правильного треугольника, поверх них лежат, касаясь друг друга еще три, пирамиду замыкает десятый, лежащий натрех верхних) по группе вращений в два цвета с весами 1, x. Решение. Группа вращений здесь совпадает с группой вращений тетраэдра.
При этом тождественная перестановка образует 10 петель, вращения вокруг вершинных осей образуют одну петлю и три цикла длины 3, авращения вокруг реберных осей — две петли и четыре цикла длины 2. Таким образом,1 10x1 + 8x1 x33 + 3x12 x24 .Z (G, x1 , . . . , x10 ) =12Вес раскраски по теореме Пойа 1.9 равенZ G, 1 + x, 1 + x2 , 1 + x334 1 (1 + x)10 + 8 (1 + x) 1 + x3 + 3 (1 + x)2 1 + x2=12= 1 + 2x + 5x2 + 14x3 + 22x4 + 24x5 + 22x6 + 14x7 + 5x8 + 2x9 + x10 .42ГЛАВА 1. КОМБИНАТОРИКА10. Найти вес орбит по группе вращений и симметрий раскрасок витража 2 × 2 в три цвета с весами 1, x, y. Решение. Группа вращений содержит 8 перестановок: тождественную, образующую 4 петли, вращения на π/2и 3π/2, образующие один цикл длины 4, вращение на π, образующее два цикла длины 2, две симметрии относительно диагоналей, образующие две петли и один цикл длины 2, а также две симметрии относительно осей,проходящих через середины противоположных ребер, образующие по два цикла длины 2.
Таким образом,Z (G; x1 , x2 , x3 , x4 ) =1 4x + 2x4 + 3x22 + 2x12 x2 .8 1Вес раскраски по теореме Пойа 1.9 равенZ G; 1 + x + y, 1 + x2 + y2 , 1 + x3 + y3 , 1 + x4 + y421=(1 + x + y)4 + 2 1 + x4 + y4 + 3 1 + x2 + y2 + 2 (1 + x + y)2 1 + x2 + y28= 1 + x + y + 2x2 + 2xy + 2y2 + x3 + 2x2 y + 2xy2 + y3 + x4 + x3 y + 2x2 y2 + xy3 + y4 .Упражнения.1. Найти цикловой индекс группы вращения вершин куба.2. Найти цикловой индекс группы вращения ребер куба.3. Найти цикловой индекс группы вращения вершин октаэдра.4.
Найти цикловой индекс группы вращения ребер октаэдра.5. Найти цикловой индекс группы вращения граней октаэдра.6. Найти цикловой индекс группы вращения витража.7. Найти цикловой индекс группы вращения пластины.1.4Частично упорядоченные множестваОсновные понятия. В параграфе, посвященном бинарным отношениям, уже вводилось понятие частично упорядоченного множества, и рассматривался пример (N, 6). Напомним, что частично упорядоченным множество называетсяпара(P, 6) ,где P — некоторое множество, а 6 — бинарное отношение частичного порядка, то есть бинарное отношение, удовлетворяющее аксиомам рефлексивности, транзитивности и антисимметричности:1. для любого x ∈ P выполняется xρ x;2.
для любых x, y, z ∈ P выполняется xρ y & yρ z ⇒ xρ z;3. для любых x, y ∈ P выполняется xρ y & yρ x ⇒ x = y.Если вдобавок выполняется еще и ∀ x, y ∈ P ⇒ x 6 y ∨ y 6 x, то пара (P, 6) называется вполне упорядоченным множеством. Если же это не верно, то элементы, для которых x y & y x, будем называть несравнимыми и обозначатьx ⊃⊂ y. Введем также уточняющие знаки: если x 6 y, x 6= y, то x < y. Введем также очень важное в дальнейшем понятиеинтервала: это множество[x, y] = {z ∈ P | x 6 z 6 y} .В случае [x, y] = {x, y} и x 6= y, будем говорить о непосредственном предшествовании x l y.
В терминах диаграммы Хассеэто означает, что между x и y есть дуга.Важным примером частичного порядка является множество всех подмножеств булева куба Bn , упорядоченных повключению (Bn , ⊆). Он изоморфен множеству всех (2n ) подмножеств конечного n-элементного множества, упорядоченных по включению, а также множеству всех наборов из нулей и единиц длины n, упорядоченных лексикографическипри 1 > 0.Определение 1.4.1. Частичным порядком, двойственным к частичному порядку (P, 6) называется частичныйпорядок (P, 61 ), где x 61 y ⇔ y 6 x. В дальнейшем, определяя что-то для частичного порядка (P, 6) по двойственности, будем подразумевать, что определяется то же самое, но для частичного порядка (P, 61 ).431.4.
ЧАСТИЧНО УПОРЯДОЧЕННЫЕ МНОЖЕСТВАОпределение 1.4.2. Элемент частично упорядоченного множества (P, 6), называется минимальным, если @ y ∈ P :y < x. Иными словами, ∀ y ∈ P ⇒ x < y ∨ x ⊃⊂ y. По двойственности определяется понятие максимального элемента.Заметим, что минимального элемента может и не быть, а в случае существования минимальных элементов, их можетбыть несколько.```I@66@I@@@@@@`@`@`(1.71)Так, например, на рисунке (1.71) все элементы нижнего слоя являются минимальными.Определение 1.4.3.
Элемент z частично упорядоченного множества (P, 6), называется наименьшим (нулем), если∀ x ∈ P : z < x. По двойственности определяется понятие наибольшего элемента (единицы).Заметим, что наименьший элемент (если он есть) является минимальным. Также, если минимальный элемент существует, то он единственен. На диаграмме Хассе (1.71) нет наименьшего элемента.Определение 1.4.4.
Подмножество Q ⊆ P частично упорядоченного множества (P, 6) называется цепью, если любыедва элемента из Q сравнимы.Определение 1.4.5. Подмножество Q ⊆ P частично упорядоченного множества (P, 6) называется антицепью, еслилюбые два элемента из Q не сравнимы.Сформулируем теперь условие на частично упорядоченные множества, с которыми мы в дальнейшем будем работать.Цепное условие Жордана-Дедекинда. Каждый интервал конечен и длины максимальной неуплотняемой цепи между любыми двумя элементами одна и та же.Это условие определяет так называемые ранжированные частично упорядоченные множества.
Сразу оговоримся, что существуют множества, на которых ввести функцию ранга невозможно — неранжированные, такие, какпентагон:I`J]J`J6J``I@@@`0Пусть частично упорядоченное множество удовлетворяет условию Жордана-Дедекинда и имеет наименьший элемент0. Тогда можно по индукции определить функцию ранга:1. rank (0) = 0;2. a l b =⇒ rank (a) + 1 = rank (b).На содержательном уровне, такое множество должно иметь слои.2 `2 `2 ``@ @6I6I66@ @`@`@`1111 `I@I@@@@`@1 `121`Так, например, частично упорядоченное множество натуральных чисел по делимости ранжируемо: для любого числаs n = pα1 1 · · · pαs s функция ранга равна rank n = ∑ αi . Заметим при этом, что мощность интервала [1, n] = mm|n равнаsi=1∏ (1 + αi ), а интервал [m, n] изоморфен интервалу 1, mn . Если множество ранжируемо, то любой его слой являетсяi=1антицепью.Определение 1.4.6.
Длина цепи от нуля до единицы (если оба элемента существуют) называется длиной множества.Определение 1.4.7. Наибольшая длина антицепи называется шириной множества.44ГЛАВА 1. КОМБИНАТОРИКАУже изучавшееся в параграфе 1.2 частично упорядоченное множество (неупорядоченных) разбиений конечногомножества, упорядоченное по подразбиениям, носит название Беллиана, а диаграммы Хассе, соответствующие этимчастичным порядкам называются диаграммами Юнга. Соответственно диаграммы Хассе, соответствующие частичноупорядоченным по подразбиениям множествам упорядоченных разбиений, называются графами Феррера.Введем ряд операций над частичными порядками. Пусть имеются два частично упорядоченных множества (P, 6P ) и(Q, 6Q ) , P ∩ Q = ∅.Определение 1.4.8.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
