

A140717


Triangle read by rows: T(n,k) is the number of Dyck paths d of semilength n such that sum of peakheights of d  number of peaks of d = k (n >= 0, 0 <= k <= floor(n^2/4)).


1



1, 1, 1, 1, 1, 2, 2, 1, 3, 5, 4, 1, 1, 4, 9, 12, 10, 4, 2, 1, 5, 14, 25, 31, 26, 16, 9, 4, 1, 1, 6, 20, 44, 70, 82, 74, 54, 38, 22, 12, 4, 2, 1, 7, 27, 70, 134, 196, 227, 215, 179, 139, 99, 64, 38, 20, 9, 4, 1, 1, 8, 35, 104, 231, 400, 558, 644, 641, 576, 488, 384, 288, 200, 134, 80
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,6


COMMENTS

T(n,k) is the number of 321avoiding permutations of {1,2,...,n} having inversion number equal to k. Example: T(4,2) = 5 because we have 1423, 1342, 3124, 2143 and 2341.


LINKS

Alois P. Heinz, Rows n = 0..50, flattened
E. Barcucci, A. Del Lungo, E. Pergola and R. Pinzani, ECO: a methodology for the enumeration of combinatorial objects, Journal of Difference Equations and Applications, 5, 1999, 435490.
E. Barcucci, A. Del Lungo, E. Pergola and R. Pinzani, Some permutations with forbidden subsequences and their inversion number, Discrete Math., 234, 2001, 115.
E. Deutsch, Dyck path enumeration, Discrete Math., 204, 1999, 167202 (see section 5).
G. Feinberg, K.H. Lee, Homogeneous representations of KLRalgebras and fully commutative elements, arXiv preprint arXiv:1401.0845 [math.RT], 20142015.
Niket Gowravaram and Tanya Khovanova, On the Structure of nilTemperleyLieb Algebras of type A, arXiv:1509.00462 [math.CO], 2015.


FORMULA

G.f.: G(t,z) = H(t,1/t,z), where H(t,x,z) = 1 + zH(t,x,z)[H(t,tx,z)1+tx] (H(t,x,z) is the trivariate g.f. of Dyck paths with respect to semilength, sum of peakheights and number of peaks, marked by z, t and x, respectively).
Sum_{k>=0} k*T(n,k) = A008549(n1).
Row n has 1 + floor(n^2/4) entries.


EXAMPLE

T(4,2) = 5 because we have UDUUDUDD (5  3 = 2), UDUUUDD (4  2 = 2), UUDDUUDD (4  2 = 2), UUDUDDUD (5  3 = 2) and UUUDDDUD (4  2 = 2); here U = (1,1), D = (1,1).
Triangle starts:
1;
1;
1, 1;
1, 2, 2;
1, 3, 5, 4, 1;
1, 4, 9, 12, 10, 4, 2;
1, 5, 14, 25, 31, 26, 16, 9, 4, 1;


MAPLE

H := 1/(1+zt*x*zz*h[1]):
for n to 13 do h[n]:=1/(1+zx*t^(n+1)*zz*h[n+1]) end do:
G := subs({h[11]=0, x=1/t}, H): Gser := simplify(series(G, z=0, 12)):
for n from 0 to 9 do P[n] := sort(coeff(Gser, z, n)) end do:
for n from 0 to 9 do seq(coeff(P[n], t, j), j=0..floor((1/4)*n^2)) end do;
# yields sequence in triangular form


MATHEMATICA

m = rows = 10; mt = 2 m + 1; mx = mz = m  1;
H[_, _, _] = 0; Do[H[t_, x_, z_] = Series[1 + z (H[t, t x, z]  1 + t x) H[t, x, z], {t, 0, mt}, {x, 0, mx}, {z, 0, mz}] // Normal, {m}];
G[t_, z_] = Series[H[t, 1/t, z], {t, 0, mt}, {z, 0, mz}] // Normal // Collect[#, z]&;
CoefficientList[#, t]& /@ CoefficientList[G[t, z], z] // Take[#, m]& // Flatten (* JeanFrançois Alcover, Nov 25 2018 *)


CROSSREFS

Row sums are the Catalan numbers A000108.
Cf. A008549, A129183.
Sequence in context: A054336 A284644 A079956 * A257005 A160232 A026300
Adjacent sequences: A140714 A140715 A140716 * A140718 A140719 A140720


KEYWORD

nonn,tabf


AUTHOR

Emeric Deutsch, Jun 08 2008


STATUS

approved



