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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle M(1,n)=0}$ если n > 1

${\displaystyle M(\alpha ,1)=\alpha }$

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

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

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

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

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

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

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

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

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

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

${\displaystyle 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),}$

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

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

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

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

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