Возникающее избегание последовательных паттернов

Основная информация

• ID статьи: 2511.02442
• Название: Emerging consecutive pattern avoidance
• Авторы: Nathanaël Hassler, Sergey Kirgizov (Université Bourgogne Europe)
• Классификация: math.CO (комбинаторика), cs.DM (дискретная математика)
• Дата публикации: 5 ноября 2025 г. (препринт arXiv)
• Ссылка на статью: https://arxiv.org/abs/2511.02442

Аннотация

В статье исследуется проблема асимптотической популярности (asymptotic popularity), то есть предельная вероятность нахождения заданного последовательного паттерна в случайной позиции случайной перестановки среди 18 классов перестановок, избегающих по крайней мере двух последовательных паттернов длины 3. Показано, что для 10 классов перестановок эта популярность может быть непосредственно выведена из структуры перестановок. Путём комбинирования аналитических и биективных методов авторы детально исследуют два более сложных случая. Проблема остаётся открытой для 5 классов перестановок.

Исследовательский контекст и мотивация

Исследуемая проблема

Статья изучает асимптотическое поведение избегания последовательных паттернов (consecutive pattern avoidance) в перестановках. Конкретно:

• Дан класс перестановок, избегающих определённые последовательные паттерны длины 3
• Исследуется асимптотическая популярность других неизбегаемых паттернов в этих классах
• Асимптотическая популярность определяется как предел вероятности нахождения конкретного паттерна p в случайной позиции случайной перестановки размера n при n → ∞

Значимость проблемы

1. Теоретическое значение: Раскрывает "замечательный факт" — некоторые паттерны асимптотически исчезают (вероятность стремится к 0)
2. Расширение классических результатов: Расширяет исследования Bóna и Homberger о классических (непоследовательных) паттернах на последовательные паттерны
3. Связь различных комбинаторных объектов: Через биекции устанавливает связь между перестановками и другими комбинаторными структурами (пути Дика, инволюции)

Ограничения существующих методов

• Работы Bóna и Homberger применимы только к классическим (непоследовательным) паттернам
• Kitaev и Mansour дали перечисление 18 классов избегающих перестановок, но не исследовали асимптотическую популярность
• Отсутствует систематический подход к обработке всех 18 классов

Исследовательская мотивация

Исходит из исследования класса 7 в работе 4 Baril, Burstein и Kirgizov, где они использовали биекцию между перестановками и рассеянными путями Дика для переноса паттернов, что вдохновило авторов на данную работу.

Основные вклады

1. Систематическое исследование 18 классов перестановок: Полный анализ классов избегающих перестановок, предложенных Kitaev-Mansour, которые избегают по крайней мере двух последовательных паттернов длины 3
2. Решение 10 простых классов: Для 10 классов перестановок (классы 1, 2, 3, 5, 6, 8, 9, 16, 18 и уже решённый класс 7) асимптотическая популярность выводится непосредственно из структуры
3. Глубокий анализ 2 сложных классов:
   • Класс 11 (Av(123,132,321)): комбинирование аналитических и комбинаторных методов
   • Класс 17 (Av(123,132)): использование преобразования Foata и биекции инволюций
4. Формулировка открытых проблем: Чётко указаны 5 классов перестановок (классы 10, 12, 13, 14, 15), для которых проблема остаётся открытой
5. Обнаружение явления исчезновения паттернов: Доказано, что в некоторых классах асимптотическая популярность конкретных паттернов равна 0 (исчезновение паттернов)

Подробное описание методов

Определение задачи

Входные данные:

• Класс перестановок $A_n = \text{Av}_n(p_1, \ldots, p_m)$, избегающий последовательные паттерны $p_1, \ldots, p_m$
• Неизбегаемый последовательный паттерн длины 3: $p$

Выходные данные:

• Асимптотическая популярность $\text{pop}_A(p) := \lim_{n \to \infty} \frac{p_n^A}{n|A_n|}$

где $p_n^A$ — общее количество вхождений паттерна p во всех перестановках из $A_n$.

Ключевые концепции

Последовательный паттерн: Перестановка π содержит последовательный паттерн p, если существует последовательная подпоследовательность $a_i a_{i+1} \cdots a_{i+r-1}$, которая порядково изоморфна p.

Симметрические операции:

• Обращение R(π): перестановка в обратном порядке
• Дополнение C(π): каждый элемент a заменяется на n+1-a
• Эти операции сохраняют вхождения последовательных паттернов

Классификация методов

1. Метод структурного анализа (простые классы)

Для классов перестановок с простой структурой асимптотическая популярность выводится непосредственно:

Класс 1 (Av(123,132,312,321)):

• Содержит только 2 чередующиеся перестановки
• Симметрия непосредственно даёт pop(213) = pop(231) = 1/2

Класс 18 (Av(132,231)):

• Форма перестановки: $a_1 \cdots a_k 1 b_1 \cdots b_{n-k-1}$
• где $a_1 \cdots a_k$ убывает, $b_1 \cdots b_{n-k-1}$ возрастает
• Подсчёт: количество вхождений 321 = $\sum_{k=1}^{n-1} \binom{n-1}{k}(k-1) = (n-1) \cdot 2^{n-2} - 2^{n-1} + 1$
• Вывод: pop₁₈(321) = pop₁₈(123) = 1/2, pop₁₈(213) = pop₁₈(312) = 0

Класс 16 (Av(123,321)):

• Использование симметрии: класс стабилен относительно R, C, R∘C
• Четыре неизбегаемых паттерна находятся во взаимно однозначном соответствии через эти биекции
• Вывод: pop₁₆(132) = pop₁₆(231) = pop₁₆(312) = pop₁₆(213) = 1/4

2. Аналитический метод (Класс 11)

Класс 11 (Av(123,132,321)):

Шаг 1: Структурный анализ

• Перестановки являются чередующимися или обратно-чередующимися
• Пропуск одного элемента справа налево даёт возрастающую последовательность
• Разделение на два подмножества: $A_n^r$ (последний элемент равен 1) и $A_n^l$ (предпоследний элемент равен 1)
• $|A_n^r| = (n-2)!!$, $|A_n^l| = (n-1)!!$

Шаг 2: Подсчёт паттерна 231 Прямое наблюдение структуры позиций: $231_n = (n-1)!! \left\lceil \frac{n-3}{2} \right\rceil + (n-2)!! \left\lceil \frac{n-2}{2} \right\rceil$

Шаг 3: Рекуррентное соотношение для паттерна 312 Установление рекуррентного соотношения (Лемма 3.2):

• $312_n^r = 312_{n-1}^l$
• $312_n^l = (n-1)(312_{n-2}^l + (n-3)!!) - (n-5)!! \frac{(n-3)(n-2)}{2}$

Шаг 4: Решение через производящие функции Пусть $u_n := \frac{312_n^l}{(n-1)!!}$, получаем производящую функцию: $f(z) = \frac{z(2(z-1)\ln(1-z) + z^3 + 3z^2 - 2z)}{4(1-z)^2(1+z)}$

Вывод: $312_n^l = (n-1)!! \left( \frac{(-1)^{n-1} + n - 3}{4} + \frac{1}{2} \sum_{\substack{k=1\\k \neq n \bmod 2}}^{n-1} \frac{1}{k} \right)$

Асимптотические результаты: pop₁₁(231) = 1/2, pop₁₁(213) = pop₁₁(312) = 1/4

3. Биективный метод (Класс 17)

Класс 17 (Av(123,132)):

Основной инструмент: Преобразование Foata Claesson доказал, что преобразование Foata устанавливает биекцию между Av_n(123,132) и множеством инволюций I_n.

Стандартная форма:

1. Каждый цикл начинается с минимального элемента
2. Циклы упорядочены по минимальным элементам в убывающем порядке
3. Удаление скобок даёт перестановку

Соответствие паттернов (Таблица 2):

• 321 в Av(123,132) ↔ (c)(b)(a) или формы с неподвижными точками в I_n
• 231 ↔ (bc)(a⋆) (без неподвижных точек)
• 213 ↔ (⋆b)(ac) (без неподвижных точек)
• 312 ↔ (⋆c)(ab) (без неподвижных точек)

Ключевые леммы:

• Лемма 4.2: Асимптотическое поведение количества неподвижных точек $\frac{\text{fp}_n}{|I_n|} \sim_{n \to \infty} \sqrt{n}$ Это показывает, что неподвижные точки редки в инволюциях и могут быть проигнорированы в паттернах, их содержащих.
• Лемма 4.3: Достаточно вычислить популярность паттернов без неподвижных точек

Анализ паттерна 231 (Предложение 4.4):

• Паттерн α = (bc)(a⋆) соответствует двум последовательным транспозициям
• Каждая пара последовательных транспозиций производит ровно один α и один β или γ
• Вывод: pop₁₇(231) = 1/2, pop₁₇(321) = 0

Анализ паттерна 213 (наиболее сложный):

• Соответствует паттерну 2314 в Av(123,132)
• Установление рекуррентного соотношения (Лемма 4.5): $2314_n = 2314_{n-1} + (n-1) \cdot 2314_{n-2} + \binom{n-2}{2}|I_{n-4}|$
• Экспоненциальная производящая функция (Предложение 4.6): $G(z) = \frac{e^{\frac{(1+z)^2}{2}}}{2} \int_0^z e^{-\frac{(1+t)^2}{2}} dt + \frac{z(z-2)e^{z+\frac{z^2}{2}}}{4}$
• Асимптотический анализ:
  • Первый член: $[z^n]z(z-2)e^{z+\frac{z^2}{2}} \sim \frac{n|I_n|}{n!}$
  • Второй член: использование метода перевала показывает $[z^n]F(z) = o(\frac{n|I_n|}{n!})$
  • Выбор точки перевала $\zeta = \sqrt{n}$ даёт достаточную верхнюю границу

Вывод: pop₁₇(312) = pop₁₇(213) = 1/4

Технические инновации

1. Комбинированный подход: Впервые систематически комбинируются структурный анализ, производящие функции и биективные методы для исследования асимптотической популярности последовательных паттернов
2. Инновационное применение метода перевала: В классе 17 путём выбора приближённой точки перевала $\zeta = \sqrt{n}$ вместо точной точки перевала упрощается анализ
3. Перенос паттернов: Использование преобразования Foata переводит проблему паттернов в перестановках в проблему циклической структуры инволюций
4. Редкость неподвижных точек: Доказано, что неподвижные точки растут как $O(\sqrt{n})$, что позволяет их игнорировать в асимптотическом анализе

Экспериментальная установка

Источники данных

Данная работа является чисто теоретической и основана на:

• Результатах перечисления 18 классов перестановок Kitaev и Mansour
• Известных производящих функциях и асимптотических формулах

Методы верификации

Хотя традиционных экспериментов нет, авторы упоминают:

• Проведение численных экспериментов для классов 10, 12, 13, 14, 15
• Очень низкую скорость сходимости, затрудняющую формирование надёжных гипотез

Экспериментальные результаты

Основные результаты (сводка в Таблице 1)

Ключевые находки

1. Явление исчезновения паттернов:
   • В нескольких классах асимптотическая популярность некоторых паттернов равна 0 (например, паттерн 231 в классе 2, паттерн 321 в классе 17)
   • Это "весьма замечательный факт"
2. Результаты симметрии:
   • Класс 16 демонстрирует совершенную четырёхкратную симметрию (все четыре паттерна имеют популярность 1/4)
   • Многие классы демонстрируют симметричное распределение 1/2
3. Рациональная популярность:
   • Во всех решённых случаях популярность является рациональным числом (0, 1/4, 1/2, 1)
   • Поставлена открытая проблема: существует ли иррациональная популярность?

Связанные работы

Классическое избегание паттернов

• Bóna & Homberger 1,2,3: Исследование классов перестановок, избегающих один классический паттерн длины 3
  • Доказано, что в Av(123) и Av(132) асимптотическая популярность паттерна 321 равна 1
• Janson 15,16: Исследование предельного распределения классических паттернов длины 3 в Av(132) и Av(321)

Исследования последовательных паттернов

• Kitaev & Mansour 17,18,19: Перечисление 18 классов избегающих перестановок (основа данной работы)
• Elizalde & Noy 9,10:
  • Методы, основанные на возрастающих деревьях и коробочных произведениях
  • Адаптация кластерного метода Goulden-Jackson

Биекции и перенос паттернов

• Barnabei, Bonetti, Silimbani 5:
  • Исследование совместного распределения последовательных паттернов размера 3 в Av(312)
  • Использование биекции Krattenthaler и инволюции Deutsch
• Baril, Burstein, Kirgizov 4:
  • Исследование статистики паттернов в словах faro и перестановках
  • Непосредственный предшественник и источник мотивации данной работы

Асимптотическая нормальность

• Borga 6: Исследование асимптотической нормальности вхождений последовательных паттернов в перестановках, избегающих определённые паттерны, на основе производящих деревьев

Заключение и обсуждение

Основные выводы

1. Полнота: Систематически решены 13 из 18 классов (10 простых + 2 сложных + 1 из известной литературы)
2. Методология: Демонстрирует эффективное комбинирование структурного анализа, производящих функций и биективных методов
3. Теоретические идеи: Раскрывает интересные явления, такие как исчезновение паттернов и симметрия

Ограничения

1. Незавершённая работа: 5 классов перестановок (классы 10, 12, 13, 14, 15) остаются открытыми
2. Численные трудности: Эти открытые классы имеют очень низкую скорость сходимости, что затрудняет формирование гипотез через численные эксперименты
3. Ограничения методов: Существующие методы, похоже, недостаточны для обработки оставшихся сложных случаев

Направления будущих исследований

Авторы в разделе 5 предлагают несколько открытых проблем:

1. Гипотеза 5.1: Если popₐ(p) = 0, то для подкласса B, избегающего p, имеем popB(q) = popₐ(q)
   • Это верно для всех решённых случаев
2. Расширенные проблемы:
   • Что происходит при избегании только одного последовательного паттерна длины 3?
   • Можно ли найти наборы паттернов, производящие иррациональную асимптотическую популярность?
   • Всегда ли существует предел (1.1)? Как охарактеризовать его существование?
3. Методологические проблемы:
   • Как решить оставшиеся 5 классов, используя перечислительные или вероятностные методы?
   • Существует ли единая схема, обрабатывающая все случаи?

Глубокая оценка

Преимущества

1. Высокая систематичность:
   • Впервые систематически исследуется асимптотическая популярность 18 классов перестановок
   • Чёткая классификация и методология (простые vs сложные)
2. Разнообразие методов:
   • Гибкое применение структурного анализа, производящих функций, биекций, метода перевала
   • Анализ класса 17 особенно изящен, демонстрируя органичное сочетание различных техник
3. Теоретическая глубина:
   • Элегантное доказательство леммы 4.2 о редкости неподвижных точек
   • Строгий вывод производящих функций (особенно дифференциальное уравнение для класса 11)
4. Ясность изложения:
   • Хорошо структурированная работа, от простого к сложному
   • Таблица 1 обеспечивает ясный обзор
   • Рисунки (Фигуры 1-2) помогают пониманию

Недостатки

1. Неполнота:
   • 5 проблем остаются нерешёнными (28% от общего числа)
   • Отсутствует глубокий анализ или частичные результаты для этих сложных случаев
2. Численная поддержка:
   • Хотя упоминаются численные эксперименты, конкретные данные не представлены
   • Отсутствует количественный анализ скорости сходимости
3. Верификация гипотез:
   • Гипотеза 5.1 проверена только на решённых случаях, недостаточно широкие доказательства
4. Технические детали:
   • Мотивация выбора точки перевала $\zeta = \sqrt{n}$ в классе 17 может быть более подробной
   • Некоторые вычислительные шаги имеют значительные пропуски

Влияние

1. Теоретический вклад:
   • Открывает систематическое исследование асимптотической популярности последовательных паттернов
   • Предоставляет новую перспективу теории избегания паттернов
2. Методологическая ценность:
   • Демонстрирует эффективное комбинирование различных техник
   • Идея переноса паттернов может быть применена к другим комбинаторным структурам
3. Вдохновляющий характер:
   • Предложенные открытые проблемы чёткие и интересные
   • Может стимулировать новые направления исследований
4. Ограничения:
   • Главным образом теоретические результаты, практическое применение не очевидно
   • Сложность оставшихся проблем может ограничить краткосрочное влияние

Области применения

1. Исследования комбинаторики:
   • Теория паттернов в перестановках
   • Асимптотическое перечисление
   • Методы производящих функций
2. Разработка алгоритмов:
   • Генерация ограниченных перестановок
   • Алгоритмы поиска паттернов
3. Смежные области:
   • Возможное применение в статистической физике для моделей с ограничениями
   • Связь с проблемами избегания паттернов в геномике

Библиография

Ключевые источники:

1. 4 Baril, Burstein, Kirgizov (2021): Непосредственный источник мотивации данной работы
2. 17 Kitaev (2003): Основа перечисления 18 классов перестановок
3. 7 Claesson (2001): Биекция преобразования Foata (ключевой инструмент для класса 17)
4. 1-3 Bóna & Homberger (2010-2012): Пионерские работы по классическим паттернам
5. 11 Flajolet & Sedgewick (2005): Стандартный справочник по аналитической комбинаторике

Общая оценка: Это солидная работа по комбинаторной математике, систематически исследующая естественную и интересную проблему. С методологической точки зрения она демонстрирует эффективное комбинирование различных техник, особенно анализ классов 11 и 17 отражает глубокие технические навыки. Хотя 5 классов остаются нерешёнными, выполненная работа создаёт прочную основу для данной области. Статья написана ясно, результаты интересны (особенно явление исчезновения паттернов), поставленные открытые проблемы чёткие и вызывающие. Для исследователей в области комбинаторной математики, особенно теории паттернов в перестановках, это статья, достойная глубокого изучения.