Элементы теории Пойя Лемма Бернсайда



Скачать 221.28 Kb.
Дата04.08.2016
Размер221.28 Kb.
  • Элементы теории Пойя

  • Лемма Бернсайда


Пусть - непустое конечное множество, а - действующая на нем группа, т.е. некоторая подгруппа симметрической группы . Элементы назовем эквивалентными, если для некоторой подстановки выполняется .

Легко проверяется, что тем самым действительно определено отношение эквивалентности на . Обозначим его .

Для произвольно фиксированного рассмотрим множество всех подстановок в , для которых является неподвижной точкой, т.е. .

Докажем, что - подгруппа . Действительно, тождественная подстановка . Далее, если , то , откуда . Наконец, при получаем: , т.е. . Подгруппа называется стабилизатором (или стационарной подгруппой) элемента .

Обозначим через множество всех подстановок, переводящих в .

Утверждение 1. Число всех подстановок, которые переводят в , равно порядку стабилизатора элемента , т.е., .

Доказательство. Определим отображение подгруппы в множество всех подстановок, переводящих в , следующим образом: (для фиксированной подстановки , переводящей в ). Легко видеть, что инъекция ( влечет ). Докажем, что сюръекция. Если переводит в , то , а так как , т.е. , то каждая подстановка, переводящая в , есть образ при отображении некоторого элемента подгруппы .

Итак, биективно отображает на смежный класс , и каждая подстановка, переводящая в , есть элемент этого класса. Но, как известно, (для любой подстановки ), и .

Можно заметить, что если , то , так как каждой подстановке, переводящей в , соответствует обратная подстановка, и . Это значит, что порядки групп-стабилизаторов всех эквивалентных элементов одинаковы.

Класс эквивалентности элемента называют орбитой этого элемента. Число элементов в орбите будем обозначать .



Утверждение 2. Индекс подгруппы в группе равен числу элементов в классе эквивалентности (орбите) .

Доказательство. Индекс равен, как известно, числу левых (или правых) смежных классов подгруппы . Множество всех правых смежных классов подгруппы обозначим . Т.е. .

Определим отображение орбиты в следующим образом: , где . Отображение инъективно, так как при предположение влечет равенство смежных классов , где . Но тогда в силу утверждения 1 каждая подстановка класса переводит в и, в частности, , что невозможно. Но отображение и сюръективно, так как класс . Итак, - биекция, и .


Из доказанного вытекает также, что если эквивалентны , то число отображений, переводящих в , также равно , так как оно составит число элементов в смежном классе , где . Но .
По теореме Лагранжа получаем, что .

Согласно утверждению 2, , или , так как порядки стабилизаторов всех эквивалентных элементов одинаковы.



Замечание. Соотношение интересно и само по себе, так как позволяет найти порядок группы по известным порядку стабилизатора произвольно выбранного элемента и числу элементов в орбите . Так, в частности, можно вычислить порядок группы автоморфизмов графа.

Пусть теперь - число классов эквивалентности по отношению , и попарно неэквивалентные представители этих классов. Тогда



. В этой сумме суммируются порядки стабилизаторов всех элементов множества , разбитого на классы эквивалентности, т.е. . Отсюда следует, что число классов эквивалентности по отношению составит .

Стоящая в записанном выражении сумма есть число всех элементов группы , оставляющих неподвижным какой-либо элемент множества . Но это же число можно получить, суммируя по всем подстановкам, оставляющим неподвижными некоторый ёё элемент (в указанной выше сумме каждая подстановка учитывается столько раз, сколько элементов множества она оставляет неподвижным1). Тогда получим



,

где через обозначено число всех элементов множества , являющихся неподвижными точками подстановки .

Полученный результат известен как лемма Бернсайда о подсчете.
Примеры. 1) Пусть , а группа порождается подстановками (12) и (34). Тогда . Следовательно, . Стабилизаторы: , и по другому способу подсчета

Далее, пусть , тогда все элементы, переводящие 1 в 2, суть элементы правого смежного класса , а .

2) Пусть множество есть множество функций из конечного множества в конечное множество , - группа, действующая на множестве . Определим действие группы на множестве функций следующим образом: , и эквивалентность функций и определим так: .

Пусть (содержательно, первое множество есть множество вершин треугольника, а второе – множество «цветов», {красное, черное}).

Все 8 функций из в опишем в виде такой формальной суммы:

Группа определяется как симметрическая группа степени 3, т.е. . Тогда , Тогда по лемме Бернсайда получается . Классы эквивалентных функций: . Тогда, например, порядок группы = 6 может быть получен как произведение порядка стабилизатора , равного 6, на число функций, эквивалентных , т.е. единицу; или произведение порядка стабилизатора , равного 2, на число функций, эквивалентных , т.е. 3, и т.д. Подстановка (23) переводит функцию в функцию , а все подстановки, переводящие в , образуют смежный класс , а подстановки, переводящие в , образуют смежный класс .

Сопоставим каждой «краске» (или «цвету», т.е. элементу множества ) вес в виде рациональной переменной: . Тогда каждой функции из можно сопоставить вес как произведение весов ее значений. Нетрудно сообразить, что эквивалентными могут быть только функции одинакового веса (обратное неверно, как скоро будет показано!). С учетом этого описание классов эквивалентных функций данного примера может быть представлено таким полиномом: . Здесь все функции одинакового веса оказались эквивалентными.

В последующем изложении мы обобщим результаты этого простого примера.


  1. Функции разметки

Пусть на множестве задана функция , отображающая в множество меток (красок, цветов) . Такая функция называется функцией разметки, или функцией раскраски (или просто раскраской). Действие группы на множестве стандартным образом распространяется на множество всех раскрасок: (для каждого ). Эквивалентность раскрасок означает тем самым, что для некоторой подстановки имеет место равенство , т.е. для каждого выполняется . Число классов эквивалентности на множестве раскрасок определяется по лемме Бернсайда.


Каждому элементу множества , называемому запасом (это, образно говоря, некое множество «красок», или «цветов») сопоставим вес в виде рациональной переменной. Тогда каждой функции разметки может быть также сопоставлен вес в виде произведения

,

а всему множеству сопоставляется так называемый перечень в виде полинома над полем рациональных чисел:



(обозначение Invt производится от английского слова inventory – перечень, инвентарь).

Можно показать, что перечень может быть представлен также в виде:

.

(Сумма в квадратных скобках называется перечнем запаса).

Действительно, получаем одинаковых сомножителей, а при раскрытии скобок каждое слагаемое (произведение сомножителей) отвечает некоторому выбору элемента запаса по номеру элемента множества , т.е. номеру сомножителя (скобки), и, тем самым, это слагаемое есть не что иное, как вес некоторой функции разметки.

Например, при раскраске вершин квадрата двумя цветами получим



,

где


, , ,

что отвечает всем возможным способам окраски вершин квадрата двумя цветами (красным (red) и голубым (blue)). Например, слагаемое означает, что существует четыре функции разметки, при которых три вершины покрашены в голубой, а одна – в красный цвет (что очевидно).

Нетрудно показать, что эквивалентные функции (раскраски) имеют одинаковый вес.

Действительно, если некоторая функция эквивалентна функции , то найдется такая подстановка , что и


где мы полагаем, что . Очевидно, что возникает перестановка элементов в виде , а так как веса, как рациональные переменные, коммутируют, то записанное выше произведение совпадет с произведением



,

что и требовалось.

Заметим, что обратное неверно, т.е. могут быть неэквивалентные функции одинакового веса.
Наша задача состоит теперь в том, чтобы найти перечень классов эквивалентности (по отношению ) раскрасок.

Рассмотрим частный случай, когда множество разбито на подмножества , и все такие функции разметки, каждая из которых постоянна на любом подмножестве . Вес какой-либо из таких функций может быть представлен термом , где через обозначен вес «цвета» . Т.е., все элементы множества «покрашены» цветом и т.д. Тогда структурный перечень множества всех таких функций может быть представлен произведением



,

где предполагается, что .

Имея в виду лемму Бернсайда, примем во внимание следующее соображение. Пусть подстановка разложена на независимые циклы: . Нетрудно сообразить, что для того, чтобы цикл сохранял раскраску (т.е. оставлял ее неподвижной), необходимо и достаточно, чтобы все его элементы были одного цвета, т.е., более формально, чтобы функция разметки принимала на нем постоянное значение. Таким образом, каждый цикл сохраняет раскрасок, а вся подстановка сохранит раскрасок, т.е. , причем перечень всех функций разметки, сохраняемых подстановкой , будет иметь вид:

,

где - число циклов длины в разложении , .



  1. Теорема Пойя


Цикловым индексом конечной группы называется многочлен над полем рациональных чисел, построенный следующим образом: каждой подстановке , разложенной на независимые циклы: , сопоставляется произведение (мультипликативный терм) , где есть число всех циклов длины в подстановке (предполагается, что - наибольшая длина цикла в группе , и, конечно, ); тогда .
Пример. Рассмотрим группу симметрий квадрата, или, что то же самое, группу автоморфизмов графа, изображенного ниже:

Сведем построение циклового индекса этой группы в следующую таблицу:




=(1)(2)(3)(4) (1234) (13)(24) (4321) (12)(34) (13)(2)(4) (24)(1)(3) (14)(23)

В итоге получаем цикловой индекс:



.

Под структурным перечнем классов эквивалентности функций разметки (или перечнем классов эквивалентности раскрасок, перечнем попарно неэквивалентых раскрасок) будем называть сумму



,

где суммирование ведется по весам всех функций, причем коэффициент показывает, сколько имеется попарно неэквивалентных функций веса (или, что то же самое, сколько классов эквивалентности покрывают функции данного веса).

Основной результат (теорема Пойя) состоит в следующем:
Перечень классов эквивалентности раскрасок равен

.

Число неэквивалентных раскрасок составляет

.
Подробное доказательство не приводится, но сформулированный результат достаточно ясно усматривается из леммы Бернсайда и соотношения (1).
Идея доказательства. Во-первых, заметим, что число всех функций (раскрасок), сохраняемых подстановкой составляет , и это число получается подстановкой на место каждой переменной в цикловом индексе группы . Тогда остается воспользоваться леммой Бернсайда.

Во-вторых, подставляя в терм веса элементов множества , получим выражение ,

где для краткости мы обозначили через вес элемента (при этом ). Это выражение есть не что иное, как перечень всех функций, сохраняемых (оставляемых неподвижными) подстановкой . Заметим также, что если вместо каждого веса подставить единицу, то число , (2)

т.е. составит число всех классов эквивалентности (а первая сумма в (2) равна числу слагаемых в терме после раскрытия скобок).

Рассмотрим подробнее структуру выражения . Этот мультипликативный терм от переменных , как было уже замечено, есть перечень всех функций (раскрасок), сохраняемых подстановкой и распределенных по весам (после приведения подобных членов). Например, если , , то , а ,

что означает, что среди всех функций, сохраняемых , по одной, принимающих постоянное значение, по две, которые красят три элемента одним цветом, а четвертый – другим, и две функции, распределяющие краски по две.

Следовательно, можно утверждать, что , где - сумма всех слагаемых одинакового веса , т.е. для некоторого натурального числа , а - множество весов всех функций, сохраняемых подстановкой .

Тогда


где , а суммирование ведется по всем весам функций разметки.

Общее число слагаемых (с учетом деления на и коэффициентов ) равно числу классов эквивалентности – в силу соотношения (2). Осталось доказать, что частное есть целое число, равное определенному выше числу .

Если рассматривать действие группы только на множестве функций заданного веса , то число классов эквивалентности на этом множестве составит, согласно лемме Бернсайда, , где - число всех функций веса , сохраняемых подстановкой (это не что иное, как введенный выше коэффициент ). Но сумма всех есть как раз число всех функций веса (где каждая функция сохраняется какими-то подстановками2), т.е. это число равно , а частное есть не что иное, как число попарно неэквивалентных функций веса , или, что то же самое, число классов эквивалентности, покрываемых функциями веса , т.е. это определенное выше число .

Итак,

,

и указанная выше замена в цикловом индексе группы действительно дает перечень классов эквивалентности, распределенных по весам функций.


Пример. 1) Для перечня неэквивалентных двухцветных раскрасок квадрата тогда имеем:


Общее число таких раскрасок составит 6=1+1+2+1+1. Это число может быть получено и подстановкой 2 на место каждой переменной циклового индекса.

2) Цикловой индекс группы автоморфизмов графа

будет иметь вид:

.
Число неэквивалентных двухцветных раскрасок этого графа составит 10.
3) Пусть дано множество и отображение , сопоставляющее каждому элементу его «кратность»3. Полагая в данном случае группу тривиальной и состоящей из одного тождественного преобразования, мы можем составить перечень всех отображений такого вида, определяя вес «кратности» элемента как , в форме произведения

Это можно записать и в таком виде: . Мы получили производящую функцию для всевозможных сочетаний с повторениями из элементов. Если нам нужно только число таких сочетаний, то, подставив вместо каждого единицу, получим



.

Это не что иное, как производящая функция для сочетаний с повторениями (произвольными) из элементов по .

Можно наложить ограничения на число повторений того или иного элемента множества . В частности, если считать, что каждый элемент может повторяться не более одного раза, получим перечень подмножеств множества (или перечень их характеристических функций):

При (для каждого ) получим бином - производящую функцию для числа сочетаний без повторений.


Другой пример: пусть . Рассмотрим всевозможные сочетания этих элементов, в которых первый элемент встречается не менее двух и не более четырех раз, второй – один или два раза, третий – не более одного раза.

Имеем перечень:



.

Раскрывая скобки и приводя подобные члены, получим:



Действуя таким же образом, можно решить, например, и такую задачу:

сколькими способами можно распределить фишек между тремя игроками так, чтобы двое из трех получили одинаковое количество фишек.
Здесь множество есть множество игроков, а число фишек, получаемых игроком, есть его «кратность». Нас интересуют все функции, принимающие постоянное значение на подмножестве . Используя соотношение (1), получаем такой перечень («индивидуализация» игроков и фишек нас не интересует, поэтому вес числа фишек полагается равным ):


Раскладывая последнюю дробь на элементарные, получим:

.

Нас интересует коэффициент при . Он равен:



,

т.е. при нечетном , и при четном .

Так при имеем 5 способов: (4+4)+1, (3+3)+3, (2+2)+5, (1+1)+7, (0+0)+9;

при 6 способов: (5+5)+0, (4+4)+2, (3+3)+4, (2+2)+6, (1+1)+8, (0+0)+10.



1 Можно рассуждать и так: введем соответствие . Тогда сумма равна числу всех пар в соответствии , а сумма равна числу пар в обратном соответствии, что, как легко заметить, есть то же самое.

2 Заметим, что каждая функция фигурирует в этой сумме не один раз, а столько раз, сколькими подстановками она сохраняется.

3 Это есть не что иное, как мультимножество над A.



Поделитесь с Вашими друзьями:


База данных защищена авторским правом ©uverenniy.ru 2019
обратиться к администрации

    Главная страница