Перегляд вихідного коду сторінки Намисто (комбінаторика)

[[Файл:Partition_necklaces_by_integer_partition.svg|міні|576x576пкс|Можливі варіанти браслетів довжини ''n'', відповідні ''k''-им [[Розбиття числа|розбиттям цілого числа]] ([[розбиття множини]] з точністю до поворотів і відбиттів)]]
[[Файл:Bracelets33.svg|міні|300x300пкс|3 '''браслети''' з 3 червоними і 3 зеленими нами́стинами. Розбиття в середині [[Хіральність (математика)|хіральне]], отже є 4 '''намиста''']]
[[Файл:Bracelets222.svg|міні|300x300пкс|11 '''браслетів''' з 2 червоними, 2 жовтими і 2 зеленими намистинами. Крайнє ліворуч намисто і чотири крайніх праворуч хіральні, отже є 16 '''намист''']]
[[Файл:Tantrix_tiles_ryg.svg|міні|300x300пкс|16 плиток [[тантрикс]], відповідних 16 '''намистам''' з 2 червоними, 2 жовтими і 2 зеленими нами́стинами.]]
У [[Комбінаторика|комбінаториці]] ''k''-колірне '''намисто''' довжини ''n''&nbsp;— це [[Відношення еквівалентності|клас еквівалентності]] (групування, для якого існує відношення еквівалентності) ''n''-символьних [[Рядок (програмування)|рядків]] над [[Абетка (інформатика)|алфавітом]] розміру ''k'', вважаючи всі [[Бітовий зсув|повороти]] еквівалентними. Намисто представляє структуру з ''n'' зв'язаних у кільце нами́стин, що мають ''k'' можливих кольорів.

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

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

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

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

: <math>N_k(n)=\frac{1}{n}\sum_{d\mid n}\varphi(d)k^\frac{n}{d}</math>

різних ''k''-колірних намист довжини ''n'', де ''<math> \varphi </math>''&nbsp;— [[функція Ейлера]]{{Sfn|Химач, Филипенко|2016|с=93}}. Це випливає безпосередньо з [[Теорема перерахування Поя|теореми перерахування Поя]], застосованої до дії циклічної групи <math>C_n</math>, що діє на множині всіх функцій <math>f : \{1,\ldots,n\} \to\{1,\ldots,k\}</math>.

=== Кількість браслетів ===
Є{{Sfn|Яковенко|1998}}{{Sfn|Химач, Филипенко|2016|с=94-95}}

: <math>B_k(n) = \begin{cases}
\tfrac12 N_k(n) + \tfrac14 (k+1)k^\frac{n}{2} & n \equiv 0 \pmod 2,\\[10px]
\tfrac12 N_k(n) + \tfrac12 k^\frac{n+1}{2} & n \equiv 1 \pmod 2
\end{cases}</math>

різних ''k''-колірних браслетів довжини ''n'', де <math>N_k(n)</math> дорівнює числу ''k''-колірних намист довжини ''n''. Це випливає з [[Теорема перерахування Поя|методу Пої]], застосованого до дії [[Діедральна група|діедральної групи]] <math>D_n</math>.

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

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

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

Згідно з {{Не перекладено|Многочлен намист|функція підрахунку намист Моро|en|Moreau's necklace-counting function}}, існує

: <math>M_k(n)=\frac{1}{n}\sum_{d\mid n}\mu(d)k^\frac{n}{d}</math>

різних ''k''-колірних аперіодичних намист довжини ''n'', де <math>\mu</math> є [[Функція Мебіуса|функцією Мебіуса]]. Дві функції, що підраховують намиста, пов'язані відношенням <math>N_k(n)\ =\ \sum\nolimits_{d|n} M_k(d),</math> де підсумовування проводиться за всіма дільниками числа ''n'', що еквівалентно [[Функція Мебіуса|оберненню Мебіуса]] для <math>M_k(n)\ =\ \sum\nolimits_{d|n} N_k(d)\,\mu(\tfrac{n}{d}).</math>

Будь-яке аперіодичне намисто містить одне {{Не перекладено|слово Ліндона||en|Lyndon word}}, так що слова Ліндона утворюють [[Відношення еквівалентності|представників]] аперіодичних намист.

== Див. також ==

* {{Не перекладено|Слово Ліндона||en|Lyndon word}}
* [[Інверсія (дискретна математика)]]
* [[Задача про відновлення намиста]]
* [[Задача про розрізання намиста]]
* [[Перестановка]]
* {{Не перекладено|Доведення малої теореми Ферма||en|Proofs of Fermat's little theorem}}

== Примітки ==
{{примітки}}

== Література ==
{{Refbegin}}
* {{Вишенський.Перестюк.Комбінаторика}}
* {{Стаття|ref=Химач, Филипенко|author=Химач Р.А., Филипенко А.А.|title=Молодежный научный форум: Технические и математические науки: электр. сб. ст. по мат. XXXIV междунар. студ. науч.-практ. конф. № 5(34).|url=https://nauchforum.ru/archive/MNF_tech/5(34).pdf|pages=90-98|date=2016}}

* {{Стаття|url=http://imit.omsu.ru/vestnik/articles/y1998-i2/a021/article.html|author=Яковенко Д.И.|ref=Яковенко|title=Задача об ожерельях|видання=Вестник Омского университета|date=1998|issue=2|pages=21-24}}
{{Refend}}

== Посилання ==
* {{MathWorld|Necklace|Намисто}}
* [https://web.archive.org/web/20061002130346/http://www.theory.csc.uvic.ca/~cos/inf/neck/NecklaceInfo.html Info on necklaces, Lyndon words, De Bruijn sequences]

[[Категорія:Нумераційна комбінаторика]]
[[Категорія:Комбінаторика слів]]