Ожерелье полиномиальное

Подсчитывает количество ожерелий из n цветных бусин, выбранных из α доступных цветов

В комбинаторной математике многочлен ожерелья или функция подсчета ожерелья Моро, введенная К. Моро  (1872), подсчитывает количество различных ожерелий из n цветных бусин, выбранных из α доступных цветов, расположенных в цикле. В отличие от обычной задачи раскраски графа , ожерелья предполагаются апериодическими (не состоящими из повторяющихся подпоследовательностей) и подсчитываются с точностью до вращения (вращение бусин вокруг ожерелья считается тем же ожерельем), но без переворачивания (изменение порядка бусин на противоположный считается другим ожерельем). Эта подсчитывающая функция также описывает размерности в свободной алгебре Ли и количество неприводимых многочленов над конечным полем.

Определение

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

${\displaystyle \alpha ^{n}\ =\ \sum _{d\,|\,n}d\,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}\varphi \!\left({n \over d}\right)\alpha ^{d},}$

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

Приложения

Полиномы ожерелья и выглядят как: ${\displaystyle M(\alpha ,n)}$ ${\displaystyle N(\alpha ,n)}$

• Число апериодических ожерелий (или эквивалентно слов Линдона ), которые являются циклическими расположениями n цветных бусин, имеющих α доступных цветов. Два таких ожерелья считаются равными, если они связаны поворотом (не учитывая отражения). Апериодический относится к ожерельям без вращательной симметрии, имеющим n различных поворотов. Соответственно, дает число ожерелий, включая периодические: это легко вычисляется с помощью теории Полиа . ${\displaystyle N(\alpha ,n)}$
• Размерность компоненты степени n свободной алгебры Ли на α- образующих («формула Витта» ^[1] ), или, что то же самое, число слов Холла длины n . Соответственно, должна быть размерностью компоненты степени n свободной йордановой алгебры . ${\displaystyle N(\alpha ,n)}$
• Число монических неприводимых многочленов степени n над конечным полем с α элементами (когда — степень простого числа). Соответственно, — число многочленов, которые являются примарными (степень неприводимого). ${\displaystyle \alpha =p^{d}}$ ${\displaystyle N(\alpha ,n)}$
• Показатель степени в циклотомическом тождестве : . ${\displaystyle \textstyle {1 \over 1-\alpha z}\ =\ \prod _{j=1}^{\infty }\left({1 \over 1-z^{j}}\right)^{\!M(\alpha ,j)}}$

Хотя все эти различные типы объектов подсчитываются одним и тем же многочленом, их точные отношения остаются неясными. Например, нет канонической биекции между неприводимыми многочленами и словами Линдона. ^[2] Однако существует неканоническая биекция, как следует ниже. Для любого монического неприводимого многочлена степени n над полем F с α элементами его корни лежат в поле расширения Галуа L с элементами. Можно выбрать элемент , такой что является F -базисом для L ( нормальным базисом ), где σ — автоморфизм Фробениуса . Тогда биекцию можно определить, взяв ожерелье, рассматриваемое как класс эквивалентности функций , к неприводимому многочлену ${\displaystyle \alpha ^{n}}$ ${\displaystyle x\in L}$ ${\displaystyle \{x,\sigma x,...,\sigma ^{n-1}x\}}$ ${\displaystyle \sigma y=y^{\alpha }}$ ${\displaystyle f:\{1,...,n\}\rightarrow F}$

${\displaystyle \phi (T)=(T-y)(T-\sigma y)\cdots (T-\sigma ^{n-1}y)\in F[T]}$ для . ${\displaystyle y=f(1)x+f(2)\sigma x+\cdots +f(n)\sigma ^{n-1}x}$

Различные циклические перестановки f , т.е. различные представители одного и того же класса эквивалентности ожерелья, дают циклические перестановки множителей , поэтому это соответствие хорошо определено. ^[3] ${\displaystyle \phi (T)}$

Отношения междуМиН

Полиномы для M и N легко соотносятся в терминах свертки Дирихле арифметических функций , считая их константами. ${\displaystyle f(n)*g(n)}$ ${\displaystyle \alpha }$

• Формула для M дает , ${\displaystyle n\,M(n)\,=\,\mu (n)*\alpha ^{n}}$
• Формула для N даёт . ${\displaystyle n\,N(n)\,=\,\varphi (n)*\alpha ^{n}\,=\,n*\mu (n)*\alpha ^{n}}$
• Их отношение дает или эквивалентно , поскольку функция полностью мультипликативна . ${\displaystyle N(n)\,=\,1*M(n)}$ ${\displaystyle n\,N(n)\,=\,n*(n\,M(n))}$ ${\displaystyle f(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 {\begin{aligned}M(1,n)&=0{\text{ if }}n>1\\[6pt]M(\alpha ,1)&=\alpha \\[6pt]M(\alpha ,2)&={\tfrac {1}{2}}(\alpha ^{2}-\alpha )\\[6pt]M(\alpha ,3)&={\tfrac {1}{3}}(\alpha ^{3}-\alpha )\\[6pt]M(\alpha ,4)&={\tfrac {1}{4}}(\alpha ^{4}-\alpha ^{2})\\[6pt]M(\alpha ,5)&={\tfrac {1}{5}}(\alpha ^{5}-\alpha )\\[6pt]M(\alpha ,6)&={\tfrac {1}{6}}(\alpha ^{6}-\alpha ^{3}-\alpha ^{2}+\alpha )\\[6pt]M(\alpha ,p)&={\tfrac {1}{p}}(\alpha ^{p}-\alpha )&{\text{ if }}p{\text{ is prime}}\\[6pt]M(\alpha ,p^{N})&={\tfrac {1}{p^{N}}}(\alpha ^{p^{N}}-\alpha ^{p^{N-1}})&{\text{ if }}p{\text{ is prime}}\end{aligned}}}$

Для , начиная с нулевой длины, они образуют целочисленную последовательность ${\displaystyle \alpha =2}$

1, 2, 1, 2, 3, 6, 9, 18, 30, 56, 99, 186, 335, ... (последовательность A001037 в OEIS )

Идентичности

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

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

где "НОД" - наибольший общий делитель , а "НОК" - наименьшее общее кратное . В более общем смысле,

${\displaystyle M(\alpha \beta \cdots \gamma ,n)=\sum _{\operatorname {lcm} (i,j,\ldots ,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).}$

Ссылки

1. Лотер, М. (1997). Комбинаторика слов . Энциклопедия математики и ее приложений. Т. 17. Перрен, Д.; Ройтенауэр, К.; Берстель, Дж.; Пин, Дж. Э.; Пирилло, Г.; Фоата, Д.; Сакарович, Дж.; Саймон, И.; Шютценбергер, МП; Чоффрут, К.; Кори, Р.; Линдон, Роджер; Рота, Джан-Карло. Предисловие Роджера Линдона (2-е изд.). Cambridge University Press . С. 79, 84. ISBN 978-0-521-59924-5. MR  1475463. Zbl  0874.20040.
2. Эми Глен, (2012) Комбинаторика слов Линдона , Мельбурнская лекция
3. Адальберт Кербер, (1991) Алгебраическая комбинаторика посредством конечных групповых действий , [1]

• Моро, К. (1872), «Sur les permutations circulaires Differentes (О различных круговых перестановках)», Nouvelles Annales de Mathématiques , Série 2 (на французском языке), 11 : 309–31, JFM  04.0086.01
• Метрополис, Н.; Рота , Джан-Карло (1983), «Векторы Витта и алгебра ожерелий», Advances in Mathematics , 50 (2): 95–125, doi : 10.1016/0001-8708(83)90035-X , ISSN  0001-8708, MR  0723197, Zbl  0545.05009
• Ройтенауэр, Кристоф (1988). «Круговые движения и несократимые полиномии». Энн. наук. Математика. Квебек . 12 (2): 275–285.