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

Возможные узоры браслетов длины n., соответствующие k-му целочисленному разбиению. (перегородки от до вращения и отражения) 3 браслета с 3 красными и 3 зелеными бусинками. Посередине - хиральный, поэтому в треугольнике 4 ожерелья ... Сравните поле (6,9). 11 браслетов с 2 красная, 2 желтые и 2 зеленые бусинки. Крайний левый и четыре крайних правых являются хиральными, поэтому в треугольнике 16 ожерелий .. Сравните поле (6,7). 16 Тантрикс плиток, соответствующих 16 ожерелья с 2 красными, 2 желтыми и 2 зелеными бусинами.

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

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

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

• 1 Классы эквивалентности
  • 1.1 Количество ожерелий
  • 1.2 Количество браслетов
• 2 Случай различных бусы
• 3 Апериодические ожерелья
• 4 См. также
• 5 Ссылки
• 6 Внешние ссылки

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

Есть

$N\; К\; (N)\; знак\; равно\; 1\; N\; \sum \; d\; \mid \; N\; \phi \; (d)\; knd\; \{\backslash \; displaystyle\; N\_\; \{k\}\; (n)\; =\; \{\backslash \; frac\; \{1\}\; \{n\}\}\; \backslash \; sum\; \_\; \{d\; \backslash \; mid\; n\}\; \backslash \; varphi\; (d)\; k\; ^\; \{\backslash \; frac\; \{n\}\; \{d\}\}\}$

различные k-арные ожерелья длины n, где $\phi \; \{\backslash \; displaystyle\; \backslash \; varphi\}$- функция Эйлера. Это непосредственно следует из теоремы Пойи о перечислении, примененной к действию циклической группы $C\; n\; \{\backslash \; displaystyle\; C\_\; \{n\}\}$, действующей на множество всех функций $е:\; \{1,\dots ,\; n\}\; \to \; \{1,\dots ,\; k\}\; \{\backslash \; displaystyle\; f:\; \backslash \; \{1,\; \backslash \; ldots,\; n\; \backslash \}\; \backslash \; to\; \backslash \; \{1,\; \backslash \; ldots,\; k\; \backslash \}\}$. Также есть

$L\; k\; (n)\; =\; k!\; n\; \sum \; d\; \mid \; N\; \phi \; (d)\; S\; (nd,\; k)\; \{\backslash \; displaystyle\; L\_\; \{k\}\; (n)\; =\; \{\backslash \; frac\; \{k!\}\; \{n\}\}\; \backslash \; sum\; \_\; \{d\; \backslash \; mid\; n\}\; \backslash \; varphi\; (d)\; S\; (\{\backslash \; frac\; \{n\}\; \{d\}\},\; k)\}$

разные ожерелья длины n с ровно k бусинок разного цвета, где $S\; (n,\; k)\; \{\backslash \; displaystyle\; S\; (n,\; k)\}$- число Стирлинга второго рода.

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

$N\; k\; (n)\; =\; \sum \; j\; =\; 1\; k\; (kj)\; L\; k\; (n)\; \{\backslash \; displaystyle\; N\_\; \{k\}\; (n)\; =\; \backslash \; sum\; \_\; \{j\; =\; 1\}\; ^\; \{k\}\; \{\backslash \; binom\; \{k\}\; \{j\}\}\; L\_\; \{k\}\; (n)\}$

и

$L\; k\; (n)\; =\; \sum \; j\; =\; 1\; k\; (-\; 1)\; К\; -\; J\; (КJ)\; N\; К\; (N)\; \{\backslash \; Displaystyle\; L\_\; \{k\}\; (п)\; =\; \backslash \; сумма\; \_\; \{j\; =\; 1\}\; ^\; \{k\}\; (-\; 1)\; ^\; \{kj\}\; \{\backslash \; binom\; \{k\}\; \{j\}\}\; N\_\; \{k\}\; (n)\}$

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

Всего

$B\; k\; (n)\; =\; \{1\; 2\; N\; k\; (n)\; +\; 1\; 4\; (k\; +\; 1)\; kn\; 2,\; если\; n\; четно\; 1\; 2\; N\; k\; (n)\; +\; 1\; 2\; kn\; +\; 1\; 2,\; если\; n\; нечетно\; \{\backslash \; displaystyle\; B\_\; \{k\}\; (n)\; =\; \{\backslash \; begin\; \{cases\}\; \{\backslash \; tfrac\; \{1\}\; \{\; 2\}\}\; N\_\; \{k\}\; (\; n)\; +\; \{\backslash \; tfrac\; \{1\}\; \{4\}\}\; (k\; +\; 1)\; k\; ^\; \{\backslash \; frac\; \{n\}\; \{2\}\}\; \{\backslash \; text\; \{if\}\}\; n\; \{\backslash \; text\; \{четно\}\}\; \backslash \backslash \; [\; 10px]\; \{\backslash \; tfrac\; \{1\}\; \{2\}\}\; N\_\; \{k\}\; (n)\; +\; \{\backslash \; tfrac\; \{1\}\; \{2\}\}\; k\; ^\; \{\backslash \; frac\; \{n\; +\; 1\}\; \{2\}\}\; и\; \{\backslash \; text\; \{если\; \}\}\; n\; \{\backslash \; text\; \{нечетно\}\}\; \backslash \; end\; \{cases\}\}\}$

различных k-арных браслетов длины n, где N k (n) - количество k-арных ожерелий длины n. Это следует из метода Полиа, примененного к действию двугранной группы $D\; n\; \{\backslash \; displaystyle\; D\_\; \{n\}\}$.

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

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

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

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

$M\; k\; (n)\; =\; 1\; n\; \sum \; d\; \mid \; n\; \mu \; (d)\; knd\; \{\backslash \; displaystyle\; M\_\; \{k\}\; (\; n)\; =\; \{\backslash \; frac\; \{1\}\; \{n\}\}\; \backslash \; sum\; \_\; \{d\; \backslash \; mid\; n\}\; \backslash \; mu\; (d)\; k\; ^\; \{\backslash \; frac\; \{n\}\; \{d\}\}\}$

различные k-арные апериодические ожерелья из длина n, где μ - функция Мёбиуса. Две функции подсчета ожерелий связаны соотношением: $N\; k\; (n)\; =\; \sum \; d\; |\; n\; M\; k\; (d),\; \{\backslash \; displaystyle\; N\_\; \{k\}\; (n)\; \backslash \; =\; \backslash \; \backslash \; sum\; \backslash \; nolimits\; \_\; \{d\; |\; n\}\; M\_\; \{k\}\; (d),\}$где сумма больше все делители числа n, что эквивалентно инверсии Мёбиуса с $M\; k\; (n)\; =\; \sum \; d\; |\; n\; N\; k\; (d)\; \mu \; (n\; d).\; \{\backslash \; Displaystyle\; M\_\; \{k\}\; (n)\; \backslash \; =\; \backslash \; \backslash \; sum\; \backslash \; nolimits\; \_\; \{d\; |\; n\}\; N\_\; \{k\}\; (d)\; \backslash ,\; \backslash \; mu\; (\{\backslash \; tfrac\; \{n\}\; \{d\}\}).\}$

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

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

• Вайсштейн, Эрик У. " Ожерелье ". MathWorld.
• Информация об ожерельях, словах Линдона, последовательностях Де Брейна