WikiSort.ru - Не сортированное

Цикловой индекс

Цикловой индекс подгруппы ${\displaystyle A}$ симметрической группы ${\displaystyle S_{n}}$ определяется как многочлен от ${\displaystyle n}$ переменных ${\displaystyle t_{1},t_{2},\ldots ,t_{n}}$

${\displaystyle Z_{A}(t_{1},t_{2},\ldots ,t_{n})={\frac {1}{|A|}}\sum _{a\in A}t_{1}^{j_{1}(a)}\cdot t_{2}^{j_{2}(a)}\cdot \ldots \cdot t_{n}^{j_{n}(a)},}$

где ${\displaystyle j_{k}(a)}$  — число циклов длины ${\displaystyle k}$ в перестановке ${\displaystyle a}$ .

Задача о количестве ожерелий

Задача. Найти количество ожерелий, составленных из ${\displaystyle n}$ бусинок двух цветов. Ожерелья, совпадающие при повороте, считаются одинаковыми (перевороты не допускаются).

Решение. Пусть множество ${\displaystyle X=\{1,2,\ldots ,n\}}$ соответствует номерам бусинок в ожерелье, а ${\displaystyle Y=\{0,1\}}$  — множество возможных цветов. Весовую функцию положим равной ${\displaystyle w(y)=y}$ для всех ${\displaystyle y\in Y}$ . Во множестве ${\displaystyle Y}$ имеется один элемент веса 0 и один — веса 1, то есть ${\displaystyle c_{0}=1}$ и ${\displaystyle c_{1}=1}$ . Откуда ${\displaystyle c(t)=1+t}$ .

Пусть ${\displaystyle F=\{f\mid f:X\rightarrow Y\}}$  — множество всех функций из ${\displaystyle X}$ в ${\displaystyle Y}$ . Любая функция ${\displaystyle f\in F}$ задает некоторое ожерелье и, наоборот, каждое ожерелье задаётся некоторой функцией из ${\displaystyle F}$ . При этом вес функции равен количеству бусинок цвета 1 в соответствующем ожерелье.

На множестве ${\displaystyle X}$ действует группа поворотов ${\displaystyle A}$ , порожденная циклической перестановкой ${\displaystyle (1,2,\ldots ,n)}$ , которая определяет отношение эквивалентности на ${\displaystyle F}$ . Тогда ожерелья совпадающие при повороте будут в точности соответствовать эквивалентным функциям, и задача сводится к подсчёту числа орбит.

Цикловой индекс группы ${\displaystyle A}$ равен

${\displaystyle Z_{A}(t_{1},\ldots ,t_{n})={\frac {1}{n}}\sum _{k=1}^{n}t_{n/(k,n)}^{(k,n)}={\frac {1}{n}}\sum _{d\mid n}\varphi (n/d)t_{n/d}^{d}={\frac {1}{n}}\sum _{d|n}\varphi (d)t_{d}^{n/d}}$ ,

где ${\displaystyle \varphi (d)}$  — функция Эйлера, ${\displaystyle (k,n)}$  — наибольший общий делитель чисел ${\displaystyle k}$ и ${\displaystyle n}$ .

По теореме Редфилда — Пойа

${\displaystyle C(t)=Z_{A}(1+t,1+t^{2},\ldots ,1+t^{n})={\frac {1}{n}}\sum _{d|n}\varphi (d)(1+t^{d})^{n/d}}$

Число орбит веса ${\displaystyle k}$ (то есть различных ожерелий с ${\displaystyle k}$ бусинками цвета 1) равно ${\displaystyle C_{k}}$ , коэффициенту при ${\displaystyle t^{k}}$ в ${\displaystyle C(t)}$ :

${\displaystyle C_{k}={\frac {1}{n}}\sum _{d|(n,k)}\varphi (d){n/d \choose k/d}}$ .

Общее число различных орбит (или ожерелий) равно

${\displaystyle \sum _{k}C_{k}=C(1)={\frac {1}{n}}\sum _{d|n}\varphi (d)2^{n/d}}$