Введение
Формула для числа орбит группового действия
Лемма Бернсайда, иногда также называемая теоремой подсчета орбит Бернсайда, леммой Коши — Фробениуса или теоремой о подсчете орбит, является результатом в теории групп, который часто полезен при учете симметрии при подсчете математических объектов. Она была открыта Огюстеном Луи Коши и Фердинандом Георгом Фробениусом и стала широко известной после цитирования Уильямом Бернсайдом. Результат позволяет перечислять орбиты группы симметрии, действующей на некоторый набор объектов: то есть, он подсчитывает различные объекты, считая симметричные друг другу объектами одинаковыми; или подсчитывает различные объекты с точностью до отношения эквивалентности по симметрии; или подсчитывает только объекты в канонической форме. Например, при описании возможных органических соединений определенного типа их рассматривают с учетом симметрии пространственного вращения: различные вращения одного и того же рисунка молекулы химически идентичны. (Однако зеркальное отражение может привести к другому соединению.) Формально, пусть G — конечная группа, действующая на множество X. Для каждого g из G пусть Xg обозначает множество элементов из X, фиксированных элементом g (инвариантных относительно g слева): то есть, Xg = { x ∈ X | g.x = x }. Лемма Бернсайда утверждает следующую формулу для числа орбит, обозначаемого |X/G|:
Таким образом, число орбит (натуральное число или +∞) равно среднему числу точек, фиксированных элементом из G. Для бесконечной группы G также существует биекция:
Ожерелья
Существует 8 возможных битовых строк длиной 3, но соединение концов строк дает только четыре различных 2-цветных ожерелья длиной 3, представленных каноническими формами 000, 001, 011, 111: остальные строки 100 и 010 эквивалентны 001 при вращении, а 110 и 101 эквивалентны 011. То есть, эквивалентность при вращении разбивает множество X строк на четыре орбиты: формула Бернсайда использует число вращений, которое равно 3, включая нулевое вращение, и число битовых строк, остающихся неизменными при каждом вращении. Все 8 битовых векторов остаются неизменными при нулевом вращении, а два (000 и 111) остаются неизменными при двух других вращениях. Таким образом, число орбит равно:
Для длины 4 существует 16 возможных битовых строк; 4 вращения; нулевое вращение оставляет все 16 строк неизменными; вращения на 1 и 3 оставляют по две строки неизменными (0000 и 1111); вращение на 2 оставляет 4 битовые строки неизменными (0000, 0101, 1010, 1111). Таким образом, число различных ожерелий равно: , представленное каноническими формами 0000, 0001, 0011, 0101, 0111, 1111. Общий случай для n бит и k цветов задается полиномом ожерелья.
Перечисление против генерации
Лемма Бернсайда подсчитывает различные объекты, но не строит их. В общем случае, комбинаторная генерация с отбрасыванием изоморфизмов рассматривает группу симметрий g, действующую на объектах x. Но вместо проверки того, что g ⋅ x = x, проверяется, что g ⋅ x ещё не было сгенерировано. Один из способов добиться этого — проверить, что g ⋅ x не является лексикографически меньше, чем x, используя лексикографически наименьший элемент каждого класса эквивалентности в качестве канонической формы этого класса. Подсчёт объектов, сгенерированных с использованием такой техники, может служить проверкой корректности применения леммы Бернсайда.
История: лемма, которая не принадлежит Бёрнсайд
Уильям Бернсайд сформулировал и доказал эту лемму в своей книге 1897 года о конечных группах, приписывая ее Фробениусу. Однако даже до Фробениуса формула была известна Коши в 1845 году. Следовательно, эту лемму иногда называют леммой, которая не принадлежит Бернсайду. Неправильное присвоение имен научным открытиям известно как закон эпонимии Стиглера.