Generalized 312-avoiding gs-permu-tations and lehmer's transformation.pdf В [1] для изучения некоторых статистик на группе перестановок Sn множества [n] = {1,... ,n} использовано преобразование Лемера. В [2] это преобразование применяется к ГС-перестановкам порядка r мультимножества {1r,... , nr}, r ^ 1, введённым И. Гесселем и Р. Стенли в [3]. ГС-перестановкой порядка r называется слово a = a1... arn над алфавитом [n], все буквы которого, стоящие между любыми двумя вхождениями символа s G [n], не меньше этого s. Мощность множества &1ПГ всех таких перестановок задаётся соотношением |еПг) | = 1 ■ (r +1) ■... ■ (r(n -1) +1). Определение 1. Пусть все символы слова ш = ш1... шт - целые положительные числа. Тогда его преобразованием Лемера l назовём слово 1ш = 1ш1... 1шт, в котором 1шг = #{j : ш^ < шг, 0 ^ j ^ i - 1, ш0 = 0}, i G [m]. Определение 1 шире использованных в [1, 2] и позволяет рассматривать для слова ш итерацию преобразования Лемера, т.е. степени 1kш, k ^ 1. Определяя также число подъёмов пве(ш) = #{i G [m] : шг-1 < шг, шо = 0}, для ГС-перестановок порядка r нетрудно получить следующее утверждение. Лемма 1. rise(a) = rise(1ka), k ^ 1, a G &П[\ т.е. число подъёмов в ГС-перестановке порядка r не изменяется при применении к ней k раз преобразования Лемера. Пример 1. Степени 1ka, k =1, 2, 3, 4, a = 3344551122 G S^, имеют вид 3344551122 -U 1133551133 -U 1133551155 -U 1133551177 -U 1133551199, а число подъёмов во всех словах равно четырём. (r) Следует также отметить, что преобразование Лемера l задает биекцию &n) на 6(r) n . Как и в [4], a ф &n назовём 312-избегающей ГС-перестановкой порядка r, если не существует тройки индексов i,j, k, i < j < k, для которых верно неравенство aj < ~ (r) < ak < ai, а множество всех таких перестановок обозначим &П . Теорема 1. ГС-перестановка a ф &Пг) тогда и только тогда, когда la = l2a. Доказательство. Достаточность: если ГС -перестановка a ф &П), то из определения 1 следует, что la = l2a. Аналогично, необходимость: если la = l2a, то ГС-перестановка a ф &Пг). ■ Следствие 1. lSПг) = 1п-1&Пг), n ^ 3. (r) (r) Доказательство. Отметим, что при n = 1, 2 имеем &П) = &П). Если ГС-перестановка a ф &Пг), то все ГС-перестановки из &П+1, полученные из нее с помощью алгоритма генерации ГС-перестановок порядка r ([2, 3]), также не входят в &Пг+1. Поэтому по индукции при n ^ 3 для a = 3r 4r ... nr 1r 2r ф &Пг) получаем ln 1a Ф 1&Пг), но ln-2a ф 1&Пг), а применение теоремы 1 даёт 1&Пг) = ln-1&П), n ^ 3, так как ln-1&П) = lk&Пг), k ^ n - 1. ■ Пример 2. Для пояснения следствия 1 дополнительно к примеру 1, в котором a = 3344551122 ф &52), покажем действие преобразования Лемера на ГС-перестановки 2233441155 ф &52) и 2233551144 ф &52): 2233441155 -->• 1133551199 и 2233551144 -->• 1133551177 -->• 1133551199. Таким образом, теорема 1 и следствие 1 дают новые характеризации множества &n) всех 312-избегающих ГС-перестановок порядка r с помощью преобразования Лемера. Число подъёмов rise(a) = #{i ф [rn] : ai-1 < ai, ao = 0} в слове a ф &n позволяет определить числа Эйлера A^k = #{a ф &Пг) : rise(a) = k} порядка r, для которых справедливо следующее рекуррентное соотношение [2]: A0rk = Sok, A^ = kAnrk + (rn - k + 2)Ark-i, kф Z, n > 0, (1) где символ Кронекера 8ij равен 1 при i = j и 0 при i = j. Применение (1) для многочленов Эйлера аПг) (t) = A^k tk порядка r приводит к формуле k=i ' A0r)(t) = 1, Anr++i(t) = (rn +1)tAnr)(t)+ t(1 - t)AAnr)(t), n ^ 0, где Dt = d/dt - оператор дифференцирования, причём Anr °(1) = i&nr)i. В [2] с помощью (1) показано, что A^k = #{a ф &Пг) : imal(a) = k}, где статистика imal(a) = |{la1,... , larn}| -число различных символов в слове la, a ф &Пг), использована при r =1 в [1] и была введена Д. Дюмоном. Следует отметить, что распределения статистик rise и imal на множестве &Пг) при n > 3 не совпадают. В силу же результатов леммы 1 и теоремы 1 статистики rise и imal на множестве &Пг) имеют одинаковые распределения, т.е. rise(a) = imal(a), a ф &Пг). ) П ) В [4] рассматриваются многочлены Нараяны An (t) = Е A-nk tk порядка r, где ~ k=1 A^k = #ia ^ SПг) : rise(a) = k}, которые описываются следующим соотношением: ^

Скачать электронную версию публикации