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

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

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

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

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

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

Классы эквивалентности

Количество ожерелий

Есть

N_{k}(n)={\frac {1}{n}}\sum _{d\mid n}\varphi (d)k^{n/d}={\frac {1}{n}}\sum _{i=1}^{n}k^{\,{\rm {gcd}}(i,n)}

различные k -арные ожерелья длины n , где $\varphi$ — это полная функция Эйлера . ^[1] Когда бусины ограничены набором определенного цвета. ${\mathcal {B}}=\{1^{n_{1}},\ldots ,k^{n_{k}}\}$ , где $n_{i}$ количество цветных бусин $i\in \{1,\ldots ,k\}$ , есть

N({\mathcal {B}})={\frac {1}{|{\mathcal {B}}|}}\sum _{d|{\rm {gcd}}(n_{1},\ldots ,n_{k})}{|{\mathcal {B}}|/d \choose n_{1}/d,\ldots ,n_{k}/d}\phi (d)

разные ожерелья из всех бусин ${\mathcal {B}}$ . ^[2]Здесь $|{\mathcal {B}}|:=\sum \limits _{i=1}^{k}n_{i}$ и ${m \choose m_{1},\ldots ,m_{k}}:={\frac {m!}{m_{1}!\cdots m_{k}!}}$ – полиномиальный коэффициент .Эти две формулы непосредственно следуют из теоремы перечисления Пойа, примененной к действию циклической группы. $C_{n}$ действуя на множество всех функций $f:\{1,\ldots ,n\}\to \{1,\ldots ,k\}$ .Если необходимо использовать все k цветов, счетчик равен

L_{k}(n)={\frac {k!}{n}}\sum _{d\mid n}\varphi (d)S\left({\frac {n}{d}},k\right)\;,

где $S(n,k)$ – число Стирлинга второго рода .

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

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

и

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

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

Количество различных k -арных браслетов длины n (последовательность A081720 в OEIS ) равно

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

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

Футляр с разными бусинами

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

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

Апериодические ожерелья

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

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

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

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

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

См. также

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

Ссылки

^ Вайсштейн, Эрик В. «Ожерелье» . Математический мир .
^ Раски, Фрэнк (2006). «Информация об ожерельях, словах Линдона, эпизодах Де Брейна» . Архивировано из оригинала 2 октября 2006 г.

Внешние ссылки

Поля, Георг; Читай, RC; Эппли, Дороти (1987). Комбинаторное перечисление групп, графов и химических соединений . Спрингер-Верлаг. ISBN 9780387964133 .
Раски, Фрэнк; Сэвидж, Карла; Ван, Терри Мин Йи (1992). «Генерация ожерелий». Журнал алгоритмов . 13 (3): 414–430. дои : 10.1016/0196-6774(92)90047-G .

[1] Вайсштейн, Эрик В. «Ожерелье» . Математический мир .

[2] Раски, Фрэнк (2006). «Информация об ожерельях, словах Линдона, эпизодах Де Брейна» . Архивировано из оригинала 2 октября 2006 г.

[1]

[2]