Прикладная дискретная математика. Приложение №1 2017

Стр.1

Стр.2

Стр.3

№10 ПРИКЛАДНАЯ ДИСКРЕТНАЯ МАТЕМАТИКА ПРИЛОЖЕНИЕ С е к ц и я 1 ПРИКЛАДНОЙ ДИСКРЕТНОЙ МАТЕМАТИКИ ТЕОРЕТИЧЕСКИЕ ОСНОВЫ УДК 519.1 DOI 10.17223/2226308X/10/1 ОБОБЩЁННЫЕ 312-ИЗБЕГАЮЩИЕ ПЕРЕСТАНОВКИ И ПРЕОБРАЗОВАНИЕ ЛЕМЕРА Л. Н. Бондаренко, М.Л. Шарапова Рассматривается преобразование Лемера введённых И. Гесселем и Р. Стенли перестановок (ГС-перестановок). Доказано, что итерация преобразования Лемера множества всех ГС-перестановок порядка r  1 приводит к множеству всех 312избегающих ГС-перестановок порядка r, что даёт новую характеризацию этих перестановок. Показано, что статистики rise и imal на множестве 312-избегающих ГС-перестановок порядка r имеют одинаковые распределения. Найдено простое соотношение, связывающее обращение производящей функции многочленов Нараяны порядка r с обращением экспоненциальной производящей функции многочленов Эйлера порядка r. Ключевые слова: ГС-перестановки, преобразование Лемера, 312-избегающие ГС-перестановки, статистики rise и imal, многочлены Эйлера, многочлены Нараяны, производящая функция, обратная функция. В [1] для изучения некоторых статистик на группе перестановок Sn множества |S(r) n | = 1 · (r + 1) · . . . · (r(n − 1) + 1). ГС-перестановкой порядка r называется слово σ = σ1 . . . σrn над алфавитом [n], все n всех таких перестановок задаётся соотношением Определение 1. Пусть все символы слова ω = ω1 . . . ωm —целые положительные i − 1, ω0 = 0}, i ∈ [m]. [n] = {1, . . . , n} использовано преобразование Лемера. В [2] это преобразование применяется к ГС-перестановкам порядка r мультимножества {1r, . . . , nr}, r  1, введённым И. Гесселем и Р. Стенли в [3]. буквы которого, стоящие между любыми двумя вхождениями символа s ∈ [n], не меньше этого s. Мощность множества S(r) числа. Тогда его преобразованием Лемера l назовём слово lω = lω1 . . . lωm, в котором lωi = #{j : ωj < ωi, 0 j Определение 1 шире использованных в [1, 2] и позволяет рассматривать для слова ω итерацию преобразования Лемера, т. е. степени lkω, k  1. Определяя также число новке порядка r не изменяется при применении к ней k раз преобразования Лемера. Пример 1. Степени lkσ, k = 1, 2, 3, 4, σ = 3344551122 ∈ S(2) 5 , имеют вид 3344551122 l−→ 1133551133 l−→ 1133551155 l−→ 1133551177 l−→ 1133551199, а число подъёмов во всех словах равно четырём. n , т. е. число подъёмов в ГС-перестаподъёмов rise(ω) = #{i ∈ [m] : ωi−1 < ωi, ω0 = 0}, для ГС-перестановок порядка r нетрудно получить следующее утверждение. Лемма 1. rise(σ) = rise(lkσ), k  1, σ ∈ S(r) Сентябрь 2017

Стр.1

8 Прикладная дискретная математика. Приложение Следует также отметить, что преобразование Лемера l задает биекцию S(r) множество, не совпадающее с S(r) Как и в [4], σ ∈ S(r) n назовём 312-избегающей ГС-перестановкой порядка r, если n . n . деления 1 следует, что lσ = l2σ. Аналогично, необходимость: если lσ = l2σ, то ГСперестановка σ /∈ S(r) Теорема 1. ГС-перестановка σ ∈ S(r) n тогда и только тогда, когда lσ = l2σ. n . перестановка σ /∈ S(r) n , то все ГС-перестановки из S(r) Следствие 1. l S(r) n = ln−1S(r) lkS(r) n , n  3. алгоритма генерации ГС-перестановок порядка r ([2, 3]), также не входят в S(r) n+1. Доказательство. Отметим, что при n = 1, 2 имеем S(r) n = S(r) но ln−2σ /∈ l S(r) n , а применение теоремы 1 даёт l S(r) n = ln−1S(r) n+1, полученные из нее с помощью n , k  n − 1. Пример 2. Для пояснения следствия 1 дополнительно к примеру 1, в котором n , n  3, так как ln−1S(r) n = 2233441155 l−→ 1133551199 и 2233551144 l−→ 1133551177 l−→ 1133551199. n позволяет σ = 3344551122 /∈ S(2) 5 , покажем действие преобразования Лемера на ГС-перестановки 2233441155 ∈ S(2) 5 и 2233551144 /∈ S(2) 5 : Таким образом, теорема 1 и следствие 1 дают новые характеризации множества S(r) n справедливо следующее рекуррентное соотношение [2]: A(r) 0,k = δ0k, A(r) n (t) = A(r) kn =1 n+1,k = kA(r) A(r) n,k = #{σ ∈ S(r) n : rise(σ) = k} порядка r, для которых n,k + (rn − k + 2)A(r) n,k−1, k ∈ Z, n  0, n,k tk порядка r приводит к формуле (1) где символ Кронекера δij равен 1 при i = j и 0 при i = j. Применение (1) для многочленов Эйлера A(r) 0 (t) = 1, A(r) n+1(t) = (rn + 1)tA(r) n (t) + t(1 − t)DtA(r) n (t), n  0, где Dt = d/dt — оператор дифференцирования, причём A(r) В [2] с помощью (1) показано, что A(r) n,k = #{σ ∈ S(r) n : imal(σ) = k}, где стаn (1) = |S(r) n |. тистика imal(σ) = |{lσ1, . . . , lσrn}| — число различных символов в слове lσ, σ ∈ S(r) n , использована при r = 1 в [1] и была введена Д. Дюмоном. Следует отметить, что распределения статистик rise и imal на множестве S(r) n при n > 3 не совпадают. В силу же результатов леммы 1 и теоремы 1 статистики rise и imal на множестве S(r) n имеют одинаковые распределения, т. е. rise(σ) = imal(σ), σ ∈ S(r) n . всех 312-избегающих ГС-перестановок порядка r с помощью преобразования Лемера. Число подъёмов rise(σ) = #{i ∈ [rn] : σi−1 < σi, σ0 = 0} в слове σ ∈ S(r) n . Если ГСПоэтому по индукции при n  3 для σ = 3r4r . . . nr1r2r /∈ S(r) n получаем ln−1σ ∈ l S(r) n , n на не существует тройки индексов i, j, k, i < j < k, для которых верно неравенство σj < < σk < σi, а множество всех таких перестановок обозначим S(r) Доказательство. Достаточность: если ГС-перестановка σ /∈ S(r) n , то из опреопределить числа Эйлера A(r)

Стр.2

Теоретические основы прикладной дискретной математики 9 A(r) n,k = #{σ ∈ S(r) n : rise(σ) = k}, которые описываются следующим соотношением: В [4] рассматриваются многочлены Нараяны A(r) n (t) = причём для производящей функции этих многочленов v = A(r)(t, u) = ∞n=1 A(r) A(r) n (t) = 1 n kn =1 k − 1 tk, A(r) n (1) = получена обратная ей функция u = A(r)(t, v)−1 = (v + t)(v + 1)r . v Для экспоненциальной производящей функции многочленов Эйлера порядка r v = A(r)(t, u) = ∞n=1 A(r) n (t)un n! авторами доказана формула, задающая обратную ей функцию u = A(r)(t, v)−1 =  v 0 (z + t)(z + 1)r . dz (3) выделения в S(r) Сравнение выражений (2) и (3) приводит к следующему неожиданному результату. Теорема 2. Имеет место равенство A(r)(t, v)−1 = vDvA(r)(t, v)−1, где Dv = d/dv. В заключение отметим, что теоремы 1 и 2 и следствие 1 показывают важность 1. Фоата Д. Распределения типа Эйлера и Макмагона на группе перестановок // Проблемы комбинаторного анализа: сб. статей. М.: Мир, 1980. С. 120–141. n подмножества S(r) n 312-избегающих ГС-перестановок порядка r. ЛИТЕРАТУРА 2. Бондаренко Л. Н., Шарапова М.Л. Параметрические комбинаторные задачи и методы их исследования // Изв. вузов. Поволжский регион. Физ.-мат. науки. 2010. №4 (16). С. 50–63. 3. Gessel I. and Stanley R. P. Stirling polynomials // J. Combinatorial Theory. Ser. A. 1978. V. 24. P. 24–33. 4. Бондаренко Л. Н., Шарапова М.Л. Обобщённые многочлены Нараяны и их q-аналоги // Прикладная дискретная математика. Приложение. 2016. №9. С. 6–8. n k rn 1 rn + 1 n (t) un kn =1 A(r) (r + 1)n n , n,k tk порядка r, где (2)

Стр.3