Оригинал: https://crypto.stanford.edu/~blynn/polya/
Допустим, вы хотите создать ожерелье из 10 бусин, и у вас в распоряжении бусины трех цветов: красные, зеленые и синие. Какое количество уникальных ожерелий можно изготовить?
Из этого количества, сколько ожерелий включают в себя по крайней мере 3 красные бусины? А сколько ожерелий состоит из комбинации 2 красных, 3 зеленых и 5 синих бусин?
На первый взгляд кажется, что ответить на эти вопросы довольно просто. Ведь, если рассмотреть схожий пример: какими способами можно упорядочить 10 различных бусин в ожерелье? Решение прямолинейно: найдите все возможные перестановки для 10 бусин, то есть 10!, после чего разделите полученное число на 20. Это потому что каждая перестановка учтена 10 раз из-за возможности вращения ожерелья, и еще каждая перестановка учтена дважды из-за возможности переворота ожерелья. Итак, ответ будет: 10!/20 = 181440.
Возможно, аналогичная методика позволит нам решить и первую задачу. Но для начала давайте рассмотрим более простой пример — ожерелье из 6 бусин. Первый этап довольно прямолинейный: число вариантов, как можно раскрасить 6 бусин, когда каждая из них может быть красной, зеленой или синей, составляет 3^6 = 729. Затем, когда бусины нанизаны на ожерелье, нужно учесть повторяющиеся узоры. Например, узоры RRRRRG и RRRRGR считаются одним и тем же, так как, вращая ожерелье, можно перейти от одного к другому. В то же время некоторые узоры, вроде RRRRRR, учитываются только один раз.
Может показаться, что здесь всего несколько особых случаев, и нам просто потребуется скорректировать общее число комбинаций для получения итогового ответа. Однако, ожерелье, где 5 бусин красные, а одна — зеленая, встречается 6 раз. Ожерелье, полностью состоящее из красных бусин, учитывается один раз. Ожерелье с 4 красными и 2 зелеными бусинами на противоположных концах (как в узоре RRGRRG) учитывается 3 раза и так далее. А мы даже еще не учли синие бусины!
Более того, драматические изменения происходят, когда добавляется всего лишь одна бусина. Например, существует 7 раскрасок, эквивалентных RRGRRRG, и фактически каждая раскраска для корпуса из 7 бусин появится либо 1, 2, 7 или 14 раз.
Нет простого выхода. Чтобы ответить на вопрос, нам необходимо изучить группу симметрии n-бусинного ожерелья: группу диэдра порядка 2 n.
Почему группа симметрии не имеет значения для простого варианта вопроса, где каждая бусинка уникальна? На самом деле так и есть, но единственная информация, которая нам нужна, — это размер группы симметрии. Когда каждая бусина уникальна, различные операции вращения и отражения гарантированно приведут к разным цветам, поэтому мы знаем, что посчитали каждую ровно 20 раз.
Когда бусины могут иметь тот же цвет, что и другие бусины, вращение или отражение могут оставить цвет неизменным. Например, поворот RRGRRG на 3 бусины не даст никакого эффекта. Поэтому наш алгоритм подсчета должен тесно задействовать группу симметрии.
Рекомендации
См. K. H. Wehrhahn, "Combinatorics: An Introduction".