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

В комбинаторике $k$ -цветное ожерелье длины $n$ — это класс эквивалентности $n$ -символьных строк над алфавитом размера $k$ , где эквивалентными считаются строки, получающиеся друг из друга вращением, или циклическим сдвигом. К примеру, для $n=5$ , $k=3$ ожерельем будет множество $\{ababc,babca,abcab,bcaba,cabab\}$ . Ожерелье можно визуально представить как структуру из $n$ связанных в кольцо бусин, имеющих $k$ возможных цветов (цвета соответствуют символам в алфавите): для этого надо взять одно из слов данного класса эквивалентности, мысленно продеть через его символы нитку и соединить ее начало и конец.

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

3 браслета с 3 красными и 3 зелёными бусинками. Разбиение в середине хирально, так что имеется 4 ожерелья

11 браслетов c 2 красными, 2 жёлтыми и 2 зелёными бусинами. Крайне левое ожерелье и четыре крайних справа хиральны, так что имеется 16 ожерелий

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

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

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

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

Число ожерелий

Имеется

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

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

Число браслетов

Есть[3][4]

B_{k}(n)={\begin{cases}{\tfrac {1}{2}}N_{k}(n)+{\tfrac {1}{4}}(k+1)k^{\frac {n}{2}}&n\equiv 0{\pmod {2}},\\[10px]{\tfrac {1}{2}}N_{k}(n)+{\tfrac {1}{2}}k^{\frac {n+1}{2}}&n\equiv 1{\pmod {2}}\end{cases}}

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

Случай различных бус

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

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

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

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

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

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

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

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

См. также

Слово Линдона
Инверсия (дискретная математика)
Задача о восстановлении бус
Задача о разрезании ожерелья
Перестановка
Доказательство малой теоремы Ферма

Примечания

Weisstein, Eric W. Necklace (англ.) на сайте Wolfram MathWorld.
Химач, Филипенко, 2016, с. 93.
Яковенко, 1998.
Химач, Филипенко, 2016, с. 94-95.

Литература

Химач Р.А., Филипенко А.А. Молодежный научный форум: Технические и математические науки: электр. сб. ст. по мат. XXXIV междунар. студ. науч.-практ. конф. № 5(34).. — 2016. — С. 90-98.

Калужин Л.А., Сущанский В.И. 13. Комбинаторные задачи // Преобразования и перестановки. — М.: «Наука», 1985. — (Проблемы науки и технического прогресса).
Яковенко Д.И. Задача об ожерельях // Вестник Омского университета. — 1998. — С. 21-24.

Ссылки

Weisstein, Eric W. Necklace (англ.) на сайте Wolfram MathWorld.
Info on necklaces, Lyndon words, De Bruijn sequences

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Weisstein, Eric W. Necklace (англ.) на сайте Wolfram MathWorld.

[_8fbf458735a80e81-2] Химач, Филипенко, 2016, с. 93.

[_12079b02c55e852b-3] Яковенко, 1998.

[_2ac75a6cc85da0c9-4] Химач, Филипенко, 2016, с. 94-95.