|
%I #36 Aug 26 2018 13:22:01
%S 1,1,1,2,6,17,46,128,372,1109,3349,10221,31527,98178,308179,973911,
%T 3096044,9894393,31770247,102444145,331594081,1077022622,3509197080,
%U 11466710630,37567784437,123380796192,406120349756,1339571374103
%N Number of Dyck paths of semilength n having no ascents of length 2.
%C 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).
%C 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
%H Robert Israel, <a href="/A102403/b102403.txt">Table of n, a(n) for n = 0..1700</a>
%H Eric S. Egge, Kailee Rubin, <a href="http://arxiv.org/abs/1508.05310">Snow Leopard Permutations and Their Even and Odd Threads</a>, arXiv:1508.05310 [math.CO], 2015.
%H <a href="/index/Lu#Lukasiewicz">Index entries for sequences related to Łukasiewicz</a>
%F G.f.: G=G(z) satisfies z^3*G^3 + z(1-z)G^2 - G + 1 = 0.
%F 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
%F From _Gary W. Adamson_, Jan 30 2012: (Start)
%F a(n) is the upper left term in M^n, M = an infinite square production matrix as follows:
%F 1, 1, 0, 0, 0, 0, ...
%F 0, 1, 1, 0, 0, 0, ...
%F 1, 0, 1, 1, 0, 0, ...
%F 1, 1, 0, 1, 1, 0, ...
%F 1, 1, 1, 0, 1, 1, ... (End)
%F (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
%F 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
%F 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
%e 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).
%e From _Gus Wiseman_, Aug 14 2018: (Start)
%e The a(5) = 17 series-reduced Mathematica expressions:
%e o[o[][],o]
%e o[o,o[][]]
%e o[o[],o[]]
%e o[o[],o,o]
%e o[o,o[],o]
%e o[o,o,o[]]
%e o[o,o,o,o]
%e o[][o[],o]
%e o[][o,o[]]
%e o[][o,o,o]
%e o[][][o,o]
%e o[o[],o][]
%e o[o,o[]][]
%e o[o,o,o][]
%e o[][o,o][]
%e o[o,o][][]
%e o[][][][][]
%e The a(5) = 17 rooted plane trees with no binary branchings:
%e (((((o)))))
%e (((ooo)))
%e (((o)oo))
%e ((o(o)o))
%e ((oo(o)))
%e ((oooo))
%e (((o))oo)
%e (o((o))o)
%e (oo((o)))
%e ((o)(o)o)
%e ((o)o(o))
%e (o(o)(o))
%e ((o)ooo)
%e (o(o)oo)
%e (oo(o)o)
%e (ooo(o))
%e (ooooo)
%e (End)
%p 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 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):
%p seq(P(n),n=0..50); # _Robert Israel_, Aug 24 2015
%t 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}];
%t Table[a[n], {n, 0, 30}] (* _Jean-François Alcover_, Jul 21 2018, after _Vladimir Kruchinin_ *)
%o (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
%o (PARI) Vec( serreverse( O(x^33) + x/(1+x/(1-x)-x^2) ) /x ) \\ _Joerg Arndt_, Apr 28 2016
%Y Cf. A000108, A001003, A001006, A007853, A102402, A126120, A318049.
%K nonn
%O 0,4
%A _Emeric Deutsch_, Jan 06 2005
|
