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,2

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)

Formula

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

Example

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

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

Crossrefs

Cf. A242167, A243820.

Sequence in context: A179956 A117388 A053052 * A002299 A303807 A304854

Adjacent sequences: A243879 A243880 A243881 * A243883 A243884 A243885

Keyword

nonn

Author

Alois P. Heinz, Jun 13 2014

Status

approved