Многочлен ожерелья

Многочлен ожерелья, или функция подсчёта ожерелий Моро, предложенный Шарлем Моро, — это семейство многочленов $M(\alpha ,n)$ от переменной $\alpha$ такое, что:

$\alpha ^{n}\ =\ \sum _{d\,|\,n}d\,M(\alpha ,d).$

С помощью обращения Мёбиуса получим формулу для $M(\alpha ,d)$

$M(\alpha ,n)\ =\ {1 \over n}\sum _{d\,|\,n}\mu \!\left({n \over d}\right)\alpha ^{d},$

где $\mu$ является классической функцией Мёбиуса.

Тесно связанным семейством, называемым обобщённый многочлен ожерелья или обобщённой функцией подсчёта ожерелий, является семейство:

$N(\alpha ,n)\ =\ \sum _{d|n}M(\alpha ,d)\ =\ {\frac {1}{n}}\sum _{d\,|\,n}\phi \!\left({n \over d}\right)\alpha ^{d},$

где $\phi$ — функция Эйлера.

Связь M и N

Вышеприведённые формулы тесно связаны в терминах свёртки Дирихле арифметических функций $f(n)*g(n)$ с $\alpha$ в качестве константы.

• Формула для M даёт $n\,M(n)\,=\,\mu (n)*\alpha ^{n}$,
• Формула для N даёт $n\,N(n)\,=\,\phi (n)*\alpha ^{n}\,=\,n*\mu (n)*\alpha ^{n}$.
• Их связь даёт $N(n)\,=\,1*M(n)$, что эквивалентно $n\,N(n)\,=\,n*(n\,M(n))$, поскольку n является вполне мультиаликативны.

Из любых двух равенств вытекает третье, например:

$n*\mu (n)*\alpha ^{n}\,=\,n\,N(n)\,=\,n*(n\,M(n))\quad \Longrightarrow \quad \mu (n)*\alpha ^{n}=n\,M(n)$

согласно сокращению в алгебре Дирихле.

Примеры

$M(1,n)=0$ если n > 1

$M(\alpha ,1)=\alpha$

$M(\alpha ,2)={\tfrac {1}{2}}(\alpha ^{2}-\alpha )$

$M(\alpha ,3)={\tfrac {1}{3}}(\alpha ^{3}-\alpha )$

$M(\alpha ,4)={\tfrac {1}{4}}(\alpha ^{4}-\alpha ^{2})$

$M(\alpha ,5)={\tfrac {1}{5}}(\alpha ^{5}-\alpha )$

$M(\alpha ,6)={\tfrac {1}{6}}(\alpha ^{6}-\alpha ^{3}-\alpha ^{2}+\alpha )$

$M(\alpha ,p)={\tfrac {1}{p}}(\alpha ^{p}-\alpha )$, если p простое

$M(\alpha ,p^{N})={\tfrac {1}{p^{N}}}(\alpha ^{p^{N}}-\alpha ^{p^{N-1}})$, если p простое

Тождества

Основная статья: Ожерельное кольцо

Многочлены удовлетворяют различным комбинаторным тождествам, которые представили Метрополис и Рота:

$M(\alpha \beta ,n)=\sum _{\operatorname {lcm} (i,j)=n}\gcd(i,j)M(\alpha ,i)M(\beta ,j),$

где «gcd» является наибольшим общим делителем, а «lcm» является наименьшим общим кратным. Более обще:

$M(\alpha \beta \cdots \gamma ,n)=\sum _{\operatorname {lcm} (i,j,\cdots ,k)=n}\gcd(i,j,\cdots ,k)M(\alpha ,i)M(\beta ,j)\cdots M(\gamma ,k),$

из чего также следует:

$M(\beta ^{m},n)=\sum _{\operatorname {lcm} (j,m)=nm}{\frac {j}{n}}M(\beta ,j).$

Цикловое тождество

Основная статья: Цикловое тождество

${1 \over 1-\alpha z}\ =\ \prod _{j=1}^{\infty }\left({1 \over 1-z^{j}}\right)^{M(\alpha ,j)}$

Приложения

Многочлены ожерелий $M(\alpha ,n)$ появляются как:

• Число апериодических ожерелий (или, эквивалентно, слов Линдона), которые могут быть сделаны путём расстановки n цветных бусин, имеющих α доступных цветов. Два таких ожерелья считаются равными, если они связаны вращением (но не отражением). Слово аперидические относятся к ожерельям без вращательной симметрии. Многочлен $N(\alpha ,n)$ даёт число ожерелий, включая периодические — это число легко вычислить с помощью теоремы Редфилда — Пойи.
• Размерность n элементов свободной алгебры Ли на α генераторах («формула Витта»). Здесь $N(\alpha ,n)$ должно быть размерностью n элементов соответствующей свободной йордановой алгебры.
• Число нормированных неприводимых многочленов степени n над конечным полем с α элементами (если $\alpha =p^{d}$ является простой степенью). Здесь $N(\alpha ,n)$ является числом многочленов, которые являются степенью неприводимого многочлена.
• Экспонента в цикловом тождестве.