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

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

Offset: 0

Author

Emeric Deutsch, Jan 06 2005

Keywords

• nonn

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

Examples

			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)
		

Links

• Robert Israel, Table of n, a(n) for n = 0..1700
• Eric S. Egge and Kailee Rubin, Snow Leopard Permutations and Their Even and Odd Threads, arXiv:1508.05310 [math.CO], 2015.
• Index entries for sequences related to Łukasiewicz

Crossrefs

Cf. A000108, A001003, A001006, A007853, A102402, A126120, A318049.

Programs

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 *)

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

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