Рассмотрим полное бинарное дерево с семью узлами и всевозможные различные варианты раскраски его узлов белым или черным цветом в предположении, что мы не отличаем «левое» от «правого». На следующем примере приведены различные представления одной и той же раскраски дерева:

В противоположность этому каждая из следующих картинок представляет собой отличную от других раскраску дерева:

Чтобы уяснить, какое же множество объектов подлежит пересчету, определим множество S представлений. Каждой картинке такого типа, как показанные выше, поставим в соответствие функцию из области D семи узлов в область R двух цветов:

D= {1,2,3,4,5,6,7},

R= {Б, Ч},

R^D={f│f: D→R}.

Заметим, что R^D состоит из 2⁷=128 элементов, называемых представлениями. Например, приведенные выше представления f₃ и f₄ соответствуют функциям

f₃(1) = f₃(3) = f₃(5) = f₃(7) =Б, f₃(2) = f₃(4) = f₃(6) = Ч

и

f₄(1) = f₄(3) = f₄(5) = f₄(6) =Б, f₄(2) = f₄(4) = f₄(7) = Ч.

На множестве R^D всех функций, отображающих D в R, определим отношение эквивалентности g и каждый класс эквивалентности отождествим с одним из подлежащих пересчету объектов (раскрасок дерева).

Интуитивно ясно, f₃ и f₄ должны принадлежать одному классу эквивалентности относительно g. Почему это так? В области D существует подстановка p, которая переставляет двух сыновей узла 3, а именно узлы 6 и 7, и две функции f₃ и f₄ отличаются только «по модулю p», т. е. f₄ = f₃p, или, что эквивалентно, функция f₄ получается применением сначала подстановки p к D и последующим отображением D на R посредством функции f₃. Поскольку мы не отличаем «левое» от «правого» и p только переставляет левого и правого сыновей узла 3, две функции такого же типа, как f₃ и f₄ должны быть эквивалентны.

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

p₁=(1)(23)(46)(57),

p₂=(1)(2)(3)(45)(6)(7),

p₃=(1)(2)(3)(4)(5)(67);

и выглядит так

перестановка	Циклическое представление	Цикловой индекс
тождественная	(1)(2)(3)(4)(5)(6)(7)
p1	(1)(23)(46)(57)
p2	(1)(2)(3)(45)(6)(7)
p3	(1)(2)(3)(4)(5)(67)
p2p3=p3p2	(1)(2)(3)(45)(67)
p1p2=p3p1	(1)(23)(4567)	t1t2t4
p1p3=p2p1	(1)(23)(4756)	t1t2t4
p1p2p3	(1)(23)(47)(56)

Определим основное, используемое в теореме Пойа:

Определение. Если дана группа подстановок G, то цикловым индексом P_G группы G называется полином относительно переменных t₁, t₂, t₃ …, который представляет собой среднее арифметическое цикловых индексов, взятыз по всем подстановкам p группы G. В нашем примере

P_G=1/8(+2+2+2 t₁t₂t₄+).

В данном случае теорема Пойа утверждает:

Число классов эквивалентности на множестве R^D, отображающих D в R, при отношении эквивалентности g, индуцированном группой подстановокG на множестве D, получается сопоставлением значения çR ç(мощности множества R) каждой переменной t_i в цикловом индексе P_G группы G. В нашем примере çR ç= 2, и отсюда получаем

P_G=1/8(2⁷+2⁵+2⁷+2⁴+2⁵)=42

Упражнение. Проверьте путем систематического конструирования, что в нашем примере число различных раскрасок действительно равно 42.

2. Цикловой индекс группы подстановок.[12]

Пример1. Пусть S – множество вершин куба, так что m=çS ç=8, и пусть G – множество всех тех подстановок S, которые могут быть получены вращением куба. Всего 6´4=24 таких вращений.

Их можно разбить на пять категорий.

(а) Тождественное.

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

(в) Шесть поворотов на 90^о вокруг прямых, соединяющих центры противоположных граней.

(г) Шесть поворотов на 180^о вокруг прямых, соединяющих середины противоположных ребер.

(д) Восемь поворотов на 120^о вокруг прямых, соединяющих середины противоположные вершины.

Поскольку 1+3+6+6+8=24, этот список полон.

Легко представить себе циклы множества S в каждом случае. В случае (а) – восемь циклов длины 1; подстановки типа (б) дают четыре цикла длины 2; в случае (в) два цикла длины 4; (г) дает четыре цикла 2; в случае (д) два цикла длины1 и два цикла длины 3. поэтому цикловой индекс таков:

P_G=1/24(+9+6+8).

Пример2. Пусть S – множество ребер куба, так что m=12, и пусть G – множество всех 24 подстановок S, которые могут быть получены вращением куба.

Вращение те же, что и в примере 2. теперь надо посмотреть, что делают вращения с ребрами. Тождественное вращение - подстановка типа <>. Вращения (б) – типа <>, в случае (в) – тип <>, в случае (г) – тип <>, и в случае (д) – тип <>.

Поэтому имеем

P_G=1/24(+3+6+6+8).

Пример 3. Опять возьмем вращения куба, но теперь пусть S – множество всех его граней. Наши пять категорий вращений дают подстановки типов <>, <>, <>, <>, <> соответственно, и поэтому

P_G=1/24(+3+6+6+8). (1)

Пример 4. Пусть S – множество из m элементов и G – группа всех подстановок S; т. е. G – симметрическая группа степени m. Ее цикловой индекс согласно свойству циклового индикатора (см. § Цикловые типы), равен

С_m(t₁, t₂,…, t_m)/m!=

или коэффициенту при u^m в разложении

exp(ut₁+u²t₂/2+u³t₃/3+…) (2)

по степеням u.

Пример 5. Пусть S – некоторая конечная группа, m=çS ç. Если а – фиксированный элемент множества S, то отображение s → as, как легко видеть, есть подстановка на множестве S. Обозначим ее через g_a, мы замечаем, что если a пробегает все множество S, то такие подстановки g_a образуют группу G. Имеем g_ag_b=g_ab, поэтому G изоморфно самой группе G, изоморфизм определяется так g_a«a. Группа G называется представлением Кэли группы S.

Мы интересуемся ее цикловым индексом.

Если aÎS имеет порядок k(a), подстановка g_a разбивает S на циклы, длины которых все равны k(a): если s – некоторый элемент S, то он принадлежит циклу, образованному из следующих элементов:

s→as→a²s→…→a^k(a)s=s.

Отсюда следует, что m делится на k(a) и что подстановка g_a разбивает S на m/k(a) циклов длины k(a).

Таким образом, мы получаем цикловой индекс:

P_G=. (4)

Эта сумма может быть записана также так:

P_G=, (5)

где d пробегает все делители m, а v(d) – это число элементов aÎS, порядок которых k(a)=d.

Пример 6. В качестве частного случая примера 5 возьмем следующую циклическую группу подстановок.

Пусть S – группа всех корней m-й степени из единицы e^2pij/m, где j=1,…,m, i – мнимая единица.

Тогда для каждого aÎS отображение s→as является подстановкой S, группа этих подстановок - циклическая.

Если a=e^2pij/m, то порядок элемента a равен k(a)=m/(m,j), где (m,j) - наибольший общий делитель m и j. Поэтому цикловой индекс

P_G=

Второе выражение получается из (5)

P_G=,

где j - функция Эйлера, т. е. j(d) – это число целых n, удовлетворяющих условию 1≤n≤d и (n,d)=1.

Пример 7. Пусть G группа подстановок множества S и пусть Н группа подстановок множества T. SÇT=Æ, U=SÈT. Любому выбору gÎG и hÎH соответствует подстановка множества U, определенная так:

u→gu, если uÎS, u→hu, если uÎT.

Обозначим такую подстановку множества U через g´h. Легко видеть, что эти подстановки образуют группу, порядок которой равен произведению порядков групп G и H. Эта группа называется прямым произведением групп G и H и обозначается G´H.

Если gÎG и hÎH и если g имеет тип<> а h имеет тип <>, то g´h имеет тип <>, так как каждый цикл в U лежит либо целиком в S, либо целиком в T. Отсюда член циклового индекса группы G´H, соответствующий элементу g´h, равен произведению члена в P_G, соответствующего элементу g, и члена в P_H, соответствующего h. Применив это ко всем членам P_G и всем членам P_H, получим формулу для произведения

P_G´H=P_G×P_H

Замечание. Тип перестановки g позволяет делать некоторые выводы о перестановке и о степенях g², g³,…, но мы очень мало можем сказать о типе произведения g₁g₂, исходя из типов сомножителей. Соответственно, хотя цикловой индекс может дать информацию о комбинаторных вопросах, касающихся группы подстановок, он мало говорит о мультипликативной структуре группы. В 1937г. Пойа привел пример двух неизоморфных групп подстановок с одинаковыми цикловыми индексами. Таким образом, цикловой индекс не всегда определяет группу однозначно.

Пойа берет две неизоморфные группы порядка p³, где p>2 простое, которые обладают тем свойством, что каждый элемент, кроме единичного, имеют порядок p.

В результате выражение (*) для циклового индекса представления Кэли дает один и тот же результат в обоих случаях.