OFFSET
0,3
COMMENTS
The consecutive patterns 101010, 101100, 110010, 110100, 111000 are avoided. Here 1=Up=(1,1), 0=Down=(1,-1).
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..1000
FORMULA
Recurrence: see Maple program.
a(n) ~ c * d^n / n^(3/2), where d = 2.97831791935148503707065... is the root of the equation 4 + 12*d + 9*d^2 - 8*d^3 - 28*d^4 - 32*d^5 - 14*d^6 + 10*d^7 + 30*d^8 + 24*d^9 + 13*d^10 - 2*d^11 - 5*d^12 - 2*d^13 + d^14 = 0, c = 0.232860224447544532825428... . - Vaclav Kotesovec, Sep 06 2014
EXAMPLE
a(n) = A000108(n) for n<3.
a(3) = 0 because no Dyck path of semilength 3 can avoid itself.
a(4) = 1: 11001100.
a(5) = 1: 1110011000.
a(6) = 4: 101110011000, 110011001100, 111001100010, 111100110000.
a(7) = 11: 10101110011000, 10111001100010, 10111100110000, 11001110011000, 11011100110000, 11100110001010, 11100110001100, 11100110011000, 11110011000010, 11110011000100, 11111001100000.
MAPLE
a:= proc(n) option remember; `if`(n<18, [1$2, 2, 0, 1$2, 4, 11, 29,
81, 220, 608, 1676, 4633, 12847, 35685, 99367, 277256][n+1],
((4*n-80)*a(n-18) +(16*n-302)*a(n-17) +(17*n-295)*a(n-16)
-(15*n-273)*a(n-15) -(61*n-971)*a(n-14) -(73*n-1043)*a(n-13)
-(19*n-191)*a(n-12) +(64*n-857)*a(n-11) +(114*n-1281)*a(n-10)
+(90*n-855)*a(n-9) +(11*n-40)*a(n-8) -(53*n-433)*a(n-7)
-(74*n-478)*a(n-6) -(42*n-225)*a(n-5) -(7*n-50)*a(n-4)
+(10*n-17)*a(n-3) +(6*n-12)*a(n-2) +(n-2)*a(n-1))/(n+1))
end:
seq(a(n), n=0..40);
MATHEMATICA
b[x_, y_, t_] := b[x, y, t] = If[y<0 || y>x, 0, If[x == 0, 1, Expand[ Sum[b[x - 1, y - 1 + 2j, Mod[2t + j, 32]]*If[MemberQ[{42, 44, 50, 52, 56}, 2t + j], z, 1], {j, 0, 1}]]]];
a[n_] := Coefficient[b[2n, 0, 0], z, 0];
CROSSREFS
KEYWORD
nonn
AUTHOR
Alois P. Heinz, Jun 16 2014
STATUS
approved