Ожерелье (комбинаторика)

Возможные узоры браслетов длины n,
соответствующие k- му целочисленному разбиению
( задать перегородки с точностью до поворота и отражения)

3 браслета с 3 красными и 3 зелеными бусинками. То, что посередине, хиральное , так что есть 4 ожерелья .
Сравните прямоугольник (6,9) в треугольнике.

11 браслетов с 2 красными, 2 желтыми и 2 зелеными бусинками. Крайний левый и четыре крайних правых - хиральные, поэтому всего 16 ожерелий .
Сравните прямоугольник (6,7) в треугольнике.

16 плиток Тантрикс , соответствующие 16 ожерельям с 2 красными, 2 желтыми и 2 зелеными бусинками.

В комбинаторике , A K -ичного ожерелье длины п является класс эквивалентности (группировка , для которой существует отношение эквивалентности) из п -character строк над алфавитом размером к , принимая все повороты как эквивалентные. Он представляет собой структуру из n соединенных по кругу бусинок k доступных цветов.

К -ичному браслет , также упоминается как оборот (или свободное ) ожерелье , это ожерелье , такой , что строки могут также быть эквивалентными при отражении. То есть для двух строк, если каждая из них противоположна другой, они принадлежат к одному и тому же классу эквивалентности. По этой причине колье можно также назвать фиксированным ожерельем, чтобы отличать его от колье с оборотом.

Формально, один может представлять собой ожерелье в качестве орбиты в циклической группе , действующей на п -character строк, и браслет в качестве орбиты группы диэдра . Можно подсчитать эти орбиты, а значит, и ожерелья и браслеты, используя теорему перечисления Поли .

Классы эквивалентности [ править ]

Количество ожерелий [ править ]

Есть

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

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

${\ displaystyle L_ {k} (n) = {\ frac {k!} {n}} \ sum _ {d \ mid n} \ varphi (d) S ({\ frac {n} {d}}, к )}$

разные ожерелья длины n с ровно k бусин разного цвета, где - число Стирлинга второго рода .${\ Displaystyle S (п, к)}$

${\ Displaystyle N_ {k} (п)}$(последовательность A054631 в OEIS ) и (последовательность A087854 в OEIS ) связаны через биномиальные коэффициенты :${\ Displaystyle L_ {k} (п)}$

${\ displaystyle N_ {k} (n) = \ sum _ {j = 1} ^ {k} {\ binom {k} {j}} L_ {k} (n)}$

и

${\displaystyle L_{k}(n)=\sum _{j=1}^{k}(-1)^{k-j}{\binom {k}{j}}N_{k}(n)}$

Количество браслетов [ править ]

Всего

${\displaystyle B_{k}(n)={\begin{cases}{\tfrac {1}{2}}N_{k}(n)+{\tfrac {1}{4}}(k+1)k^{\frac {n}{2}}&{\text{if }}n{\text{ is even}}\\[10px]{\tfrac {1}{2}}N_{k}(n)+{\tfrac {1}{2}}k^{\frac {n+1}{2}}&{\text{if }}n{\text{ is odd}}\end{cases}}}$

различных k -арных браслетов длины n , где N _k ( n ) - количество k -арных ожерелий длины  n . Это следует из метода Полиа, примененного к действию группы диэдра .${\displaystyle D_{n}}$

Случай различных бусин [ править ]

Для данного набора из n бусинок, все разные, количество различных ожерелий, сделанных из этих бусинок, считая повернутые ожерелья одинаковыми, равноп !/п= ( n  - 1) !. Это потому, что бусинки могут быть расположены линейно по n ! способов, и все n круговых сдвигов в таком порядке дают одно и то же ожерелье. Точно так же количество различных браслетов, считая повернутые и отраженные браслеты одинаковыми, равно п !/2 п, для n  ≥ 3.

Если не все бусины различны, имеют повторяющийся цвет, то ожерелий (и браслетов) меньше. Приведенные выше полиномы подсчета ожерелий дают числовые ожерелья, сделанные из всех возможных мультимножеств бус. Полином инвентаря узора Polya уточняет счетный полином, используя переменную для каждого цвета бусинок, так что коэффициент каждого монома подсчитывает количество ожерелий на заданном мультимножестве бусинок.

Апериодические ожерелья [ править ]

Апериодическое ожерелье длины п есть вращение класса эквивалентности , имеющий размер п , т.е., не существует два различных вращений ожерелья из такого класса не равны.

Согласно функции подсчета ожерелий Моро , есть

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

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

Каждое апериодическое ожерелье содержит одно слово Lyndon, так что слова Lyndon образуют представителей апериодических ожерелий.

См. Также [ править ]

• Линдон слово
• Инверсия (дискретная математика)
• Проблема с ожерельем
• Проблема раскола ожерелья
• Перестановка
• Доказательства маленькой теоремы Ферма # Доказательство подсчетом ожерелий
• Число Форте , представление двоичных браслетов длиной 12, используемых в атональной музыке .

Ссылки [ править ]

Внешние ссылки [ править ]

• Вайсштейн, Эрик В. «Ожерелье» . MathWorld .
• Информация об ожерельях, слова Линдона, последовательности Де Брёйна