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

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

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

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

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

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

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

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

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

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

Є

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

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

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

Є

$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, де $N_{k}(n)$ дорівнює числу k-колірних намист довжини n. Це випливає з методу Пої, застосованого до дії діедральної групи $D_{n}$.

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

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

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

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

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

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

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

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

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

Див. також

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

Література

• Химач Р.А., Филипенко А.А. Молодежный научный форум: Технические и математические науки: электр. сб. ст. по мат. XXXIV междунар. студ. науч.-практ. конф. № 5(34).. — 2016. — 4 червня. — С. 90-98.
• Калужин Л.А., Сущанский В.И. 13. Комбинаторные задачи // Преобразования и перестановки. — М. : «Наука», 1985. — (Проблемы науки и технического прогресса)
• Яковенко Д.И. Задача об ожерельях // Вестник Омского университета. — 1998. — Вип. 2 (4 червня). — С. 21-24.

Посилання

• Weisstein, Eric W. Намисто(англ.) на сайті Wolfram MathWorld.
• Info on necklaces, Lyndon words, De Bruijn sequences