Перейти к содержанию

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

Материал из энциклопедии Руниверсалис

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

Примечания

Литература

  • Moreau C. Sur les permutations circulaires distinctes (On distinct circular permutations) // Nouvelles Annales de Mathématiques, Journal des Candidats Aux écoles Polytechnique et Normale, Sér. 2. — 1872. — Т. 11. — С. 309–31.
  • Metropolis N., Rota G.-C. Witt vectors and the algebra of necklaces // Advances in Mathematics. — 1983. — Т. 50, вып. 2. — С. 95–125. — ISSN 0001-8708. — doi:10.1016/0001-8708(83)90035-X.
  • Christophe Reutenauer. Mots circulaires et polynomies irreductibles // Ann. Sc. Math. Quebec. — 1988. — Т. 12, вып. 2. — С. 275–285.
  • Lothaire M., Perrin D., Reutenauer C., Berstel J., Pin J. E., Pirillo G., Foata D., Sakarovitch J., Simon I., Schützenberger M. P., Choffrut C., Cori R., Lyndon R., Rota G-C. Combinatorics on words. — 2nd. — Cambridge University Press, 1997. — Т. 17. — (Encyclopedia of Mathematics and Its Applications). — ISBN 978-0-521-59924-5.