A112412 Number of Dyck paths of semilength n for which the number of ascents of length 1 is equal to the number of descents of length 1.

1, 1, 2, 5, 12, 30, 82, 237, 708, 2188, 6980, 22814, 75994, 257266, 883006, 3065757, 10748620, 38005844, 135385700, 485439532, 1750738084, 6347006468, 23118315044, 84565309214, 310536661002, 1144393816154, 4231119156334

Offset

0,3

Comments

Apparently: Number of Dyck n-paths with equal numbers of peaks to the left and to the right of the midpoint (ordinate x=n). - David Scambler, Aug 08 2012

References

R. P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge Univ. Press, Cambridge, 1999, p. 179.

Links

Table of n, a(n) for n=0..26.

Formula

G.f. is the diagonal of g(t, s, z), where g=g(t, s, z) is defined by z(1+tz-tsz)(1+sz-tsz)g^2 - [1+(1-ts)z-(1-t)(1-s)z^2]g+1=0 (g is the trivariate g.f. of Dyck paths, where z marks semilength and t (s) marks number of ascents (descents) of length 1.

Example

a(4)=12 because among the 14 Dyck paths of semilength 4 the only
counterexamples are UUDUUDDD and UUUDDUDD, where U=(1,1), D=(1,-1).

Prog

(PARI) z=x; s; t; f(g) = z*(1+t*z-t*s*z)*(1+s*z-t*s*z)*g^2-(1+(1-t*s)*z-(1-t)*(1-s)*z^2)*g+1 nxt(fx) = fx=truncate(fx); fx+=O(x^2)*x^poldegree(fx); fx+=f(fx) oo=30; g=1+O(z); for(n=1, oo, g=nxt(g)); g1=polcoeff(subst(subst(g, s, y), t, 1/y), 0, y); for(n=0, oo, print(n" "polcoeff(g1, n)))

Crossrefs

Sequence in context: A182488 A363912 A261788 * A309506 A319557 A261937

Adjacent sequences: A112409 A112410 A112411 * A112413 A112414 A112415

Keyword

nonn

Author

Emeric Deutsch, Dec 08 2005

Status

approved