Лемма Бернсайда и теорема Пойа: Комбинаторика симметрий
При решении сложных комбинаторных задач часто возникает проблема симметрии. Например, сколькими способами можно раскрасить грани куба в три цвета? Если использовать обычные формулы размещений, мы посчитаем один и тот же раскрашенный куб несколько раз, просто потому что его можно повернуть в пространстве. Для точного подсчета уникальных конфигураций с учетом симметрий в дискретной математике применяется лемма Бернсайда и ее мощное обобщение — теорема Редфилда-Пойа.
Лемма Бернсайда (часто называемая леммой не Бернсайда, так как она была известна еще Коши и Фробениусу) является краеугольным камнем теории групп в применении к комбинаторике. Она позволяет найти количество орбит (классов эквивалентности) при действии конечной группы на конечное множество.
Суть леммы заключается в следующем: количество уникальных объектов с учетом симметрии равно среднему арифметическому чисел неподвижных точек для каждого элемента группы симметрий. Возвращаясь к нашему кубу: группа вращений куба состоит из 24 элементов (включая тождественное вращение — оставление на месте). Чтобы узнать число уникальных раскрасок, мы должны для каждого из 24 вращений посчитать, сколько раскрасок не меняют своего вида при этом конкретном вращении, сложить эти числа и разделить на 24.
Однако при большом количестве элементов считать неподвижные точки вручную становится невозможно. Здесь на помощь приходит теорема перечисления Пойа. Венгерский математик Дьёрдь Пойа формализовал этот процесс, введя понятие циклического индекса группы. Это специальный многочлен, который кодирует структуру всех перестановок в группе симметрий.
Подставляя в циклический индекс веса цветов (или другие параметры объектов), можно одним алгебраическим действием получить не только общее количество уникальных конфигураций, но и точное распределение: например, сколько существует кубов, у которых ровно две грани красные, а четыре — синие.
Этот математический аппарат имеет грандиозное прикладное значение. В химии теорема Пойа используется для подсчета количества структурных изомеров сложных органических молекул (например, алканов). В информатике она применяется для анализа изоморфизма графов, перечисления булевых функций с точностью до перестановки переменных и в задачах криптоанализа для оценки пространства ключей при блочном шифровании.
