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

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

Определение

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

α н   =   ∑ г | н г М ( α , г ) . {\displaystyle \alpha ^{n}\ =\ \sum _{d\,|\,n}d\,M(\alpha ,d).}

По методу обращения Мёбиуса они задаются выражением

М ( α , н )   =   1 н ∑ г | н μ ( н г ) α г , {\displaystyle M(\alpha ,n)\ =\ {1 \over n}\sum _{d\,|\,n}\mu \!\left({n \over d}\right)\alpha ^{d},}

где — классическая функция Мёбиуса . μ {\displaystyle \мю}

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

Н ( α , н )   =   ∑ г | н М ( α , г )   =   1 н ∑ г | н φ ( н г ) α г , {\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(\альфа,n)} Н ( α , н ) {\displaystyle N(\альфа,n)}

  • Число апериодических ожерелий (или эквивалентно слов Линдона ), которые являются циклическими расположениями n цветных бусин, имеющих α доступных цветов. Два таких ожерелья считаются равными, если они связаны поворотом (не учитывая отражения). Апериодический относится к ожерельям без вращательной симметрии, имеющим n различных поворотов. Соответственно, дает число ожерелий, включая периодические: это легко вычисляется с помощью теории Полиа . Н ( α , н ) {\displaystyle N(\альфа,n)}
  • Размерность компоненты степени n свободной алгебры Ли на α- образующих («формула Витта» [1] ), или, что то же самое, число слов Холла длины n . Соответственно, должна быть размерностью компоненты степени n свободной йордановой алгебры . Н ( α , н ) {\displaystyle N(\альфа,n)}
  • Число монических неприводимых многочленов степени n над конечным полем с α элементами (когда — степень простого числа). Соответственно, — число многочленов, которые являются примарными (степень неприводимого). α = п г {\displaystyle \альфа =p^{d}} Н ( α , н ) {\displaystyle N(\альфа,n)}
  • Показатель степени в циклотомическом тождестве : . 1 1 − α з   =   ∏ дж = 1 ∞ ( 1 1 − з дж ) М ( α , дж ) {\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 \альфа ^{n}} х ∈ Л {\displaystyle x\in L} { х , σ х , . . . , σ н − 1 х } {\displaystyle \{x,\сигма x,...,\сигма ^{n-1}x\}} σ у = у α {\displaystyle \sigma y=y^{\alpha }} ф : { 1 , . . . , н } → Ф {\displaystyle f:\{1,...,n\}\rightarrow F}

ϕ ( Т ) = ( Т − у ) ( Т − σ у ) ⋯ ( Т − σ н − 1 у ) ∈ Ф [ Т ] {\displaystyle \phi (T)=(Ty)(T-\sigma y)\cdots (T-\sigma ^{n-1}y)\in F[T]} для . у = ф ( 1 ) х + ф ( 2 ) σ х + ⋯ + ф ( н ) σ н − 1 х {\displaystyle y=f(1)x+f(2)\сигма x+\cdots +f(n)\сигма ^{n-1}x}

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

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

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

  • Формула для M дает , н М ( н ) = μ ( н ) ∗ α н {\displaystyle n\,M (n)\,=\,\mu (n)*\alpha ^{n}}
  • Формула для N даёт . н Н ( н ) = φ ( н ) ∗ α н = н ∗ μ ( н ) ∗ α н {\displaystyle n\,N(n)\,=\,\varphi (n)*\alpha ^{n}\,=\,n*\mu (n)*\alpha ^{n}}
  • Их отношение дает или эквивалентно , поскольку функция полностью мультипликативна . Н ( н ) = 1 ∗ М ( н ) {\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)}

путем сокращения в алгебре Дирихле.

Примеры

М ( 1 , н ) = 0  если  н > 1 М ( α , 1 ) = α М ( α , 2 ) = 1 2 ( α 2 − α ) М ( α , 3 ) = 1 3 ( α 3 − α ) М ( α , 4 ) = 1 4 ( α 4 − α 2 ) М ( α , 5 ) = 1 5 ( α 5 − α ) М ( α , 6 ) = 1 6 ( α 6 − α 3 − α 2 + α ) М ( α , п ) = 1 п ( α п − α )  если  п  является главным М ( α , п Н ) = 1 п Н ( α п Н − α п Н − 1 )  если  п  является главным {\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}}}

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

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

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

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

M ( α β , n ) = ∑ lcm ⁡ ( i , j ) = n gcd ( i , j ) M ( α , i ) M ( β , j ) , {\displaystyle M(\alpha \beta ,n)=\sum _{\operatorname {lcm} (i,j)=n}\gcd(i,j)M(\alpha ,i)M(\beta ,j),}

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

M ( α β ⋯ γ , n ) = ∑ lcm ⁡ ( i , j , … , k ) = n gcd ( i , j , ⋯ , k ) M ( α , i ) M ( β , j ) ⋯ M ( γ , k ) , {\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),}

что также подразумевает:

M ( β m , n ) = ∑ lcm ⁡ ( j , m ) = n m j n M ( β , j ) . {\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 .
Retrieved from "https://en.wikipedia.org/w/index.php?title=Necklace_polynomial&oldid=1229922960"