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

%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