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
Robert Israel, Table of n, a(n) for n = 0..1700
Eric S. Egge, Kailee Rubin, Snow Leopard Permutations and Their Even and Odd Threads, arXiv:1508.05310 [math.CO], 2015.
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
From Gary W. Adamson, Jan 30 2012: (Start)
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).
From Gus Wiseman, Aug 14 2018: (Start)
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):
seq(P(n), n=0..50); # Robert Israel, Aug 24 2015
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}];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Jul 21 2018, after Vladimir Kruchinin *)
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
Emeric Deutsch, Jan 06 2005
STATUS
approved