|
| |
|
|
A102403
|
|
Number of Dyck paths of semilength n having no ascents of length 2.
|
|
10
|
|
|
|
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 Łukasiewicz paths of length n having no (1,1) steps. A Łukasiewicz 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).
Also the number of series-reduced Mathematica expressions with one atom and n + 1 positions. Also the number of rooted plane trees with n + 1 nodes in which there are no binary branchings (nodes of out-degree 2). - Gus Wiseman, Aug 14 2018
|
|
|
LINKS
|
|
|
|
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. - 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, ... (End)
(69*n^2+207*n+138)*a(n) + (97*n^2+609*n+830)*a(n+1) + (-38*n^2-342*n-694)*a(n+2) + (37*n^2+333*n+734)*a(n+3) + (2*n^2+18*n+34)*a(n+4) + (-7*n^2-87*n-266)*a(n+5) + (n^2+15*n+56)*a(n+6) = 0. - Robert Israel, Aug 24 2015
Recurrence (of order 4): (n+1)*(n+2)*(28*n^2 - 32*n - 39)*a(n) = 4*(n+1)*(14*n^3 - 9*n^2 - 62*n + 39)*a(n-1) + (140*n^4 - 160*n^3 - 401*n^2 + 469*n - 78)*a(n-2) - 12*(n-2)*(14*n^3 - 9*n^2 - 28*n - 8)*a(n-3) + 23*(n-3)*(n-2)*(28*n^2 + 24*n - 43)*a(n-4). - Vaclav Kotesovec, Mar 06 2016
a(n) ~ s * sqrt((1 - 2*r + 3*r^2*s)/(1 - r + 3*r^2*s)) /(2*sqrt(Pi)*n^(3/2)*r^n), where r = 0.2869905464691794898... and s = 1.850270202250705342... are roots of the system of equations 3*r^3*s^2 = 1 + 2*(-1 + r)*r*s, 1 + r^3*s^3 = s + (-1 + r)*r*s^2. - Vaclav Kotesovec, Mar 06 2016
|
|
|
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).
The a(5) = 17 series-reduced Mathematica expressions:
o[o[][],o]
o[o,o[][]]
o[o[],o[]]
o[o[],o,o]
o[o,o[],o]
o[o,o,o[]]
o[o,o,o,o]
o[][o[],o]
o[][o,o[]]
o[][o,o,o]
o[][][o,o]
o[o[],o][]
o[o,o[]][]
o[o,o,o][]
o[][o,o][]
o[o,o][][]
o[][][][][]
The a(5) = 17 rooted plane trees with no binary branchings:
(((((o)))))
(((ooo)))
(((o)oo))
((o(o)o))
((oo(o)))
((oooo))
(((o))oo)
(o((o))o)
(oo((o)))
((o)(o)o)
((o)o(o))
(o(o)(o))
((o)ooo)
(o(o)oo)
(oo(o)o)
(ooo(o))
(ooooo)
(End)
|
|
|
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
P:= gfun:-rectoproc({(69*n^2+207*n+138)*a(n)+(97*n^2+609*n+830)*a(n+1)+(-38*n^2-342*n-694)*a(n+2)+(37*n^2+333*n+734)*a(n+3)+(2*n^2+18*n+34)*a(n+4)+(-7*n^2-87*n-266)*a(n+5)+(n^2+15*n+56)*a(n+6), a(0)=1, a(1)=1, a(2)=1, a(3)=2, a(4)=6, a(5)=17}, a(n), remember):
|
|
|
MATHEMATICA
|
a[n_] := 1/(n+1) Sum[Binomial[n+1, j] Binomial[3j-n-3, j-1] (-1)^(n+1-j), {j, n+1, (n+3)/3, -1}];
|
|
|
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); \\ Vladimir Kruchinin, Mar 07 2011
(PARI) Vec( serreverse( O(x^33) + x/(1+x/(1-x)-x^2) ) /x ) \\ Joerg Arndt, Apr 28 2016
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
