A243882 Number of Dyck paths of semilength n such that all eight consecutive step patterns of length 3 occur at least once.

1, 21, 124, 636, 2749, 11265, 44028, 168673, 636526, 2385703, 8903294, 33177968, 123602040, 460821006, 1720240295, 6432225711, 24095079682, 90435264009, 340097165156, 1281506663877, 4838093967400, 18299480354681, 69340086808691, 263195643048634

Offset: 5

Author

Alois P. Heinz, Jun 13 2014

Keywords

• nonn

Examples

			a(5) = 1: 1011100010.
a(6) = 21: 101011100010, 101110001010, 101110100010, 101111000010, 101111000100, 101111001000, 110010111000, 110011101000, 110100111000, 110111000010, 110111000100, 110111001000, 111000101100, 111000110100, 111001011000, 111001101000, 111010001100, 111010011000, 111011000010, 111011000100, 111011001000.
Here 1=Up=(1,1), 0=Down=(1,-1).
		

Links

• Alois P. Heinz and Vaclav Kotesovec, Table of n, a(n) for n = 5..1000 (first 500 terms from Alois P. Heinz)
• Vaclav Kotesovec, Recurrence (of order 14)

Crossrefs

Cf. A242167, A243820.

Programs

Maple

b:= proc(x, y, t, s) option remember; `if`(y<0 or y>x, 0,
      `if`(x=0, `if`(s={}, 1, 0), `if`(nops(s)>x, 0, add(
      b(x-1, y-1+2*j, irem(2*t+j, 4), s minus {2*t+j}), j=0..1))))
    end:
a:= n-> add(b(2*n-2, l[], {$0..7}), l=[[0, 2], [2, 3]]):
seq(a(n), n=5..35);

Mathematica

b[x_, y_, t_, s_List] := b[x, y, t, s] = If[y<0 || y>x, 0, If[x == 0, If[s == {}, 1, 0], If[Length[s]>x, 0, Sum[b[x-1, y-1 + 2*j, Mod[2*t+j, 4], s ~Complement~ {2*t + j}], {j, 0, 1}]]]]; a[n_] :=  Sum[b[2*n-2, Sequence @@ l, Range[0, 7]], {l, {{0, 2}, {2, 3}}}]; Table[a[n], {n, 5, 35}] (* Jean-François Alcover, Feb 05 2015, after Alois P. Heinz *)

Formula

a(n) ~ 4^n / (sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Jun 15 2014