Многочлен ожерелья, или функция подсчёта ожерелий Моро, предложенный Шарлем Моро, — это семейство многочленов от переменной такое, что:
С помощью обращения Мёбиуса получим формулу для
где является классической функцией Мёбиуса.
Тесно связанным семейством, называемым обобщённый многочлен ожерелья или обобщённой функцией подсчёта ожерелий, является семейство:
где — функция Эйлера.
Связь M и N Вышеприведённые формулы тесно связаны в терминах свёртки Дирихле арифметических функций с в качестве константы. Формула для M даёт , Формула для N даёт . Их связь даёт , что эквивалентно , поскольку n является .
Из любых двух равенств вытекает третье, например:
согласно сокращению в .
Примеры если n > 1
, если p простое , если p простое
Тождества
Многочлены удовлетворяют различным комбинаторным тождествам, которые представили Метрополис и Рота:
где «gcd» является наибольшим общим делителем, а «lcm» является наименьшим общим кратным. Более обще:
из чего также следует:
Цикловое тождество
Приложения Многочлены ожерелий появляются как:
Число апериодических ожерелий (или, эквивалентно, слов Линдона), которые могут быть сделаны путём расстановки n цветных бусин, имеющих α доступных цветов. Два таких ожерелья считаются равными, если они связаны вращением (но не отражением). Слово аперидические относятся к ожерельям без вращательной симметрии. Многочлен даёт число ожерелий, включая периодические — это число легко вычислить с помощью теоремы Редфилда — Пойи. Размерность n элементов свободной алгебры Ли на α генераторах («формула Витта»). Здесь должно быть размерностью n элементов соответствующей свободной йордановой алгебры. Число нормированных неприводимых многочленов степени n над конечным полем с α элементами (если является простой степенью). Здесь является числом многочленов, которые являются степенью неприводимого многочлена. Экспонента в .
Примечания
Литература
Категория:Комбинаторика слов Категория:Перечислительная комбинаторика