Задача об ожерельях

Определение:

Требуется посчитать количество ожерелий из [math]n[/math] бусинок, каждая из которых может быть покрашена в один из [math] k [/math] цветов. При сравнении двух ожерелий их можно поворачивать, но не переворачивать (т.е. разрешается сделать циклический сдвиг).

Решение этой задачи опирается на лемму Бернсайда и теорему Пойа.

Определение:

Инвариантная перестановка — такая перестановка, которая по условию задачи не меняет сам объект, а только его представление.

Примером инвариантной перестановки в нашем случае является циклический сдвиг.

Определение:

Неподвижной точкой [math]f[/math] для перестановки называется такой элемент, который инвариантен относительно этой перестановки.

Лемма Бернсайда

Лемма (Бернсайд):

Количество комбинаторных объектов равно сумме количеств неподвижных точек по всем перестановкам из группы [math]G[/math] , делённой на размер этой группы: [math] C = [/math] [math]\frac{1} {|G|}[/math][math]\sum\limits_{k \in G}I(k)[/math]. Где [math]I(k)[/math] — количество неподвижных точек для перестановки [math]k[/math].

Доказательство:

[math]\triangleright[/math]

Рассмотрим сумму в числителе дроби справа: [math]\sum\limits_{k \in G}I(k)[/math] — это ничто иное как количество "инвариантных пар". Очевидно, что в формуле мы имеем право изменить порядок суммирования - сделать внешнюю сумму по элементам множества [math]f[/math], а внутри нее поставить величину [math]J(f)[/math] — количество перестановок, относительно которых объект [math]f[/math] инвариантен: [math]C =[/math] [math] \frac{1} {|G|}[/math][math]\sum\limits_{f} J(f)[/math] Для доказательства этой формулы составим таблицу, столбцы которой будут подписаны всеми значениями [math]f_i[/math], строки — всеми перестановками [math]k_j[/math], а в клетках таблицы будут стоять их произведения . Тогда, если мы будем рассматривать столбцы этой таблицы как множества, то некоторые из них могут совпасть, и это будет означать, что соответствующие этим столбцам [math]f[/math] также эквивалентны. Таким образом, количество различных как множество столбцов равно количеству различных комбинаторных объектов. Столбцы таблицы сами распадаются на комбинаторные обекты; зафиксируем теперь какой-либо объект и рассмотрим столбцы в нём. Во-первых, заметим, что в этих столбцах могут стоять только элементы [math]f_i[/math] одного объекта (иначе получилось бы, что некоторым эквивалентным преобразованием мы перешли в другой комбинаторный объект, что невозможно). Во-вторых, каждый элемент [math]f_i[/math] будет встречаться одинаковое число раз во всех столбцах (это также следует из того, что столбцы соответствуют эквивалентным элементам). Отсюда можно сделать вывод, что все столбцы внутри одного комбинаторного объекта совпадают друг с другом как мультимножества. Теперь зафиксируем произвольный элемент [math]f[/math]. С одной стороны, он встречается в своём столбце ровно [math]J(f)[/math] раз (по самому определению). С другой стороны, все столбцы внутри одного комбинаторного объекта одинаковы как мультимножества. Следовательно, внутри каждого столбца данного комбинаторного объекта любой элемент [math]g[/math] встречается ровно [math]J(g)[/math] раз. Таким образом, если мы возьмём произвольным образом от каждого класса эквивалентности по одному столбцу и просуммируем количество элементов в них, то получим, с одной стороны, [math]C|G|[/math] (это получается, просто умножив количество столбцов на их размер), а с другой стороны — сумму величин [math]J(f)[/math] по всем [math]f[/math](это следует из всех предыдущих рассуждений): [math] C =[/math] [math] \frac{1} {|G|}[/math][math]\sum\limits_{f} J(f)[/math]

[math]\triangleleft[/math]

Теорема Пойа

Теорема (Пойа):

[math] C =[/math] [math] \frac{1} {|G|}[/math][math]\sum\limits_{k \in G} l^{P(k)}[/math] ,где [math]C[/math] — кол-во различных комбинаторных объектов, [math]P(k)[/math] - кол-во циклов в перестановке [math]k[/math], [math]l[/math] — кол-во различных состояний одного элемента.

Доказательство:

[math]\triangleright[/math]

Для доказательства этой теорем достаточно установить следующее равенство [math]I(k) = l^{P(k)}[/math] Рассмотрим некоторую перестановку [math]k[/math] и некоторый элемент [math]f[/math]. Под действием перестановки [math]k[/math] элементы [math]f[/math] передвигаются, как известно, по циклам перестановки. Заметим, что внутри каждого цикла перестановки должны находиться одинаковые элементы [math]f[/math]. В то же время, для разных циклов никакой связи между значениями элементов не возникает. Таким образом, для каждого цикла перестановки [math]k[/math] мы выбираем по одному значению, и тем самым мы получим все представления [math]f[/math], инвариантные относительно этой перестановки, т.е.: [math]I(k) = l^{P(k)}[/math]

[math]\triangleleft[/math]

Алгоритм решения задачи про ожерелья

Пусть нам даны бусинки [math]k[/math] различных цветов, а ожерелье должно состоять из [math]n[/math] бусинок.

Для решения воспользуемся формулой из теоремы Пойа.

[math]C =[/math] [math] \frac{1} {|G|}[/math][math]\sum\limits_{l \in G} k^{P(l)}[/math]

Очевидно, что для каждой перестановки длины [math]n[/math] существует ровно [math]n[/math] циклических сдвигов, теперь найдем [math]P(i)[/math]. Заметим, что в [math]i[/math]-ой перестановке на [math]l[/math]-ой позиции стоит элемент [math](i + l)\mod n[/math]. Также, заметим, что элемент [math]a[/math] переходит в элемент [math]a + in[/math], где [math]i \in [1; k][/math]. Из этого следует, что длина цикла для [math]i[/math]-ой перестановки равна [math]lcm(n, i)/i = n/gcd(i,n)[/math].Откуда следует что:

[math]C =[/math] [math] \frac{1} {n}[/math][math]\sum\limits_{i = 1}^{n} k^{gcd(i,n)}[/math].

где [math]C[/math] - кол-во различных ожерелий,которые можно составить из [math]n[/math] бусинок [math]k[/math] различных цветов.

Cсылки

• Ожерелья