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

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

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

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

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

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

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

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

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

Связь M и N

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

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

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

$n*\mu (n)*{\alpha }^n=nN(n)=n*(nM(n))⟹\mu (n)*{\alpha }^n=nM(n)$

согласно сокращению в Шаблон:Не переведено 5.

Примеры

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

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

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

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

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

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

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

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

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

Тождества

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

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

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

$M(\alpha \beta \cdots \gamma ,n)=\sum _{\mathrm{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 _{\mathrm{lcm}(j,m)=nm}\frac{j}{n}M(\beta ,j).$

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

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

Приложения

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

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

Литература

• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга