Полином ожерелья - Necklace polynomial

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

Определение

Полиномы ожерелья - это семейство многочленов в переменной такой, что

К Инверсия Мёбиуса они даны

куда это классика Функция Мёбиуса.

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

куда является Функция Эйлера.

Приложения

Полиномы ожерелья отображаются как:

  • Количество апериодические ожерелья (или эквивалентно Слова Линдона ), что можно сделать, расположив п цветные бусины, имеющие α доступные цвета. Два таких ожерелья считаются равными, если они связаны вращением (но не отражением). Апериодический относится к ожерельям без симметрии вращения, имеющим п отчетливые вращения. Полиномы укажите количество ожерелий, включая периодические: это легко вычислить с помощью Теория Полиа.
  • Размер степени п кусок свободная алгебра Ли на α генераторы («формула Витта»[1]). Здесь должен быть размером степени n соответствующего свободного Йорданова алгебра.
  • Количество различных слов длины п в Набор для прихожей. Обратите внимание, что множество Холла обеспечивает явный базис для свободной алгебры Ли; таким образом, это обобщенная настройка для вышеупомянутого.
  • Число монических неприводимых многочленов степени п через конечное поле с α элементы (когда - простая степень). Здесь - количество примарных многочленов (степень неприводимого).
  • Показатель в циклотомическая идентичность.

Несмотря на то, что многочлены появляются в этих различных параметрах настройки, точные отношения между ними остаются загадочными или неизвестными. Например, не существует известной биекции между неприводимыми многочленами и словами Линдона.[2]

Отношения между M и N

Многочлены для M и N легко связаны с точки зрения Свертка Дирихле арифметических функций , касательно как константа.

  • Формула для M дает ,
  • Формула для N дает .
  • Их отношение дает или эквивалентно , поскольку п является полностью мультипликативный.

Любые два из них подразумевают третий, например:

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

Примеры

За , начиная с нулевой длины, они образуют целочисленная последовательность

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

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

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

где "gcd" наибольший общий делитель а "lcm" - наименьший общий множитель. В более общем смысле,

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

Циклотомическая идентичность

Рекомендации

  1. ^ Лотэр, М. (1997). Комбинаторика слов. Энциклопедия математики и ее приложений. 17. Perrin, D .; Reutenauer, C .; Berstel, J .; Pin, J. E .; Pirillo, G .; Foata, D .; Сакарович, Дж .; Саймон, I .; Schützenberger, M. P .; Choffrut, C .; Cori, R .; Линдон, Роджер; Рота, Джан-Карло. Предисловие Роджера Линдона (2-е изд.). Издательство Кембриджского университета. С. 79, 84. ISBN  978-0-521-59924-5. МИСТЕР  1475463. Zbl  0874.20040.
  2. ^ Эми Глен (2012) Комбинаторика слов Линдона, Разговор в Мельбурне
  • Ройтенауэр, Кристоф (1988). "Круговые движения и неприводимые многочлены". Анна. Sc. Математика. Квебек. 12 (2): 275–285.