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

Возможные шаблоны браслетов длины 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 , где - функция Эйлера . Это непосредственно следует из перечислительной теоремы Поли, примененной к действию циклической группы, действующей на множестве всех функций . Это также ${\ 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 бусин разного цвета, где - число Стирлинга второго рода . (Переменная k перегружена, и неясно, относится ли 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) ^ {kj} {\ binom {k} {j}} N_ {k} (n)}

Количество браслетов

Всего есть

{\ displaystyle B_ {k} (n) = {\ begin {case} {\ tfrac {1} {2}} N_ {k} (n) + {\ tfrac {1} {4}} (k + 1) k ^ {n / 2} & {\ text {if}} n {\ text {четно}} \\ [10px] {\ tfrac {1} {2}} N_ {k} (n) + {\ tfrac {1} {2}} k ^ {(n + 1) / 2} & {\ text {if}} n {\ text {нечетное}} \ end {case}}}

различных 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 , что эквивалентно обращению Мёбиуса к ${\ textstyle N_ {k} (n) = \ sum _ {d | n} M_ {k} (d),}$ ${\ textstyle M_ {k} (n) = \ sum _ {d | n} N_ {k} (d) \, \ mu {\ bigl (} {\ tfrac {n} {d}} {\ bigr)} .}$

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

Смотрите также

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

Languages

In other projects