Ожерелье (комбинаторика)
Материал из Википедии — свободной encyclopedia
В комбинаторике -цветное ожерелье длины — это класс эквивалентности -символьных строк над алфавитом размера , где эквивалентными считаются строки, получающиеся друг из друга вращением[англ.], или циклическим сдвигом. К примеру, для , ожерельем будет множество . Ожерелье можно визуально представить как структуру из связанных в кольцо бусин, имеющих возможных цветов (цвета соответствуют символам в алфавите): для этого надо взять одно из слов данного класса эквивалентности, мысленно продеть через его символы нитку и соединить ее начало и конец.
-цветный браслет длины , о котором говорят как об обращаемом (или свободном) ожерелье определяется аналогично как класс эквивалентности строк длины в -символьном алфавите, однако эквивалентными в данном случае считаются строки, получающиеся друг из друга вращением, зеркальной симметрией или комбинацией этих преобразований. Если прибегнуть к визуальному представлению браслетов в виде бус, их отличие от ожерелий будет заключаться в том, что ожерелья запрещается переворачивать, а браслеты — разрешается. По этой причине ожерелье может называться также фиксированным ожерельем. Например, ожерелье, соответствующее строке , отличается от ожерелья, соответствующего строке , однако из этих двух строк получается один и тот же браслет (ведь две эти строки получаются друг из друга зеркальной симметрией).
С точки зрения алгебры ожерелье можно представить как орбиту циклической группы действия над -символьными строками, а браслет — как орбиту диэдральной группы. Можно подсчитать эти орбиты, а следовательно, число таких ожерелий и браслетов, с помощью теоремы перечисления Пойа.