Л.А. Калужнин, В.И. Сущанский - Преобразования и перестановки (1127096), страница 16
Текст из файла (страница 16)
Сопоставим парам (а, т), а ен 6, т ен М, вершины прямоугольной сети и отметим те из них, для которых соответствующая пара (а, т) находится в указанном отношении, т. е. (т)а= 3 =т (рис. 32). Иными словами, построим график указанного. отношения. Число от- У меченных точек (точек, принад- лежащих графику) можно под"е ае ас " а се считать двУмЯ способами: опРис. 32 ределнть число отмеченных точек на каждой вертикали и просуммировать полученные величнны или же определить число таких точек .по каждой горизонтали и затем вычислить их сумму. Согласно определению отношения на каждой вертикали отмечаются все точки, сохраняемые перестановкой а, соответствующей этой вертикали.
Их число равно у (а). 'Поэтому число всех точек графика равно Х (ас) + Х (а 1) + ° ° . + Х (сси-1) = ~~ у (о) . аао С другой стороны, на каждой горизонтали отмечаются все перестановки, сохраняющие элемент т енМ, отвечающий этой горизонтали. Мы знаем, что они образуют группу 6 -стабилизатор элемента т — и их число, согласно предыдущей теореме, равно .
)6, | =)61: (6(т)(. а4 Поэтому при втором способе подсчета числа отмеченных точек графика рассматриваемого отношения получаем выражение ~6т!+~0в~+...+!6!= Х ~6 !. (2) ю2 е м Однако если элементы (, у ~ М содержатся в одной орбите, то О (() = 0 (у) н поэтому ! 6; ( = ! 6 ): ~ 0 (т) ! = ( 6 (: ! 0 ()) (= = ) Оу ~. Пусть 0„0„..., О, — все орбиты группы 6, такие, что М = О, () Оз ()... () Оы и слагаемые в этом объединении не пересекаются. Разобьем сумму (2) на части так, чтобы внутри каждой из частей суммирование шло по элементам некоторой орбиты: 'У', ~6 != ~ !6 !+ ~", !6„!+...+,'5, '~6 ~. ашМ тшо аатп Оз мшо Каждое из ~ слагаемых в правой части этого равенства можно преобразовать следующим образом.
иео Поэтому т ~а.1-~а~а-...а-~а~-~~а~. Таким образом, при втором способе подсчета мы полу- чили (~0~ отмеченных точек графика. Приравнивая вели- чины„полученные при первом и втором способах, получим У!6~= 'У, 'Х(а), ашС т. е. г=г(0) = —, ~ у(а). Лемма доказана. ! ~0~ .йы аж с В частности, если группа 6 транзитивная, т. е, г(6)=1, то по лемме Бернсайда !61= Х Х(сз) пшс Упражнении К Пусть 0 — группа симметрий куба. Найдите порядок стабилизатора некоторой вершины в втой группе. Какие перестановки в нем содержатся? 3. Проверьте правильность утверждения леммы Берисайда на примере группы 0 (пример 4 4 9).
85 3. Перестановки а и й из группы С сопряжены в ней, если в С найдется такая перестановка у, что у т ° а ° у=9. Доназать, что а) каждая перестановка сопряжена сама с собой; б) если перестановка а сопряжена с перестановкой Е, то и, наоборот, перестановка р сопряжена с перестановкой ак в) если а сопряжена с (), а () — с у, то сс сопряжена с у. 4.
Из свойств а), б), в) упражнения 3 следует, что множество С разбивается в объединение непересекающихся подмножеств перестановок, попарно сопряженных между собой, которые называются классами сопряженных перестановок группы С. Докажите это. 5. Если перестановки а н р сопряжены, то Х(а)=Х(()) г. е. функция Х постоянна на классах сопряженных элементов С. 6. Используя предыдущую задачу, показать, что формулу для определения числа орбит группы С можно переписать в виде г(с) = — „7„х фп ! 'Ю ~с~ .?, ' *' где Х; — общее значение Х(а) для перестановок Ьго класса сопряженных перестановок, ф — число перестановок в Ьм классе сопряженных перестановок, з — чксло классов сопряженных перестановок.
7. Доказать, что сопряженные перестановки имеют одинаковый тип. 8. Если перестановки сс и й сопряжены, то при любом и ы 2 перестановки сеч и Р" тоже будут сопряженнымн. Доказать это. Следует ли из сопряженности пар перестановок ам а| и рд, ()з сопряжевность их произведенийг 9. Группа вращений куба естественным образом определяет группу перестановок на множестве его ребер. Определить типы всех перестановок из этой группы. 1О. Каждое вращение куба естественным образом переставляет его грани, т. е, группа вращений куба определяет группу перестановок на множестве его граней. Доказать, что эта группа транзитивна.
Определить стабилизатор одной из точек (граней куба) в этой группе. $13. КОМБИНАТОРНЫЕ ЗАДАЧИ Рассмотрим два простых примера, иллюстрирующих возможности применения леммы Бернсайда при решении комбинаторных задач на перечисление. Ряд примеров читатель найдет также в упражнениях к этому параграфу.
1. Раскраска вершин куба. Сколькими способами можно раскрасить вершины куба в три цвета (например, красный, синий и зеленый)? На первый взгляд может показаться, что задача совсем простая. Поскольку каждую из восьми вершин куба можно раскрасить тремя способами, причем независимо от того, как раскрашены другие вершины, то множество всех вершин куба можно раскрасить Зз = 6561 различными способами. Однако при таком подходе к решению задачи 66 молчаливо предполагается, что мы умеем различать вершины куба перед окраской, т. е., скажем, куб жестко закреплен или его вершины занумерованы.
При этом полученный ответ можно интерпретировать следующим образом: можно так раскрасить 3' абсолютно одинаковых, жестко закрепленных кубов, что все они будут различаться. Для 3'+! кубов этого сделать уже нельзя. Ситуация существенно меняется, если мы откажемся от предположения о том, что кубы жестко закреплены, так как по-разному окрашенные кубы можно повернуть так, что в новом положении их окраски совпадут (рис. 33). « 1 « о-««««««л«н ° -нр«««ые «е««««-«««««н«««ем Рис.
ЗЗ Естественно считать, что два куба раскрашены одинаково, если их раскраски совпадают после некоторого вращения одного из кубов в пространстве. Будем говорить, что такие раскраски кубов геометрически неотличимы. Поэтому естественным уточнением задачи о раскраске является следующая задача: Сколькими геометрически различными способами можно раскрасить вершины куба в три цвета. Переформулируем теперь эту задачу так, чтобы стала понятной ее связь с леммой Бернсайда. Пусть М вЂ” множество всевозможных по-разному раскрашенных кубов одного размера, положенре которых в пространстве фиксировано, )М ~ =3«, 6 — группа всех вращений куба, состоящая из 24 перестановок.
Группа 6 естественным образом определяет группу перестановок на множестве М. Именно: если и он 6 — 'йекоторое вращение, то каждому кубу из М можно сопоставить некоторый, вообще говоря, другой куб, который получается из первого при вращении а. Это соответствие является, очевидно, перестановкой на множестве М, которую будем обозначать а.
Группу всех таких перестановок множества М, определяемых перестановками из 6, мы будем обозначать 6. Ясно, что!6)=)6). 87 То, что два куба К, и К, из М 'раскрашены геометриче= ски одинаково, означает, что один из них можно неревести вращением в такое положение, в котором они неразличимы. Иными словами, существует такая перестановка а еяО, что (К~)я =Км т. е.
К, и К, содержатся в одной орбите группы О, действующей на множестве М. Таким образом, для того чтобы определить число геометрически различимых способов раскраски вершин куба, нужно найти количество орбит группы 6 на множестве Л4. Считая вершины кубов занумерованными числами 1, 2, 3, 4, 5, 5, 7, 8, раскраску каждого из 3' кубов можно однозначно охарактеризовать «словом» из 8 букв, каждая из которых есть либо к, либо с, либо з. То, чго 1-я буква слова 'равна к (или с, или з), означает; что 1-я вершина при выбранной нумерации окрашена в красный цвет (или в синий, или в зеленый соответственно). Например, для кубпв, изображенных иа рис, 33, имеем соответственно последовательности ссззсскк, ссссккзз.
Перестановки из группы О переставляют такие последовательности. Например, если я = (1, 2, 3, 4) ° (5, б, 7, 8) е= О, то перестановка а слово сссссссз переводит в ссссзссс, слово ссззсскк переводит в сззссккс, слова сссссссс, кккккккк, зззззззз оставляет неизменными и т. д. Выписать всю таблицу значений для перестановки й затруднительно, поскольку она состоит из 3' строк! Для того чтобы применить лемму Бернсайда, необходимо определить число неподвижных точек каждой перестановки из О. Последовательность букв к, с, з будет неподвижной для перестановки а ен 6 тогда и только тогда, когда при разложении соответствующей перестановки а енО в произведение циклов вершины куба, номера которых входят в один и тот же цикл, окрашены одним цветом.
Например, если я=(1, 2, 3, 4) ° (5, б, 7, 8), то неподвижными относительно а будут слова, составленные целиком из одной буквы, и слова, составленные из двух разных букв, причем одна из них стоит на первых четырех местах в слове, а вторая — из четырех последующих. Поэтому имеется 9 неподвижных точек перестановки а на множестве М. Уже на этом примере видно, что подсчет числа неподвижных точек перестановок из О сильно упрощается, если известны разложения в произведение циклов соответствующих перестановок из О.
Если перестановка а ~ 6 разложена в произведение й-циклов, то число ее непо- ав движных точек равно За (1(А =.8). Поэтому сначала мы опишем разложения в произведение цикловдля всех перестановок из группы 0 вращений куба. а) Вокруг каждой из трех осей, соединяющих центры противоположных граней, имеется три нетождественных вращения. Им соответствуют перестановки (1, 5, 8, 4) (2, 6, 7, 3), (1, 4, 3, 2) (5, 8, 7, 6), (1, 8) (2, 7) (3, 6) (4, 5), (1, 3) (2, 4) (5, 6) (6, 8), (1, 4, 8, 5) (2, 3, 7, 6); (1, 2, 3, 4) (5, 6, 7, 8); (1, 5, б, 2) ° (3, 4, 8, 7), (1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
