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

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

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

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

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

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

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

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

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

Есть

${\displaystyle 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 , где — функция Эйлера . ^[1] Когда бусины ограничены определенным цветовым мультимножеством , где — число бусин цвета , существуют ${\displaystyle \varphi }$ ${\displaystyle {\mathcal {B}}=\{1^{n_{1}},\ldots ,k^{n_{k}}\}}$ ${\displaystyle n_{i}}$ ${\displaystyle i\in \{1,\ldots ,k\}}$

${\displaystyle 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)}$

различные ожерелья, сделанные из всех бусин . ^[2] Здесь и - мультиномиальный коэффициент . Эти две формулы напрямую следуют из теоремы Полиа о перечислении, примененной к действию циклической группы, действующей на множестве всех функций . Если все k цветов должны быть использованы, то подсчет будет ${\displaystyle {\mathcal {B}}}$ ${\displaystyle |{\mathcal {B}}|:=\sum \limits _{i=1}^{k}n_{i}}$ ${\displaystyle {m \choose m_{1},\ldots ,m_{k}}:={\frac {m!}{m_{1}!\cdots m_{k}!}}}$ ${\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\left({\frac {n}{d}},k\right)\;,}$

где — числа Стерлинга второго рода . ${\displaystyle S(n,k)}$

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

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

и

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

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

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

${\displaystyle 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 ,}$

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

Случай отдельных бусин

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

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

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

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

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

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

${\displaystyle M_{k}(n)={\frac {1}{n}}\sum _{d\mid n}\mu (d)k^{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 )}.}$

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

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

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

Ссылки

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

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

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