Подсчёт ожерелий с симметрией и функцией Эйлера

Это лекция 8.2 из моей мини-серии «Освоение инверсии Мёбиуса» о математическом мышлении.

В лекции 8.1 мы использовали инверсию Мёбиуса для подсчёта примитивных нитей длины n в алфавите из c цветов. В этом выпуске мы сделаем следующий шаг: согнем эти нити в окружности и посчитаем ожерелья – раскраски с точностью до поворота.

Ожерелье – это круговая композиция из бусин, в которой поворот начальной точки не создаёт нового объекта. Это вводит симметрию, и правильный способ её решения – рассматривать ожерелья как орбиты нитей под действием группы поворота размера n.

В этой лекции мы рассмотрим:

Что такое ожерелье: строки по модулю поворота, без отражений

Как повороты действуют на позиции и создают циклы НОД(n, k)

Когда поворот на k позиций фиксирует раскраску

Формула в стиле Бернсайда для количества ожерелий:
N(n) = (1 / n) * сумма_{k = 0}^{n-1} c^{НОД(n, k)}

Как это преобразуется в формулу суммы делителей с функцией Эйлера:
N(n) = (1 / n) * сумма_{d | n} φ(d) * c^{n/d}

Определение примитивных ожерелий (полный период n по окружности)

Связь между примитивными строками A(n) и примитивными ожерельями M(n):
M(n) = A(n) / n = (1 / n) * сумма_{d | n} μ(d) * c^{n/d}

Конкретные примеры, включая двоичные ожерелья длины 4 и задачу из 5 бусин с c = 3

Эта лекция предназначена для опытных старшеклассников и студентов младших курсов бакалавриата (AMC/AIME, Putnam, участников олимпиадной математики или всех, кто знаком с основами теории чисел и комбинаторики), которые хотят увидеть, как обращение Мёбиуса и функция Эйлера естественным образом проявляются в задачах на подсчёт симметрии.

Если вам это будет полезно, рекомендуем сначала посмотреть лекцию 8.1, где мы выводим формулу для примитивных струн с помощью обращения Мёбиуса. А если вам нравятся подобные короткие, концептуально-ориентированные математические материалы, пожалуйста, поставьте лайк, подпишитесь и поделитесь ими с другом, который увлекается комбинаторикой и теорией чисел.