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

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

[math]\displaystyle{ \alpha^n \ =\ \sum_{d\,|\,n} d \, M(\alpha, d). }[/math]

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

[math]\displaystyle{ M(\alpha,n) \ =\ {1\over n}\sum_{d\,|\,n}\mu\!\left({n \over d}\right)\alpha^d, }[/math]

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

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

[math]\displaystyle{ N(\alpha,n)\ =\ \sum_{d|n} M(\alpha,d)\ =\ \frac{1}{n}\sum_{d\,|\,n}\phi\!\left({n \over d}\right)\alpha^d, }[/math]

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

Связь M и N

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

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

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

[math]\displaystyle{ n*\mu(n)*\alpha^n \,=\, n\,N(n) \,=\, n*(n\,M(n)) \quad\Longrightarrow\quad \mu(n)*\alpha^n = n\,M(n) }[/math]

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

Примеры

[math]\displaystyle{ M(1,n) = 0 }[/math] если n > 1

[math]\displaystyle{ M(\alpha,1) = \alpha }[/math]

[math]\displaystyle{ M(\alpha,2) = \tfrac12 (\alpha^2-\alpha) }[/math]

[math]\displaystyle{ M(\alpha,3) = \tfrac13 (\alpha^3-\alpha) }[/math]

[math]\displaystyle{ M(\alpha,4) = \tfrac14 (\alpha^4-\alpha^2) }[/math]

[math]\displaystyle{ M(\alpha,5) = \tfrac15(\alpha^5-\alpha) }[/math]

[math]\displaystyle{ M(\alpha,6) = \tfrac16(\alpha^6-\alpha^3-\alpha^2+\alpha) }[/math]

[math]\displaystyle{ M(\alpha,p) = \tfrac1p (\alpha^{p}-\alpha) }[/math], если p простое

[math]\displaystyle{ M(\alpha,p^N) = \tfrac1{p^N}(\alpha^{p^N}-\alpha^{p^{N-1}}) }[/math], если p простое

Тождества

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

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

[math]\displaystyle{ M(\alpha\beta, n) =\sum_{\operatorname{lcm}(i,j)=n} \gcd(i,j)M(\alpha,i)M(\beta,j), }[/math]

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

[math]\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), }[/math]

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

[math]\displaystyle{ M(\beta^m, n) =\sum_{\operatorname{lcm}(j,m)=nm} \frac{j}{n} M(\beta,j). }[/math]

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

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

[math]\displaystyle{ {1 \over 1-\alpha z}\ =\ \prod_{j=1}^\infty\left({1 \over 1-z^j}\right)^{M(\alpha,j)} }[/math]

Приложения

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

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