MAXimal | |
добавлено: 4 Nov 2008 11:48 Содержание [скрыть] Лемма Бернсайда. Теорема ПойаЛемма БернсайдаЭта лемма была сформулирована и доказана Бернсайдом (Burnside) в 1897 г., однако было установлено, что эта формула была ранее открыта Фробениусом (Frobenius) в 1887 г., а ещё раньше - Коши (Cauchy) в 1845 г. Поэтому эта формула иногда называется леммой Бернсайда, а иногда - теоремой Коши-Фробениуса. Лемма Бернсайда позволяет посчитать количество классов эквивалентности в некотором множестве, основываясь на некоторой его внутренней симметрии. Объекты и представленияПроведём чёткую грань между количеством объектов и количеством представлений. Одним и тем же объектам могут соответствовать различные представления, но, разумеется, любое представление соответствует ровно одному объекту. Следовательно, множество всех представлений разбивается на классы эквивалентности. Наша задача — в подсчёте именно числа объектов, или, что то же самое, количества классов эквивалентности. Пример задачи: раскраска бинарных деревьевДопустим, мы рассматриваем следующую задачу. Требуется посчитать количество способов раскрасить корневые бинарные деревья с Множество объектов здесь — это множество различных в этом понимании раскрасок деревьев. Определим теперь множество представлений. Каждой раскраске поставим в соответствие задающую её функцию Например, пусть Инвариантные перестановкиПочему эти две функции Итак, исходя из условия задачи, мы можем найти все инвариантные перестановки, т.е. применяя которые мы не не переходим из одного класса эквивалентности в другой. Тогда, чтобы проверить, являются ли две функции Нахождение всех таких инвариантных перестановок, относительно которых наша задача инвариантна — это ключевой шаг для применения как леммы Бернсайда, так и теоремы Пойа. Понятно, что эти инвариантные перестановки зависят от конкретной задачи, и их нахождение — процесс чисто эвристический, основанный на интуитивных соображениях. Впрочем, в большинстве случаев достаточно вручную найти несколько "основных" перестановок, из которых все остальные перестановки могут быть получены их всевозможными произведениями (и эту, исключительно механическую, часть работы можно переложить на компьютер; более подробно это будет рассмотрено ниже на примере конкретной задачи). Нетрудно понять, что инвариантные перестановки образуют группу — поскольку произведение любых инвариантных перестановок тоже является инвариантной перестановкой. Обозначим группу инвариантных перестановок через Формулировка леммыДля формулировки осталось напомнить одно понятие из алгебры. Неподвижной точкой Тогда лемма Бернсайда звучит следующим образом: количество классов эквивалетности равно сумме количеств неподвижных точек по всем перестановкам из группы Хотя лемма Бернсайда сама по себе не так удобна для применения на практике (пока непонятно, как быстро искать величину Доказательство леммы БернсайдаОписанное здесь доказательство леммы Бернсайда не так важно для её понимания и применения на практике, поэтому его можно пропустить при первом чтении. Приведённое здесь доказательство является самым простым из известных и не использует теорию групп. Это доказательство было опубликовано Богартом (Bogart) и Кеннетом (Kenneth) в 1991 г. Итак, нам нужно доказать следующее утверждение: Величина, стоящая справа — это не что иное, как количество "инвариантных пар" Для доказательства этой формулы составим таблицу, столбцы которой будут подписаны всеми значениями Итак, столбцы таблицы сами распадаются на классы эквивалентности; зафиксируем теперь какой-либо класс и рассмотрим столбцы в нём. Во-первых, заметим, что в этих столбцах могут стоять только элементы Теперь зафиксируем произвольный элемент Таким образом, если мы возьмём произвольным образом от каждого класса эквивалентности по одному столбцу и просуммируем количество элементов в них, то получим, с одной стороны, что и требовалось доказать. Теорема Пойа. Простейший вариантТеорема Пойа (Polya) является обобщением леммы Бернсайда, к тому же предоставляющая более удобный инструмент для нахождения количества классов эквивалентности. Следует отметить, что ещё до Пойа эта теорема была открыта и доказана Редфилдом (Redfield) в 1927 г., однако его публикация прошла незамеченной математиками того времени. Пойа независимо пришёл к тому же результату лишь в 1937 г., и его публикация была более удачной. Здесь мы рассмотрим формулу, получающуюся как частный случай теоремы Пойа, и которую очень удобно использовать для вычислений на практике. Общая теорема Пойа в данной статье рассматриваться не будет. Обозначим через где ДоказательствоЭта формула является прямым следствием леммы Бернсайда. Чтобы получить её, нам надо просто найти явное выражение для величины Итак, рассмотрим некоторую перестановку где Пример задачи: ОжерельяЗадача "ожерелья" — это одна из классических комбинаторных задач. Требуется посчитать количество различных ожерелий из В этой задаче мы можем сразу найти группу инвариантных перестановок. Очевидно, она будет состоять из Найдём явную формулу для вычисления Подставляя найденные значения в теорему Пойа, получаем решение: Можно оставить формулу в таком виде, а можно её свернуть ещё больше. Перейдём от суммы по всем где Применение леммы Бернсайда совместно с программными вычислениямиДалеко не всегда удаётся чисто аналитическим путём получить явную формулу для количества классов эквивалентности. Во многих задачах количество перестановок, входящих в группу, может быть слишком большим для ручных вычислений, и вычислить аналитически количество циклов в них не представляется возможным. В таком случае следует вручную найти несколько "основных" перестановок, которых будет достаточно для порождения всей группы Рассмотрим для примера задачу о количестве раскрасок тора. Имеется прямоугольный клетчатый лист бумаги В данной задаче представлением можно считать лист бумаги Таким образом, мы можем написать реализацию решения этой задачи: 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; }
|