|
| |
|
|
A102403
|
|
Number of Dyck paths of semilength n having no ascents of length 2.
|
|
5
|
|
|
|
1, 1, 1, 2, 6, 17, 46, 128, 372, 1109, 3349, 10221, 31527, 98178, 308179, 973911, 3096044, 9894393, 31770247, 102444145, 331594081, 1077022622, 3509197080, 11466710630, 37567784437, 123380796192, 406120349756, 1339571374103
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,4
|
|
|
COMMENTS
|
Number of Lukasiewicz paths of length n having no (1,1) steps. A Lukasiewicz path of length n is a path in the first quadrant from (0,0) to (n,0) using rise steps (1,k) for any positive integer k, level steps (1,0) and fall steps (1,-1) (see R. P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge Univ. Press, Cambridge, 1999, p. 223, Exercise 6.19w; the integers are the slopes of the steps). Example: a(4)=6 because we have HHHH, HU(2)DD, U(2)DDH, U(2)DHD, U(2)HDD and U(3)DDD where H=(1,0), U(2)=(1,2), U(3)=(1,3) and D=(1,-1).
|
|
|
LINKS
|
Table of n, a(n) for n=0..27.
|
|
|
FORMULA
|
G.f.=G=G(z) satisfies z^3*G^3+z(1-z)G^2-G+1=0.
a(n)=1/n*sum(j=ceiling((n+2)/3)..n, binomial(n,j)*binomial(3*j-n-2,j-1)*(-1)^(n-j)), n>0. [From Vladimir Kruchinin, Mar 07 2011].
a(n) is the upper left term in M^n, M = an infinite square production matrix as follows:
1, 1, 0, 0, 0, 0,...
0, 1, 1, 0, 0, 0,...
1, 0, 1, 1, 0, 0,...
1, 1, 0, 1, 1, 0,...
1, 1, 1, 0, 1, 1,...
- Gary W. Adamson, Jan 30 2012
|
|
|
EXAMPLE
|
a(3)=2 because we have UDUDUD and UUUDDD, where U=(1,1) and D=(1,-1); the other three Dyck paths of semilength 3, namely UD(UU)DD, (UU)DDUD and (UU)DUDD, have ascents of length 2 (shown between parentheses).
|
|
|
MAPLE
|
Order:=35: S:=solve(series(V*(1-V)/(1-V^2+V^3), V)=z, V): seq(coeff(S, z^n), n=1..33); # V=zG
|
|
|
PROG
|
(Maxima)
a102403(n):=1/n*sum(binomial(n, j)*binomial(3*j-n-2, j-1)*(-1)^(n-j), j, ceiling((n+2)/3), n); [From Vladimir Kruchinin, Mar 07 2011].
|
|
|
CROSSREFS
|
Cf. A102402.
Sequence in context: A109961 A190050 A005592 * A200379 A032638 A090039
Adjacent sequences: A102400 A102401 A102402 * A102404 A102405 A102406
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
Emeric Deutsch, Jan 06 2005
|
|
|
STATUS
|
approved
|
| |
|
|
