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

Три браслета с тремя красными и тремя зелеными бусинами. Тот, что посередине, хиральный , поэтому ожерелья 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 , где – функция Эйлера totient . ^[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 ,}$

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

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

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

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

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

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