©Akademie d. Wissenschaften Wien; download unter www.biologiezentrum.at Sitzungsberichte Sitzungsber. Abt. II (1999) 208: 3-20 Mathematisch-naturwissenschaftliche Klasse Abt. II Mathematische, Physikalische und Technische Wissenschaften © Österreichische Akademie der Wissenschaften 2000 Printed in Austria q-Catalan- und q-Motzkinzahlen Von J. Cigler (Vorgelegt in der Sitzung der math.-nat. Klasse am 25. März 1999 durch das w. M. Johann Cigler) Hern? Prof Dr. L. Scbmetterer ^um 80. Geburtstaggewidmet Summary Inspired by ideas of [1] and [3] this paper wants to give new insights into some q-analogs of Catalan und Motzkin numbers. 1 Sei W„ die Menge aller Wörter x,x x,2 . x,n der Länge n über dem Alpha­ bet {x_h x0,xh x2, ■ ■ •}, welchei\ +/2 + ■ • + 4 ^ —1 für alle/fe > 1 erfül­ len (vgl. z.B. [7] oder [9]). Diese Wörter lassen sehr unterschiedliche kombinatorische Deutungen zu. Wir wollen sie hier als positive Gitter­ wege von (0,0) nach («, — X^/= l h) interpretieren. Dabei entspricht dem Symbol x_i ein „Aufstieg“ (1, 1) der Höhe 1 und jedem anderen x; ein „Abstieg“ (1,1 —i) der Höhe 1 —/.Wir ordnen nun jedem Buchstaben xj ein Gewicht w(xj) £ N zu, wobei w(x_\) = 1 sei. Die „Höhe“ eines Wortes XjxXi2 .Xjn sei die Zahl a„ = b(xn . x,n) = —{i\ + +4) — 1- Dann ist ol„ + 1 die Höhe des Gitterweges an der n-ten Stelle. Unter dem Gewicht eines Wortes wollen wir das Produkt des Gewichts der Buchsta­ ben und der qa' verstehen; genauer sei «/(*.,. .X.J = w(xh) .w(xiH)qa'+a2+'"+a\ (1) Ähnliche Gewichte wurden auch in [9] oder [10] betrachtet. ©Akademie d. Wissenschaften JW. ieCn;i gdolewrnload unter www.biologiezentrum.at Aus (1) ergibt sich sofort, daß _ -ik+ik+1. IV {xj • • A"/J = q '(*V. • *7,) (2) gilt. Das legt es nahe, jedem Wort x;-x/2 ... x,ti das entsprechende Wort ip(xixxi2 ■ ■ x/„) = JiiJb -Jin in den Symboleny-, zuzuordnen, welche die q-Kommutationsregeln J'iJ'j = (3) erfüllen. Speziell gilt dannj/_i jv_i =qy,—\ y~ 1, wobei r > 1 sei. Nun kann man den q-binomischen Lehrsatz ([11], [4]) anwenden und erhält k n—k (j-i +JV-i)" = JV-lJ-l k=0 Daraus lassen sich sehr einfach einige nützliche Hilfsresultate ableiten: Bezeichnet man mit Vnk die Menge aller Wörter, in welchen k Symbole x,._^ und n—k Symbole x_i Vorkommen, so ist also ( k n—k\ w{y„^ = IV Man rechnet leicht nach, daß .k _ ji(n-rk)+r(^j - ("V) w{xkr_xx":*) = q gilt Interpretiert man ein Wort aus V,hk als einen (nicht notwendig positi­ ven) Gitterweg von (0, 0) nach (;;, n — rk), so ergibt sich also, daß das Gewicht dieser Wege gegeben ist durch //(//—yvfe)—("t1) (2) (4) Als weiteres Hilfsmittel für später berechnen wir das Gewicht der Menge U^x aller positiven Gitterwege von (0, (r — \)k) nach (k-\- x,x) für ein x > 1, welche mit einem Aufstieg beginnen und genau k Abstiege haben. Jedem solchen Weg entspricht ein Wort der Form v, wobei v E ist. Daher ist nach (4) x + k — 1 ( k X— 1 \ <Uk,x) = IV k ©Akademie d. Wissenschaften Wien; download unter www.biologiezentrum.at und wegen «'(x -ix ^ x ^ 1) = q^'~x^ 2 )+U (man beachte, daß der erste Punkt des Gitterweges die Höhe (r — \)k +1 besitzt) gilt also m(Uks) = ^ '-'^ ‘iO + fe) [X + k ~ 11 (5) L k Sei nun A (;z, x) das Gesamtgewicht der Menge W„{x) aller Wörter ^E IV„ der Höhe h(%) = ot„ = x — 1, d.h. der positiven Gitterwege von (0,0) nach (n, x). Für diese Zahlen gelten die folgenden wichtigen Bezie­ hungen: A (;;, x) = qx~x (A {11 — 1, x — 1) + w[xj)A (n — 1, x + /)) (6) />0 und n A (/z, x + j) = 'y^jA {n — k, x)A {k,y)qkx (7) £=0 mit den Randbedingungen .4 (n, 0) = 6„fi und ^4 (0, k) = 6kß. (8) Denn für x,-x/2 . x/u = %x/ir E W„(x) ist w{xlxxl2 . x/J = iv^XjJ = #'(^)^(x/J ^x_1 mit ^ E H7 (x + /„), woraus sich (6) ergibt. Ist Xjxx,2 . xln = E W„{x +j'), wobei s das längste Anfangsstück des Wortes ist mit W„(x), so ist ^ E W„(J) und iv(s%) = w(s)w{^)qkx, wobei k die Länge von ^ ist. Daraus folgt unmittelbar (7). 2 Als Beispiel betrachten wir den Fall, wo w{x_a) = w{xr_\) = 1 für ein r > 1 ist und alle anderen Buchstaben das Gewicht 0 haben. Wir sprechen kurz von Wörtern vom Typ r. Bezeichnen wir das entsprechende Gewicht von W„ (x) mit A ^ (n, x), so gilt also A ^4^ x) == q'~\A{r 1 *1TT—1+ — 1, X + r -1)) (9) Für r = 2 ergibt sich 0 0 0 0 0 (x 0 ^ 0 1 0 0 0 0 0 0 0 9 0 0 0 0 0 q 0 03 0 0 0 (10) 0 0 q2\Aq> o <1 0 0 0 q2 + q4 0 *4[3],, 0 T 0 v° 0 q3 + 2q:’ + q1 + q* 0 0 q 15 /. ©Akademie d. Wissenschaften Wien; download unter www.biologiezentrum.at Im Fall q = 1 gilt A ^ (r/z + x, x) = G„ (x, r), wobei _ x (rn + x\ G„(*, r) = ( J rn + x V « / die Gouldpolynome bezeichnet, weil beide Ausdrücke die Anzahl der positiven Gitterwege von (0,0) nach (r/z + x, x) zählen (vgl. z.B. [5]). Dieser Zusammenhang bleibt auch beim Übergang zu den q-Analoga sinngemäß erhalten. Unter den q-Gouldpolynomen G„(x, r, q) verstehen wir die Funktio­ nen, die durch G„(x + 1, r, q) — G„(x, r, q) = qxG„-1 (x + r, r, (11) und die Randbedingungen Go(x,r,q) = l,G„(0,r,q) = <5„,o (12) eindeutig festgelegt sind (vgl. [5]). Z.B. ist für r = 2 / I I 1 \ 0 1 1 + q 0 1 -\- q 1+2q q2 -\- q^ 0 1+2 q + q2 + q3 1 + 3q + 3q2 + 3<?3 + 2^4 + V / Zum besseren Verständnis bemerken wir, daß die q-Gouldpolynome die positiven Gitterwege von (0, 0) nach (rn-\-x,x) mit dem folgenden Gewicht versehen: Wir können ein Wort x-nx,2 . mit n Abstiegen xr_i eindeutig durch die Folge c„... c2c\ der Höhen jener n Anfangswörter beschreiben, die mit einem Abstieg enden. Diese erfüllt 0 < cx<x und Cj+^Cf+r-X. Mit diesen Bezeichnungen gilt G„{x,r,q) = q,'+ '+‘- (13) Denn sei H„(x, r, q) = qCl+'"+c". Dann ist Hn(x + 1, r, q) = H„(x, r, q) + qxH„-\(x + r, r, q) erfüllt, weil beide Seiten das Gewicht der Folgen c„... c2c\ mit q < x +1 messen. Die Randbedingungen sind trivialerweise erfüllt. Daraus ergibt sich A^'\m + x,x) = ^"(2) + (2) G„(x, r, q'). (14) ©Akademie d. Wissenschaften Wien; download unter www.biologiezentrum.at Zum Beweis bemerken wir zunächst, daß A^'\n, x) ^ 0 nur für // = x(mod r) möglich ist, wie sofort aus (9) folgt. Dann ergibt sich ebenfalls aus (9) / (n, x + 1) — f (», x) = q'x f (n — 1, x + r). Ein Vergleich mit (11) liefert dann das behauptete Resultat. Speziell ergibt sich A{r\rn+ 1,1) = q‘^ C r„(qr) (15) wobei die C'H{q) die in [5] betrachteten verallgemeinerten q-Catalanzah- len sind. 3 Wir wollen nun im Fall r = 2 ein q-Analogon von zwei wohlbekannten Catalandreiecken ableiten: Wir zerlegen die positiven Gitterwege von (0, 0) nach (2(in + n) + 1,1) in die Wege von (0, 0) nach (2# + l,2/ + l) und die Restwege von (2n +1,2/ +1) nach (2(m + n) + 1,1), die wegen der Symmetrie zwischen Aufstiegen und Abstiegen dasselbe Gewicht wie die positiven Wege von (0,0) nach (2m + 1,2/ + 1) haben. Für die Gewichte gilt Y,A^(2n +1,2/ +1) q~2/ A^2\2m +1,2/ +1) = A ^ (2m + 2n +1,1), weil das Gewicht des Punktes (2n +1,2/ +1) in der Summe doppelt gezählt wird. Das kann auch folgendermaßen formuliert werden: Sei Cnj (q) — A ^(2n +1,2/ +1). Dann ist C0j/ = 60j und E™o(/,,w) c»Aq) = qm+HCZ+,u{q2) oder in Matrixform ( Co.o C 1,0 <^2,0 Cl,o ^2,0 ^3,0 Q ,0 ^3,0 Q ,0 / (16) Die Cjj lassen sich auch durch eine einfache Rekurrenz beschreiben. ©Akademie d. Wissenschaften Wien; download unter www.biologiezentrum.at Da jeder Weg, der in (2n +1,1) endet, entweder über (2n — 1, 1) oder über (2n — 1, 3) gehen muß, ist C ,0 = qC„-\p + qC„-\^\ und analog ergibt sich für i > 1, daß jeder Weg nach (2n +1,2/ -(-1) mit enden muß. Daher ist C/,/ — ^ 1 (<^//—1 l + (1 + ^2)C;-i,/ + <72Cv-i,/+i)- Z.B. ergibt sich / l o o o \ (C,^ = q q' 0 0 <T^ct q4+q('+q* qu) 0 \ + 2q" + q1 + q'} q* + Iq1 + 2<f + 2qu + qu + q1* qn + qn + qX:> + qv + q19 q2x ) Speziell rechnet man sofort nach, daß C,un — q'l(^'1+V) und daher (C</,//)2 q~2" — qr" ist. Daher ergibt sich 4E /2 det(C+y,o);'“lo = ? 1 (17) Beachtet man (15), so ergibt sich schließlich für die Hankeimatrix der Carlitz’schen q-Catalanzahlen (C^(q)), die durch k+/=)i und C^(q) = 1 definiert sind (vgl. [8]), die Gleichung „ 2> ,/2_ (,“?') //(«+1)(4//— 1) det(<4M)"y=0 = q ' = q (18) Interessant ist auch die folgende Tatsache, die sich sehr einfach bewei­ sen läßt und wahrscheinlich bekannt ist. (Man vgl. [1], wo etwas ähnliches für Motzkinzahlen gemacht wird). Cn-\,iC„j — CniCu— | j (19) ist für 0 < i <j ein Polynom in q mit nicht negativen Koeffizienten. Das zeigt man leicht mit Induktion nach n. Für 1 < i <j ist zu zeigen, daß (C/-i,/-i + (1 + q2)C„ - + <72C,_v+ i)(Cv _i + (1 + q2)C,^j + q2C„j+\) — (C/-1,7-1 + (1 + q2)C„-\j + q2C„-\j+\)(C/,/-l + (1 + q2)C„j + q2C„j+\) nichtnegative Koeffizienten als Polynom in q hat. Das ist für / + 2 <j klar. Für j = i +1 brauchen wir bloß dieTerme mit C/7/C/7_1/+1 und C,v+1C/?_i j ©Akademie d. Wissenschaften Wien; download unter www.biologiezentrum.at extra betrachten. Hier ist zu zeigen, daß der Ausdruck (1 -\-q2)2C„_\,■ 2 22 2 • 5 ^//,/+1 ^ 0 ^ ^ q Cu—i;/,/+1 nichtne­ gative Koeffizienten hat. Das ist aber klar, weil er in der Form [(l+/)2-/]- [C-vCv+i /+iC,v] geschrieben werden kann. Der Fall / = 0,y > 0 ist noch einfacher. Als Korollar ergibt sich für die q-Catalanzahlen C2(q): c 2„ -M cl+M - (cl^ ))1 (20) hat nichtnegative Koeffizienten. Denn diese Aussage ist äquivalent damit, daß C/-l,o(C/,0 + C/,1) — C/,()(C/-1,0 + C/-l,l) nichtnegative Koeffizienten hat. Diese ist aber nach obigem klar. 4 Ganz analog zeigt man, daß sich jeder Weg von (0,0) nach (2/7 + 2 m +1,1) in einen Weg von (0,0) nach (2n,2i) und einen Restweg von (2/7,2/) nach (2 n + 2m +1, 1) zerlegen läßt. Das Gewicht aller Restwege ist A('2\2m + 2,2/). Folglich gilt. A (2) (2/7, 2i)q~2i+'[A (2) (2m + 2, 2t) = .4(2) (2m + 2n + 1,1). /=l Setzt man nun D„j :=A^ (2/7,2/), so ist D0>/= <50/, D„$ = <5//0 und D„,, =^<2>(2»,2) =^<2>(2/;+l,l) = ?"C*(?2). Daher ergibt sich fl D„tiD„tiq-2,+1 =D„/+„_U . (21) /=1 Das kann wieder als eine entsprechende Matrixgleichung geschrieben werden, wo rechts eine Hankeimatrix mit q-Catalanzahlen auftritt. Für die Dnj zeigt man wie oben, daß die Rekurrenz = qA' 3(Dw_1/_1 + (1 + q2)Dn-\j + q2D„-\j+\),n > 0, / > 1 gilt mit D0 j = 8qj und D„q = 6„p. Bemerkung. Eine ähnliche Rekurrenz wurde auch in [5], (1) gefunden. Haben die die dort angegebene Bedeutung, so leitet man leicht ab, ©Akademie d. Wissenschaften Wien; download unter www.biologiezentrum.at daß die obige Aussage äquivalent ist mit E r (2)r (2) /+i _ r (2) ^ //,/' ^ n/,i 1 m+n— 15 /=1 wobei rechts wieder die üblichen q-Catalanzahlen von Carlitz auftreten. Man rechnet wieder leicht nach, daß D/v, = 1 )-3w und daher D2;/^_2//+1 = q(2n~^ ist. Daher ergibt sich für die Hankeimatrix der die Gleichung X > -i)2 det(D/+y_1)1)"y.=1 = q 1 Daraus ergibt sich wieder für die Carlitz’schen q-Catalanzahlen die Identität (22) Bemerkung. Durch die Gleichungen (18) und (22) für alle n sind die q-Catalanzahlen eindeutig festgelegt. Das verallgemeinert die bekannte Tatsache, daß für^ = l die entsprechenden Hankeimatrizen die Deter­ minante 1 besitzen und daß diese Eigenschaft die Catalanzahlen cha­ rakterisiert. Für r > 2 gibt es kein direktes Analogon zu (21), weil die Situation nicht mehr symmetrisch ist. Die entsprechenden Matrizen spielen aber auch hier eine wichtige Rolle. Dazu beachten wir, daß jeder positive Gitterweg von (0, 0) nach (rn + x, x) über einen eindeutig bestimmten Punkt der Form (rn, ri) = (r (n — i) + ri, ri) verläuft. Der Restweg liegt dabei in Vxj. Aus (4) folgt daher A ^ (rn + x, x) = A ^ ^ (rn, ri) q'x q"x G) ( 2) ^^A^'\rn, ri) ^(2)+'G) ©Akademie d. Wissenschaften Wien; download unter www.biologiezentrum.at Setzt man = A ^ (rn, ri), so endet jeder Weg von (0,0) nach (r/7, ri) mit einem Wort aus Vrk, 0 <k< r. Bei festem k ist j (' 2') (0 +;'2(1-^) (24) = Daher gilt £ C 21) +',2(l— J'(ri-r(\-k)) jjir) ^ = n— 1 1 +k Jk=0 und schließlich D(; h / ' - ('v ) £ D'nU ;,-\^n > !,/ > ! k=0 (>■) _ mit D^o = ^,o und DQj ^0,/- Bemerkung. Man kann dadurch auch einen anderen Zugang zu den Ergebnissen von [5] erhalten. Dort wurde in Gleichung (4) in etwas anderer Notation c\'](q) = G „--,{ri,r,q)qbetrachtet. Unter Verwen­ dung von (14) sieht man nun sofort, daß = q"^C^) (q') gilt. Denn die linke Seite ist^4^ (r/7, ri) = ^("“^Ü+U C„_/(r/, r, qr) =qll^c\'lJ (q'). Nun wollen wir die Situation, die zu (21) führte, auf andere Weise ver­ allgemeinern. Jeder Weg von (0,0) nach (r/7 + rm +1,1) läßt sich zerlegen in einen Weg von (0, 0) nach (r/7, ri) und einen Restweg von (r/7, ri) nach (r/7 + rm +1,1). Wir wollen nun das Gewicht E^+^ -t des Restweges bestim­ men. Dann gilt in Analogie zu (21) für /;? > 1 £ d^E % =A^\r(m + n - 1) + 1,1) (25) i=\ = A ^ (r(m + n — 1), r) = D^'^ E?w0' )i ist das Gewicht aller positiven Wege von (0, ri) nach (r(m — 1) + 1,1). Ein solcher Weg hat m — i-1-1 Abstiege und (r — \)(m — 1) + 1 — i Auf­ stiege. Das größte i, für welches ein solcher Weg existiert, ist i — (r — 1 )(m — 1) + 1. Das zu einem solchen Weg gehörende Wort beginnt mit einem Anfangswort aus V,-^. Da der Weg auf der Höhe ri beginnt, ist also nach (4) das Gewicht aller solchen Wege mit k Abstiegen gegeben durch q'"' [^] ©Akademie d. Wissenschaften Wien; download unter www.biologiezentrum.at Somit ergibt sich die folgende Rekursionsformel k=o mit den Randbedingungen E^] = 8\j und E)'Jj = 0 für i < 0. Man beachte, daß sich für r> 2 keine Dreiecksmatrizen mehr ergeben. Im Fall r= 2 rechnet man leicht nach, daß hier E^j = {D^Jq2'~X) gilt, sodaß (21) ein Spezialfall von (25) wird. Wir wollen noch auf eine andere Darstellung der Gewichte A ^’\rn + x,x) hinweisen. Dazu suchen wir in jedem Weg von (0, 0) nach (rn + x, x) den letzten Abstieg, vor welchem genau (r — 1 )n Aufstiege liegen. Dieses Anfangs­ stück hat also (r — 1 )n Aufstiege und eine gewisse Anzahl von Abstiegen, die wir in der Form n — k schreiben. Das Gewicht aller dieser Anfangs­ stücke ist A ^(rn — k, (r — l)/fc). Der Restweg ist ein Weg von (0, (r — l)k) nach (k + x, x), der mit einem Aufstieg beginnt und genau k Abstiege besitzt. Aus (5) folgt daher x + k — 1 A^\rn-{- x,x) = ^ ^A^\rn — k,(r— 1 )k)q^ ^('2 ) + G) k (27) Wir wollen jedoch auf diese Entwicklung hier nicht näher eingehen, weil analoge Dinge bereits in [6] mit anderen Methoden behandelt wurden. 7 Sei nun W,uk (x) die Menge aller Wörter der Gestalt (x_1)/fe+1 % G W„(x). Dann ist W„(x) = Wn$(x). Für (x_{)k x^ 1 zeigt man leicht die Identität ü>((x-\)kxj%) = 2 \v((x-\)k Sei nun Ak (n, x) := w(\W,ui,(x)\ Es ergibt sich Ak(n,x)=Ak-\{n,x) — ^2,w(xi)q{<k~l^,+^ ( 2 ^Ak-,-\(n— 1 ,x). ;>o