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
Keywords
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
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
Comments