Математика / Дискретная математика
Лемма Бёрнсайда: число объектов с учётом симметрий
Число классов объектов относительно конечной группы симметрий равно среднему числу объектов, неподвижных при её элементах. Лемма Бёрнсайда учитывает симметричные объекты с меньшими орбитами.
Формула
Для двух цветов при поворотах на 0,1,2,3 шага фиксировано 16,2,4,2 раскраски. Среднее равно 6 орбитам.
Обозначения
- $X$
- конечное множество всех размеченных объектов, —
- $G$
- конечная группа разрешённых симметрий, —
- $\operatorname{Fix}(g)$
- объекты, которые преобразование g оставляет неизменными, —
- $|X/G|$
- число классов эквивалентности, или орбит, шт.
Условия применения
Множество X и группа G конечны; каждое преобразование действует на X, тождественное действие сохраняет объект, а композиция согласована с умножением в группе. Симметрии должны сохранять все ограничения задачи. Все цвета различимы, если их перестановки специально не включены в действие группы.
Ограничения
Простое деление |X| на |G| верно только при свободном действии, когда ни один нетождественный элемент не фиксирует объект. Нельзя усреднять по произвольному списку преобразований, не образующему группу. Если запрещены некоторые раскраски, неподвижные объекты тоже считают с этими запретами.
Подробное объяснение
Орбита объекта состоит из всех его записей, получаемых разрешёнными симметриями. У асимметричного объекта орбита может содержать |G| записей, но у одноцветного ожерелья все повороты совпадают. Поэтому равномерное деление общего количества записей на число поворотов теряет вклад симметричных объектов.
Рассмотрим пары (g,x), для которых gx=x. Подсчёт по g даёт сумму размеров Fix(g). Подсчёт по орбитам даёт ровно |G| на каждую орбиту: размер орбиты, умноженный на число симметрий, фиксирующих её представитель, равен |G|. Деление двух подсчётов на |G| и даёт число классов.
При раскраске позиций в q цветов каждый цикл перестановки позиций должен иметь один цвет, иначе преобразование изменит раскраску. Если у преобразования c циклов, неподвижных раскрасок qᶜ. Для поворота n позиций на j шагов число циклов равно gcd(n,j); этот факт позволяет составить сумму без перебора всех qⁿ записей.
Отражение обычно имеет другой набор циклов, чем поворот. Добавляя отражения, нужно усреднять уже по диэдральной группе размера 2n, а не добавлять отдельную поправку к прежнему ответу. Для малых n полезно независимо построить орбиты и выбрать, например, лексикографически минимальную запись каждой: это проверяет и сумму, и выбранную эквивалентность.
Как пользоваться формулой
- Определите множество размеченных объектов X и выпишите группу преобразований, относительно которой записи считаются одинаковыми.
- Для каждого вида преобразования найдите число циклов позиций или прямо перечислите объекты, которые оно оставляет неизменными.
- Посчитайте неподвижные раскраски qᶜ с учётом всех дополнительных ограничений; умножьте на количество преобразований данного вида.
- Сложите фиксированные количества и разделите на размер группы; проверьте целочисленность результата и малые предельные случаи.
Историческая справка
Лемма относится к традиции подсчёта объектов с точностью до групповых действий. Название «лемма Бёрнсайда» широко используется в учебной литературе, но само имя не служит доказательством единоличного авторства. Важное математическое различие — подсчёт размеченных записей и подсчёт орбит — сохраняется независимо от исторического обозначения.
В книге Ричарда Стэнли Topics in Algebraic Combinatorics, версия 2013 года, подсчёт при действии группы выделен в отдельную главу. Он связывает простой двойной подсчёт фиксированных пар с более развитыми методами перечисления раскрасок. Современная учебная запись через Fix(g) подчёркивает, что результат применим к любому конечному действию, а не только к круговым ожерельям. Конкретная группа симметрий остаётся частью условия каждой задачи.
Историческая линия формулы
Используется общепринятое название «лемма Бёрнсайда», также известная как лемма подсчёта орбит. Историческое первенство по одному названию здесь не устанавливается. Доказательство двойным подсчётом дано непосредственно, а источники проверяют формулу и применение к конечным группам.
Пример
Три бусины по кругу окрашивают в два различимых цвета. Ожерелья считаются одинаковыми при повороте, но не при переименовании цветов; отражения отдельно в эквивалентность не добавляем. Сколько разных ожерелий получится? Группа имеет три элемента: повороты на 0, 1 и 2 шага. Тождественный поворот фиксирует 2³=8 записей. Каждый из двух остальных объединяет все позиции в один цикл и фиксирует только две одноцветные записи. Число орбит равно (8+2+2)/3=4. Это классы с нулём, одной, двумя и тремя бусинами второго цвета. Наивное 8/3 не даёт целого, поскольку одноцветные записи имеют орбиту размера 1, а смешанные — размера 3. Ответ безразмерный, это число классов.
Частая ошибка
Не следует делить число всех записей на число симметрий без учёта стабилизаторов. Повороты не переименовывают цвета: красный и синий остаются различимыми. Для Fix(g) требуется неизменность всей раскраски, а не наличие хотя бы одной неподвижной позиции. Отражения включают только тогда, когда условие задачи считает перевёрнутые объекты одинаковыми.
Практика
Задачи с решением
Четыре бусины
Условие. Найдите число двухцветных ожерелий из 4 бусин только с точностью до поворота.
Решение. Повороты на 0,1,2,3 шага имеют 4,1,2,1 циклов. Среднее (16+2+4+2)/4=6.
Ответ. 6 классов.
Три цвета
Условие. Для трёх бусин доступны 3 цвета. Отождествляются только повороты.
Решение. Тождественный элемент фиксирует 27 записей, два поворота — по 3. (27+3+3)/3=11.
Ответ. 11 классов.
Дополнительные источники
- https://math.mit.edu/~rstan/algcomb/algcomb.pdf
- https://math.mit.edu/~setia/6310fa18.pdf
Связанные формулы
Математика
Распределение числа совпадений в перестановке
Число перестановок с ровно k неподвижными точками получается выбором совпавших мест и беспорядком на остальных позициях. Деление на n! даёт вероятность ровно k совпадений в случайной перестановке.
Математика
Ладейный многочлен: назначения с запретами
Ладейные числа считают совместимые наборы запрещённых назначений. Чередующаяся сумма с факториалами затем даёт число перестановок, которые избегают всех запрещённых клеток таблицы.
Математика
Эйлеровы числа: перестановки с заданным числом спусков
Эйлерово число A(n,k) считает перестановки n различных чисел с ровно k спусками между соседними позициями. Рекурсия строит распределение по k вставкой нового наибольшего элемента.
Математика
Число перестановок без повторений
Формула описывает прием «перестановки разных объектов» для подсчета конечных объектов без полного перебора. Она фиксирует, что именно считается: случаи, шаги, группы, пересечения, рекуррентные члены или пары вершин, и помогает избежать двойного счета.