Теорема Пойа
По этой ссылке вы найдёте полный курс лекций по математике:
| Решение задач по математике |
эквивалентности , если Пусть элементам г € Я приписаны веса Цг) (элементы некоторого коммутативного кольца). В предыдущем параграфе указано, как задается вес функции и вес класса эквивалентности W(F). ' Теорема. Сумма весов классов эквивалентности равна где Рс — цикловой индекс группы подстановок G. Прежде, чем доказывать саму теорему, укажем на ее простое Следстаие. Число классов эквивалентности равно Действительно, если положить вес каждого элемента R равным 1, то и вес каждой функции, и, значит, каждого класса эквивалентности будет равен 1; поэтому сумма весов всех классов эквивалентности будет равна их числу.
Доказательство теоремы Пойа. Пусть Sw — множество функций, имеющих вес w: Теорема Пойа Обозначим через Ти(д) число функций веса w, инвариантных относительно подстановки д £ G, т.е. таких, что . Тогда (о Докажем, что число классов эквивалентности для множества Sw равно (2) Доказательство основывается на лемме Бернсайда. Если / € Sw, то для произвольной подстановки д € G функция также имеет вес w (ввиду эквивалентности ~ /; как было доказано в предыдущем параграфе, эквивалентные функции имеют одинаковый вес).
Следовательно, подстановка д, действующая на множестве Z), задает подстановку функций из множества 5W; обозначим ее жд: Нетрудно убедиться в том, что соответствие д тгд является гомоморфизмом. Действительно, для любой функции / то есть ъдф = тгр2. Осталось заметить, что отношения эквивалентности, порожденные на множестве Sw подстановками д (действующими на множестве D) и подстановками жд (действующими на самом множестве Sw), совпадают; а инвариантность функции / относительно д означает ее инвариантность относительно . Теперь непосредственное применение леммы Бернсайда дает (2).
Зная число классов эквивалентности Nw для любого (фиксированного) веса w, запишем соотношение для суммы весов всех классов эквивалентности: Применив (1), получим: Теорема Пойа Как отмечалось в § 1, подстановка д разбивает множество D на орбиты, элементы которых циклически переставляются данной подстановкой. Если fg = /, то на каждой такой орбите функция / постоянна: Верно и обратное. Пусть функция / постоянна на каждой орбите, порожденной подстановкой д.
Тогда для любого.элемента d € Dy что означает: Таким образом, множество функций, инвариантных относительно д, совпадает с множеством функций, принимающих постоянные значения на орбитах, порожденных подстановкой д (обозначим Поэтому можно применить соотношение (3) из предыдущего параграфа: Если у подстановки д тип (т.е. имеется к\ орбит длины 1, к2 орбит длины 2 и т.д.), то, перегруппировав множители в последнем произведении, получим: Найденное произведение можно рассматривать как результат замены переменных в цикловом индексе подстановки д, равном , значениями сумм соответствующих степеней весов элементов г € Я.
Таким образом, согласно (3) сумма весов классов эквивалентности есть среднее арифметическое (по множеству G) цикловых индексов подстановок д е G при указанных значениях переменных Теорема доказана. В этом параграфе теорема Пойа будет применена к решению ряда комбинаторных задач. 1. Начнем с задачи о числе существенно различных раскрасок вершин тетраэдра в к цветов (решенной ранее с помощью леммы Бернсайда).
Здесь D — множество вершин тетраэдра; R — множество цветов, |Я| = к\ G — гр#ипа подстановок вершин тетраэдра, порожденных вращениями тетраэдра; RD — множество раскрасок. Класс эквивалентности в множестве RD составляют раскраски, которые переходят друг в друга в результате вращений тетраэдра. Таким образом, задача сводится к подсчету числа классов эквивалентности. Цикловой индекс группы G был найден в § 1: Применив следствие из теоремы Пойа, получим тот же ответ, что и ранее (см. § 2):
Заметим, что применение теоремы Пойа позволяет найти не только обшее число существенно различных раскрасок, но и определить число таких раскрасок при фиксированном распределении цветов. Если известно, какое количество вершин каким цветом должно быть покрашено, то тем самым задан вес раскраски. Коэффициент в инвентаре (сумме весов) / классов эквивалентности при соответствующем весе и есть искомое число. 2.
Задача о перечислении изомеров органических молекул заданной структуры (рис. 3), где С — атом углерода, а места, обозначенные крестиками, могут занимать метил , водород (Н) и хлор (С1). Математическая модель этих молекул — тетра- 1 эдр, в центре которого расположен атом углерода. Расположение х в вершине тетраэдра определенной группы атомов будем считать рис 3 покраской вершины в определенный цвет (один из четырех). Таким образом, задача сведена к предыдущей (при к = 4).
Возможно вам будут полезны данные страницы:
| Следствия закона Авогадро |
| Химическая термодинамика |
| Форматы чертежей по ГОСТ |
| Некоторые виды уравнений, интегрируемых в квадратурах |
Обшее число молекул равно Для того чтобы подсчитать число молекул с фиксированным числом атомов водорода, положим: Тогда вес молекулы с i атомами водорода будет равен xi. Применяя теорему Пойа, найдем инвентарь множества изомеров молекул: Значит, существует 1 молекула СН4 (метан), 3 молекулы с 3 атомами Н, 6 молекул с 2 атомами Н, 11 молекул с 1 атомом Н, 15 молекул без атома Н. 3. Задача о компостере. Компостером назовем двоичную матрицу 4x4. Здесь D — множество позиций элементов в матрице, .
Группа G подстановок множества D определяется группой самосовмешений квадрата (см. § 6 гл. LXVII) и состоит из 8 элементов: • тождественная подстановка е (порождающая 16 единичных орбит; ее цикловой индекс (ц.и.) х]6); Теорема Пойа • две подстановки, соответствующие поворотам на 90° по и против часовой стрелки (4 орбиты длины 4; цикловой индекс каждой из подстановок xj); • подстановка, соответствующая центральной симметрии (8 орбит длины 2; ц.и. xj); •
две подстановки, соответствующие осевым симметриям относительно вертикальной и горизонтальной осей • две подстановки, соответствующие симметриям относительно диагоналей (4 элемента остаются на месте, остальные разбиваются на пары; ц. и. х\х\). Цикловой индекс группы G равен Если отождествить компостеры, которые получаются друг из друга указанными преобразованиями2), то число различных компостеров определится так: Если читателю задача о числе компостеров кажется неактуальной, то можно указать на сводящуюся к ней задачу о фотошаблонах рисунков соединений интегральных схем (чипов). 4.
Задача о числе ожерелий.
Имеется неограниченный запас бусинок к цветов. Сколько можно составить различных ожерелий из п бусинок (ожерелья, получающиеся друг из друга плоскими вращениями, не будем различать)? Считая, что бусинки располагаются в вершинах правильного п-угольника, сведем задачу к задаче о числе геометрически различных (т. е. не получающихся друг из друга вращениями в плоскости) раскрасок вершин правильного п-угольника в к цветов. При этом D — множество вершин, R — множество цветов, — множество раскрасок. Отношение эквивалентности на множестве RD задается с помощью G — группы подстановок вершин, порожденной вращениями правильного n-угольника; Пусть где — подстановка, возникающая в результате поворота на угол (в частности, тождественная подстановка е = дп).
Тогда, если отождествить вершину с ее номером, положив (номера проставляются по порядку против часовой стрелки), то подстановка gj описывается соотношениями: Подстановка сводится к увеличению номера вершины на j по модулю п: Длину орбиты произвольного элемента можно найти как наименьшее натуральное число к, для которого kj делится на п. Если (п, j) — наибольший общий делитель , где j\ и п, - взаимно простые числа.
Поэтому ) делится на п = nt(n, j) тогда и только тогда, когда к делится на П], наименьшее натуральное к с таким свойством равно Итак, при повороте на угол ^£2 все орбиты имеют длину ^ , стало быть, число орбит равно (n,j). Запишем цикловой индекс группы подстановок: 2) Практическая задача, которой соответствует описываемая математическая постановка, очевидна: множеству D отвечают места возможных дырок, которые пробивает реальный компостер; 1(0) отвечает наличию (отсутствию) дырки в соответствующем месте; наконец, эквивалентные компостеры харакгерны тем, что по пробитому абонемент невозможно определить, на каком из них он был прокомпостирован.
По следствию из теоремы Пойа общее число раскрасок N выражается формулой: В полученной сумме показатели степеней к принимают значения делителей числа п. Несложно видеть, что общее количество чисел из множества {1, 2,..., п}, для которых их наибольший делитель с п равен d, где d|n, совпадает с количеством натуральных чисел, не превосходящих число \ и взаимно простых с ним, т.е. ~ функция Эйлера). Таким образом, Замечание.
Задача не слишком усложнится, если не отличать друг от друга также ожерелья, переходящие друг в друга в результате выполнения осевых симметрий; вместо группы вращений правильного n-угольника нужно будет рассматривать группу его симметрий. Упражнения 1. Пусть группа подстановок, действующая на множестве S: 1) Убедиться в том, что G — группа, составив для нее квадрат Кэли. 2) Отношение эквивалентности на S порождается группой G. С помошью леммы Бернсайда найти число классов эквивалентности.
3) Выписать классы эквивалентности в явном виде. Теорема Пойа 2. Составляются трехбуквенные слова из букв а и Ь. Два различных слова считаются эквивалентными, если они получаются друг из друга при перемене местами крайних букв; например, abb ~ bba. Определить число классов эквивалентности, пользуясь леммой Бернсайда. Выписать классы эквивалентности в явном виде. 3. Вокруг стола рассаживаются п человек.
Сколько существует различных расположений, если отождествлять такие, которые получаются одно из другого сдвигом всех людей по часовой стрелке на произвольное, но одинаковое для всех число мест? 4. На листках бумаги пишут числа от 00000 до 99 999 (числа, меньшие 10 000, дополняют слева нулями). Будем считать, что при переворачивании цифры 0, 1, 8 не меняются, а цифры 6 и 9 переходят друг в друга. Например, для чисел 06981 и 18 690 можно приготовить только один листок.
Сколько всего листков понадобится? 5. Составляются ожерелья из бусин трех цветов. Каждое ожерелье состоит из 1) 5; 2) 6 бусин. Не будем различать ожерелья, получающиеся друг из друга поворотом в плоскости. Пользуясь леммой Бернсайда, найти число различных ожерелий. 6. Решить предыдущую задачу в предположении, что не различаются ожерелья, получающиеся друг из друга поворотом в пространстве.
Решить задачи 5, 6 с помошью следствия из теоремы Пойа. 8. Сколько ожерелий можно составить из двух красных, двух зеленых и двух синих бусин в предположениях задач 5 и 6? 9. Завод выпускает погремушки в виде кольца с надетыми на него р красными и q синими шариками. Сколько различных погремушек может быть выпущено? Две погремушки считаются одинаковыми, если могут быть получены друг из друга передвижением шариков по кольцу или переворачиванием. 10.
| Доказать, что цикловой индекс |
группы подстановок на множестве вершин правильного п-угольника, порожденный его вращениями в плоскости, есть 11. Составляются ожерелья из П| бусинок 1-го вида, п2 бусинок 2-го вида,..пт бусинок m-го вида. Не считаются различными ожерелья, которые могут быть получены друг из друга вращением в плоскости.
Доказать, что число различных ожерелий равно где суммирование ведется по всем числам d, одновременно являющимся делителями чисел 12. Найти цикловой индекс группы подстановок на множестве вершин правильного п-угольника, порожденных группой его симметрий. 13. Сколькими способами можно раскрасить в к цветов 1) ребра; 2) грани тетраэдра, который может свободно вращаться в пространстве? 14. Сколькими способами можно раскрасить в к цветов 1) вершины; 2) ребра; 3) грани куба, который может свободно вращаться в пространстве? 15.
Сколькими геометрически различными способами можно раскрасить вершины куба в два цвета так, чтобы вершин каждого цвета былб поровну? 16. Сколькими способами можно раскрасить 5 ребер куба в синий цвет, а остальные ребра в красный цвет? 17. Найти число существенно различных способов размещения восьми одинаковых пометок на шахматной доске размера 8x8. Ява способа разметки считаются существенно различными, если их нельзя преобразовать друг в друга вращением доски или отражением относительно любой из четырех осей симметрии.
18. Конструктор интегральных схем строит чипы с 16 элементами, расположенными в виде матрицы 4x4. Чтобы реализовать различные схемы, эти элементы нужно соединять; непосредственно соединяются только элементы, соседние по горизонтали или по вертикали (рис.4). Чтобы напылить межкомпонентные соединения, необходим фотошаблон рисунка соединений. Для двух рисунков, показанных выше, используется один и тот же фотошаблон (схемы симметричны относительно диагонали).
Сколько требуется фотошаблонов для того, чтобы на этих чипах реализовать все возможные рисунки соединений? 19. Следующие две картинки (рис. 5) называются соответственно «Звезда Давида» и «Мечи Магомета». Рис. 5 Представим себе, что эти фигуры составлены из кусков проволоки, спаянных в точках пересечений. Сколько сушествует различных звезд и мечей с точки зрения вида пересечений?
Две фигуры отождествляем, если одну из них можно переместить в пространстве гак, что они становятся неразличимыми по виду пересечений (рис.6). В полученной сумме нижний индекс при х принимает значения всех делителей числа п. В качестве упомянутого индекса число d встретится столько раз, сколько есть чисел до п, для которых (n,j) = n/d. Такие числа имеют вил , где число к взаимно просто с d и не превосходит d.
Значит, d будет в качестве нижнего индекса ровно Применив теорему Пойа. выражение для циклового индекса из предыдущей задачи и полиномиальную формулу, получим: Нас интересует коэффициент при Указанное произведение возникает лишь при d, деляшем одновременно . Дальнейшее просто. Если п четно, то Теорема Пойа Если n нечетно, то