Исследование свойств орбит преобразования Донахью тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат наук Бызов Виктор Александрович

• Бызов Виктор Александрович
• кандидат наук
• 2021

Оглавление диссертации кандидат наук Бызов Виктор Александрович

Введение

Глава 1. История вопроса и предварительные замечания

1.1 Основные понятия и определения

1.2 Обзор литературы

1.3 Специальные классы деревьев

Глава 2. Исследование ручных компонент преобразования Донахью

2.1 Карусельный эффект для триад

2.2 Карусельный эффект для внутренних ростков

2.3 Ручные компоненты: длинные орбиты

2.4 Ручные компоненты: большие семейства коротких орбит

Глава 3. Графы поворотов

3.1 Производящие функции для количества вершин в графах поворотов

3.2 Производящие функции для количества вершин в примитивных графах поворотов

3.3 Перечисление циклов в графах поворотов

3.3.1 Перечисление циклов в графах первого уровня

3.3.2 Перечисление циклов в графах второго уровня

Глава 4. Дуги преобразования Донахью

4.1 Перечисление всех деревьев с заданными длинами дуг

4.2 Перечисление примитивных деревьев

с заданными длинами дуг

4.3 Переход от локальных свойств деревьев к глобальным

Заключение

Список литературы

Введение диссертации (часть автореферата) на тему «Исследование свойств орбит преобразования Донахью»

Введение

Многие специалисты отмечают (например, в [1], [2]), что современный математический аппарат плохо подходит для решения задач описания наноуров-невых процессов. Используя классические приемы математического анализа, которые чаще всего встречаются в контексте классической физики, ученые, по существу, основываются на предположении о безграничной делимости вещества, в то время как на наноуровне данное утверждение вступает в противоречие с самой природой рассматриваемых процессов.

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

Следует, однако, понимать, что клеточно-автоматные модели до сих пор являются лишь «обособленными иллюстрациями». Учёные редко используют их в качестве моделей реальных процессов; и даже в этих случаях рассматриваются, как правило, только двумерные клеточно-автоматные модели. Их обычно исследуют на целочисленной решетке, в то время как нанопроцессы могут происходить в самых различных условиях. Кроме того, правила функционирования клеточных автоматов, которые аппроксимируют реальные наноуровневые процессы, довольно сложно вычислить. Также маловероятно, что клеточные автоматы являются единственным адекватным рассматриваемой ситуации классом моделей.

В современной литературе комбинаторные динамические системы как правило либо относятся к задачам символической динамики, либо описываются клеточными автоматами. Варианты, не относящиеся к этим двум классам моделей, встречаются крайне редко. В этом смысле работа, посвящённая исследованию нетривиального примера комбинаторной динамической модели, представляется весьма актуальной.

В качестве такого объекта изучения автором было выбрано преобразование Донахью плоских деревьев [4]. Преобразование Донахью можно рассматривать

как перестановку на множестве деревьев заданного размера. При этом, структура этой перестановки, как отмечается, в [4], [5], является весьма сложной.

Важно заметить, что в научной литературе достаточно часто рассматриваются различные биекции между комбинаторными интерпретациями чисел Каталана (к которым, в частности, относятся плоские деревья). Накоплено большое количество результатов относительно возникающих при рассмотрении этих биекций перечислительных задач. Так, например, отметим работы В. Че-на (W.Y.C. Chen), Э. Дойча (E. Deutsch), Д. Каллана (D. Callan), С. Элизальде (S. Elizalde) (см., например, [5—17]). То есть имеется устойчивый интерес исследователей к решению задач рассматриваемой проблематики.

Рассматриваемый в работе контекст — не единственный, в котором продуктивно взаимодействуют понятия деревьев и динамических систем. Так, например, отметим работы [18—20], в которых это происходит, правда, совсем иначе. В частности, деревья там служат способом организации иерархии, а не точками динамической системы.

Целью данной работы является исследование свойств орбит и фрагментов орбит преобразования Донахью и решение возникающих при этом перечислительных задач.

Для достижения данной цели были поставлены следующие задачи.

1. Исследование свойств ручных компонент преобразования Донахью. Под ручными компонентами здесь и далее будем понимать деревья и фрагменты деревьев, для которых результат преобразования Донахью можно вычислить значительно быстрее, чем при непосредственном моделировании.

2. Попытка упрощённой аппроксимации преобразования Донахью при помощи уровневых графов поворотов.

3. Исследование свойств деревьев с заданными длинами дуг и решение возникающих при этом перечислительных задач. Дугами будем называть фрагменты орбит преобразования Донахью, расположенные между деревьями определённого вида.

Научная новизна. Все полученные в диссертации результаты являются новыми.

Теоретическая и практическая значимость. Работа носит теоретический характер. Исследованная динамическая система, несмотря на конечность и обратимость, представляется достаточно трудным объектом для изучения, ко-

торое потребовало не только применения стандартных методов, но и разработки специальных подходов, применимых и в смежных задачах комбинаторной динамики.

Методология и методы исследования. В диссертации используются комбинаторные методы и методы асимптотического анализа.

Основные положения, выносимые на защиту.

Конструктивные результаты:

1. построено семейство плоских деревьев, длины орбит преобразования Донахью для которых растут как 0(п2), где п — количество триад в дереве;

2. построено новое семейство орбит преобразования Донахью длины 6, количество которых растёт как 0(п2), где п — количество триад дерева;

3. построено семейство орбит преобразования длины 9, количество которых растёт как 0(2^), где п — количество триад.

Результаты, полученные при исследовании графов поворотов:

1. вычислены производящие функции и получены асимптотические оценки для количества вершин в графах поворотов и примитивных графах поворотов;

2. вычислены производящие функции и получена явная формула для количества циклов заданной длины в графе поворотов первого уровня (без кратных рёбер). Вычислены производящие функции и получены асимптотические оценки для количества циклов длины 2 и 3 в графе поворотов второго уровня (без кратных рёбер).

Результаты, полученные при исследовании дуг преобразования:

1. вычислены производящие функции и получены асимптотические оценки для количества деревьев с заданными длинами нескольких первых дуг. Результаты аналогичного вида получены для примитивных деревьев;

2. сформулированы достаточные условия, при выполнении которых длины всех дуг дерева равны одному, двум. Эти условия позволяют от локальных (структурных) свойств деревьев перейти к глобальным свойствам (кратность длины орбиты на два, три).

Апробация работы. Основные результаты работы докладывались на межрегиональной научно-практической конференции «Математическое моделирование и вычислительная математика» (г. Киров) в 2012 г.; на ежегодной всероссий-

ской конференции «Общество, наука, инновации» (г. Киров) в 2012, 2014, 2016, 2017 гг.; на всероссийской научно-практической конференции «Математика и междисциплинарные исследования» (г. Пермь) в 2019 г.; на международной конференции «Алгебра и математическая логика: теория и приложения» (г. Казань) в 2019 г.

Личный вклад. Содержание диссертации и основные положения, выносимые на защиту, отражают персональный вклад автора в опубликованные работы. Подготовка к публикации полученных результатов проводилась совместно с научным руководителем И.А. Пушкаревым, причем вклад диссертанта был определяющим. Все результаты, представленные к защите, получены лично автором.

Публикации. По основным результатам исследования опубликовано 16 работ. Из них 4 статьи в журналах, рекомендованных ВАК ([A1-A4]), 9 статей в сборниках тезисов и трудах конференций докладов ([A5-A13]) и 3 статьи в журналах не из списка ВАК ([A14-A16]). Две статьи были переведены на английский язык и вышли в журнале, входящем в базу данных международного цитирования Scopus ([A1, A2]). Также имеются 3 свидетельства о государственной регистрации программ для ЭВМ ([A17-A19]).

Объем и структура работы. Диссертация состоит из введения, четырёх глав и заключения. Полный объём диссертации составляет 133 страницы, включая 82 рисунка и 2 таблицы. Список литературы содержит 38 наименований.

Глава 1. История вопроса и предварительные замечания

1.1 Основные понятия и определения

Насколько нам известно, впервые рассматриваемое преобразование было дано в работе [4] Р. Донахью Donaghey). Преобразование Донахью действует на комбинаторных интерпретациях чисел Каталана. Определим его для плоских кубических деревьев с висячим корнем (далее будем использовать аббревиатуру ПКДВК). Ниже описаны основные элементы структуры ПКДВК.

1. У любого ПКДВК есть выделенная вершина — (висячий) корень, имеющая ровно одного сына.

2. Все остальные вершины ПКДВК делятся на два непересекающихся класса: листья и нелистья. Каждый нелист имеет ровно двух сыновей — левого и правого. Лист не имеет сыновей и вообще потомков.

Пусть а0 — сын корня ПКДВК Т, а\ — правый сын а0, а2 — правый сын а\ и т.д., ап — правый сын ап-\ и при этом —лист. Последовательность вершин (а0, ..., ап) назовем старшей правой цепью (в том случае, когда а0 — произвольная вершина дерева, полученную конструкцию назовем просто правой цепью). Все вершины старшей правой цепи, кроме ап, являются, в свою очередь, корнями дочерних деревьев (сыном корня дочернего дерева, корнем которого является а^, является левый сын этой вершины). Дерево с корнем а^ обозначим Т{ = Тг(оц), а данную ситуацию в целом запишем формулой

которую назовем правым разложением дерева Т.

Аналогично определяется старшая левая цепь и левое разложение дере-

Т = \То(ао),Т\(а\),... ,Тп-1(ап-\), ап),

(1.1)

(1.2)

Определение 1.1.1.

1. Если Т — тривиальное дерево, состоящее только из корня и сына корня,

то т (Т) = Т.

2. Пусть Т — ПКДВК, и для всех ПКДВК 5 с меньшим количеством вершин их образ т (Б) уже определен. Далее, пусть Т = |То(а0),Т1(а1),...,Тп-1 (ап-1),ап) —правое разложение дерева Т. Тогда образом Т назовем дерево т(Т), левое разложение которого есть г (Т) = (ао,т (То)Ы,..., г (Тп-1)(ап )|.

В данном виде преобразование Донахью определено как преобразование помеченного ПКДВК (т. е. дерева, все вершины и ребра которого различны).

На рисунке 1.1 показано, как изменяется ПКДВК при рассматриваемом преобразовании.

О О

Рисунок 1.1 — Пример преобразования Донахью

Другое определение преобразования Донахью можно получить естественным образом из рассмотрения биекции между ПКДВК и плоскими (не обязательно кубическими) деревьями с висячим корнем (ПДВК). Отличие ПДВК от ПКДВК состоит в том, что нелист ПДВК может иметь любое натуральное количество упорядоченных сыновей. Для построения этой биекции нам понадобится понятие уголка в некубическом дереве.

Определение 1.1.2. Пусть и — вершина ПДВК. Уголком называется тройка (и, е1, е2), где е1 и е2 — два (необязательно различных) ребра, смежных с вершиной и. Уголок (и, е1, е2) может быть:

- открывающим, если е1 — ребро, входящее в вершину и, е2 — первое ребро, выходящее из вершины и;

- закрывающим, если е2 — ребро, входящее в вершину и, е1 — последнее ребро, выходящее из вершины и;

- регулярным, если оба ребра е1 и е2 выходят из вершины и и при этом являются соседними в смысле линейного порядка на сыновьях вершины и, то есть имеют номера п и п + 1;

- развёрнутым, если оба ребра е1 = е2 совпадают с ребром, входящим в вершину и (которая в этом случае обязана быть листом).

- корневым, если и = г — корень дерева и оба ребра е1 = е2 совпадают с ребром, выходящим из вершины г.

Все уголки, рассматриваемые в работе, принадлежат к одному из пяти указанных типов. На рисунке 1.2 уголок 1 является корневым, уголки 2 и 6 — открывающими, 3, 4 и 7 — регулярными, 5 и 8 — закрывающими, 9 — развёрнутым.

Рисунок 1.2 — Уголки в некубическом дереве

Известно, что количество ПКДВК с п листьями равно количеству ПДВК с п некорневыми вершинами, фактически это два из многочисленных определений чисел Каталана. Кроме того, хороша известна биекция между этими множествами деревьев. При этом вершинам кубического дерева соответствуют уголки некубического. Эта биекция проиллюстрирована на рисунке 1.3.

Назовем данную биекцию правой. Существует также симметричный вариант этой биекции (левый), переводящий дерево Т в дерево 1(Т) (рисунок 1.4).

Совпадение правых деревьев на рисунках 1.1 и 1.4 не случайно.

Определение 1.1.3. Пусть Т — ПКДВК. Применим к нему правую биекцию, получим ПДВК г(Т). Применим к нему биекцию, обратную к левому варианту, получим новое ПКДВК т(Т) = I-1 о г(Т). Назовем его образом дерева Т при преобразовании Донахью.

7 8 13 14

т

13*

г(Г)

Рисунок 1.3 — Правая биекция между ПКДВК и ПДВК

X 14

13

»3 5

/(т(Т)) 2/\з т(Г)

Рисунок 1.4 — Левая биекция между ПКДВК и ПДВК

Равносильность двух приведенных определений почти очевидна. Вершины некубического дерева при правой обратной биекции превращаются в правые цепи в кубическом дереве, а при левой обратной — в левые цепи, поэтому их длины равны, а деревья потомков располагаются в одном и том же порядке и подвергаются аналогичным преобразованиям. Это обстоятельство иллюстрирует рисунок 1.5.

Третье определение представляет преобразование Донахью в виде композиции двух инволюций и увязывает его ещё с одной интерпретацией чисел Каталана, так называемыми путями Дика.

На множестве всех ПКДВК есть естественная инволюция а (назовем её симметрией), делающая всех левых сыновей правыми и наоборот. На множестве путей Дика тоже есть естественная инволюция 0 (назовем её осевым отражением), соответствующая прохождению пути в обратном направлении (рисунок 1.6). Кроме того, есть каноническая биекция превращающая ПКДВК с п листьями в путь Дика, состоящий из 2(п — 1) звеньев.

о

о

3

5

7

13

Рисунок 1.5 — Второе определение преобразования Донахью

Определение 1.1.4. Преобразованием Донахью назовем композицию (преобразования выполняются справа налево) о 0 о ^ о а.

Равносильность третьего определения второму следует из вида прямой би-екции между путями Дика и некубическими деревьями, которую иллюстрирует рисунок 1.7.

Таким образом, доказана

Теорема 1.1.1 (равносильность определений преобразования 1).

Три вышеприведённых определения равносильны.

Примером альтернативного типа элементов, при помощи которого можно описать структуру дерева, являются юниты, неформально говоря — «половинки рёбер». При этом каждое ребро распадается на два юнита, верхний и нижний, верхний смежен с двумя другими юнитами в вершине, из которой выходит ребро, а нижний —в вершине, в которую ребро входит. Не останавливаясь на юнитах, перейдём сразу к производным от них более удобным элементам, называемым триадами. Триады в первом приближении соответствуют вершинам бинарного дерева, получающегося из кубического удалением листьев.

Определение 1.1.5. Сопоставим каждой нелистовой и некорневой вершине и плоского кубического дерева одноимённую триаду — четвёрку (и, 82,в3), где элементы — суть юниты, смежные с этой вершиной. Для

G

15

15

7 8 13 14

т

14 13 8 7

ч>

о

,J J J ê\ tj è~~

/г-• • • \ , P 9 \

//2 4 6 Ь'/1^712 14 \

1 9 11 15

в

Ч>

4 4 \5

2- «3 r(T)

o

'/ • * 'A 4 / i

/У14 12уУт\'/

6 4 2\

15

11 9

Рисунок 1.6 — Третье определение преобразования Донахью

Рисунок 1.7 — Биекция между путями Дика и ПДВК

определённости: й! —верхний юнит, з2 — левый, — правый. Юниты триады могут быть свободными или связанными:

1. Верхний юнит является свободным, если триада соответствует сыну корня, и связанным, если триада соответствует нелисту, являющемуся сыном другого нелиста.

1

2. Левый юнит является свободным, если левым сыном нелиста и является лист, иначе является связанным. Аналогично определяется сво-бодность или связанность правого юнита в3.

Например, если нелист V является левым сыном нелиста и, то левый юнит триады (и, з1,з2, в3) с верхним юнитом ¿1 триады являются

связанными (и образуют «полноценное» ребро). Пример декомпозиции дерева в виде набора триад проиллюстрирован на рисунке 1.8.

Триаду, содержащую сына корня, назовём корневой. Заметим, что на множестве триад дерева можно рассматривать инцидентности аналогично вершинам. Так, например, на рисунке 1.8 слева у триады 7 левым сыном является триада 8, а правым — триада 9. Триада 1 является корневой. Дерево, присоединённое к корневой триаде слева, будем называть левым поддеревом, справа — правым поддеревом.

Дадим определение преобразования Донахью на языке триад.

Определение 1.1.6.

1. Определим правую цепь триад аналогично тому, как это сделано для вершин. В частности, она начинается с триады, не являющейся ничьим правым потомком — либо с левого сына, либо с корневой триады. Аналогично определяются левые цепи триад.

2. Операцией переклейки цепочки назовём следующее преобразование дерева, сформированного из триад:

- выбирается старшая правая цепь триад;

- выделяются первая и последняя (не имеющая правого потомка) триады этой цепи; заметим, что верхний юнит первой триады является связанным (кроме случая корневой триады), а правый юнит последней триады — свободным;

- правый юнит последней триады связывается с тем же самым юнитом, с которым был связан верхний юнит первой триады; если первая триада была корневой, то правый юнит последней триады становится верхним юнитом корневой триады;

- верхний юнит первой триады освобождается;

- все триады цепи подвергаются однотипному переименованию юнитов: правый становится верхним, верхний — левым, левый — правым.

Заметим, что в результате этого преобразования старшая правая цепь триад становится старшей левой цепью триад, при этом порядок старшинства триад инвертируется.

3. Преобразованием Донахью дерева называется процедура, состоящая из переклейки старшей правой цепи триад и последующего аналогичного преобразования всех дочерних деревьев.

Определение 1.1.6 проиллюстрировано на рисунке 1.8. Следующая теорема очевидна по построению.

Теорема 1.1.2 (равносильность определений преобразования 2).

Определения 1.1.1 и 1.1.6 равносильны.

Рисунок 1.8 — Преобразование Донахью для дерева, разбитого на триады

Далее в работе будет использоваться как обычное представление дерева, так и триадное изображение.

Стоит отметить, что приведённые определения преобразования Донахью не являются единственно возможными, имеется большое количество довольно разнообразных его равносильных определений. Источником таковых является большое количество комбинаторных интерпретаций чисел Каталана, каждая из которых позволяет некоторым образом определить преобразование. В [21] приводится небольшой обзор такого рода определений на языках наиболее распро-

странённых интерпретаций (положительные пути хромого короля, правильные расстановки скобок, триангуляции правильного многоугольника и т. д.).

Преобразование Донахью по сути является перестановкой на множестве плоских ПКДВК (или других интерпретаций чисел Каталана). Циклы этой перестановки назовём орбитами преобразования Донахью.

Определение 1.1.7. Правой огибающей цепью называется последовательность триад дерева, полученная по следующим правилам:

1. первым элементом этой последовательности становится корневая триада;

2. если у последнего добавленного в последовательность элемента есть правый сын, то этот правый сын становится следующим элементом последовательности;

3. если у последнего добавленного в последовательность элемента нет правого сына, но есть левый сын, то этот левый сын становится следующим элементом последовательности;

4. если у последнего добавленного в последовательность элемента нет ни правого, ни левого сыновей, то формирование правой огибающей цепи завершается.

Аналогичным образом определим левую огибающую цепь.

Определение 1.1.8. Левой огибающей цепью называется последовательность триад дерева, полученная по следующим правилам:

1. первым элементом этой последовательности становится корневая триада;

2. если у последнего добавленного в последовательность элемента есть левый сын, то этот левый сын становится следующим элементом последовательности;

3. если у последнего добавленного в последовательность элемента нет левого сына, но есть правый сын, то этот правый сын становится следующим элементом последовательности;

4. если у последнего добавленного в последовательность элемента нет ни левого, ни правого сыновей, то формирование левой огибающей цепи завершается.

Рисунок 1.9 иллюстрирует данные определения. Слева на рисунке изображено дерево, элементы правой огибающей цепи которого выделены жирным и

пронумерованы. Справа проиллюстрировано, как изменяется правая огибающая цепь при преобразовании Донахью.

1 2

/К 3 X X 4 X X Х^ . т > XX _ ^ X ч X Хз X X XX X Хе

X

Рисунок 1.9 — Правая огибающая цепь дерева

В следующих разделах нам потребуется вспомогательное утверждение, связанное с понятием огибающих цепей.

Лемма 1.1.3.

1. Дерево т (Т) имеет пустое правое поддерево тогда и только тогда, когда старшая правая цепь дерева Т заканчивается триадой, не имеющей левого сына.

2. Дерево т-1(Т) имеет пустое левое поддерево тогда и только тогда, когда старшая левая цепь дерева Т заканчивается триадой, не имеющей правого сына.

3. Дерево т2(Т) имеет пустое правое поддерево тогда и только тогда, когда правая огибающая цепь дерева Т заканчивается триадой, являющейся левым сыном.

4. Дерево т-2(Т) имеет пустое левое поддерево тогда и только тогда, когда левая огибающая цепь дерева Т заканчивается триадой, являющейся правым сыном.

Доказательство. Докажем пункты 1 и 3. Пункты 2 и 4 доказываются аналогично.

1. Пусть г — корень дерева Т, а — триада, являющая концом старшей правой цепи дерева Т. Тогда а становится корневой триадой дерева г (Т). Из определения преобразования у триады а нет левого сына в дереве Т тогда и только тогда, когда в дереве г(Т) у а нет правого сына, то есть г(Т) имеет пустое правое поддерево. Таким образом, пункт 1 доказан.

3. Рассмотрим произвольное дерево Т\. Конечную триаду старшей правой цепи Т\ обозначим через а\; левое поддерево дерева с корнем а\ обозначим

через Т2. Конец старшей правой цепи дерева Т2 обозначим через а2, через Т3 обозначим левое поддерево дерева с корнем а2. Будем продолжать этот процесс до тех пор, пока очередное дерево не окажется пустым. Рисунок 1.10 иллюстрирует введённые обозначения. Заметим, что триады а!, ..., а^ принадлежат правой огибающей цепи (см. раздел 1.2) дерева Т!. Триада а^ — конец этой огибающей цепи.

Рисунок 1.10 — Иллюстрация к доказательству леммы 1.1.3

Из определения преобразования в дереве т(Т!) к триаде а! справа будет присоединено дерево т(Т2), в дереве т(Т2) справа к триаде а2 будет присоединено дерево т(Т3), и т.д., в дереве т(Т^х) к триаде ак-х будет присоединено дерево т (Ть). Также заметим, что при % = 1, к в дереве т (Т{) корневой триадой будет а,.

Таким образом, в дереве т(Тх) триады ах, ..., а^ образуют старшую правую цепь. Из пункта 1 дерево т2(Тх) имеет пустое правое поддерево тогда и только тогда, когда в дереве т(Тх) старшая правая цепь заканчивается триадой, не имеющей левого сына. То есть в дереве т(Тх ) триада аи не имеет левого сына. Из определения преобразования это равносильно тому, что в дереве Тх правая цепь, заканчивающаяся триадой о^, состоит из одной триады. А это эквивалентно тому условию, что правая огибающая цепь дерева Тх заканчивается триадой аи, являющейся левым сыном. □

1.2 Обзор литературы

Р. Донахью в работе [4] описывает рассматриваемое преобразование для четырех множеств: двух видов расстановок скобок, плоских кубических деревьев и бинарных деревьев. В предыдущем разделе было рассмотрено действие преобразования на множестве плоских деревьев. Приведём определения для множеств расстановок скобок из статьи [4].

Расстановку скобок первого вида назовём обычной расстановкой скобок; она определяется посредством следующих правил:

1. пустая строка является обычной расстановкой скобок;

2. если Б — обычная расстановка скобок, то (Б) — тоже обычная расстановка скобок;

3. если А и В — обычные расстановки скобок, то (АВ) — тоже обычная расстановка скобок.

Другой способ расстановки скобок, называемый бинарной расстановкой скобок, определяется следующим образом: это правильная расстановка п пар скобок (включая одну внешнюю пару) в неассоциативной сумме п + I переменной, из которой затем стираются все переменные. Например, если количество пар скобок п равно двум, то множество обычных расстановок скобок состоит из элементов (()) и ()(), а множество бинарных расстановок скобок —из элементов (+(+)) и ((+)+). Для множества обычных расстановок п пар скобок введём обозначение СВ(п), для множества бинарных расстановок скобок — ВВ(п).

Определение 1.2.1. Отображение Я (соответственно Ь) из СВ (п) в В В (п) действует на элемент из СВ (п) следующим образом:

1. во-первых, каждая закрывающая (соответственно открывающая) скобка заменяется на +;

2. затем расставляются новые закрывающие (соответственно открывающие) скобки (их позиции однозначно определены).

При п = 3 биекции Я и Ь действуют следующим образом:

GB(3) Д BB(3) £ GB(3)

((( ))) (((+)+)+) ( )( )( )

(( )( )) ((+(+))+) (( ))( )

( )(( )) (+((+)+)) (( )( ))

(( ))( ) ((+)+(+)) ( )(( ))

( )( )( ) (+(+(+))) ((( )))

Определим следующие два отображения:

1. MG = L-1 о R: GB (п) ^ GB (п)

2. Мв = R о L-1: ВВ(п) ^ ВВ(п)

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

Кроме определения преобразования в основополагающей работе [4] приведено понятие примитивного дерева (см. раздел 2.1) и доказаны некоторые свойства таких деревьев. Также в статье содержатся эмпирические данные относительно длин орбит преобразования.

В статье [22] описывается аналог преобразования Донахью для 312-избе-гающих перестановок. Перестановка п элементов п называется 312-избегающей, если не существует номеров 1 ^ i < j < к ^ п таких, что j) < ж (к) < ж(i). Биекция In : Post между множеством кубических деревьев и множеством 312-избегающих перестановок определяется следующим образом. Рассмотрим триадное представление дерева Т и пронумеруем триады этого дерева числами от 1 до п, совершая симметричный обход (inorder traversal). Выписывая номера триад при обратном обходе дерева Т (postorder traversal), получим перестановку, являющуюся образом дерева при биекции In : Post (доказательство того, что данное отображение действительно является биекцией, приведено в [22]). Схожим образом действует и биекция Pre : In: триады дерева нумеруются при прямом обходе (preorder traversal), а номера читаются при симметричном. Ниже на рисунке 1.11 приведен пример построения перестановок In : Post(T) и Pre : In(T).

Список литературы диссертационного исследования кандидат наук Бызов Виктор Александрович, 2021 год

Список литературы

1. Еленин Г. Г. Нанотехнологии, наноматериалы, наноустройства // Информационные технологии и вычислительные системы. — 2002. — № 2. — С. 32—56.

2. Малинецкий Г. Г., Курдюмов С. П. Новое в синергетике. Взгляд в третье тысячелетие. — М. : Эдиториал УРСС, 2001. — 328 с.

3. Эбелинг В., Энгель А., Файстель Р. Физика процессов эволюции : Пер. с нем. — М. : «Наука», 2002. — 480 с.

4. Donaghey R. Automorphisms on Catalan trees and bracketings // Journal of Combinatorial Theory, Series B. - 1980. - Vol. 29, no. 1. - P. 75-90.

5. Callan D. A Bijection on Dyck Paths and its Cycle Structure // The Electronic Journal of Combinatorics. — 2007. — Vol. 14, no. 1. — R28.

6. Chen W. Y. A general bijective algorithm for trees // Proceedings of the National Academy of Sciences. — 1990. — Vol. 87. — P. 9635-9639.

7. Emeric D. A bijection on Dyck paths and its consequences // Discrete Math" ematics. — 1998. — Vol. 179, no. 1-3. — P. 253-256.

8. Deutsch E. An involution on Dyck paths and its consequences // Discrete Mathematics. — 1999. — Vol. 204, no. 1-3. — P. 163-166.

9. Deutsch E. Dyck path enumeration // Discrete Mathematics. — 1999. — Vol. 204, no. 1-3. — P. 167-202.

10. Deutsch E. A Bijection on Ordered Trees and Its Consequences // Journal of Combinatorial Theory, Series A. — 2000. — Vol. 90, no. 1. — P. 210-215.

11. Deutsch E. A bijective proof of the equation linking the Schroder numbers, large and small // Discrete Mathematics. — 2001. — Vol. 241, no. 1-3. — P. 235-240.

12. Elizalde S., Deutsch E. A simple and unusual bijection for Dyck paths and its consequences // Annals of Combinatorics. — 2003. — Vol. 7, no. 3. — P. 281-297.

13. Callan D. Some bijections and identities for the Catalan and Fine numbers // Sem. Lothar. Combin. — 2004/06. — Vol. 53, B53e.

14. Callan D. Two bijections for Dyck path parameters, preprint. — 2004 (дата обращения: 15 августа 2018 г.) — http://www.arxiv.org/abs/math.CO/ 0406381.

15. William Y.C. Chen Emeric Deutsch S. E. Old and young leaves on plane trees // European Journal of Combinatorics. — 2006. — Vol. 27, no. 3. — P. 414-427.

16. Chen W. Y., Yan S. H., Yang L. L. Identities from weighted Motzkin paths // Advances in Applied Mathematics. — 2008. — Vol. 41, no. 3. — P. 329-334.

17. Deutsch E., Elizalde S. A bijection between bargraphs and Dyck paths // Discrete Applied Mathematics. — 2018. — Vol. 251. — P. 340-344.

18. Григорчук Р. И. Некоторые вопросы динамики групповых действий на корневых деревьях // Современные проблемы математики, Сборник статей. К 75-летию Института, Тр. МИАН. — 2011. — С. 64—175.

19. Nekrashevych V. Free subgroups in groups acting on rooted trees // Groups, Geometry, and Dynamics. — 2010. — Vol. 4. — P. 847-862.

20. Nagnibeda T., Perez A. Schreier graphs of spinal groups and associated dy" namical systems // arXiv: Group Theory. — 2020. — P. 1-27.

21. Пушкарев И. А., Бызов В. А. Преобразование Донахью: элементарный подход // Записки научных семинаров ПОМИ им. В. А. Стеклова Российской академии наук. — 2013. — Т. 411. — С. 148—177.

22. Feil T., Hutson K., Kretchmar R. M. Tree Traversals and Permutations // Congressus Numerantium. — 2005. — Vol. 172. — P. 201-221.

23. Shapiro L. W. The Cycle of Six // The Fibonacci Quarterly. — 1979. — Vol. 17, no. 3. — P. 253-259.

24. Кнут Д. Э., Грэхем Р. Л., Паташник О. Конкретная математика. Математические основы информатики : Пер. с англ. — М. : Вильямс, 2009. — 784 с.

25. Кнут Д. Э. Искусство программирования. Том 4, A. Комбинаторные алгоритмы. Часть 1 : Пер. с англ. — М. : Вильямс, 2013. — 960 с.

26. Кнут Д. Э. Искусство программирования. Том 1. Основные алгоритмы : Пер. с англ. — М. : Вильямс, 2002. — 720 с.

27. Karttunen A. A080070 - OEIS. — 2003 (дата обращения: 15 августа 2018 г.) — https://oeis.org/A080070/.

28. Karttunen A. A079438 - OEIS. — 2003 (дата обращения: 15 августа 2018 г.) — https://oeis.org/A079438/.

29. Пушкарев И. А. Об одном преобразовании плоских деревьев // Математический вестник педвузов и университетов Волго-Вятского региона. — 2006. — № 8. — С. 92—99.

30. Donaghey R. Restricted plane tree representations of four Motzkin-Catalan equations // Journal of Combinatorial Theory, Series B. — 1977. — Vol. 22, no. 2. — P. 114-121.

31. Bernhart F. R. Catalan, Motzkin, and Riordan numbers // Discrete Mathemat" ics. — 1999. — Vol. 204, no. 1-3. — P. 73-112.

32. Non-Contiguous Pattern Avoidance in Binary Trees / M. Dairyko [et al.] // Electronic Journal of Combinatorics. — 2012. — Vol. 19, no. 3. — P22.

33. Yuan Q. The Catalan numbers, regular languages, and orthogonal polynomials. — 2009 (дата обращения: 15 августа 2018 г.) — https : //qchu. wordpress. com/2009/06/07/the - Catalan- numbers - regular- languages -and-orthogonal-polynomials/.

34. Janjic M., Petkovic B. A Counting Function Generalizing Binomial Coeffi" cients and Some Other Classes of Integers // Journal of Integer Sequences. — 2014. — Vol. 17, no. 3. — P. 1-23.

35. Flajolet P, Sedgewick R. Analytic Combinatorics. — Cambridge University Press, 2009. — 810 p.

36. Drmota M. A Bivariate Asymptotic Expansion of Coefficients of Powers of Generating Functions // European Journal of Combinatorics. — 1994. — Vol. 15, no. 2. — P. 139-152.

37. Albert M. H., Vatter V. Generating and Enumerating 321-Avoiding and Skew-Merged Simple Permutations // Electronic Journal of Combinatorics. — 2013. — Vol. 20, no. 2. — P44.

38. Bergeron F., Labelle G., Leroux P. Combinatorial Species and Tree-like Struc" tures. — New York : Cambridge University Press, 1997. — 457 p.