Намисто (комбінаторика)

У комбінаториці k-колірне намисто довжини n — це клас еквівалентності (групування, для якого існує відношення еквівалентності) n-символьних рядків над алфавітом розміру k, вважаючи всі повороти еквівалентними. Намисто представляє структуру з n зв'язаних у кільце нами́стин, що мають k можливих кольорів.

Можливі варіанти браслетів довжини n, відповідні k-им розбиттям цілого числа (розбиття множини з точністю до поворотів і відбиттів)

3 браслети з 3 червоними і 3 зеленими нами́стинами. Розбиття в середині хіральне, отже є 4 намиста

11 браслетів з 2 червоними, 2 жовтими і 2 зеленими намистинами. Крайнє ліворуч намисто і чотири крайніх праворуч хіральні, отже є 16 намист

16 плиток тантрикс, відповідних 16 намистам з 2 червоними, 2 жовтими і 2 зеленими нами́стинами.

k-колірний браслет, про який кажуть як про оборотне (або вільне) намисто, це намисто, яке збігається з собою при дзеркальній симетрії. Тобто, якщо дано два варіанти намиста, симетричні один одному, вони належать до деякого класу еквівалентності. З цієї причини намисто може називатися також фіксованим намистом, щоб відрізняти його від оборотного намиста.

Формально можна представити як намисто орбіту циклічної групи дії над n-символьними рядками, а браслет як орбіту діедральної групи. Підрахувати ці орбіти, а отже, число таких намист і браслетів, можна за допомогою теореми перерахування Поя.

Класи еквівалентності

Кількість намист

Є

${\displaystyle N_{k}(n)={\frac {1}{n}}\sum _{d\mid n}\varphi (d)k^{\frac {n}{d}}}$

різних k-колірних намист довжини n, де ${\displaystyle \varphi }$ — функція Ейлера^[1]. Це випливає безпосередньо з теореми перерахування Поя, застосованої до дії циклічної групи ${\displaystyle C_{n}}$, що діє на множині всіх функцій ${\displaystyle f:\{1,\ldots ,n\}\to \{1,\ldots ,k\}}$.

Кількість браслетів

Є^[2][3]

${\displaystyle B_{k}(n)={\begin{cases}{\tfrac {1}{2}}N_{k}(n)+{\tfrac {1}{4}}(k+1)k^{\frac {n}{2}}&n\equiv 0{\pmod {2}},\\[10px]{\tfrac {1}{2}}N_{k}(n)+{\tfrac {1}{2}}k^{\frac {n+1}{2}}&n\equiv 1{\pmod {2}}\end{cases}}}$

різних k-колірних браслетів довжини n, де ${\displaystyle N_{k}(n)}$ дорівнює числу k-колірних намист довжини n. Це випливає з методу Пої, застосованого до дії діедральної групи ${\displaystyle D_{n}}$.

Випадок різних намистин

Для даного набору з n (різних) нами́стин число різних намист, зроблених з цих намистин, якщо вважати повернені намиста тими ж самими, дорівнює n!/n = (n − 1)!. Це випливає з того, що намистини можна розташувати лінійно n! способами і n циклічних зсувів кожного такого лінійного порядку дає те саме намисто. Аналогічно, число різних браслетів, якщо вважати повороти і відображення тими самими, дорівнює n!/2n для ${\displaystyle n\geqslant 3}$.

Якщо намистини не різні, тобто є повторення кольорів, то кількість намист (і браслетів) буде меншою. Наведені вище многочлени підрахунку намист дають число намист, зроблених з усіх можливих мультимножин намистин. Многочлен перерахування конфігурацій Поя покращує многочлен підрахунку за допомогою змінної для кожного кольору намистин, так що коефіцієнт кожного одночлена підрахує кількість намист на даній мультимножині намистин.

Аперіодичні намиста

Аперіодичне намисто довжини n є класом еквівалентності поворотів, що мають розмір n, тобто ніякі два різних повороти намиста з цього класу не еквівалентні.

Згідно з функція підрахунку намист Моро^[en], існує

${\displaystyle M_{k}(n)={\frac {1}{n}}\sum _{d\mid n}\mu (d)k^{\frac {n}{d}}}$

різних k-колірних аперіодичних намист довжини n, де ${\displaystyle \mu }$ є функцією Мебіуса. Дві функції, що підраховують намиста, пов'язані відношенням ${\displaystyle N_{k}(n)\ =\ \sum \nolimits _{d|n}M_{k}(d),}$ де підсумовування проводиться за всіма дільниками числа n, що еквівалентно оберненню Мебіуса для ${\displaystyle M_{k}(n)\ =\ \sum \nolimits _{d|n}N_{k}(d)\,\mu ({\tfrac {n}{d}}).}$

Будь-яке аперіодичне намисто містить одне слово Ліндона^[en], так що слова Ліндона утворюють представників аперіодичних намист.

Див. також

• Слово Ліндона^[en]
• Інверсія (дискретна математика)
• Задача про відновлення намиста
• Задача про розрізання намиста
• Перестановка
• Доведення малої теореми Ферма^[en]