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

Crossrefs

Column k=0 of A243998.

Cf. A000108, A014486, A063171, A243966.

Sequence in context: A235955 A077762 A244677 * A322838 A085496 A228748

Adjacent sequences: A243983 A243984 A243985 * A243987 A243988 A243989

Keyword

nonn

Author

Alois P. Heinz, Jun 16 2014

Status

approved