Теорема Пойа и перечисление графов

 

Рассмотрим для примера  симметрическую группу . Заметим, что тождественная подстановка (1)(2)(3) имеет три единичных цикла дающих слагаемое . Три подстановки (1)(23), (2)(13) и (3)(12) имеют каждая по единичному циклу и по одному циклу длины 2, так что получается одно слагаемое . Наконец, подстановки (123) и (132) вносят . Таким образом, имеем 

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

Назовем разбиением натурального числа n его представление в виде суммы некоторых натуральных чисел. Заметим, что каждая подстановка a на n объектах может быть связана с определенным разбиением числа n, имеющим для каждого  точно  частей, равных числу k. Будем задавать разбиение числа n посредством вектора , где  — число частей разбиения, равных k. Итак,

 

 

 

Пример

4 = 1 + 1 + 1 + 1	(4, 0, 0, 0)
4 = 1 + 1 + 2	(2, 1, 0, 0)
4 = 2 + 2	(0, 2, 0, 0)
4 = 1 + 3	(1, 0, 1, 0)
4 = 4	(0, 0, 0, 1)

Пусть h(j) — число подстановок в группе , разложение которых на непересекающиеся циклы соответствует разбиению (j), в том смысле, что для каждого k выполняется . Тогда имеет место следующая лемма.

Лемма

   Таким образом, после приведения подобных членов в выражении (1.1), цикловой индекс  примет следующий вид.

Теорема

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

где сумма берется по всем разбиениям (j) числа n, а h(j) задается выражением  
(1.2).

Пример

3 = 1 + 1 + 1	(3, 0, 0)	h = 3! / 3! = 1
3 = 1 + 2	(1, 1, 0)	h = 3! / 1·1!·2·1! = 3
3 = 3	(0, 0, 1)	h = 3! / 3·1!

Иногда удобно расматривать производящую функцию цикловых индексов и пользоваться следующим свойством.

Теорема

где  по определению.

Часто бывает удобным выразить  через , где . Рекуррентная формула, следующая из (1.4), может быть представлена следующим образом.

Теорема

Цикловой индекс симметрической группы удовлетворяет рекуррентному соотношению

Пример

 

 

 

 

 

2.   Эквивалентность, порождаемая группой подстановок

 

Отношение эквивалентности

Отношение эквивалентности  на множестве   — это бинарное отношение, для которого выполнены следующие условия:

• Рефлексивность: для любого   в ,
• Симметричность: если , то ,
• Транзитивность: если   и , то .

Запись вида «  » читается как « a эквивалентно b».

Пусть A — группа подстановок с множеством объектов  . Элементы x и y из X называются A-эквивалентными, если существует подстановка a из A, такая, что . Нетрудно показать, что введенное нами отношение есть отношение эквивалентности. Множество X разбивается на классы эквивалентности. Эти классы называются орбитами.

Для каждого x из X положим

Так определенное множество A(x) называется стабилизатором элемента x. Нетрудно видеть, что стабилизатор является подгруппой группы A. Заметим, что всякий раз, когда элементы x и y принадлежат одной и той же орбите, множества A(x) и A(y) являются сопряженными подгруппами группы A (то есть существует такая подстановка a из A, что  и, следовательно, |A(x)| = |A(y)|.

Теорема

Для любого элемента y из орбиты Y группы A выполнятся следующее соотношение

|A| = |A(y)| · |Y|

Доказательство. Разложим группу A в объединение правых классов смежности по подгруппе A(y):

Теперь остается только указать  естественноe взаимно однозначное  соответствие между этими классами смежности и элементами орбиты Y. Для каждого  сопоставляем классу смежности элемент   из Y. Если i не равно j, то   y не равно  y, так как иначе бы подстановка  принадлежала подгруппе A(y) и, следовательно, подстановка   являлась бы элементом множества  A(y), что противоречит соотношению  A(y) ∩   A(y) = Ø. Значит, указанное соответствие является взаимно однозначным. Для всякого объекта y′ из Y при некоторой подстановке a из A выполняется равенство ay = y′. Из разложения группы A на классы смежности следует, что , если b принадлежит A(y). Следовательно,  и, таким образом, каждый элемент орбиты Y соответствует некоторому классу смежности. Значит, m есть число элементов в орбите Y и формула (1.7) доказана. 

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

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

Число N(A) орбит группы A дается формулой

 

Доказательство. Пусть — орбиты группы A, и для каждого  пусть  — элемент i-й орбиты . Тогда из формулы (1.7) имеем

Мы видели, что если x и принадлежат одной и той же орбите, то. Следовательно, соотношение (1.9) можно записать так:

 

или, в других обозначениях,

Теперь, меняя порядок  суммирования в правой части формулы (1.9) и изменяя соответствующим образом индексы суммирования, имеем

Но  есть в точности . Таким образом, для завершения доказательства надо обе части разделить на |A|.

Также нам нужно будет  ограничивать действие группы A на некоторое подмножество Y множества X, где Y   объединение каких-либо орбит группы A. Поэтому обозначим через A|Y множество подстановок, действующих на Y и получающихся с помощью ограничения на подмножество Y соответствующих подстановок группыA. Для каждой подстановки a из группы A число элементов в Y, неподвижных относительно подстановки a, обозначим через . Теперь можно сформулировать следствие леммы Бернсайда.

Ограниченная форма леммы  Бернсайда

 

3. Теорема Пойа

Пусть A — группа подстановок с множеством объектов и пусть B — конечная группа подстановок со счетным множеством объектов Y, содержащим не менее двух элементов. Тогда степенная группа, обозначаемая , имеет в качестве множества объектов совокупность  всех функций, действующих из X в Y. Подстановками группы  являются все упорядоченные пары подстановок a из A и b из B, записываемые в виде (a, b). Образ произвольной функции f из  при действии на нее подстановки (a, b) дается формулой

 

при всех x из X.

Для того, чтобы привести классическую формулу перечисления Пойа, мы возьмем B = E — единичной группе на множестве Y. Рассмотрим теперь степенную группу , действующую на множестве . Пусть  — функция, область значений которой является множеством неотрицательных целых чисел и для которой при всех k. В терминах теории перечисления  для каждого называют числом «фигур» веса k.

Об элементе y из Y, для которого , говорят, что он имеет вес k, а функцию w называют весовой функцией. Далее, ряд

относительно переменной x, который перечисляет элементы множества Y в соответствии с их весами, называют «перечисляющим рядом для фигур».

Вес функции f из YX определяется формулой

и тогда нетрудно показать, что функции, принадлежащие одной и той  же орбите степенной группы , имеют одинаковые веса. Весом w(F) орбиты F группы  назовем вес любой функции f из орбиты F. Так как для всякого k = 0, 1, 2, …, то существует только конечное число орбит каждого веса. Обозначим через  число орбит веса k. Ряд относительно переменной x назовем «перечисляющим рядом для функций» или «перечисляющим рядом для конфигураций».

Теперь мы можем сформулировать основную теорему, выражающую ряд C(x) в терминах циклового индекса Z(A) и ряда c(x). В приводимой ниже формуле Z(A, c(x)) является сокращением для Z(A, c(x), c(), c(), …).

Теорема (теорема  перечисления Пойа, 1927)

Ряд C(x), перечисляющий функции, получается с помощью подстановки в цикловой индекс Z(A) на место каждой переменной  ряда  перечисляющего фигуры. Символически:

Доказательство. Пусть e — тождественная подстановка на Y. Для всякой подстановки a из A и любого k = 0, 1, 2, … обозначим через φ(a, k) число функций веса k, неподвижных относительно подстановки (a; e). Ограничивая для каждого k действие степенной группы  на множество функций веса k и применяя ограниченную форму леммы Бернсайда (1.13), имеем

Следовательно,

 

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

 

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

Предположим, что функция f из  непожвижна относительно подстановки (a; e). Тогда для всех x из X и в силу формулы (1.14), имеем . Таким образом, для всех x должно выполняться равенство , то есть функция f должна быть постоянной на непересекающихся циклах подстановки a. Обратно, все функции, постоянные на циклах подстановки a, неподвижны относительно подстановки (a; e).

Пусть  — цикл длины r в подстановке a. Если функция f отображает элементы цикла  в один из  элементов множества Y, имеющих вес k, то цикл  вносит в вес функции f значение r·k. Тогда легко видеть, что для каждого k коэффициент при  в ряду

равен числу способов, которыми можно определить функцию f на элементах цикла   так, чтобы она была неподвижна относительно подстановки (a; e) и чтобы вклад в вес w(f) составлял r·k. Отсюда следует, что ряд  перечисляет в соответствии с их весами различные способы определения функций, постоянных на всех циклах длины r подстановки a.

Рассматривая все циклы подстановки a, мы можем выразить ряд для функций, постоянных на циклах, в виде произведения

Теперь утверждение теоремы  Пойа (18) следует из (1.21), (1.23) и определения циклового индекса Z(A).

 

 

 

 

 

 

 

2. Практическое применение Теоремы Пойа и перечисления

графов.

 

1. Решение задач о перечислении графов с помощью теоремы 

Пойа.

 

Мы будем перечислять  графы с n вершинами. Мы считаем, что  задана некая нумерация множества  вершин V, т.е. . Множество X, с которым мы будем работать, это множество функций, область определения которых – это множество пар вершин (т.е. пар чисел) , а область значений  это множество из двух элементов {0,1}. Такая функция полностью описывает граф: если i-я и j-я вершины не соединены ребром а если — то соединены. Иначе это можно описать так: рассмотрим полный граф , т.е. граф с n вершинами, где каждая пара вершин соединена ребром. Раскрасим множество ребер графа в два цвета — черный и белый. Теперь удалим белые ребра.

Группа перестановок действует  на множестве V (перенумерация вершин). Но она действует и на множестве следующим образом. Перестановку s мы рассматриваем как отображение множества {1, 2, . . . , n} в себя. Так перестановка s = 2, 4, 1, 3 — это отображение s : {1, 2, 3, 4} → {1, 2, 3, 4}: s(1) = 2, s(2) = 4, s(3) = 1, s(4) = 3. Перестановка s действует на множестве    так: s переводит пару (i, j) в пару (s(i), s(j)), если s(i) < s(j), и в пару (s(j), s(i)) в противном случае. В терминах теоремы Пойя множество — это множество M , а множество X — это множество раскрасок элементов в два цвета — черный и белый. Выбор раскраски задает граф, а перенумерация вершин дает другую раскраску , но изоморфный граф.

 

 

 

Пример. Пусть n = 4. Перестановка s = 2, 4, 1, 3 действует на так:

s((1,2))=(2,4),s((1,3))=(1,2),s((1,4))=(2,3),s((2,3))=(1,4)s((2,4))=(3,4)),s((3,4))= (1, 3).

Если

f ((1, 2)) = 0, f ((1, 3)) = 1, f ((1, 4)) = 0, f ((2, 3)) = 0, f ((2, 4)) = 1, f ((3, 4)) = 1, то

g((1, 2)) = 1, g((1, 3)) = 1, g((1, 4)) = 0, g((2, 3)) = 0, g((2, 4)) = 0, g((3, 4)) = 1,

где g = s(f ).

 

Функции f и g задают следующие  графы

Рисунок 2.1 – граф f.                           Рисунок 2.2 - граф g.

 

Разумеется эти графы  изоморфны.

Число графов — это число  орбит действия группы Sn  на множестве  раскраскок множества в два цвета. Чтобы найти число орбит нам нужно вычислить цикловый индекс действия   на .

Пример. n = 3. Рассмотрим действие группы на . Имеем

• s = e. Действие s: ()())().
• s = (1, 2)(3). Действие s: ()(, ).
• s = (1, 3)(2). Действие s: (, )).
• s = (1)(2, 3). Действие s: (, )().
• s = (1, 2, 3). Действие s: ().
• s = (1, 3, 2). Действие s: ().