A191519 Number of dispersed Dyck paths of semilength n (i.e., Motzkin paths of length n with no (1,0)-steps at positive heights) having no UUU's (U=(1,1)).

1, 1, 2, 3, 6, 10, 19, 33, 62, 110, 205, 368, 683, 1235, 2286, 4153, 7674, 13986, 25813, 47150, 86949, 159077, 293176, 537014, 989267, 1813659, 3339940, 6127355, 11280954, 20706414, 38114723, 69988457, 128809594, 236602202, 435400253, 799958582, 1471961037

Offset

0,3

Comments

a(n) = A191518(n,0).

Links

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Formula

G.f.: 2/(1-2*x-x^2+sqrt(1-2*x^2-3*x^4)).

a(n-1)=sum(m=floor((n+1)/2)..n, ((2*m-n)*sum(j=0..m, binomial(j,n+2*j-3*m)*binomial(m,j)))/m). [Vladimir Kruchinin, Mar 09 2013]

D-finite with recurrence (n+1)*a(n) +(-n-1)*a(n-1) +3*(-n+1)*a(n-2) +(n-5)*a(n-3) +(-n+11)*a(n-4) +(5*n-19)*a(n-5) +3*(n-5)*a(n-6) +3*(n-5)*a(n-7)=0. - R. J. Mathar, Jul 24 2022

Example

a(6) = 19 because among the 20 (=A001405(6)) dispersed Dyck paths of length 6 only UUUDDD has a UUU (U=(1,1), D=(1,-1)).

Maple

g := 2/(1-2*z-z^2+sqrt(1-2*z^2-3*z^4)): gser := series(g, z = 0, 40): seq(coeff(gser, z, n), n = 0 .. 36);
# second Maple program:
a:= proc(n) option remember;
      `if`(n<7, [1, 1, 2, 3, 6, 10, 19][n+1],
      ((n+1)*a(n-1)+(3*n-3)*a(n-2)-(n-5)*a(n-3)
      +(n-11)*a(n-4)-(5*n-19)*a(n-5)-(3*n-15)*a(n-6)
      -(3*n-15)*a(n-7))/(n+1))
    end:
seq(a(n), n=0..50);  # Alois P. Heinz, Jun 02 2014

Mathematica

a[n_] := Sum[((2*m-n-1)*Sum[Binomial[j, n+2*j-3*m+1]*Binomial[m, j], {j, 0, m}])/m, {m, Floor[(n+2)/2], n+1}]; Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Mar 31 2015, after Vladimir Kruchinin *)

Crossrefs

Cf. A001405, A191518.

Sequence in context: A136752 A093126 A003237 * A165920 A274160 A190501

Adjacent sequences: A191516 A191517 A191518 * A191520 A191521 A191522

Keyword

nonn

Author

Emeric Deutsch, Jun 07 2011

Status

approved