Русская Википедия:Многочлен ожерелья
Многочлен ожерелья, или функция подсчёта ожерелий Моро, предложенный Шарлем МороШаблон:Sfn, — это семейство многочленов <math>M(\alpha,n)</math> от переменной <math>\alpha</math> такое, что:
- <math>\alpha^n \ =\ \sum_{d\,|\,n} d \, M(\alpha, d).</math>
С помощью обращения Мёбиуса получим формулу для <math>M(\alpha, d)</math>
- <math> M(\alpha,n) \ =\ {1\over n}\sum_{d\,|\,n}\mu\!\left({n \over d}\right)\alpha^d,</math>
где <math>\mu</math> является классической функцией Мёбиуса.
Тесно связанным семейством, называемым обобщённый многочлен ожерелья или обобщённой функцией подсчёта ожерелий, является семейство:
- <math>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>\phi</math> — функция Эйлера.
Связь M и N
Вышеприведённые формулы тесно связаны в терминах свёртки Дирихле арифметических функций <math>f(n)*g(n)</math> с <math>\alpha</math> в качестве константы.
- Формула для M даёт <math> n\,M(n) \,=\, \mu(n)*\alpha^n</math>,
- Формула для N даёт <math> n\,N(n) \,=\, \phi(n)*\alpha^n \,=\, n*\mu(n)*\alpha^n</math>.
- Их связь даёт <math>N(n)\,=\,1*M(n)</math>, что эквивалентно <math> n\,N(n) \,=\, n*(n\,M(n))</math>, поскольку n является Шаблон:Не переведено 5.
Из любых двух равенств вытекает третье, например:
- <math>
n*\mu(n)*\alpha^n \,=\, n\,N(n) \,=\, n*(n\,M(n)) \quad\Longrightarrow\quad \mu(n)*\alpha^n = n\,M(n)</math> согласно сокращению в Шаблон:Не переведено 5.
Примеры
- <math>M(1,n) = 0</math> если n > 1
- <math>M(\alpha,1) = \alpha </math>
- <math>M(\alpha,2) = \tfrac12 (\alpha^2-\alpha) </math>
- <math>M(\alpha,3) = \tfrac13 (\alpha^3-\alpha) </math>
- <math>M(\alpha,4) = \tfrac14 (\alpha^4-\alpha^2) </math>
- <math>M(\alpha,5) = \tfrac15(\alpha^5-\alpha) </math>
- <math>M(\alpha,6) = \tfrac16(\alpha^6-\alpha^3-\alpha^2+\alpha) </math>
- <math>M(\alpha,p) = \tfrac1p (\alpha^{p}-\alpha) </math>, если p простое
- <math>M(\alpha,p^N) = \tfrac1{p^N}(\alpha^{p^N}-\alpha^{p^{N-1}})</math>, если p простое
Тождества
Шаблон:Основная статья Многочлены удовлетворяют различным комбинаторным тождествам, которые представили Метрополис и Рота:
- <math>
M(\alpha\beta, n) =\sum_{\operatorname{lcm}(i,j)=n} \gcd(i,j)M(\alpha,i)M(\beta,j), </math> где «gcd» является наибольшим общим делителем, а «lcm» является наименьшим общим кратным. Более обще:
- <math>
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>
M(\beta^m, n) =\sum_{\operatorname{lcm}(j,m)=nm} \frac{j}{n} M(\beta,j). </math>
Цикловое тождество
- <math>{1 \over 1-\alpha z}\ =\ \prod_{j=1}^\infty\left({1 \over 1-z^j}\right)^{M(\alpha,j)}</math>
Приложения
Многочлены ожерелий <math>M(\alpha,n)</math> появляются как:
- Число апериодических ожерелий (или, эквивалентно, Шаблон:Не переведено 5), которые могут быть сделаны путём расстановки n цветных бусин, имеющих α доступных цветов. Два таких ожерелья считаются равными, если они связаны вращением (но не отражением). Слово аперидические относятся к ожерельям без вращательной симметрии. Многочлен <math>N(\alpha,n)</math> даёт число ожерелий, включая периодические — это число легко вычислить с помощью теоремы Редфилда — Пойи.
- Размерность n элементов Шаблон:Не переведено 5 на α генераторах («формула Витта»Шаблон:Sfn). Здесь <math>N(\alpha,n)</math> должно быть размерностью n элементов соответствующей свободной йордановой алгебры.
- Число нормированных неприводимых многочленов степени n над конечным полем с α элементами (если <math>\alpha=p^d</math> является простой степенью). Здесь <math>N(\alpha,n)</math> является числом многочленов, которые являются степенью неприводимого многочлена.
- Экспонента в Шаблон:Не переведено 5.
Примечания
Литература
Шаблон:Refend Шаблон:Изолированная статья Шаблон:Rq
