Главная
Статьи





03.07.2022


03.07.2022


03.07.2022


03.07.2022


03.07.2022






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

22.01.2022

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

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

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

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

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

Имеется

N k ( n ) = 1 n ∑ d ∣ n φ ( d ) k n d {displaystyle N_{k}(n)={frac {1}{n}}sum _{dmid n}varphi (d)k^{frac {n}{d}}}

различных k {displaystyle k} -цветных ожерелий длины n {displaystyle n} , где φ {displaystyle varphi } — функция Эйлера. Это следует непосредственно из теоремы перечисления Пойа, применённой к действию циклической группы C n {displaystyle C_{n}} , действующей на множестве всех функций f : { 1 , … , n } → { 1 , … , k } {displaystyle f:{1,ldots ,n} o {1,ldots ,k}} .

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

Есть

B k ( n ) = { 1 2 N k ( n ) + 1 4 ( k + 1 ) k n 2 n ≡ 0 ( mod 2 ) , 1 2 N k ( n ) + 1 2 k n + 1 2 n ≡ 1 ( mod 2 ) {displaystyle B_{k}(n)={egin{cases}{ frac {1}{2}}N_{k}(n)+{ frac {1}{4}}(k+1)k^{frac {n}{2}}&nequiv 0{pmod {2}},[10px]{ frac {1}{2}}N_{k}(n)+{ frac {1}{2}}k^{frac {n+1}{2}}&nequiv 1{pmod {2}}end{cases}}}

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

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

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

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

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

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

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

M k ( n ) = 1 n ∑ d ∣ n μ ( d ) k n d {displaystyle M_{k}(n)={frac {1}{n}}sum _{dmid n}mu (d)k^{frac {n}{d}}}

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

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