login
This site is supported by donations 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
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 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.

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

Row sums are the Catalan numbers (A000108).

Sum(k*T(n,k), k>=0)=A008549(n-1).

REFERENCES

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, 435-490.

E. Barcucci, A. Del Lungo, E. Pergola and R. Pinzani, Some permutations with forbidden subsequences and their inversion number, Discrete Math., 234, 2001, 1-15.

E. Deutsch, Dyck path enumeration, Discrete Math., 204, 1999, 167-202 (see section 5).

LINKS

Alois P. Heinz, Rows n = 0..50, flattened

G. Feinberg, K.-H. Lee, Homogeneous representations of KLR-algebras and fully commutative elements, arXiv preprint arXiv:1401.0845, 2014

Niket Gowravaram and Tanya Khovanova, On the Structure of nil-Temperley-Lieb Algebras of type A, arXiv:1509.00462, 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 peak-heights and number of peaks, marked by z, t and x, respectively).

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+z-t*x*z-z*h[1]): for n to 13 do h[n]:=1/(1+z-x*t^(n+1)*z-z*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

CROSSREFS

Cf. A000108, 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

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

License Agreements, Terms of Use, Privacy Policy .

Last modified February 19 13:25 EST 2018. Contains 299333 sequences. (Running on oeis4.)