cp's OEIS Frontend

A102403 Number of Dyck paths of semilength n having no ascents of length 2.

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