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

• Валюженич, Александр Андреевич
• кандидат наук
• 2015

Оглавление диссертации кандидат наук Валюженич, Александр Андреевич

Оглавление

Введение

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

1.1 Слова и языки

1.2 Морфизмы

1.3 Конечные перестановки

1.4 Бесконечные перестановки

1.5 Бесконечные перестановки, порожденные бесконечными словами

2 Перестановки, порожденные неподвижными точками сравнимых равно-блочных морфизмов

2.1 Введение

2.2 Необходимые сведения и определения

2.3 Общая схема

2.4 Класс С}1

2.5 Сопряженные перестановки

2.6 Алгоритм для вычисления ¡(и)

2.7 Специальные вправо слова

2.8 Вычисление перестановочной сложности

2.9 Перестановочная сложность слова Туэ-Морса

2.10 Заключительные замечания

3 Перестановки, порожденные неподвижными точками обобщенного морфиз-ма Фибоначчи

3.1 Введение

3.2 Предварительные сведения и определения

3.3 Общая схема

3.4 Оценка /(и) <2

3.5 Вклад специальных слов

3.6 Случай f(u) = 1, f(ua) = 2

3.7 Характеризация и перечисление плохих слов

3.8 Основная теорема

3.9 Связи с комбинаторной сложностью

4 Морфизмы на перестановках

4.1 Введение

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

4.3 Общая схема

4.4 Существование предка

4.5 Основная теорема

4.6 Алгоритм вычисления комбинаторной сложности

4.7 Пример вычисления комбинаторной сложности

4.8 Связь с перестановками, порожденными бесконечными словами

5 Рамочные паттерны в перестановках

5.1 Введение

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

5.3 Гипотеза Стэнли-Вильфа для рамочных паттернов

5.4 Мультиизбегание классических и рамочных паттернов

Литература

Введение диссертации (часть автореферата) на тему «Комбинаторные свойства факторных языков перестановок»

Введение

В данной работе исследуются свойства факторных языков перестановок: мы изучаем языки подперестановок бесконечных перестановок; а также языки конечных перестановок, избегающих подпоследовательностей с определенными свойствами. Эти задачи относятся к комбинаторике слов, бесконечных перестановок, а также теории паттернов в перестановках. Основы комбинаторики слов и теории паттернов в перестановках изложены в монографиях [4,13] и [16,41] соответственно; недавний обзор по бесконечным перестановкам может быть найден в работе [36].

Приведем основные определения. Алфавитом называется конечное (непустое) множество элементов, которые будем называть символами или буквами. Далее алфавит будем обозначать через Е. Конечным словом длины п над алфавитом Е называется последовательность и — щ ... ип из п символов алфавита Е. Длину конечного слова и, то есть число символов в нем, обозначим через |м|. Слово длины 0 называется пустым и обозначается через г. Множество всех конечных слов над алфавитом Е обозначается через Е*.

Бесконечным словом над алфавитом Е называется бесконечная вправо последовательность и — и}\Ш2Шз... символов алфавита Е. Конкатенацией конечного слова и и слова V (конечного или бесконечного) называется слово х = гсьг2... такое, что Х{ = щ для г < |и| и XI — для г > \и\. Конкатенация слов и и у обозначается через иу. Слово V называется подсловом конечного или бесконечного слова и, если существуют слова й! и 52 такие, что и = з1уз2. Если при этом б'х - е (¿-2 — е), то V называется префиксом (,суффиксом) слова и. Вхождением слова ибГв слово и называется пара (и,т,) такая, что и = и)т^1ит+2 ■ ■ ■ и>т+п- Комбинаторной сложностью сш(п) бесконечного слова ш называется число его различных подслов длины п. Бесконечное слово вида и = -ииу... обозначается через уш. Бесконечное слово ш называется периодическим, если и> — иуш для некоторых конечных слов и и V. Бесконечное слово ш называется непериодическим, если его нельзя представить в виде и = иь'^ для некоторых конечных слов и и у. Языком называется произвольное подмножество Е*. Язык называется факторным, если он с каждым своим элементом содержит все его подслова, то есть замкнут относительно операции взятия подслова. Нетрудно видеть, что язык подслов Р(и>) произвольного

бесконечного слова и является факторным.

Отображение h : Е* —> Е* называется морфизмом, если h(xy) - h(x)h(y) для любых слов х,у Е Е*. Нетрудно видеть, что морфизм однозначно определяется образами всех символов алфавита Е, которые будем называть блоками. Морфизм называется 1-равноблочным, если все его блоки имеют длину I. Морфизм р : Е* —> Е* называется маркированным, если его блоки имеют вид р(а) = baxaca, где ха — некоторое произвольное слово, Ьа и са — символы алфавита Е, и все Ьа (как и все са) различны для разных символов алфавита. Морфизм р : Е* —> Е*, где Е = {0,1}, будем называть бинарным. Морфизм р : Е* —> Е* называется нестирающим, если все его блоки непусты.

Пусть а е Е. Рассмотрим нсстирающий морфизм р : Е* —Е* такой, что р(а) начинается с символа а и <р(а) ф а, то есть р(а) — ах для некоторого непустого слова х. Определим бесконечное слово со следующим образом: положим префикс oj\.. слова со равным слову рп(а). Поскольку для любого п рп~^(а) — это префикс рп(а), то слово и определено корректно. Полученное слово из будем обозначать через lim рп(а).

П—УОО

Также заметим, что для построенного слова ш выполнено равенство и = <р{ш). Произвольное слово U1 называется неподвижной точкой морфизма р, если и> = р(и). Отметим, что единственная неподвижная точка морфизма р, начинающаяся с символа а, равна lim рп(а).

п—»оо

Будем говорить, что ¿-равноблочный маркированный бинарный морфизм р такой, что слово <¿>(0) начинается с Ü, принадлежит классу Qu если р имеет следующие свойства (мы предполагаем, что I > 2): Свойства.

1. Если у?(0) = ОиОх для некоторого слова х, то Oi/l не является полсловом </?(0) и <^(1), и 0?; не является суффиксом <¿>(0) и <¿>(1).

2. Если р( 1) = lulx для некоторого слова х, то 1 иО не является подсловом 93(0) и у?(1), и lu не является суффиксом <^(0) и у?(1).

Бинарный морфизм р будем называть сравнимым, если р £ Qi для некоторого I > 2. Морфизм вида (¿(0) = 01^,^(1) — 0, где к > 2, будем далее называть обобщенным морфизмом Фибоначчи.

Конечной перестановкой х длины п будем называть упорядоченную тройку х — ({1____, п}, <х. <), где <х — это некоторый линейный порядок на множестве {1.2... .п},

а < — естественный порядок на множестве {1,2,... ,п}. В дальнейшем будем писать х — Х\Х2---ХП, если {х1,х2,. ■ ■ ,хп} — это некоторая перестановка чисел из множества {1,2, ...,п} такая, что хг < если и только если I <х ]. Рассмотрим произвольную перестановку 7г = 7Г17Г2... 7гп длины п. Классическим паттерном (или просто паттерном) называется перестановка х длины к. Подпоследовательность тхп-к12.. .-п{к называется вхождением классического паттерна х — х\х2 ...Хк в перестановку 7г, если 7Г;а < 7г,-( тогда и только тогда, когда хя < х1 для всех 1 < в < Ь < к. Будем говорить, что перестановка -к избегает паттерн х, если она не содержит вхождений этого паттерна. Множество перестановок длины п, избегающих паттерна х, обозначим через 5„(ж); мощность множества Бп(х) обозначим через вп(х).

Бесконечной перестановкой будем называть упорядоченную тройку 5 = (М, <д,<), где <5 — это некоторый линейный порядок на множестве натуральных чисел N. а < — естественный порядок на множестве натуральных чисел. Пусть 5 — бесконечная перестановка. Конечную перестановку х длины п такую, что г <х ] тогда и только тогда, когда т + г — 1 <6 т + ] — 1 обозначим через 5[т, т + п — 1]. Конечная перестановка 7г длины п называется подперестановкой длины п бесконечной перестановки 5, если 7г = ¿[г, 1 + 71 — 1] для некоторого г > 0. Комбинаторной сложностью А$(п) бесконечной перестановки 5 называется число ее различных подперестановок длины п. Бесконечной в обе стороны перестановкой будем называть упорядоченную тройку 5 = (2, <$,<), где <в — это некоторый линейный порядок на множестве целых чисел Ъ, а < — естественный порядок на множестве целых чисел.

Пусть ш — произвольное бесконечное непериодическое слово над алфавитом £ = {0,1,..., <7 — 1}. Непериодическому слову и сопоставим действительное число Яш{г) — 0,0^0^1... = ^2к>ои1+к(Г{,к+1'>■ Определим бесконечную перестановку 5Ш, порождаемую словом со, как упорядоченную тройку 5^ — (М, где <цш и < — линейные порядки на множестве натуральных чисел N. При этом определяется следующим образом: тогда и только тогда, когда Пш(г) < 11ш{])- Отметим, что порядок совпадает с лексикографическим порядком на множестве суффиксов ш[г\ слова и (ш[г\ — ■ ■ ■). Пусть и — некоторое подслово бесконечного непериодического слова и. Вхождение (и,т) слова и длины п порождает перестановку 7г, если 77 = + 1, т + п\. Подслово и слова ш порождает перестановку 7г, если существует вхождение (и,т), которое порождает 7г. Множество всех перестановок, порожденных

словом и, обозначим через Ни. Языком перестановок будем называть произвольное множество конечных перестановок. Язык перестановок будем называть факторным, если он с каждым своим элементом содержит все его подперестановки, то есть замкнут относительно операции взятия подперестановки.

Для произвольных функций /, g : N —> N будем писать / = (/ = 0(g)),

если существуют такие константы С\,С-2 > О (С > 0), что С\ ■ д(п) < f(n) < С2 • д(п) (f(n) < С ■ д(п)) для любого и G N. Функцию / : M —> N будем называть кусочно-линейной, если / = 0(га).

В главах 2, 3 и 4 мы впервую очередь концентрируемся на изучении функции комбинаторной сложности бесконечных перестановок. Так как комбинаторная сложность бесконечных перестановок является естественным аналогом комбинаторной сложности бесконечных слов, то приведем небольшой обзор по работам о комбинаторной сложности бесконечных слов. Кроме того, приведем обзор работ по бесконечным перестановкам.

Комбинаторная сложность бесконечного слова — функция неубывающая. Также для нее выполнены тривиальные оценки 1 < си(п) < qn, где q — мощность алфавита £. При этом, далеко не любая неубывающая функция / : N —» N, для которой

1 < f(n) < q71, является функцией комбинаторной сложности для некоторого бесконечного слова над алфавитом мощности q. Обзор известных условий, которым удовлетворяет функция комбинаторной сложности бесконечного слова может быть найден в работе [35]. Полная характеризация функций, являющихся функцией комбинаторной сложности для некоторого бесконечного слова, до сих пор неизвестна.

Заметим, что если и — бесконечное периодическое слово, то его комбинаторная сложность, начиная с некоторого момента, становится константой, то есть существует N такое, что сш(п) = со для некоторой константы с0 при п > N. Классический результат Морса и Хэдлунда 1940 года [55] утверждает, что если и — непериодическое слово, то его комбинаторная сложность — функция строго возрастающая и сш(п) > п + 1. Бесконечное слово и, для которого сы(п) — п+ 1, называется словом Штурма. Таким образом, слова Штурма имеют наименьшую возможную комбинаторную сложность среди непериодических слов. Класс слов Штурма хорошо изучен, в частности существует много эквивалентных определений слов Штурма (см. обзор [13], а также главу

2 монографии [48]). Классическим примером слова Штурма является слово Фибоначчи OJ = lim v?"(0) — неподвижная точка морфизма <¿>(0) = 01, <¿>(1) = 0.

п—юо

Кроме того, специалистами активно изучаются бесконечные слова с кусочно-линейной комбинаторной сложностью [24,29-31,47]. Одним из самых сильных и нетривиальных результатов в данной области является результат Ж. Кассеня [24], утверждающий, что для любого слова и с кусочно-линейной комбинаторной сложностью первые разности его комбинаторной сложности си(п + 1) — сш(п) ограничены некоторой константой. Из последних результатов стоит отметить работу Ж. Леруа [47]. При этом, достаточно удобная характеризация слов с кусочно-линейной комбинаторной сложностью до сих пор не найдена.

Отметим также ряд работ [5,6,12,20], в которых исследовалась функция комбинаторной сложности для различных бесконечных слов и классов бесконечных слов .

Одной из первых работ о комбинаторной сложности неподвижных точек морфизмов является статья А. Эренфойхта, К. П. Ли и Г. Розенберга [33] 1975 года. В этой работе они доказали, что для неподвижной точки морфизма ш верно соотношение сш(п) = 0(п2), то есть, что рост комбинаторной сложности не более чем квадратичный.

В 1984 году Ж.-Ж. Пансьо [56] доказал, что если и — неподвижная точка морфизма, то выполнено одно из следующих условий: сш(п) = 9(1), либо сш(п) = Э(д), либо сш(п) = 0(т? либо сш(п) = <д(п\о£п), либо сш(п) = 0(п2). Кроме того, в

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

Точная формула комбинаторной сложности слова Туэ-Морса была впервые получена в 1989 году С. Брлеком в [19] и независимо А. де Лукой и С. Варриччио в [46]. Позднее этот результат был переоткрыт в работе С. В. Августиновича [1].

В работе [23] Ж. Кассень разработал алгоритм, позволяющий вычислить комбинаторную сложность неподвижных точек бипрефиксных морфизмов. Стоит отметить, что в этой работе впервые был применен ставший уже классическим, метод биспециальпых слов. Позднее в [7] С. В. Августинович и А. Э. Фрид переоткрыли метод биспециальпых слов и получили точную формулу для комбинаторной сложности неподвижных точек бипрефиксных морфизмов. Точная формула для комбинаторной сложности неподвижных точек равноблочных буферных морфизмов была найдена А. Э. Фрид в работе [38]. Из последних результатов в данной области отметим результат К. Клоуды [44], который описал множество всех биспециальных слов для неподвижных точек циркулярных поп-риэЬу морфизмов (зная множество биспециальных слов бесконечного слова, легко найти

его комбинаторную сложность).

Теперь приведем краткий обзор результатов о бесконечных перестановках. Бесконечные перестановки как линейные порядки на множестве натуральных чисел впервые были введены в работе А. Э. Фрид и Д. Г. Фон-дер-Флаасса [39], хотя некоторые проблемы, связанные с ними, исследовались и ранее. К примеру, в статье [28] 1977 года рассматривались перестановки, избегающие длинных монотонных арифметических паттернов. Напомним, что конечное или бесконечное слово и — ■ • • называется ¿~ периодическим, если с^ = для всех г таких, что символ корректно определен. Легко видеть, что число ¿-периодических бесконечных слов над алфавитом мощности q равно qt. В работе [39] А. Э. Фрид и Д. Г. Фон-дер-Флаасс рассмотрели один из возможных аналогов ¿-периодичности для перестановок: конечная или бесконечная перестановка х называется Апериодической, если г <х з тогда и только тогда, когда г + Ь <х ] для всех допустимых г и Оказалось, что в отличии от бесконечных слов, число ¿-периодических бесконечных перестановок счетно для любого £ > 1.

В комбинаторике слов хорошо известна следующая теорема Файна-Вильфа 1965

года:

• Если конечное слово длины не менее p + q — (р, <?) является р-периодическим и ^-периодическим, то оно является (р, д)-периодическим. Кроме того, существует слово длины p + q— (р,ц) — 1, которое р-периодическое и (/-периодическое, но при этом не является (р, ^-периодическим.

В работе А. Э. Фрид [37] был получен аналог этой теоремы для перестановок:

• Пусть конечная перестановка х длины не менее р + q является р-периодической и (/-периодической, причем (р, </) = 1. Тогда х является 1-периодической. Длина

является наименьшей возможной, для которой теорема всегда верна, то есть существует перестановка длины р + <? — 1, которая является р-периодической и (/-периодической, но при этом не является 1-периодической.

В случае, когда р и q не взаимно просты, теорема Файна-Вильфа для перестановок не верпа, однако верпа следующая теорема [37]:

• Пусть перестановка х длины п является р-периодической и д-периодической. Тогда любая ее подперестановка длины не более п — р — q + 2(р, <7) + 1 является (р, (/)-периодической.

Как мы уже отмечали выше, бесконечное слово является периодическим тогда и только тогда, когда его комбинаторная сложность, начиная с некоторого момента, становится константой; кроме того, для любого непериодического слова ш выполнено неравенство сш{п) > п + 1 (слова с комбинаторной сложностью п + 1 называются словами Штурма). Аналогичные вопросы, связанные с комбинаторной сложностью периодических и непериодических бесконечных перестановок, впервые были исследованы в работе А. Э. Фрид и Д. Г. Фон-дер-Флаасса [39].

В этой работе они получили следующие результаты о бесконечных перестановках:

• Бесконечная перестановка является периодической тогда и только тогда, когда функция ее комбинаторной сложности, начиная с некоторого момента, становится константой.

• Для любой неограниченной функции д(п) существует непериодическая бесконечная перестановка 5 такая, что А¿(п) < д(п) для любого достаточно большого п.

Для бесконечных в обе стороны перестановок ситуация немного иная [39]:

• Для любой непериодической и бесконечной в обе стороны перестановки 6 существует сколь угодно большая константа С, такая, что АДп) <п — С для любого

п.

Понятие бесконечной перестановки, порожденной бесконечным словом, впервые было введено в работе М. А. Макарова [50]. В той же работе было доказано, что число перестановок Р(п + 1) длины п + 1, каждая из которых является подперестановкой некоторой бесконечной перестановки, порожденной каким-то бинарным словом, равно

п

Р(р + 1 ) = = 2"(п - с + 0(п2~п/2)).

t=1

где 4>(t) — это число примитивных бинарных слов длины t. Позднее в работе [34] С. Елизалде обобщил этот результат на алфавит произвольной мощности q.

В работе [51] М. А. Макаров вычислил комбинаторную сложность бесконечных перестановок, порожденных хорошо известным семейством слов Штурма.

Комбинаторная сложность бесконечной перестановки, порожденной словом удвоения периода, была найдена М. А. Макаровым в работе [52]. В работе [64] С. Уидмер

нашел формулу для комбинаторной сложности перестановки, порожденной словом Туэ-Морса. Здесь стоит отметить, что из этой формулы следует, что аналог результата Ж. Кассеня о первой разности кусочно-линейной комбинаторной сложности не верен: комбинаторная сложность перестановки Туэ-Морса — кусочно-линейная функция, и при этом ее первая разность — тоже кусочно-линейная функция (а значит и неограниченная). Рассмотрим морфизм (1 такой, что <¿(0) = 00 и с1( 1) = И. В работе [63] С. Уидмер нашел связь между комбинаторной сложностью бесконечных перестановок, порожденных словами и и ¿(и) соответственно, где си — произвольное бинарное равномерно рекуррентное слово. В частности, он нашел верхнюю оценку для комбинаторной сложности перестановки, порожденной а в случае, когда и — слово Штурма или слово Туэ-Морса, нашел точную формулу.

Как мы отмечали выше, линейный порядок — это лексикографический порядок на множестве суффиксов слова си, где 6и — бесконечная перестановка, порожденная словом си. Поэтому изучение бесконечных перестановок, порожденных бесконечными словами, — это, по сути, изучение свойств лексикографического порядка на множестве суффиксов бесконечного слова. Здесь стоит отметить ряд статей [26,27], в которых также изучались свойства лексикографического порядка на множестве сдвигов бесконечного слова: в этих работах исследовались минимальные (с точки зрения лексикографического порядка) слова из орбиты морфических слов. В частности, в работе [27] было доказано, что минимальное слово в орбите неподвижной точки примитивного морфизма также является неподвижной точкой примитивного морфизма.

Также отметим ряд работ, в которых изучались другие типы сложностей бесконечных перестановок: в статье [8] исследовали максимальную шаблонную сложность бесконечных перестановок, а в работах [50] и [3] — арифметическую сложность.

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

Теория паттернов в перестановках — раздел комбинаторики, изучающий конечные перестановки, избегающие подпоследовательностей определенного типа. Основные книги по данной тематике — это монографии [16] и [41]. Первые работы, посвященные изучению паттернов в перестановках, появились еще в середине 18 века. К примеру, в 1749 году Л. Эйлер изучал полиномы + 1)п1к = (Т~7^гт- Полином А„(£), который

теперь называется многочленом Эйлера является производящей функцией числа спусков

в перестановках длины п (An(t) = Z)<7es„ В 1880 году МакМахон нашел произ-

водящую функцию для распределения инверсий в перестановках, что в современной терминологии соответствует вхождениям паттерна 21. Андрэ в 1879 году доказал, что экспоненциальная производящая функция для числа пилообразных (up-down) перестановок равна sec(:r) + tan (я-) (перестановка а = ai... ап называется пилообразной, если

O-i > Й2 < «з > CI4 < ...).

Современная теория паттернов в перестановках берет начало с работ Д. Ротема [58], Д. Г. Роджерса [57] и Д. Кнута [45]. Систематическое же изучение паттернов в перестановках началось со статьи Р. Симиона и Ф. Шмидта [59] 1985 года.

В теории паттернов в перестановках специалисты исследуют в первую очередь следующие вопросы:

1. Для данного паттерна р найти число перестановок sn(p) длины п, избегающих

паттерн р. Либо найти рост последовательности sn{p).

2. Для двух паттернов р и q определить, выполняется ли равенство sn(p) — sn(q).

Если sn(p) = sn(q), то паттерны р и q называются эквивалентными по Вильфу.

Обзначается эта эквивалентность через р q.

Заметим, что для любого паттерна р из множества {132,231,213,312} для последовательности sn(p) выполнено такое же рекуррентное соотношение как и для чисел Каталана Сп. Поэтому sn(p) — Сп для любого патттерна р е {132,231,213,312}. Оказывается, что для паттернов 123 и 321 также выполнено равенство ¿¡„(123) = s„(321) = Сп (см. работу МакМахона [49]). Поэтому возникает естественный вопрос — найти би-екцию между множествами ¡(321) и ¿'„(132). Впервые такая биекция была построена Д. Кнутом в работе [45]. Для этого им была построена биекция между множеством ¿>„(321) и путями Дика (позже эта биекция стала называться соответствием Робинсона-Шенстеда-Кнута), и между множеством ¿>п(132) и путями Дика. Комбинируя эти биек-ции, он построил биекцию между множествами ¿>„(321) и ¿>„(132). Позднее появилось много других интересных биекций между множествами ¿>„(321) и ¿>„(132). Текущий обзор по данной тематике можно найти в работе [25].

Д. Бэкелин в работе [11] доказал, что 1243 2143. 3. Станкова в работах [61] и [62] доказала, что 1342 2413 и 1234 3214. Пусть Л -- {1234,1243. 2143,3214}, В = {1342,2413} и С = {1324}. Тогда с помощью тривиальных биекций получаем, что любой

паттерн длины 4 либо принадлежит одному из множеств А, В и С, либо эквивалентен по Вильфу некоторому паттерну из этих множеств. Точные формулы для в„(1234) и ¿>•„(1342) были получены И. Гесселем и М. Боной в работах [40] и [14] соответственно. Для последовательности йп(1324) точная формула до сих пор неизвестна; рекуррентная же формула для з„(1324) может быть найдена в работе [53] . Также отметим работу М. Боны [15], в которой было доказано, что «„(1342) < «„(1234) < .<>„(1324) для п > б.

В 1980 году Р. Стэнли и Г. Вильф выдвинули следующую гипотезу: для любого классического паттерна р существует константа ср, зависящая только от р такая, что $п(р) < с™. В 2004 году А. Маркус и Г. Тардош [54] доказали гипотезу Фюреди-Хайнала, из которой следует справедливость гипотезы Стэнли-Вильфа.

В последние годы теория паттернов в перестановках активно изучается многими авторами. В частности, рассматриваются различные обобщения классических паттернов — сплошные [34], винкулярные [10], бивинкулярные [17], арифметические [9] и др. В отличие от классических паттернов, для сплошных и винкулярных паттернов гипотеза Стэнли-Вильфа не верна [41]. Из последних обобщений классических паттернов стоит отметить ряд работ по мэш паттернам [18,42,43]. Мэш паттерны были введены в работе [18] с целью выразить различные статитистики на перестановках с помощью их линейной комбинации. В пятой главе данной диссертации мы продолжаем исследования мэш паттернов, рассматривая их определенный подкласс.

Основные результаты диссертации.

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

2. Найдена точная формула для комбинаторной сложности бесконечных перестановок, порожденных неподвижными точками обобщенного морфизма Фибоначчи. Впервые получена точная формула для комбинаторной сложности бесконечных перестановок, порожденных неподвижными точками неравноблочных морфизмов. (Теорема 3.2)

3. Доказано, что аналог известной гипотезы Стэнли-Вильфа для классических паттернов в перестановках не выполняется для любого рамочного паттерна длины более три, и отличного от паттернов 2143, 3142, 2413 и 3412. (Теорема 5.3)

Результаты 1 и 2 получены автором лично. Результат 3 получен в неразделимом соавторстве с С. В. Августиновичем и С. В. Китаевым.

Приведем структуру работы.

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

Во второй главе изучаются бесконечные перестановки, порожденные неподвижными точками морфизмов из класса Q¡. Основной результат состоит в нахождении точной формулы для комбинаторной сложности этих перестановок. Таким образом, впервые получена точная формула для комбинаторной сложности бесконечных перестановок, порожденных неподвижными точками бесконечного семейства морфизмов.

Пусть ri > I2 + 1. Тогда для числа п существует единственная пара чисел к(п) и s(n) такая, что s(n) > 0, к(п) е {/,..., I2' - 1} и k(n)l"{n) < п < (к(п) + Число

п — k(n)ls(п) обозначим через г(п). Заметим, что п = к{п)1ь{-п' + г(гг) и r(n) е Основным результатом второй главы является следующая теорема:

Теорема 2.3. Пусть и — неподвижная точка морфизма р, где б Qt и п > I2 + 1. Тогда комбинаторная сложность перестановки вычисляется следующим образом:

Л(п) = (r(n) - 1)р(к(п) + 2) + - г(п) + 1 )х(к(п) + 1) ~ + 1)

для г(п) > 1 и

A(n) = l^x(Hn) + 1) - а(к(п))

для г(п) = 1.

Все функции р(т), \(т), и а(т) однозначно определяются с помощью се-

мейства множеств Ни, где и — произвольное подслово слова и длины т или т + 1.

В третьей главе изучаются бесконечные перестановки, порожденные неподвижными точками морфизмов вида <¿(0) = OlA <¿>(1) = 0 для к > 2. Основной результат состоит в нахождении точной формулы для комбинаторной сложности этих перестановок. Таким образом, впервые получена точная формула для комбинаторной сложности бесконечных перестановок, порожденных неподвижными точками неравноблочных морфизмов.

Пусть Ai = и д2 _ _ собственные значения матрицы А —

1 1 | (/. l + v/i+4*"^. 1 + уТД /х/ГЙГГ 1 ¡.-)x y/1+Ifr-i

^ I, С^х.у) = -2 Vli4k—1—- и с2(х,у) = —2-^^—i—у~. Рассмотрим

последовательности ая = с\(к+1, к2)Х\+с2(к-{-1, А*2)А2 + 1, Ьа = Сх(2, к)Х\ 1+с2(2, А;)А2 2 + 1 и т, = с1(1,0)А'Г1 +с2(1,0)АГ1.

Основным результатом третьей главы является следующая теорема:

Теорема 3.2. Пусть и — неподвижная тонка морфизма <р, где <¿>(0) = 0]Л <¿>(1) = 0, п > к2 + к + 1, к > 2 и в > 2. Тогда комбинаторная сложность перестановки 5Ш может быть вычислена следующим образом:

1. При а3<п < Ъа+з имеем А(п) = 2п + Л^А^1 + М2ХЬ2+1 + \УЪ где Л/2 = + А;,Р) + с1(1,0)А1 -С1(1,1)А?), М2 = д^-[(с2(1 + А;, /о2) + с2(1,0)А2 - с2(1,1)Л|) а И^ — некоторая константа, зависящая от к;

2. При Ь3+з < гс < а5+1 ижеел* А(п) = 3п - ав+1 + М^Х^2 + М2Х2+2 + И^, где = 1^т(с1(1+/о, А-2)+С1(1,0)А, -с, (1,1)А2), М2 = -^(1+*;, А-2)+с2(1, 0)А2-с2(1, 1)А2) и 1¥2 — некоторая константа, зависящая от к.

Для к = 2 доказывается следующий результат: при аа < п < Ъ3+2 имеем А(r¿) = гс + ад+Чад+Ч^, Где ^ = _1_(С1(1+А;,А:2) + С1(1,0)-С1(1)1)А1), ТУ2 - ¿тЫ1 + /г, А;2) + с2(1, 0) — с2(1,1)А2) и — некоторая константа, зависящая от к\ при Ь,+2 <п< а.,+ 1 имеем Л(п) = 2п — ая+\ Ы\Х\+2 + М2Х2+2 + С}2, где Ых = ¿^(с^ + к, к2) + <^(1, 0) -С] (1,1)Л1), Ы2 — д^зу(с2(1 + к, к2) + с2(1, 0) — с'2(1,1)Ах) и — некоторая константа, зависящая от к.

Список литературы диссертационного исследования кандидат наук Валюженич, Александр Андреевич, 2015 год

Литература

[1] Августинович С. В. Число различных подслов заданной длины в последовательности Морса-Хедлунда // Сибирский журнал исследования операций. 1994. Т. 1, №2. С. 3-7.

[2] Фрид. А. Э. О комбинаторных свойствах D0L слов. Дисс. канд. физ.-мат. наук: 01.01.09. - Новосибирск, 2000. - 104 с.

[3] Макаров М. Антимонотонные перестановки // Сибирские электронные математические известия. 2012. Т. 9. С. 346-359.

[4] Allouche J. -P., Shallit J. Automatic sequences — theory, applications, generalizations. Cambridge University Press, 2003.

[5] Allouche J. -P. The number of factors in a paperfolding sequence // Bull. Austal. Math. Soc. 1992. Vol. 46. p. 23-32.

[6] Arnoux P., Rauzy G. Représentation géométrique de suites de complexité 2n + 1 // Bull. Soc. Math. France. 1991. Vol. 119. p. 199-215.

[7] Avgustinovich S. V., Frid A. E. On bispecial words and subword complexity of D0L sequences // in: Proceedings of SETA'98, DMTCS series. Springer. 1999, p. 191-204.

[8] Avgustinovich S. V., Frid A. E, Kamae T., Salimov P. Infinite permutations of lowest maximal pattern complexity // Theoretical Computer Science. 2011. Vol. 412. p. 29112921.

[9] Avgustinovich S. V., Kitaev S. V., Valyuzhenich A. A. Crucial and bicrucial permutations with respect to arithmetic monotone patterns // Sib. Elektron. Mat. Izv. 2012. Vol. 9. p. 660-671.

[10] Babson E., Steingri'msson E. Generalized permutation patterns and a classification of the Mahonian statistics // Sém. Lothar. Combin. 2000. Vol. 44. Art. B44b, 18pp. (electronic).

[11] Backelin J., West J., Xin G. Wilf-equivalence for singleton classes // Advances in Applied Mathematics. 2007. Vol. 38, no. 2. p. 133-148.

[12] Baryshnikov Yu. Complexity of trajectories in rectangular billiards // Commun. Math. Phys. 1995. Vol. 174. p. 43-56.

[13] Berstel J. Sturmian and episturmian words (a survey of some recent results). // In S. Bozapalidis and G. Rahonis, editors, CAI 2007, Vol. 4728 of Lecture Notes in Computer Science, Springer-Verlag. 2007. p. 23-47.

[14] Bona M. Exact enumeration of 1342-avoiding permutations: a close link with labeled trees and planar maps // J. Combin. Theory Ser. A. 1997. Vol. 80. no. 2. p. 257-272.

[15] Bona M. Exact and asymptotic enumeration of permutations with subsequence conditions. PhD thesis, Massachusetts Institute of Technology, 1997.

[16] Bona M. Combinatorics of permutations. Discrete Mathematics and its Applications (Boca Raton). Chapman Hall/CRC, Boca Raton, FL, 2004. With a foreword by Richard Stanley.

[17] Bousquet-Melou M., Claesson A., Dukes M., Kitaev S. (2 + 2)-free posets, ascent sequences and pattern avoiding permutations // J. Combin. Theory Ser. A. 2010. Vol. 117, no. 7. p. 884-909.

[18] Branden P., Claesson A. Mesh patterns and the expansion of permutation statistics as sums of permutation patterns // Electronic Journal of Combinatorics. 2011. Vol. 18, no. 2. #P5, 14pp.

[19] Brlek S. Enumeration of factors in the Thue-Morse word // Discrete Applied Mathematics. 1989. Vol. 24. p. 83-96.

[20] Cassaigne J., Karhumaki J. Toeplitz words, generalized periodicity and periodically iterated morphisms // European Journal of Combinatorics. 1997. Vol. 18. p. 497-510.

[21] Cassaigne J., Nicolas F. Factor Complexity in Combinatorics, Automata and Number Theory, V. Berthe and M. Rigo (eds.), Cambridge Unicersity Press, Cambridge, 2010.

Cassaigne J. An algorithm to test if a given circular HDOL-language avoids a pattern // IFIP World Computer Congress'94. Elsevier (North-Holland). 1994. Vol 1. p. 459464.

[23] Cassaigne J. Complexité et facteurs spéciaux // Bull. Belg. Math. Soc. 1997. Vol. 4. p. 67-88.

[24] Cassaigne J. Special factors of sequences with linear subword complexity // Developments of Language Theory II. Singapore: World Sci.Publishing. 1996. p. 25-34.

[25] Claesson A., Kitaev S. Classification of bijections between 321- and 132- avoiding permutations // Sém. Lothar. Combin. 2008. Vol. 60. Art. B60d, 30.

[26] Currie J. Lexicographically least words in the orbit closure of the Rudin-Shapiro word // Theoretical Computer Science. 2011. Vol. 412. p. 4742-4746.

[27] Currie J., Rampersad N., Saari K., Zamboni L. Extremal words in morphic subshifts // Discrete Mathematics. 2014. Vol. 322. 53-60.

[28] Davis J., Entringer R., Graham R., Simmons G. On permutations containing no long arithmetic progressions // Acta Arithmetica. 1977. Vol. 34. p. 81-90.

[29] Durand F. A characterization of substitutive sequences using return words // Discrete Mathematics. 1998. Vol. 179. p. 89-101.

[30] Durand F. Linearly recurrent subshifts have a finite number of non-periodic subshift factors // Ergodic Theory and Dynamical Systems. 2000. Vol. 20. p. 1061-1078.

[31] Durand F., Leroy J., Richomme G. Do the Properties of an S-adic Representation Determine Factor Complexity // Journal of Integer Sequences. 2013. Vol. 16, no. 2:Art. 13.2.6, 30.

[32] Elizalde S. The number of permutations realized by a shift // SIAM J. Discrete Math. 2009. Vol. 23. p. 765-786.

[33] Ehrenfeucht A., Lee K. P., Rozenberg G. Subword complexities of various classes of deterministic developmental languages without interactions // Theoretical Computer Science. 1975. Vol. 1. p. 59-75.

[34] Elizalde S., Noy M.. Consecutive patterns in permutations. Advances in Applied Mathematics. 2003. Vol. 30, no. (1-2). p. 110-125.

[35] Ferenczi S. Complexity of sequences and dynamical systems // Discrete Math. 1999, Vol. 206, p. 145-154.

[36] Frid A. Infinite permutations vs. infinite words // Eletronic Proceedings in Theoretical Computer Science. 2011. Vol. 63. p. 13-19.

[37] Frid A. E. Fine and Wilf's theorem for permutations // Siberian Electronic Mathematical Reports. 2012. Vol. 9. p. 377-381.

[38] Frid A. E. On uniform D0L words // STACS'98, Lect. Notes Comp. Sci. 1998. Vol. 1373. p. 544-554.

[39] Fon-Der-Flaass D. G. and Frid A. E. On periodicity and low complexity of infinite permutations // European Journal of Combinatorics. 2007. Vol. 28, no. 8. p. 21062114.

[40] Gessel I. M. Symmetric functions and P-recursiveness // J. Combin. Theory Ser. A. 1990. Vol. 53, no. 2. p. 257-285.

[41] Kitaev S. Patterns in permutations and words, Springer-Verlag, 2011.

[42] Kitaev S., Liese J. Harmonic numbers, Catalan triangle and mesh patterns // Discrete Mathematics. 2013. Vol. 313. p. 1515-1531.

[43] Kitaev S., Remmel J. Quadrant marked mesh patterns // Journal of Integer Sequences. 2012. Vol. 15. Article 12.4.7, 29pp.

[44] Klouda K. Bispecial factors in circular non-pushy D0L languages // Theoretical Computer Science. 2012. Vol. 445. p. 63-74.

[45] Knuth D. E. The art of computer programming. Volume 1, Fundamental Algorithms. Addison-Wesley, Reading, second edition, 1975. Addison-Wesley Series in Computer Science and Information Processing.

[46] de Luca A. and Varricchio S. Some combinatorial properties of the Thue-Morse sequence and a problem in semigroups // Theoretical Computer Science. 1989. Vol. 63. p. 333-348.

[47] Leroy J. An S-adic characterization of minimal subshifts with first difference of complexity 1 < p(n + l) — p(n) < 2 // Discrete Mathematics and Theoretical Computer Science. 2014. Vol. 16, no. 1. p. 233-286.

[48] Lothaire, M. Algebraic Combinatorics on Words. // V. 90 of Encyclopedia of Mathematics and Its Applications. Cambridge University Press, 2002.

[49] MacMahon P. A. Combinatory analysis. Vol. I, II (bound in one volume). Dover Phoenix Editions. Dover, Mineola, 2004. Reprint of An introduction to combinatory analysis (1920) and Combinatory analysis. Vol. I, II (1915,1916).

[50] Makarov M. A. On permutations generated by infinite binary words // Sib. Elektron. Mat. Izv. 2006. Vol. 3. p. 304-311 (in Russian).

[51] Makarov M. A. On the permutations generated by the Sturmian words // Sib. Math. J. 2009. Vol. 50, no. 4. p. 674-680.

[52] Makarov M. A. On the infinite permutation generated by the period doubling word // European Journal of Combinatorics. 2010. Vol. 31, no. 1. p. 368-378.

[53] Marinov D., Radoicic R.. Counting 1324-avoiding permutations // Electronic Journal of Combinatorics, 9(2):Research paper 13, 9 pp. (electronic), 2002/03.

[54] Marcus A., Tardos G. Excluded permutation matrices and the Stanley-Wilf conjecture // J. Combin. Theory Ser. A. 2004. Vol. 107, no. 1, 153-160.

[55] Morse M., Hedlund G. A. Symbolic Dynamics II: Sturmian Trajectories // Amer. J. Math. 1940. Vol. 61. p. 1-42.

[56] Pansiot J.-J. Complexité des facteurs des mots infinis enegendrés par morphismes itérés // in ICALP '84, Lecture Notes in Computer Science 172, Springer-Verlag (1984), p. 380-389.

[57] Rogers D. G. Ascending sequences in permutations // Discrete Mathematics. 1978. Vol. 22, no. 1. p. 35-40.

[58] Rotem D. On a correspondence between binary trees and a certain type of permutation // Information Processing Letters. 1975/76. Vol. 4, no. 3. p. 58-61.

[59] Simion R., Schmidt F. W. Restricted permutations // European Journal of Combinatorics. 1985. Vol. 6, no. 4. p. 383-406.

[60] N. J. A. Sloane, The on-line encyclopedia of integer sequences, published electronically at http : //www. research. att. com/~nj as/sequences/.

[61] Stankova Z. E. Forbidden subsequences // Discrete Mathematics. 1994. Vol. 132, no. (1-3). p. 291-316.

[62] Stankova Z. E. Classification of forbidden subsequences of length 4 // European Journal of Combinatorics. 1996. Vol. 17, no. 5. p. 501-517.

[63] Widmer S. Permutation Complexity of the Thue-Morse Word // Advances in Applied Mathematics. 2011. Vol. 47, no. 2. p. 309-329.

[64] Widmer S. Permutation complexity related to the letter doubling map // Electronic Proceedings in Theoretical Computer Science. 2011. Vol. 63. pp. 265-276.

Публикации автора по теме диссертации

[65] Валюженич А. О перестановочной сложности неподвижных точек некоторых нерав-ноблочных бинарных морфизмов // Сибирские электронные математические известия. 2015. Т. 12. С. 64-79.

[66] Avgustinovich S., Kitaev S., Valyuzhenich A. Avoidance of boxed mesh patterns on permutations // Discrete Applied Mathematics. 2013. Vol. 161. p. 43-51.

[67] Valyuzhenich A. On permutation complexity of fixed points of some uniform binary morphisms // Discrete Mathematics and Theoretical Computer Science. 2014. Vol.16, no. 3. p. 95-128.

[68] Valyuzhenich A. Permutation complexity of the fixed points of some uniform binary morphisms // Electronic Proceedings in Theoretical Computer Science. 2011. Vol. 63. p. 257-264.

[69] Valyuzhenich A. Permutation complexity of the fixed points of comparable morphisms // Proc. 2nd Russian Finnish Symposium on Discrete Mathematics. 2012. Vol. 17 of TUCS Lecture Notes. Turku, p. 184-186.

[70] Valyuzhenich A. On factor complexity of infinite permutations // Local Proc. 9th International Conference in Combinatorics on Words. 2013. Vol. 20 of TUCS Lecture Notes. Turku, p. 97-108.