Enumeration of symmetrical necklaces.pdf Задача об ожерелье является одной из хорошо известных в дискретной математике [1. С. 246; 2. С. 212]. На ее примере наглядно демонстрируется один из таких конструктивных методов теории групп, как действие некоторой группы симметрий G = (X, на заданное множество ожерелий [3. С. 301]. Основной вопрос, который встает при исследовании симметрий ожерелий, заключается не столько в их подсчете в некотором множестве, сколько в их реальном перечислении - построении алгоритма получения ожерелий в явном виде [4]. В рассматриваемом случае мы сталкиваемся с феноменом так называемой хиральности - разновидностью симметрии, не совпадающей с осевой симметрией. Хиральность как атрибут многих сложных систем является объектом изучения в общей теории симметрии [5-7], органической химии [8, 9], кристаллографии [10] и многих других научных дисциплинах. Цель статьи - рассмотрение алгоритмического подхода к решению задачи перечисления симметричных ожерелий и перенесение ее на теорию поэтических структур - строф, моделями которых служат ожерелья. Такое моделирование позволяет не только выявить симметрии поэтических строф, но и расширить их классификацию за счет внесения в нее различных признаков симметрии типа правила альтернанса или правила скрещения рифмических цепей [11. С. 195]. Эта задача является тем более актуальной, что проблема аналитического перечисления симметричных ожерелий в явном виде на сегодняшний день остается в полном объеме нерешенной. 1. Постановка задачи В [12. С. 14, 18] была предложена модель строфических структур в виде кольцевых диаграмм, или ожерелий [1. С. 246]. Такое представление позволяет эффективно исследовать свойства поэтической строфы с позиций симметрии при условии, что в качестве признаков симметрии строфы рассматриваются только такие, которые допускают строгую формализацию, - системы рифмовок, слоговый объем стихов, ритмический профиль и т.д. Рассмотрим стихотворение А. Блока «На зов метелей» [13. С. 165]. Система рифмовки его строфы IV соответствует симметричному ожерелью abcb adcd (см. ниже: рис. 3, ожерелье 2 в табл. 2), где одинаковыми буквами обозначены звенья соответствующих рифмических цепей: На зов метелей IV’ И мгла заломила руки, Заломила руки ввысь. Ты опустила очи, И мы понеслись. И навстречу вставали новые звуки: Летели снега, Налетающей ночи Звенели рога. Эта восьмистишная строфа симметрична, и все бы хорошо, но дело в том, что здесь я осуществляю подлог - на самом деле у Блока два последних стиха переставлены местами. В результате этого симметрия нарушается, и все наши красивые рассуждения рушатся. Возникает вопрос: может, Блок на подсознательном уровне стремился к симметрии и просто ошибся в чередовании двух последних стихов? О приведении строф к симметрии говорится в [14], где, в частности, анализируется 98 Григорьев Ю.Д. Перечисление симметричных ожерелий отклонение от симметрии в стихотворении Д. Мережковского «Март» и высказывается предположение, что в этом стихотворении вообще пропущен один стих, нарушающий симметрию. В статье решается вопрос, сколько симметричных (mi, m2, ... , m^-ожерелий длины n, щ = n, существует при заданном распределении его бусин (mt - число бусин i -го цвета). Цвета бусин применительно к стихосложению определяют систему рифмовки и рассматриваются как признак симметрии строфы. Так, варианту Блока соответствует несимметричное (2, 2, 2, 2)-ожерелье, а после его реконструкции (второй вариант) - симметричное, хотя в обоих случаях распределение бусин одно и то же. Задача алгоритмического подсчета, перечисления и анализа симметричных ожерелий длины n иллюстрируется в статье на примере 8-стишных строф. 2. Симметричные ожерелья Пусть T - множество ожерелий x е T, в котором определено отношение эквивалентности ~, G - множество операторов g е G, g: T^T, т.е. gx еТ, GхG^G - композиция операторов, относительно которой G является группой, в общем случае неабелевой. 2.1. Симметрия Пусть G действует на x еТ, при этом g (g2x) = (gg) x, ex = x. Ожерелье x еТ называется симметричным, если существует оператор g Ф e такой, что gx ~ x . Метризуем множество T. Пусть d(x, у) - число несовпадающих бусин ожерелий x, у еТ , взятых в порядке следования. Это известное расстояние Хемминга [15. C. 52], используемое для строк одинаковой длины любых r-ичных алфавитов. Очевидно, ожерелье xеТ симметрично тогда и только тогда, когда существует элемент g Ф e такой, что d(gx, x) = 0 . В связи с этим такие операторы g называются изометриями. Это определение симметричности эквивалентно предыдущему. Вопрос о количестве N(m\\, ... , mr) орбит, индуцируемых действием на множество Tкакой-либо группы G, решается с помощью леммы Бернсайда. Однако на вопрос о том, сколько существует симметричных орбит (орбит, содержащих симметричные ожерелья), лемма Бернсайда ответа не дает. 2.2. Представительные графы Расстояние p(a, b) между двумя бусинами а и b ожерелья x определим как цепь наименьшей длины, связывающую а и b. Кроме того, ясно что для V a ,b : p(a, b) е {1,2,...,[n/2]}. Например, для соседних узлов а и b имеем p(a, b) = 1. Легко проверить что p(a, b) - метрика [16. C. 42]. Сопоставим (mi, m2, ... , тг)-ожерелью x еТ длины n следующую (n, n - ^)-диаграмму H с n вершинами и n - q ребрами - отрезками прямых линий: (а) вершины диаграммы H определим как вершины правильного n-угольника; (б) ребра H - как звенья r компонент связности длины mi, образующие цепи наименьшей длины (если mi = 2, то полагаем, что цепь состоит из одного звена); (в) q - количество координат mi, равных 2. Так, если рассматривается (3, 3, 2)-ожерелье, то n = 8, r = 3, q = 1. Следовательно, ожерелью x сопоставляется (8, 7)-диаграмма H, содержащая 8 вершин и 7 ребер, образующих 3 компоненты связности. Ребра диаграммы H при их изображении на плоскости могут пересекаться, но точки их пересечения вершинами H не являются. Описанная (n, n - q)-диаграмма однозначно определяет ожерелье xеТ и отличается от обычного определения (n, n - q)-графа лишь дополнительным требованием (а). Такая диаграмма названа в [12. С. 21] представительным графом симметричного ожерелья x. Этот граф будем считать непомеченным. Каждый граф H имеет группу автоморфизмов Г = T(H), состоящую из изоморфизмов H на себя [16. С. 311]. Среди n! перестановок n узлов H только 2n перестановок являются изометриями в смыс-99 Информатика и программирование / Informatics and programming ле метрики p(-,-) . Данные изометрии сохраняют инвариантными n(n - 1)/2 расстояний между узлами графа H. Очевидно, это вращения и зеркальные отражения, которые в совокупности образуют группу диэдра Dn = {s, t:s" = t2 = (st) = e} , где s - вращение на угол 2n/n, t - отражение. Поскольку далее предметом нашего интереса будут восьмистишия, кратко охарактеризуем свойства симметрий группы Ds [7]. Для этого выделим в ней подгруппу G+ и ее дополнение G ~ = G \\ G+ : G+ = {ss-2i: i = 0,..., 3} , G = {s9-2t, tss-J : i = 0,...,3, j = 0,...,7} . Группа G+ = G' - коммутант Ds, при этом G/G' = D2. Изометрии g e G+ - это вращения. Дополнение G ~ = G \\ G+ группой не является, но, как и G+, состоит из объединения классов сопряженности группы Ds, из них два множества - S, S e G - представляют особый интерес: S = {t, ts2, ts4, ts6} , S = {ts, ts3, ts5, ts1} . Множество SI содержит отражения относительно диагоналей правильного 8-угольника. Их можно представить в виде композиций отражений относительно осей симметрии, проходящих через середины сторон 8-угольника, и вращений. Множество 52 - это отражения относительно осей симметрии, проходящих через середины противоположных сторон 8-угольника. Эти отражения нельзя получить с помощью композиций отражений, принадлежащих 51, и последующих вращений. Оба множества при любом n = 2m содержат одинаковое число элементов. Существование множеств 51 и 52 - источник ахиральной и хиральной симметрии ожерелий. 2.3. Хиральность С понятием симметрии тесно связан феномен хиральности. Согласно лорду Кельвину, классическое определение хиральности звучит так: «Я называю любую геометрическую фигуру или группу точек хиральной и говорю, что она обладает хиральностью, если ее отражение в идеально плоском зеркале не может быть перенесено так, чтобы оно совпало с нею самой» [7]. Применительно к нашим обозначениям это определение формулируется следующим образом: ожерелье x eT хирально, если оно неэквивалентно (относительно вращений) своему зеркальному отражению у = ф(х) . В противном случае ожерелье x ахирально, т.е. х ~ ф(х) . Исходя из этого определения ахиральность трактуется как искаженная зеркальная симметрия, а хиральность означает отсутствие зеркальной симметрии. Таким образом, ахиральность и хиральность являются характеристическими свойствами множеств 5i, S2 e Dg. Комбинаторная проблема перечисления хиральных объектов в R2 связана с проблемой перечисления автоморфизмов 2-го порядка группы симметрий G [5. С. 278]. Поскольку группой автоморфизмов ожерелья как простого (n, ^-цикла [2. С. 26] является группа диэдра Dn, содержащая отражения, т.е. автоморфизмы порядка 2, то в множестве T каждое ожерелье а сопровождает двойственный ему элемент b, образующий с ним энантиомерную пару (a, b), при этом энантиомеры a и b принадлежат разным орбитам. В приложениях этот факт хорошо известен [8. С. 63]. Очевидно также, что если ожерелье a ахирально, т.е. a ~ ф(а) , то энантиомеры a и b = ф(а) принадлежат одной орбите. Перечисленные виды симметрии могут иметь разный порядок, т.е. представительные графы H могут иметь несколько осей симметрии того или иного порядка. В связи с этим возможны следующие типы симметрий [k, l]: [k,0], [k, k], [0, l], [0,0], k, l > 1, где k > 0 - порядок зеркальной или ахиральной симметрии, l > 0 - порядок хиральной симметрии. Ахиральная симметрия может встречаться только в сочетании с осевой, при этом всегда k = l > 0. Если k = l = 0, то ожерелье по определению несимметрично. К этому случаю из чисто алгоритмиче-100 Григорьев Ю.Д. Перечисление симметричных ожерелий ских соображений будем относить и центральную симметрию - вращение вокруг точки, которое можно представить как композицию двух зеркальных симметрий [16. С. 52-56]. Одному и тому же типу симметрии может соответствовать несколько классов симметрии. Под ожерельями разных классов, принадлежащими одному типу симметрии, понимаются ожерелья, графы H которых изоморфны [2. С. 24], но не могут быть переведены друг в друга никаким движением (сдвигом, вращением, отражением или их композициями), т.е. каким-либо изометрическим преобразованием [18. С. 278]. Ожерелья, которые могут быть переведены одно в другое некоторым движением, назовем конгруэнтными. Такие ожерелья принадлежат одному классу симметрии. Пример 1. На рис. 1, 2 представлена энантиомерная пара хиральных ожерелий, представляющая строфы I и II стихотворения А. Пушкина «Осень». Строфы отличаются тем, что в них А. Пушкин меняет местами мужские и женские рифмы. Аналогично построены и последующие пары строф. Сами же строфы представляют знаменитую твердую форму - октаву [11. С. 172]. Ей соответствует симметрия [0, 1]. Рис. 1. А. Пушкин. Осень («Октябрь уж наступил...»). Строфа I: abab abcc (ожерелье 11 в табл. 1) Fig. 1. A. Pushkin. Autumn («October has already come.». The stanza I: abcb adcd (necklace 11 in the table 1) Рис. 2. А. Пушкин. Осень («Теперь моя пора.»). Строфа II: baba bacc (ожерелье 11 в табл. 1) Fig. 2. A. Pushkin. Autumn («Now is my time.». The stanza II: abcd cabd (necklace 11 in the table 1) 3. Перечисление ожерелий Аналитический подсчет числа представительных графов является нерешенной в общем случае задачей. Некоторое продвижение в ее решении можно получить в частных случаях, используя лемму Бернсайда. Теорема 1. Количество Nc (2, n - 2) представительных графов (2, n - 2)-ожерелий равно Nc (2, n - 2) = [n/2]. (1) Доказательство. Пусть ф(х) - функция Эйлера [19. С. 28], P(k, Г) = (k +1)!/kill - биномиальный коэффициент, НОД (к, Г) - наибольший общий делитель целых чисел к и l. Согласно лемме Бернсайда количество орбит (2, n - 2)-ожерелий равно N0 (2, n - 2) = n1 £ q

Скачать электронную версию публикации