login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

%I #21 Nov 26 2018 04:24:50

%S 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,

%T 20,44,70,82,74,54,38,22,12,4,2,1,7,27,70,134,196,227,215,179,139,99,

%U 64,38,20,9,4,1,1,8,35,104,231,400,558,644,641,576,488,384,288,200,134,80

%N 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)).

%C T(n,k) is the number of 321-avoiding 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.

%H Alois P. Heinz, <a href="/A140717/b140717.txt">Rows n = 0..50, flattened</a>

%H E. Barcucci, A. Del Lungo, E. Pergola and R. Pinzani, <a href="https://doi.org/10.1080/10236199908808200">ECO: a methodology for the enumeration of combinatorial objects</a>, Journal of Difference Equations and Applications, 5, 1999, 435-490.

%H E. Barcucci, A. Del Lungo, E. Pergola and R. Pinzani, <a href="https://doi.org/10.1016/S0012-365X(00)00359-9">Some permutations with forbidden subsequences and their inversion number</a>, Discrete Math., 234, 2001, 1-15.

%H E. Deutsch, <a href="http://dx.doi.org/10.1016/S0012-365X(98)00371-9">Dyck path enumeration</a>, Discrete Math., 204, 1999, 167-202 (see section 5).

%H G. Feinberg, K.-H. Lee, <a href="http://arxiv.org/abs/1401.0845">Homogeneous representations of KLR-algebras and fully commutative elements</a>, arXiv preprint arXiv:1401.0845 [math.RT], 2014-2015.

%H Niket Gowravaram and Tanya Khovanova, <a href="http://arxiv.org/abs/1509.00462">On the Structure of nil-Temperley-Lieb Algebras of type A</a>, arXiv:1509.00462 [math.CO], 2015.

%F 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 peak-heights and number of peaks, marked by z, t and x, respectively).

%F Sum_{k>=0} k*T(n,k) = A008549(n-1).

%F Row n has 1 + floor(n^2/4) entries.

%e 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).

%e Triangle starts:

%e 1;

%e 1;

%e 1, 1;

%e 1, 2, 2;

%e 1, 3, 5, 4, 1;

%e 1, 4, 9, 12, 10, 4, 2;

%e 1, 5, 14, 25, 31, 26, 16, 9, 4, 1;

%p H := 1/(1+z-t*x*z-z*h[1]):

%p for n to 13 do h[n]:=1/(1+z-x*t^(n+1)*z-z*h[n+1]) end do:

%p G := subs({h[11]=0,x=1/t},H): Gser := simplify(series(G,z=0,12)):

%p for n from 0 to 9 do P[n] := sort(coeff(Gser,z,n)) end do:

%p for n from 0 to 9 do seq(coeff(P[n],t,j), j=0..floor((1/4)*n^2)) end do;

%p # yields sequence in triangular form

%t m = rows = 10; mt = 2 m + 1; mx = mz = m - 1;

%t 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}];

%t G[t_, z_] = Series[H[t, 1/t, z], {t, 0, mt}, {z, 0, mz}] // Normal // Collect[#, z]&;

%t CoefficientList[#, t]& /@ CoefficientList[G[t, z], z] // Take[#, m]& // Flatten (* _Jean-François Alcover_, Nov 25 2018 *)

%Y Row sums are the Catalan numbers A000108.

%Y Cf. A008549, A129183.

%K nonn,tabf

%O 0,6

%A _Emeric Deutsch_, Jun 08 2008

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 19 04:58 EDT 2024. Contains 370952 sequences. (Running on oeis4.)