Математика · объяснение и практика

Почему число раскрасок с точностью до поворота нельзя всегда делить на число поворотов

Как считать раскраски кольца с точностью до поворота, почему симметричные узоры мешают простому делению и как среднее число неподвижных раскрасок исправляет подсчёт.

Синяя и оранжевая половины складываются в целый круг.

В теме Доказательства и комбинаторные модели · Учебная карта

В маршруте Счёт через устройство объектов · 10 тем

Главная мысль

Лемма Бёрнсайда считает классы раскрасок как среднее число раскрасок, сохраняемых каждым разрешённым преобразованием. Для кольца нужно заранее решить, разрешены ли только повороты или также отражения.

Почему деление на число позиций даёт сбой

В кольце из четырёх позиций с двумя цветами есть шестнадцать раскрасок помеченных мест. Если забыть начало и считать одинаковыми циклические повороты, простое деление на четыре дало бы четыре класса. Но одноцветный узор имеет только одну различимую повёрнутую запись, а произвольный несимметричный — четыре. Размеры классов неодинаковы.

В этой статье разрешены только повороты, не перевороты кольца. Число классов равно среднему количеству раскрасок, которые не меняются под действием каждого поворота. Тождественное преобразование тоже учитывается: оно сохраняет все исходные раскраски. Исключение этого преобразования из среднего сразу исказило бы результат.

Сосчитать неподвижные раскраски

Для четырёх позиций поворот на четверть оборота требует одного цвета во всех местах и сохраняет две раскраски. Поворот на половину допускает независимые цвета двух пар противоположных мест и сохраняет четыре. Поворот на три четверти снова сохраняет две, а отсутствие поворота — шестнадцать. Среднее (16+2+4+2)/4=6 даёт число классов.

Общий механизм виден через циклы перестановки позиций. Все места одного цикла должны иметь одинаковый цвет, а разные циклы можно красить независимо. При q цветах и c циклах получается qᶜ неподвижных раскрасок. Это подсчёт на конкретном преобразовании, после которого нужно усреднить по всем преобразованиям выбранной группы.

Пример

Сколько раскрасок трёхместного кольца тремя цветами существует с точностью только до поворота?

Без поворота сохраняются 3³=27 раскрасок. Каждый из двух нетождественных поворотов циклически связывает все места и сохраняет три одноцветных. Среднее (27+3+3)/3=11.

Граница между ожерельем и браслетом

Если разрешить отражения, набор преобразований расширится, и некоторые ранее разные поворотные классы объединятся. Нельзя просто ещё раз поделить число на два: зеркально симметричные классы снова имеют меньшую орбиту. Нужно отдельно учесть неподвижные раскраски отражений в том же среднем.

Также меняет задачу требование фиксированного количества бусин каждого цвета. Тогда не всякая одноцветная или циклически постоянная раскраска допустима. Для каждого поворота считают только сохраняемые узоры нужного состава. Формула среднего продолжает работать, но исходные числа неподвижных объектов уже не равны безусловным степеням количества цветов.

От чтения к действию

А теперь — вы

Кольцо имеет пять позиций и два цвета; одинаковыми считаются только повороты. Каждый нетождественный поворот сохраняет две одноцветные раскраски. Сколько классов?

Частые вопросы

Почему тождественный поворот входит в формулу?

Он является элементом группы разрешённых поворотов и сохраняет каждую раскраску; среднее берётся по всей группе.

Можно ли тем же способом считать с отражениями?

Да, но нужно включить их как дополнительные преобразования и отдельно вычислить число сохраняемых ими допустимых раскрасок.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться