Р А З Д Е Л 10

Теория Пойя

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

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

Пусть X – множество, на котором действует группа G. Обозначим через rG(X) число орбит в множестве X.

Теорема 10.1 (Лемма Бернсайда)

1 X

rG(X) = |G| g G |Xg|,

где Xg = {x X | gx = x} – множество элементов из X, неподвижных относительно g G.

Пусть, в дополнение к принятым обозначениям, Y – некоторое множество. Обозначим через Y X множество всех отображений из

40

Е. А. Каролинский, Б. В. Новиков

41

X в Y . Тогда возникает правое действие G на Y X: если α Y X, x X, g G, то полагаем αg : x 7→α(gx).

Многие перечислительные задачи сводятся к нахождению числа rG(Y X) по известному действию G на X.

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

Теорема 10.2 (Ослабленная теорема Пойя)

rG Y X = |G1 | X |Y |rg(X).

g G

Пример (задача об ожерельях). Пусть X – множество вершин правильного n-угольника, Y – множество цветов, которыми раскрашиваются эти вершины. Будем отождествлять два раскрашенных n-угольника, если их можно с помощью поворотов и симметрий совместить так, что совпавшие вершины имеют один и тот же цвет. Сколько существует различных раскрасок?

Ответом является число rn,m = rG(Y X), где G = Dn – группа диэдра (см. раздел 9), m = |Y |. Вычисляя величины rg(X), получаем следующее

Предложение 10.3

rn,m = 21n			ϕ(d)mn/d + An,m	,
		X
		d	n

где ϕ – функция Эйлера, суммирование ведется по всем делителям числа n и

An,m =	nm(n+1)/2,	если n нечетно,
	21 n(m + 1)mn/2,	если n четно.
	* * *

42	Раздел 10. Теория Пойя

Предварительные задачи по комбинаторике1

10.1. Флаг составляется из 7 полос четырех цветов так, чтобы соседние полосы имели различные цвета. Сколькими способами это можно сделать?

10.2. Три человека x, y, z должны разделить между собой m рублей, так, чтобы x и y получили равные суммы. Сколькими способами это можно сделать?

10.3. n параллельных прямых на плоскости пересекаются с другими m параллельными прямыми. Сколько параллелограммов можно выделить в образовавшейся сетке?

10.4. Сколькими способами можно расставить на шахматной доске размера n × n две ладьи различного цвета так, чтобы ладьи могли взять друг друга?

10.5. n человек, в том числе A и B, располагаются в ряд в случайном порядке. Найдите вероятность того, что между A и B стоит ровно r человек.

10.6. Пусть m – натуральное число. Докажите, что число целых неотрицательных решений уравнения

x1 + . . . + xr = m

равно Crr+−m1 −1.

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

10.8. Докажите, что число bn всех подстановок n-й степени, не имеющих неподвижных точек, удовлетворяет рекуррентному уравнению

bn+1 = n(bn + bn−1),

n ≥ 1, с начальными условиями b0 = 1, b1 = 0.

10.9.* Решите рекуррентные уравнения из задач 10.7 и 10.8.

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

Е. А. Каролинский, Б. В. Новиков

43

10.10. Сколько подстановок n-й степени имеют ровно k (k ≤ n) неподвижных точек?

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

10.11.* Пусть S, T – непересекающиеся множества, группы G и H действуют на S и T соответственно.

а) Определим действие группы G×H на U = S T следующим образом:

(g, h)u = gu, если u S, hu, если u T .

Найдите rG×H(U).

б) Определим действие G × H на V = S × T следующим образом:

(g, h)(s, t) = (gs, ht).

Найдите rG×H(V ).

10.12. Определим действие симметрической группы S(X) на декартовом квадрате X × X следующим образом: g : (x, y) 7→ (gx, gy). Сколько орбит имеет S(X)-множество X × X?

10.13.* Пусть n > 1. Используя задачи 10.10 и 10.12, докажите

равенство

m

X

k2Cnkbn−k = 2n!

k=1

(число bn определено в задаче 10.8).

10.14. Докажите, что

а) число раскрасок вершин квадрата m цветами равно

18 m(m + 1)(m2 + m + 2);

б) число раскрасок вершин правильного p-угольника (где p – нечетное простое число) m цветами равно

2p	m 2	+ 1 m 2	+ p − 1 .
m	p−1	p−1

44	Раздел 10. Теория Пойя

10.15. Сколькими способами можно ориентировать стороны правильного n-угольника?

10.16.* Найдите число раскрасок m цветами а) вершин, б) ребер, в) граней

тетраэдра.

10.17.* Зафиксируем некоторое множество V . Мы будем рассматривать ориентированные графы без петель с V в качестве множества вершин. Два таких графа и 0 с множествами ребер E и E0 соответственно называются изоморфными, если существует такая биекция ϕ : V → V , что

(u, v) E (ϕu, ϕv) E0.

Положим X = (V ×V )\{(v, v) | v V }, Y = {0, 1}. Тогда каждое отображение α : X → Y определяет граф α с множеством ребер

Eα = {(u, v) | α(u, v) = 1}.

Обратно, каждому графу с множеством ребер E соответствует отображение α такое, что

α(u, v) = 1 (u, v) E.

Определим действие симметрической группы S(V ) на X так же, как и в задаче 10.12.

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

10.18. Найдите число неизоморфных ориентированных графов без петель

а) с тремя вершинами; б) с четырьмя вершинами.

10.19.* Найдите число неизоморфных неориентированных графов без петель

а) с тремя вершинами;

Е. А. Каролинский, Б. В. Новиков

45

б) с четырьмя вершинами.

10.20.* Группоидом называется множество A с заданной на нем бинарной операцией “·”. Группоиды A(·) и B( ) называются изотопными, если существует такая тройка биекций α, β, γ : A → B, что αx βy = γ(x · y) для любых x, y A (проверьте, что отношение изотопности является эквивалентностью). Если γ – тождественное отображение, то группоиды A(·) и B( ) называются главно изотопными. Сколько, с точностью до главной изотопии, существует группоидов из трех элементов?