|
Search: id:A112412
|
|
|
| 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. |
|
+0
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
(list; graph; listen)
|
|
|
OFFSET
|
0,3
|
|
|
REFERENCES
|
R. P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge Univ. Press, Cambridge, 1999, p. 179.
|
|
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).
|
|
PROGRAM
|
(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: A120895 A101785 A003089 this_sequence A125023 A129804 A110035
Adjacent sequences: A112409 A112410 A112411 this_sequence A112413 A112414 A112415
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Emeric Deutsch (deutsch(AT)duke.poly.edu), Dec 08 2005
|
|
|
Search completed in 0.002 seconds
|
