e-maxx_algo
.pdfЛемма Бернсайда. Теорема Пойа
Лемма Бернсайда
Эта лемма была сформулирована и доказана Бернсайдом (Burnside) в 1897 г., однако было установлено, что эта формула была ранее открыта Фробениусом (Frobenius) в 1887 г., а ещё раньше - Коши (Cauchy) в 1845 г. Поэтому эта формула иногда называется леммой Бернсайда, а иногда - теоремой Коши-Фробениуса.
Лемма Бернсайда позволяет посчитать количество классов эквивалентности в некотором множестве, основываясь на некоторой его внутренней симметрии.
Объекты и представления
Проведём чёткую грань между количеством объектов и количеством представлений.
Одним и тем же объектам могут соответствовать различные представления, но, разумеется, любое представление соответствует ровно одному объекту. Следовательно, множество всех представлений разбивается на классы эквивалентности. Наша задача — в подсчёте именно числа объектов, или, что то же самое, количества классов эквивалентности.
Пример задачи: раскраска бинарных деревьев
Допустим, мы рассматриваем следующую задачу. Требуется посчитать количество способов раскрасить корневые бинарные деревья с вершинами в 2 цвета, если у каждой вершины мы не различаем правого и левого сына.
Множество объектов здесь — это множество различных в этом понимании раскрасок деревьев.
Определим теперь множество представлений. Каждой раскраске поставим в соответствие задающую её функцию , где , а . Тогда множество представлений — это множество различных
функций такого вида, и размер его, очевидно, равен . В то же время, на этом множестве представлений мы ввели разбиение на классы эквивалентности.
Например, пусть , а дерево таково: корень — вершина 1, а вершины 2 и 3 — её сыновья. Тогда следующие функции и считаются эквивалентными:
Инвариантные перестановки
Почему эти две функции и принадлежат одному классу эквивалентности? Интуитивно это понятно — потому что мы можем переставить местами сыновей вершины 1, т.е. вершины 2 и 3, а после такого преобразования функции и совпадут. Но формально это означает, что найдётся такая инвариантная перестановка (т.е. которая
по условию задачи не меняет сам объект, а только его представление), такая, что:
Итак, исходя из условия задачи, мы можем найти все инвариантные перестановки, т.е. применяя которые мы не не переходим из одного класса эквивалентности в другой. Тогда, чтобы проверить, являются ли две функции и
эквивалентными (т.е. соответствуют ли они на самом деле одному объекту), надо для каждой
инвариантной перестановки проверить, не выполнится ли условие: |
(или, что то же самое, |
|
). Если хотя бы для одной перестановки обнаружилось это равенство, то и |
эквивалентны, иначе они |
|
не эквивалентны. |
|
|
Нахождение всех таких инвариантных перестановок, относительно которых наша задача инвариантна — это ключевой шаг для применения как леммы Бернсайда, так и теоремы Пойа. Понятно, что эти инвариантные перестановки зависят от конкретной задачи, и их нахождение — процесс чисто эвристический, основанный на интуитивных соображениях. Впрочем, в большинстве случаев достаточно вручную найти несколько "основных" перестановок, из которых все остальные перестановки могут быть получены их всевозможными произведениями (и эту, исключительно механическую, часть работы можно переложить на компьютер; более подробно это будет рассмотрено ниже на примере конкретной задачи).
Нетрудно понять, что инвариантные перестановки образуют группу — поскольку произведение любых инвариантных перестановок тоже является инвариантной перестановкой. Обозначим группу
Теорема Пойа. Простейший вариант
Теорема Пойа (Polya) является обобщением леммы Бернсайда, к тому же предоставляющая более удобный инструмент для нахождения количества классов эквивалентности. Следует отметить, что ещё до Пойа эта теорема была открыта и доказана Редфилдом (Redfield) в 1927 г., однако его публикация прошла незамеченной математиками того времени. Пойа независимо пришёл к тому же результату лишь в 1937 г., и его публикация была более удачной.
Здесь мы рассмотрим формулу, получающуюся как частный случай теоремы Пойа, и которую очень удобно использовать для вычислений на практике. Общая теорема Пойа в данной статье рассматриваться не будет.
Обозначим через |
количество циклов в перестановке . Тогда выполняется следующая формула |
(частный случай теоремы Пойа):
|
|
|
где — количество значений, которые может принимать каждый элемент представления |
. Например, в |
|
нашей задаче-примере (раскраска корневого бинарного дерева в 2 цвета) |
. |
|
Доказательство
Эта формула является прямым следствием леммы Бернсайда. Чтобы получить её, нам надо просто найти явное выражение для величины , фигурирующую в лемме (напомним, это количество неподвижных
точек перестановки ).
Итак, рассмотрим некоторую перестановку и некоторый элемент . Под действием перестановки элементы передвигаются, как известно, по циклам перестановки. Заметим, что так как в результате должно получаться
, то внутри каждого цикла перестановки должны находиться одинаковые элементы . В то же время, для
разных циклов никакой связи между значениями элементов не возникает. Таким образом, для каждого цикла перестановки мы выбираем по одному значению (среди вариантов), и тем самым мы получим все представления
, инвариантные относительно этой перестановки, т.е.:
где — количество циклов перестановки.
Пример задачи: Ожерелья
Задача "ожерелья" — это одна из классических комбинаторных задач. Требуется посчитать количество различных ожерелий из бусинок, каждая из которых может быть покрашена в один из цветов. При сравнении двух ожерелий их можно поворачивать, но не переворачивать (т.е. разрешается сделать циклический сдвиг).
В этой задаче мы можем сразу найти группу инвариантных перестановок. Очевидно, она будет состоять из перестановок:
|
|
|
|
|
|
|
|
Найдём явную формулу для вычисления |
. Во-первых, заметим, что перестановки имеют такой вид, что в - |
||||||
ой перестановке на |
-ой позиции стоит |
(взятое по модулю |
, если оно больше ). Если мы будем |
|
|||
рассматривать циклическую структуру -ой перестановки, то увидим, что единица переходит в |
, |
переходит |
|||||
в |
, |
— в |
, и т.д., пока не придём в число |
; для остальных элементов |
|
|
|
выполняются похожие утверждения. Отсюда можно понять, что все циклы имеют одинаковую длину, |
|
|
|||||
равную |
|
, т.е. |
|
("gcd" — наибольший общий делитель, "lcm" — наименьшее общее |
кратное). Тогда количество циклов в -ой перестановке будет равно просто . Подставляя найденные значения в теорему Пойа, получаем решение:
Можно оставить формулу в таком виде, а можно её свернуть ещё больше. Перейдём от суммы по всем к сумме только по делителям . Действительно, в нашей сумме будет много одинаковых слагаемых: если не является делителем , то таковой делитель найдётся после вычисления . Следовательно, для каждого делителя его
слагаемое учтётся несколько раз, т.е. сумму можно представить в таком виде:
|
|
|
|
|
где |
— это количество таких чисел |
, что |
. Найдём явное выражение для этого количества. |
|
Любое такое число имеет вид: |
, где |
(иначе было бы |
). |
|
Вспоминая функцию Эйлера, мы находим, что количество таких — это величина функции Эйлера |
. |
Таким образом, , и окончательно получаем формулу:
Применение леммы Бернсайда совместно с программными вычислениями
Далеко не всегда удаётся чисто аналитическим путём получить явную формулу для количества классов эквивалентности. Во многих задачах количество перестановок, входящих в группу, может быть слишком большим для ручных вычислений, и вычислить аналитически количество циклов в них не представляется возможным.
В таком случае следует вручную найти несколько "основных" перестановок, которых будет достаточно для порождения всей группы . Далее можно написать программу, которая сгенерирует все перестановки группы , посчитает в каждой из них количество циклов и подставит их в формулу.
Рассмотрим для примера задачу о количестве раскрасок тора. Имеется прямоугольный клетчатый лист бумаги , некоторые из клеток покрашены в чёрный цвет. Затем из этого листа получают
цилиндр, склеивая две стороны с длинами . Затем из цилиндра получают тор, склеивая две окружности (базы цилиндра) без перекручивания. Требуется посчитать количество различных торов (лист был изначально
покрашен произвольно), считая, что линии склеивания неразличимы, а тор можно поворачивать и переворачивать.
В данной задаче представлением можно считать лист бумаги , некоторые клетки которого покрашены в чёрный цвет. Нетрудно понять, что следующие виды преобразований сохраняют класс эквивалентности: циклический сдвиг строк листа, циклический сдвиг столбцов листа, поворот листа на 180 градусов; также интуитивно можно понять, что этих трёх видов преобразований достаточно для порождения всей группы инвариантных преобразований. Если мы каким-либо образом занумеруем клетки поля, то мы можем записать
три перестановки , , , соответствующие этим видам преобразований. Дальше остаётся только сгенерировать все перестановки, получающиеся как произведения этой. Очевидно, что все такие перестановки имеют вид
, где , , .
Таким образом, мы можем написать реализацию решения этой задачи:
void mult (vector<int> & a, const vector<int> & b) { vector<int> aa (a);
for (size_t i=0; i<a.size(); ++i) a[i] = aa[b[i]];
}
int cnt_cycles (vector<int> a) { int res = 0;
for (size_t i=0; i<a.size(); ++i) if (a[i] != -1) {
++res;
for (size_t j=i; a[j]!=-1; ) { size_t nj = a[j]; a[j] = -1;
j = nj;
}
}
return res;
}
int main() {
int n, m;
cin >> n >> m;
vector<int> p (n*m), p1 (n*m), p2 (n*m), p3 (n*m); for (int i=0; i<n*m; ++i) {
p[i] = i;
p1[i] = (i % n + 1) % n + i / n * n; p2[i] = (i / n + 1) % m * n + i % n;
p3[i] = (m - 1 - i / n) * n + (n - 1 - i % n);
}
int sum = 0, cnt = 0; set < vector<int> > s;
for (int i1=0; i1<n; ++i1) {
for (int i2=0; i2<m; ++i2) {
for (int i3=0; i3<2; ++i3) { if (!s.count(p)) {
s.insert (p); ++cnt;
sum += 1 << cnt_cycles(p);
}
mult (p, p3);
}
mult (p, p2);
}
mult (p, p1);
}
cout << sum / cnt;
}
Сколько есть перестановок чисел от до таких, что первый элемент больше |
, а последний — меньше |
? |
|
Посчитаем число "плохих" перестановок, т.е. таких, у которых первый элемент |
и/или последний |
. |
|
Обозначим через |
множество перестановок, у которых первый элемент |
, а через — у которых |
|
последний элемент |
. Тогда количество "плохих" перестановок по формуле включений-исключений равно: |
||
|
|
|
|
|
|
|
|
Проведя несложные комбинаторные вычисления, получаем, что это равно:
Отнимая это число от общего числа перестановок , мы получим ответ.
Простая задачка о (0,1,2)-последовательностях
Сколько существует последовательностей длины , состоящих только из чисел |
, причём каждое |
число встречается хотя бы раз? |
|
Снова перейдём к обратной задаче, т.е. будем считать число последовательностей, в которых не присутствует хотя бы одно из чисел.
Обозначим через () множество последовательностей, в которых не встречается число . Тогда по формуле включений-исключений число "плохих" последовательностей равно:
|
|
|
|
Размеры каждого из |
равны, очевидно, |
(поскольку в таких последовательностях могут встречаться только два |
|
вида цифр). Мощности каждого попарного пересечения |
равны (поскольку остаётся доступной только |
одна цифра). Наконец, мощность пересечения всех трёх множеств равна (поскольку доступных цифр вообще не остаётся).
Вспоминая, что мы решали обратную задачу, получаем итоговый ответ:
Количество целочисленных решений уравнения
Дано уравнение:
где все (где ). Требуется посчитать число решений этого уравнения.
Забудем сначала про ограничение |
, и просто посчитаем число неотрицательных решений этого уравнения. |
||
Это легко делается через биномиальные коэффициенты — мы хотим разбить |
элементов на групп, т.е. |
||
распределить "стенок", разделяющих группы, по |
местам: |
|
|
|
|
|
|
|
|
|
|
Посчитаем теперь по формуле включений-исключений число "плохих" решений, т.е. таких решений уравнения, в которых один или более больше .
Обозначим через |
(где |
) множество таких решений уравнения, в которых |
, а все |
|
остальные |
(для всех |
). Чтобы посчитать размер множества |
, заметим, что у нас по сути та |
же комбинаторная задача, что решалась двумя абзацами выше, только теперь элементов исключены из рассмотрения и точно принадлежат первой группе. Таким образом:
Аналогично, мощность пересечения двух множеств и равна числу:
Мощность каждого пересечения трёх и более множеств равна нулю, поскольку элементов не хватит на три и более переменных, больше либо равных .
Объединяя всё это в формулу включений-исключений и учитывая, что мы решали обратную задачу, окончательно получаем ответ: