Лемма Бёрнсайда и Теорема Пойа

Иногда требуется провести подсчет комбинаторных объектов с точностью до некоторого отношения эквивалетности. Если это отношение является отношением "с точностью до действия элементом группы", то такой подсчет можно провести с помощью Леммы Бернсайда.

Определение:

Пусть группа [math]G[/math] действует на множество [math]X[/math]. Неподвижной точкой для элемента [math]g[/math] называется такой элемент [math]x[/math], для которого [math]gx=x[/math].

Определение:

Множество неподвижных точек элемента [math]g[/math] называется его стабилизатором и обозначается [math]St(g)[/math].

Определение:

Пусть группа [math]G[/math] действует на множество [math]X[/math]. Будем называть два элемента [math]x[/math] и [math]y[/math] эквивалентными, если [math]x = gy[/math] для некоторого [math]g \in G[/math]. Классы эквивалентности данного отношения называются орбитами, множество орбит обозначается как [math]X/G[/math].

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

Лемма (Бернсайд, англ. Burnside's lemma):

Число орбит равно средней мощности стабилизатора элементов группы [math]G[/math]. [math]|X/G| = \dfrac{1} {|G|}\sum\limits_{g \in G}|St(g)|[/math].

Доказательство:

[math]\triangleright[/math]

Так как [math]St(g)[/math] — стабилизатор элемента [math]g[/math], то по определению [math]\sum\limits_{g \in G}|St(g)| = |\{(x, g) \in G\times X \mid g\cdot x = x\}|[/math]. Следовательно для доказательства леммы необходимо и достаточно доказать следующее равенство: [math]|X/G|\cdot|G| = |\{(x, g) \in G\times X \mid g\cdot x = x\}|[/math] Введем обозначение [math]C=X/G[/math]. Рассмотрим правую часть равенства: [math]|\{(x, g) \in G\times X \mid g\cdot x = x\}| = \sum\limits_{x \in X} |G_x| = \sum\limits_{x \in X}[/math][math] \dfrac{|G|}{|Gx|} = |G| \sum\limits_{x \in X}\dfrac{1}{|Gx|} [/math] [math]= |G|\sum\limits_{P\in C}\sum\limits_{x\in P}[/math][math] \dfrac{1}{|P|}[/math] Заметим, что [math]\sum\limits_{x\in P} \dfrac{1}{|P|} \dfrac{1}{|P|}\sum\limits_{1}^{|P|}{1} = 1.[/math] Следовательно: [math]|G|\sum\limits_{P\in C}\sum\limits_{x\in P} \dfrac{1}{|P|} = |G|\sum\limits_{P\in C} 1[/math]. Очевидно, что [math]\sum\limits_{P\in C} 1 = \sum\limits_{1}^{|C|}{1} = |C|.[/math] Тогда получим: [math]|G|\sum\limits_{P\in C} 1 = |C|\cdot|G|.[/math] Откуда следует, что [math]\sum\limits_{g \in G}|St(g)| = |C|\cdot|G|.[/math]

[math]\triangleleft[/math]

Теорема Пойа

Теорема Пойа является обобщением леммы Бёрнсайда. Она также позволяет находить количество классов эквивалентности, но уже используя такую величину, как кол-во циклов в перестановке. В основе доказательства теоремы Пойа лежит лемма Бёрнсайда.

Теорема (Пойа, англ. Pólya enumeration theorem):

[math]C = \dfrac{1}{|G|}\sum\limits_{g \in G} l^{P(g)}[/math] ,где [math]C[/math] — кол-во различных классов эквивалентности, [math]P(g)[/math] — кол-во циклов в перестановке [math]g[/math], [math]l[/math] — кол-во различных состояний одного элемента.

Доказательство:

[math]\triangleright[/math]

Для доказательства этой теоремы достаточно установить следующее равенство [math]|St(g)| = l^{P(g)}[/math] Рассмотрим некоторую перестановку [math]g[/math] и некоторый элемент [math]f[/math]. Под действием перестановки [math]g[/math] элементы [math]f[/math] передвигаются, как известно, по циклам перестановки. Заметим, что так как в результате должно получаться [math]fg = f[/math], то внутри каждого цикла перестановки должны находиться одинаковые элементы [math]f[/math]. В то же время, для разных циклов никакой связи между значениями элементов не возникает. Таким образом, для каждого цикла перестановки [math]g[/math] мы выбираем по одному значению, и, тем самым, мы получим все представления [math]f[/math], инвариантные относительно этой перестановки, т.е.: [math]|St(g)| = l^{P(g)}[/math]

[math]\triangleleft[/math]

Задача о числе раскрасок прямоугольника

Задача:

Выведите формулу для числа раскрасок прямоугольника [math][n \times m][/math] в [math]k[/math] цветов с точностью до отражения относительно горизонтальной и вертикальной оси.

Решим данную задачу, воспользуясь леммой Бёрнсайда.

Решение

Для начала определим, какие операции определены на группе [math]G[/math] — это операция "отражение относительно горизонтальной оси", обозначим ее как [math]\alpha[/math], "отражение относительно вертикальной оси" — [math]\beta[/math] и "переход из одного состояния в него же" — [math]e[/math]. Таким образом, [math]G[/math] содержит 4 комбинации операций: [math]G = \{e, \alpha, \beta, \alpha \circ \beta \}[/math].

Стоит уделить особое внимание тому факту, что никакие иные комбинации функций [math]\alpha[/math] и [math]\beta[/math] не были включены в [math]G[/math]. Это объясняется довольно просто: очевидно то, что операции коммутативны, то есть [math]\alpha \circ \beta = \beta \circ \alpha[/math], а также то, что [math]\alpha \circ \alpha = \beta \circ \beta = e[/math], тогда любая комбинация данных функций может быть упрощена до вышеперечисленных (в [math]G[/math]) путем совмещения одинаковых и замены их на [math]e[/math].

Отметим также то, что количество раскрасок прямоугольника [math][m \times n][/math] в [math]k[/math] цветов:

1. С точностью до операции [math]\alpha[/math] при нечетном [math]m[/math] равно количеству раскрасок прямоугольника [math][m-1 \times n][/math] в [math]k[/math] цветов.

2. С точностью до операции [math]\beta[/math] при нечетном [math]n[/math] равно количеству раскрасок прямоугольника [math][m \times n-1][/math] в [math]k[/math] цветов.

3. С точностью до операции [math]\alpha \circ \beta[/math] при нечетных [math]n[/math] и [math]m[/math] равно количеству раскрасок прямоугольника [math][m-1 \times n-1][/math] в [math]k[/math] цветов (а также частные случаи, когда [math]n[/math] или [math]m[/math] нечетные).

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

Количество неподвижных точек в случае с действием [math]e[/math] равно [math]k^{nm}[/math], так как ни одна раскрашенная клетка не повторилась при действии нулевого действия. Для действий [math]\alpha[/math] и [math]\beta[/math] количество раскрасок будет [math]k^{\lceil \dfrac{m}{2} \rceil n}[/math] и [math]k^{{\lceil {\dfrac{n}{2}} \rceil}m}[/math] соответственно, для их композиции количество раскрасок [math]k^{{\lceil {\dfrac{nm}{2}} \rceil}}[/math], так как верхняя левая четверть прямоугольника однозначно задаёт правую нижнюю, аналогично с правой верхней.

Тогда воспользуемся Леммой Бёрнсайда и определим количество таких раскрасок.

[math] |C| = \dfrac{1} {|G|} \sum\limits_{g \in G}|St(g)| = \dfrac{I_1 + I_2 + I_3 + I_4}{4} = \dfrac{k^{nm}+k^{\lceil \dfrac{m}{2} \rceil n} + k^{{\lceil {\dfrac{n}{2}} \rceil}m} + k^{{\lceil {\dfrac{nm}{2}} \rceil}}}{4}[/math]

См. также

• Теорема Кэли
• Задача об ожерельях

Источники информации

• Википедия — Лемма Бёрнсайда
• Википедия — Теорема Пойа
• Wikipedia — Burnside's lemma
• Wikipedia — Pólya enumeration theorem