|
| |
|
|
A114509
|
|
Number of Dyck paths of semilength n having no ascents of length 4.
|
|
3
| |
|
|
1, 1, 2, 5, 13, 37, 111, 345, 1104, 3611, 12016, 40548, 138414, 477076, 1657956, 5802920, 20436910, 72369903, 257518806, 920333307, 3302003826, 11888979066, 42944410207, 155576009845, 565127618392, 2057903975752, 7510967300206
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,3
|
|
|
COMMENTS
| Also number of ordered trees with n edges that have no vertices of outdegree 4.
|
|
|
FORMULA
| G.f. G=G(z) satisfies z^5*G^5-z^4*G^4+zG^2-G+1=0.
a(n):=1/n*sum(j=ceiling((3*n+2)/5)..n, binomial(n,j)*binomial(5*j-3*n-2,j-1)*(-1)^(n-j)), n>0 [From Vladimir Kruchinin, Mar 07 2011]
|
|
|
EXAMPLE
| a(4)=13 because among the Catalan(4)=14 Dyck paths of semilength 4 only UUUUDDDD has an ascent of length 4 (here U=(1,1), D=(1,-1)).
|
|
|
MAPLE
| Order:=35: Y:=solve(series((Y-Y^2)/(1-Y^4+Y^5), Y)=z, Y): seq(coeff(Y, z^n), n=1..30); #(Y=zG)
|
|
|
PROG
| (Maxima)
a114509(n):=1/n*sum(binomial(n, j)*binomial(5*j-3*n-2, j-1)*(-1)^(n-j), j, ceiling((3*n+2)/5), n); [From Vladimir Kruchinin, Mar 07 2011]
|
|
|
CROSSREFS
| Cf. A102403, A114507, A114508.
Sequence in context: A126031 A151416 A193114 * A003080 A149854 A151442
Adjacent sequences: A114506 A114507 A114508 * A114510 A114511 A114512
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| Emeric Deutsch (deutsch(AT)duke.poly.edu), Dec 03 2005
|
| |
|
|
