Generalized narayana polynomials and their q-analogues.pdf Если все буквы слова а = а1... arn длины |а| = rn над алфавитом Nn = {1,... ,n}, где r ^ 1 - целочисленный параметр, стоящие между любыми двумя вхождениями символа i Е Nn, не меньше этого i, то эту особенность а назовем ГС-свойством, а множество всех перестановок мультимножества {1r,...,nr}, обладающих ГС-свойством (ГС-перестановок), обозначим GSn,r. Эти названия мотивированы применением И. Гесселем и Р. Стенли множества GSn,2 для изучения полиномиальных последовательностей Стирлинга обоих родов [1], а также исследованием свойств чисел Эйлера порядка r, комбинаторная интерпретация которых связана с рассмотрением GSn,r [1-3]. Введем обобщение понятия рассматриваемой в [4, 5] 312-избегающей перестановки. Определение 1. Слово а Е GSn,r назовем 312-избегающей ГС-перестановкой порядка r, если не существует тройки индексов i < j < k, для которых выполняется неравенство aj < ak < ai, а множество всех таких перестановок обозначим GSn,r. Для слова а Е GSn,r стандартным образом вводятся неотрицательные целочисленные функции (статистики): rise(a) = |{i Е Nn : ai-i < ai,a0 = 0}| -число подъёмов; des(a) = |{i Е Nn : ai > ai+1,an+1 = 0}| -число спусков; inv(a) = |{(i, j) Е Nn : i < j, ai > aj}|/r - приведённое число инверсий. n Теорема 1. Производящие многочлены An,r (t) = An,r,k tk статистик rise и des _ ' k=i на множестве GSn,r совпадают и определяются равенством Anr(t) = nkc(k)(k- i)tk■ (1) 9 ПРИКЛАДНАЯ ДИСКРЕТНАЯ МАТЕМАТИКА - числа Фусса - Каталана [2]. (r + 1)n 1 где Л n,r (1) = Cn, r+1 rn +1 n Доказательство. Так как rise(a) = des(n), а, п Е GSn,r, пг = arn+1-i; i Е Nrn, то многочлены (1) статистик rise и des совпадают. Для вычисления коэффициента An,r,k = |{а Е GSn,r : rise(a) = k}| сопоставим каждой перестановке а Е GSn,r слово т = т1... Trn, тг = rn + 1 - ато+1-г, i Е Nrn, упорядочиваемое с помощью единственного стека, и сформируем новую последовательность, в которую записывается 1, когда символ слова т помещается в стек, и -1, когда он вынимается из стека, причём в соответствии с принципом «последним пришёл - первым ушёл» из стека вынимаются последовательно r одинаковых символов. В результате перестановке а Е GSn,r сопоставляется последовательность длины 2rn, состоящая из одинакового числа 1 и -1 (число записанных подряд -1 кратно r), её частичные суммы неотрицательны, а rise(a) = k, если в этой последовательности имеется k переходов с 1 на -1. rn n - 1 пар k-композиций Л : а1 + ... + ak Имеется ^ ^ пар k-композиций Л : а1 + ... + ak = rn + 1 и B : b1 + ... + bk = n взаимно простых чисел rn + 1 и n. Пусть циклическая последовательность w = w(A, B) состоит из а1 единиц, rb1 минус единиц, а2 единиц, rb2 минус единиц и т.д., причём имеет ровно k пар (Лг,Вг), i = 1,...,k, вида Лг : аг + аг+1 +... + ak + а1 +... + аг- = rn + 1, Вг : bi + bi+1 +... + bk + b1 +... + bi-1 = n. Тогда по лемме Рени [2, 4] единственным способом можно разорвать w так, чтобы получилась последовательность, начинающаяся с 1, после удаления которой любая частичная сумма оставшейся последовательности неотрицательна. Таким образом, получена биекция циклических классов эквивалентности {(Лг,Вг) : i = 1,... , k} с множеством {а Е GSn,r : rise(a) = k} и 1 / n nk 1 rn kU - 1 n - 1 k1 rn k1 Л, n,r,k Отметим, что при r =1 эта конструкция аналогична используемой в [4, 5], а An,r (1) легко вычисляется с помощью свёртки Вандермонда. ■ При r =1 выражение (1) задает многочлены Нараяны, коэффициенты которых называются числами Нараяны. Эти многочлены и числа встречаются в ряде комбинаторных задач [4]. Поэтому в рассматриваемом обобщении назовем An,r,k числами Нараяны порядка r, а Лп,г (t) - многочленами Нараяны порядка r. Следствие 1. Многочлены Нараяны порядка r находятся по формуле 1 dn-1 An,r(*) = n ^((v + + 1)гп)ь_о Доказательство. Непосредственное вычисление (2) с помощью формулы Лейбница для (n - 1)-й производной приводит к выражению (1). ■ Х_ Теорема 2. Производящей функции v = Лг(t,u) = Y1 An,r(z) un отвечает обратn=1 ная функция u = A-1(t, v) = v(v + t)-1(v + 1)-r, и справедливо соотношение Ao,r(t) = 1, A+1,r(t) = (t - 1) (Aln,r(t)}r + (an,r(t)}r+1 , n ^ 0, (3) где (Pn(t))m = Pkl (t)... Pkm (t) - m-кратная свёртка последовательности fc1 + ...+fcm=n, ki >0 многочленов Po(t), P\(t),..., Pn(t), deg(Pk(t)) = k, k = 0,1,... ,n. Доказательство. Первое утверждение теоремы 2 вытекает из (2) и теоремы Лагранжа [4]. Применение функции v = Ar(t,u), увеличенной на 1, к u = A-1(t,v) даёт алгебраическое уравнение u(v + 1)r+1 + u(t - 1)(v + 1)r - (v +1) +1 = 0. Так как ко/ ~ ) r+1 эффициент при un степенного ряда (v + 1)r+1 равен свертке (An,r (z)) , то сравнение коэффициентов в этом уравнении при степенях u даёт рекуррентное соотношение (3), причём при t =1 уравнение и соотношение (3) соответствуют формулам из [2]. ■ Теорема 2 допускает q-обобщение. Теорема 3. Справедливо рекуррентное соотношение Adrv(t,q) = 1, A£irv(t,q) = (t - 1) (Anrv(t,q))r + (An;rv(t,q))^ , n ^ 0, (4) где (Pn(t,q))m = £ qk2+2fc3+...(m-1)fcmPki(t,q)... Pkm(t,q) является q-аналогом ki + ...+km=n, ki >0 m-кратной свёртки последовательности многочленов P0(t,q), P1(t,q),... , Pn(t,q), а те_ производящая функция AdJes,inv(t,u; q) = £ Aner,inv(t,q)un удовлетворяет уравнению ~ - n=0 , Ades,lnv(t, u; q) = 1 + u(Aldes,lnv(t, u; q) + t - 1)Ades,lnv(t, qu; q)... Afs,inv(t, qru; q). Доказательство. Рекуррентное соотношение (4) для производящих многочленов пары (des, inv) является q-обобщением выражения (3) и может быть получено применением метода математической индукции по r к словам из 1 и -1, используемым в доказательстве теоремы 1, причем для случая r =1 применяется метод доказательства, аналогичный рассмотренному в [6] при t =1. Ооотношение (4) при t = 1 определяет q-многочлены Нараяны Bnr(q) = An+fr^!, q) порядка r, совпадающие при r = 1 с многочленами из [6]. Уравнение для производящей функции AdJes,inv(t,u; q) соответствует рекуррентному соотношению (4). ■ Таким образом, рассмотрение статистик на множестве 312-избегающих ГС-перестановок порядка r позволяет получить естественным путём как обобщённые многочлены Нараяны, так и их q-аналоги.

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