cp's OEIS Frontend

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

%I A243882 #17 Feb 05 2015 09:15:47
%S A243882 1,21,124,636,2749,11265,44028,168673,636526,2385703,8903294,33177968,
%T A243882 123602040,460821006,1720240295,6432225711,24095079682,90435264009,
%U A243882 340097165156,1281506663877,4838093967400,18299480354681,69340086808691,263195643048634
%N A243882 Number of Dyck paths of semilength n such that all eight consecutive step patterns of length 3 occur at least once.
%H A243882 Alois P. Heinz and Vaclav Kotesovec, <a href="/A243882/b243882.txt">Table of n, a(n) for n = 5..1000</a> (first 500 terms from Alois P. Heinz)
%H A243882 Vaclav Kotesovec, <a href="/A243882/a243882.txt">Recurrence (of order 14)</a>
%F A243882 a(n) ~ 4^n / (sqrt(Pi) * n^(3/2)). - _Vaclav Kotesovec_, Jun 15 2014
%e A243882 a(5) = 1: 1011100010.
%e A243882 a(6) = 21: 101011100010, 101110001010, 101110100010, 101111000010, 101111000100, 101111001000, 110010111000, 110011101000, 110100111000, 110111000010, 110111000100, 110111001000, 111000101100, 111000110100, 111001011000, 111001101000, 111010001100, 111010011000, 111011000010, 111011000100, 111011001000.
%e A243882 Here 1=Up=(1,1), 0=Down=(1,-1).
%p A243882 b:= proc(x, y, t, s) option remember; `if`(y<0 or y>x, 0,
%p A243882       `if`(x=0, `if`(s={}, 1, 0), `if`(nops(s)>x, 0, add(
%p A243882       b(x-1, y-1+2*j, irem(2*t+j, 4), s minus {2*t+j}), j=0..1))))
%p A243882     end:
%p A243882 a:= n-> add(b(2*n-2, l[], {$0..7}), l=[[0, 2], [2, 3]]):
%p A243882 seq(a(n), n=5..35);
%t A243882 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_ *)
%Y A243882 Cf. A242167, A243820.
%K A243882 nonn
%O A243882 5,2
%A A243882 _Alois P. Heinz_, Jun 13 2014