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

На правах рукописи

В ал южен и ч Александр Андреевич

КОМБИНАТОРНЫЕ СВОЙСТВА ФАКТОРНЫХ ЯЗЫКОВ

ПЕРЕСТАНОВОК

01.01.09 — дискретная математика и математическая кибернетика

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Новосибирск-2015

Работа выполнена в Федеральном государственном автономном образовательном учреждении высшего образования «Новосибирском национальном исследовательском государственном университете».

Научный руководитель:

доктор физико-математических наук

Кротов Денис Станиславович.

Официальные оппоненты: Шалагинов Леонид Викторович

кандидат физико-математических наук, Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Челябинский государственный университет», доцент кафедры компьютерной безопасности и прикладной алгебры;

Шур Арсений Михайлович

доктор физико-математических наук, профессор, Федеральное государственное автономное образовательное учреждение высшего профессионального образования «Уральский федеральный университет имени первого Президента России Б. Н. Ельцина», профессор кафедры алгебры и дискретной математики.

Ведущая организация: Федеральное государственное бюджетное образовательное учреждение высшего образования «Московский государственный университет имени М. В. Ломоносова».

Защита состоится 20 мая 2015 года в 17 часов 30 минут на заседании диссертационного совета Д 003.015.01 при Федеральном государственном бюджетном учреждении науки Институте математики им. С. Л. Соболева Сибирского отделения Российской академии наук по адресу: 630090, г. Новосибирск, пр. Академика Коптюга 4.

С диссертацией можно ознакомиться в библиотеке и на сайте Федерального государственного бюджетного учреждения науки Института математики им. С. Л. Соболева Сибирского отделения Российской академии наук, http://math.n8C.ru.

Автореферат разослан «15» апреля 2015 I

Ученый секретарь диссертационного совета доктор физико-математических наук

российская

ГОСУДАМПиЫШАЯ

БИБЛИОТЕКА

2015_

----Общая характеристика работы

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

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

Бесконечным словом над алфавитом Е называется бесконечная вправо последовательность и> = Ш\Ш2Шз ... символов алфавита Е. Конкатенацией конечного слова и и слова v (конечного или бесконечного) называется слово х = Х1Х2... такое, что хi = щ для г < |и| и хг = г;г_|и| для г > |и|. Конкатенация слов и и v обозначается через иу. Слово V называется подсловом конечного или бесконечного слова и, если существуют слова вх и яг такие, что и = в^яг. Если при этом = е ($2 = £), то г; называется префиксом (суффиксом) слова и. Вхождением слова и € Е* в слово ш называется пара (и, т) такая, что и = шт_|_1Шт+2 • • • ^>т+п- Комбинаторной сложностью сш(п) бесконечного слова со называется число его различных подслов длины п. Бесконечное слово вида со = ьт ... обозначается через . Бесконечное слово оо называется периодическим, если и> = иьш для некоторых конечных слов ииу. Бесконечное слово и называется непериодическим, если его нельзя представить в виде со = иьш для некоторых конечных слов ип v. Языком называется произвольное подмножество Е*. Язык называется факторным, если он с каждым своим элементом содержит все его подслова, то есть замкнут относительно операции взятия подслова.

Нетрудно видеть, что язык подслов F(oj) произвольного бесконечного слова ш является факторным.

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

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

Свойства.

1. Если у?(0) = OuOx для некоторого слова х, то Oul не является подсловом </з(0) и <р(1), и Огг не является суффиксом у?(0) и <р(1).

2. Если </?(1) = lull для некоторого слова х, то 1и0 не является подсловом <¿>(0) и у(1), и 1 и не является суффиксом уз(0) и </>(!)•

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

Конечной перестановкой х длины п будем называть упорядоченную тройку х — ({1,..., п}, <х, <), где <х — это некоторый линейный порядок на множестве {1,2,... ,п}, а < — естественный порядок на множестве {1,2,...,п}. В дальнейшем будем писать х = xix2...xn, если {xi,x2, ...,!„} — это некоторая перестановка чисел из множества {1,2, ...,п} такая, что xt < Xj, если и только если i <х j. Рассмотрим произвольную перестановку тг = П\ТГ2 ■ ■ ■ кп длины п. Классическим паттерном (или просто паттерном) называется перестановка х длины к. Подпоследовательность тг11тг12 ... 7ги называется вхождением классического паттерна х = ххх2 ... zfc в перестановку 7г, если 7гг> < 7г1( тогда и только тогда, когда х3 < xt для всех 1 < s < t < к. Будем говорить, что перестановка 7Г избегает паттерн х, если она не содержит

вхождений этого паттерна. Множество перестановок длины п, избегав ющих паттерна х, обозначим через Sn(x); мощность множества Sn(x) обозначим через sn(х).

Бесконечной перестановкой будем называть упорядоченную тройку S = (N, <г, <), где <î — это некоторый линейный порядок на множестве натуральных чисел N, а < — естественный порядок на множестве натуральных чисел. Пусть (5 — бесконечная перестановка. Конечную перестановку х длины п такую, что i <х j тогда и только тогда, когда т + г — 1 <s m + j — 1 обозначим через S\m,m + n — 1]. Конечная перестав новка 7г длины п называется подперестановкой длины п бесконечной перестановки 6, если ж = ¿[г, г + п — 1] для некоторого i > 0. Комбинаторной сложностью Л¿(п) бесконечной перестановки <5 называется число ее различных подперестановок длины п.

Пусть ui — произвольное бесконечное непериодическое слово над алфавитом £ = {0,1,...,g — 1}. Непериодическому слову ш сопоставим действительное число Лш(г) = 0,ojjWi+1 ... = J2k>o Опре-

делим бесконечную перестановку 6Ш, порождаемую словом ш, как упорядоченную тройку 6Ш = (N, <), где и < — линейные порядки на множестве натуральных чисел N. При этом определяется следующим образом: i<s„j тогда и только тогда, когда < R^U)- Отметим, что порядок совпадает с лексикографическим порядком на множестве суффиксов ui[i\ слова ш (и[г] = шги>{+1 ...). Пусть и — некоторое подслово бесконечного непериодического слова ш. Вхождение (и, тп) слова и длины п порождает перестановку 7Г, если 7Г = 5ш[тп + 1, m + п]. Подслово и слова и> порождает перестановку 7г, если существует вхождение (и, тп), которое порождает 7Г. Множество всех перестановок, порожденных словом и. обозначим через Ни. Языком перестановок будем называть произвольное множество конечных перестановок. Язык перестановок будем называть факторным, если он с каждым своим элементом содержит все его подперестановки, то есть замкнут относительно операции взятия подперестановки.

Для произвольных функций /, g : N —> N будем писать / = 9 (g) (/ = О((/)), если существуют такие константы С\,С2 > 0 (С > 0), что Ci-gin) < f{n) < С2 ■ gin) if in) < С ■ gin)) для любого n € N. Функцию / : N —» N будем называть кусочно-линейной, если / = В in).

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

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

Комбинаторная сложность бесконечного слова — функция неубывающая. Также для нее выполнены тривиальные оценки 1 < сш(п) < где ц — мощность алфавита При этом, далеко не любая неубывающая функция / : N —М, для которой 1 < /(п) < д™, является функцией комбинаторной сложности для некоторого бесконечного слова над алфавитом мощности д. Обзор известных условий, которым удовлетворяет функция комбинаторной сложности бесконечного слова может быть найден в работе [30]. Полная характеризация функций, являющихся функцией комбинаторной сложности для некоторого бесконечного слова, до сих пор неизвестна.

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

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

Одной из первых работ о комбинаторной сложности неподвижных точек морфизмов является статья А. Эренфойхта, К. П. Ли и Г. Розен-

берга [28] 1975 года. В этой работе они доказали, что для неподвижной точки морфизма и> верно соотношение сш(п) = 0(п2), то есть, что рост комбинаторной сложности не более чем квадратичный.

В 1984 году Ж.-Ж. Пансьо [50] доказал, что если ш — неподвижная точка морфизма, то выполнено одно из следующих условий: сш(п) = ©(1), либо (^(п) = &(п). либо сш(п) = Q(nloglogn), либо Cjj(ti) = ©(nlogn), либо сш(п) = ©(п2). Кроме того, в той же работе приведен алгоритм, позволяющий по морфизму определить, к какому из пяти классов принадлежит комбинаторная сложность его неподвижной точки.

Точная формула комбинаторной сложности слова Туэ-Морса (неподвижной точки морфизма <,£>(0) = 01. <^(1) = 10) была впервые получена в 1989 году С. Брлеком в [16] и независимо А. де Лукой и С. Варриччио в [41]. Позднее этот результат был переоткрыт в работе С. В. Августи-новича [1].

В работе [19] Ж. Кассень разработал алгоритм, позволяющий вычислить комбинаторную сложность неподвижных точек бипрефиксных морфизмов. Стоит отметить, что в этой работе впервые был применен ставший уже классическим, метод биспециальных слов. Позднее в [6] С. В. Августинович и А. Э. Фрид переоткрыли метод биспециальных слов и получили точную формулу для комбинаторной сложности неподвижных точек бипрефиксных морфизмов. Точная формула для комбинат торной сложности неподвижных точек равноблочных буферных морфизмов была найдена А. Э. Фрид в работе [33]. Из последних результат тов в данной области отметим результат К. Клоуды [39], который описал множество всех биспециальных слов для неподвижных точек циркулярных non-pushy морфизмов (зная множество биспециальных слов бесконечного слова, легко найти его комбинаторную сложность).

Теперь приведем краткий обзор результатов о бесконечных перестановках. Бесконечные перестановки как линейные порядки на множестве натуральных чисел впервые были введены в работе А. Э. Фрид и Д. Г. Фон-дер-Флаасса [34], хотя некоторые проблемы, связанные с ними, исследовались и ранее. К примеру, в статье [24] 1977 года рассматривались перестановки, избегающие длинных монотонных арифметических паттернов. Напомним, что конечное или бесконечное слово w = u>iW2 .. ■ наг зывается t-периодическим, если Ш; = ojJ+i для всех г таких, что символ (jt+t корректно определен. В работе [34] А. Э. Фрид и Д. Г. Фон-дер-Флаасс рассмотрели один из возможных аналогов i-периодичности для

перестановок: конечная или бесконечная перестановка х называется I периодической, если г <х j тогда и только тогда, когда i + t <х j + t для всех допустимых 11/13.

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

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

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

Понятие бесконечной перестановки, порожденной бесконечным словом, впервые было введено в работе М. А. Макарова [45]. В той же работе была получена формула для числа перестановок длины п, каждая из которых является подперестановкой некоторой бесконечной перестановки, порожденной каким-то бинарным словом. Позднее в работе [29] С. Елизалде обобщил этот результат на алфавит произвольной мощности </. В работе [46] М. А. Макаров вычислил комбинаторную сложность бесконечных перестановок, порожденных хорошо известным семейством слов Штурма. Комбинаторная сложность бесконечной перестановки, порожденной словом удвоения периода, была найдена М. А. Макаровым в работе [47|. В работе [58| С. Уидмер нашел формулу для комбинаторной сложности перестановки, порожденной словом Туэ-Морса. Здесь стоит отметить, что из этой формулы следует, что аналог результата Ж. Кассеня о первой разности кусочно-линейной комбинаторной сложности не верен: комбинаторная сложность перестановки Туэ-Морса — кусочно-линейная функция, и при этом ее первая разность — тоже кусочно-линейная функция (а значит и неограниченная). Рассмотрим морфизм (1 такой, что ¿(0) = 00 и ¿¿(1) = 11. В работе [57] С. Уидмер нашел связь между комбинаторной сложностью бесконечных

перестановок, порожденных словами и> и d(ui) соответственно, где ш — произвольное бинарное равномерно рекуррентное слово. Также отметим, что понятие комбинаторной сложности бесконечной перестановки, порожденной бесконечным словом (permutation complexity), было независимо введено в работе [5].

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

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

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

Теория паттернов в перестановках — раздел комбинаторики, изучающий конечные перестановки, избегающие подпоследовательностей определенного типа. Основные книги по данной тематике — это монографии [13] и [36]. Современная теория паттернов в перестановках берет начало с работ Д. Ротема [52], Д. Г. Роджерса [51] и Д. Кнута [40]. Систематическое же изучение паттернов в перестановках началось со статьи Р. Симиоиа и Ф. Шмидта [53] 1985 года.

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

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

2. Для двух паттернов р и q определить, выполняется ли равенство sn(p) = sn(q). Если sn(p) — sn(q), то паттерны р и q называются эквивалентными по Вильфу. Обзначается эта эквивалентность через р ~w q-

Хорошо известно, что для любого классического паттерна р длины 3 Ап(р) = Сп, где Сп — последовательность чисел Каталана (см. работу МакМахона [44]). Поэтому возникает естественный вопрос — найти би-екцию между множествами 5П(321) и 5П(132). Впервые такая биекция была построена Д. Кнутом в работе [40]. Для этого им была построена биекция между множеством ¿'„(321) и путями Дика (позже эта биекция стала называться соответствием Робинсона-Шенстеда-Кнута), и между множеством 5П(132) и путями Дика. Комбинируя эти биекции, он построил биекцию между множествами 5„(321) и 5П(132). Позднее появилось много других интересных биекций между множествами £п(321) и 5„(132). Текущий обзор по данной тематике можно найти в работе [21].

Д. Бэкелин в работе [10] доказал, что 1243 ~ц/ 2143. 3. Станкова в работах [55] и [56] доказала, что 1342 2413 и 1234 3214. Пусть А = {1234,1243,2143,3214}, В = {1342,2413} и С = {1324}. Тогда с помощью тривиальных биекций получаем, что любой паттерн длины 4 либо принадлежит одному из множеств А, В и С, либо эквивалентен по Вильфу некоторому паттерну из этих множеств. Точные формулы для вп(1234) и я„(1342) были получены И. Гесселем и М. Боной в работах [35] и [12] соответственно. Для последовательности й„(1324) точная формула до сих пор неизвестна.

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

В последние годы теория паттернов в перестановках активно изучав ется многими авторами. В частности, рассматриваются различные обобщения классических паттернов — сплошные [29], винкулярные [9], би-винкулярные [14|, арифметические [8| и др. В отличие от классических паттернов, для сплошных и винкулярных паттернов гипотеза Стэнли-Вильфа не верна [36]. Из последних обобщений классических паттернов стоит отметить ряд работ по мэш паттернам [15,37,38]. Мэш паттерны были введены в работе [15] с целью выразить различные статитистики на перестановках с помощью их линейной комбинации. В пятой главе данной диссертации мы продолжаем исследования мэш паттернов, рассматривая их определенный подкласс.

Целью данной работы является исследование языков подперестано-

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

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

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

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

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

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

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

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

Апробация работы. Результаты диссертации докладывались на Международной молодежной школе-конференции "Современные проблемы математики и ее приложений "(г. Екатеринбург, 2012, 2013), на Международной конференции "Современные проблемы математики,

информатики и биоинформатики посвященной 100-летию со дня рождения членагкорреспондента АН СССР Алексея Андреевича Ляпунова (г. Новосибирск, 2011), на Международной конференции по комбинаторике слов WORDS 2011 (г. Прага, 2011), на втором Международном Русско-Финском симпозиуме по дискретной математике RuFiDiM 2012 (г. Турку, 2012), на Международной конференции по комбинаторике слов WORDS 2013 (г. Турку, 2013).

Публикации. Результаты автора по теме диссертации опубликовав ны в шести работах [59-64], из них три статьи опубликованы в журналах из списка ВАК [59-61], три — в тезисах и трудах международных конференций [62-64]. Результаты работы [60] получены в неразделимом соавторстве с С. В. Августиновичем и С. В. Китаевым.

Структура и объем диссертации. Диссертация состоит из введения, 5 глав и списка литературы. Объем диссертации составляет 134 страницы. Список литературы содержит 70 наименований.

Содержание диссертации

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

Во введении обосновывается актуальность темы исследования, освещается степень ее разработки; изложены цели, методы исследоваг ния и основные результаты диссертации; отражены научная новизна и значимость работы и данные об апробации. Также приведены сведения о публикации результатов диссертации.

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

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

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

Пусть п > I2 + 1. Тогда для числа п существует единственная пара чисел к(п) и я(п) такая, что в(п) > 0, к(п) е {/, ...,12 - 1} и к(п)1з(-п' < п < (к(п) + 1 )1"(п\ Число п — /с(7г)Р(п) обозначим через г(п). Заметим, что п = к(п)1"(п) +г(п) и г(тг) £ Основным результатом второй

главы является следующая теорема:

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

А(п) = (г(п) - 1)ц(к(п) + 2) + (1- г(п) + 1)х(Л(п) + 1) - £(*(") + 1)

для г(п) = 1.

Все функции ^(ш), х(т)> Р(т) и а(т) однозначно определяются с помощью семейства множеств Ни, где и — произвольное подслово слова Ш ДЛИНЫ ТП или тп + 1.

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

Пусть А1 = 1+у/1+4к и д2 = 1-у/1+4к — собственные значения мат-

1, к2)Х\ + с2(к + 1,к2)\°2 + 1, Ь. = с1(2,к)А31~1 + с2(2,к)А^1 + 1 и

=с1(1,0)АГ1 +са(1,0)А5"1.

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

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

для г(п) > 1 и

А(п) = ¿*(п)х(*:(п) + 1) - а(к(п))

рмтткт

—. Рассмотрим последовательности ав = с\(к +

1. При а3 <п < Ь3+з имеем А(гс) = 2п + MiA'+1 + M2\\+l + Wx, где Mi = x^ry(ci(l + к, к2) -h ci(1,0)Aj - ci(l, l)Af), M2 = j^t(c2(1 + к,к2) + с2(1,0)А2 - С2(1,1)А2) и W\ — некоторая константа, зависящая от к;

2. При Ь3+з < п < as+i имеем A(n) = Зп — ал+1 + MiX[+2 + M2y2+2 + W2, где Ml = i^_(c1(1+A;1/C2)+C1(1,0)AI - Cl(l, 1)А?), M2 = д^ту(с2(1 + к,к2) + с2(1,0)А2 -С2(1, 1)Аз) и W2 — некоторая константа, зависящая от к.

Для к = 2 доказывается следующий результат: при а3 < п < Ья+2 имеем A(n) = п + Nr\\+l + JV2A*+1 4- Qu где = j^Ml + к, к2) + ci(l,0) - Cl(l, l)Aj), N2 = д^гт(с2(1 + к, к2) + 02(1,0)'- с2(1,1)Л2) и Qx

— некоторая константа, зависящая от к; при b3+2 < п < а3+1 имеем A (n) = 2n - as+i + MAÎ+a + N2\32+2 + Q2, где Ni = j^Ml + к, к2) + ci(l,0)-c1(l,l)A1), N2 = ^гт(с2(1 + k,k2) +^(1,0)-c2(l, l)Ai) и Q2

— некоторая константа, зависящая от к.

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

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

В пятой главе вводится понятие рамочного мэш паттерна и изучаются языки конечных перестановок, избегающих эти паттерны. Мэш паттерном называется пара р = (л-, R), где 7г — некоторая перестановка длины к и R G [0, к] х [0, к]. Пусть 7Г = 7Ti7r2 ... 7ГП — произвольная перестановка длины п. Множество точек плоскости G(7г) = {(г,7Г*)|г = 1,..., п} будем называть диаграммой перестановки 7Г. Вхождением мэш паттерна р в перестановку г называется подмножество точек и множества G(t) такое, что существуют две сохраняющие порядок инъекции а,0 : [1, к] —> [1,п] такие, что выполнены два следующих условия:

1. Ш = {(а(г),^)):(г,ЯеС(тг)}.

2. Определим множество Д^ = [а(г) + 1, а(г + 1) — 1] х [/?(.?) + 1, /3(+ 1) - 1] для г,^ е [О,*], где а(0) = /3(0) = 0 и а(к + 1) = /3(к + 1) = п + 1. Тогда если (г,.?) € Д, то Д^ П С(т) = 0.

Мэш паттерн р = (х, Д), для которого Я = [1, к — 1] х [1, А; — 1], будем называть рамочным мэш паттерном или просто рамочным паттерном. Обозначим рамочный паттерн р = (х, Д) через [х).

Доказывается, что аналог известной гипотезы Стэнли—Вильфа не выполняется для любого рамочного паттерна длины более три, и отличного от паттернов 121431,131421, |2413| и 134121. Также доказывается, что аналог гипотезы Стэнли-Вильфа не выполняется для паттернов 11231 и |3211:

Теорема 5.3. Пусть [р] — произвольный рамочный паттерн длины к > 4, который не принадлежит множеству {[2143].[31421,[24131 [3412р. Тогда я„([рр > ([£])!.

Кроме того, в пятой главе найдены производяшиие функции для

последовательностей $п(а,|123[), где а — произвольный классический

паттерн длины три. В частности, доказана следующая теорема:

Теорема 5.5. Последовательность (яп(231,| 123 |))п>о с точностью до сдвига совпадает с последовательностью обобщенных чисел Каталана (см. последовательность Л004148 в ОЕ1Б ¡54]). Производящая функция последовательности зп(231,Г123|) равна

1-х -х2 - \/1 - 2х - х2 - 2х3 + 2^3

4

Благодарности

Автор выражает благодарность своему научному руководителю Денису Станиславовичу Кротову за неоценимую помощь во время работы над диссертацией. Автор благодарит А. Э. Фрид, С. В. Августиновича и С. В. Китаева за интересные задачи и полезные обсуждения. Автор признателен всем сотрудникам лаборатории совершенных комбинаторных структур ИМ СО РАН за творческую атмосферу и полученные знания в процессе обучения в аспирантуре. Также автор благодарит своего брата В. А. Валюженича, взявшего на себя труд прочитать первоначальный вариант черновика диссертации.

Литература

[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] Amigó J. M. Permutation complexity in dynamical systems. Springer Series in Synergetics, Springer-Verlag, Berlin, 2010.

[6] 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.

[7] Avgustinovich S. V., Prid A. E, Kamae Т., Salimov P. Infinite permutations of lowest maximal pattern complexity // Theoretical Computer Science. 2011. Vol. 412. p. 2911-2921.

[8] 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.

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

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

[11] 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.

[12] B<5na 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.

[13] 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.

[14] Bousquet-Mélou 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.

[15] Bràndén 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.

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

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

[18] 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. 459-464.

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

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

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

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

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

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

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

[26] 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.

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

[28] 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.

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

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

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

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

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

[34] 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. 2106-2114.

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

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

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

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

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

[40] 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.

[41] 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.

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

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

[44] 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).

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

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

[47] 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.

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

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

[50] 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.

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

[52] 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.

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

[54] N. J. A. Sloane, The on-line encyclopedia of integer sequences, published electronically at http: /www.research.att.com/"njas/sequences/.

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

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

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

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

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

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

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

[61] 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.

Публикации в тезисах и трудах конференций

[62] 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.

[63] 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.

[64] 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.

Подписано в печать 20.03.2015 Формат 60x84 1\16 Усл. печ. л. 1,5 Объем24стр. Тираж 100 экз. Заказ №43 Отпечатано Омега Принт 630090, г. Новосибирск, пр. Ак.Лаврентьева.б email: omegap@yandex.ru

15 -- 4 4 7 5

2010016357

2010016357