A243986 Number of Dyck paths of semilength n avoiding all five consecutive patterns of Dyck paths of semilength 3.

1, 1, 2, 0, 1, 1, 4, 11, 29, 81, 220, 608, 1676, 4633, 12847, 35685, 99367, 277256, 775197, 2171691, 6095329, 17138861, 48274370, 136197884, 384868351, 1089211676, 3087038820, 8761410780, 24898994687, 70850054269, 201848300443, 575723018363, 1643931888516

Offset: 0

Author

Alois P. Heinz, Jun 16 2014

Keywords

• nonn

Comments

The consecutive patterns 101010, 101100, 110010, 110100, 111000 are avoided. Here 1=Up=(1,1), 0=Down=(1,-1).

Examples

			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.
		

Links

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

Crossrefs

Column k=0 of A243998.

Cf. A000108, A014486, A063171, A243966.

Programs

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];
a /@ Range[0, 40] (* Jean-François Alcover, Dec 21 2020, after Alois P. Heinz in A243998 *)

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