A243986 -id:A243986 - cp's OEIS frontend

A243966 Number of Dyck paths of semilength n such that all five consecutive patterns of Dyck paths of semilength 3 occur at least once.

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 12, 138, 1152, 8166, 52098, 308964, 1733444, 9311300, 48280464, 243112106, 1194286106, 5744306228, 27129749648, 126111332862, 578106334718, 2617667137358, 11723920607410, 51998857149406, 228621028644376, 997286152915772

Offset: 0

Alois P. Heinz, Jun 16 2014

nonn

The five consecutive patterns that occur at least once each are 101010, 101100, 110010, 110100, 111000. Here 1=Up=(1,1), 0=Down=(1,-1).

			a(12) = 12: 101010110010110100111000, 101010110010111000110100, 101100101010110100111000, 101100101010111000110100, 110100101010110010111000, 110100101100101010111000, 110100111000101010110010, 110100111000101100101010, 111000101010110010110100, 111000101100101010110100, 111000110100101010110010, 111000110100101100101010.
Here 1=Up=(1,1), 0=Down=(1,-1).

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

Cf. A014486, A063171, A243820, A243965, A243986.

b:= proc(x, y, l) option remember; local m; m:= min(l[]);
      `if`(y>x or y<0 or 7-m>x, 0, `if`(x=0, 1,
      b(x-1, y+1, [[2, 3, 4, 4, 2, 2, 7][l[1]],
       [2, 3, 3, 5, 3, 2, 7][l[2]], [2, 3, 3, 2, 6, 3,7][l[3]],
       [2, 2, 4, 5, 2, 4, 7][l[4]], [2, 2, 4, 2, 6, 2,7][l[5]]])+
      b(x-1, y-1, [[1, 1, 1, 5, 6, 7, 7][l[1]],
       [1, 1, 4, 1, 6, 7, 7][l[2]], [1, 1, 4, 5, 1, 7, 7][l[3]],
       [1, 3, 1, 3, 6, 7, 7][l[4]], [1, 3, 1, 5, 1, 7, 7][l[5]]])))
    end:
a:= n-> b(2*n, 0, [1$5]):
seq(a(n), n=0..35);

b[x_, y_, l_] := b[x, y, l] = Module[{m = Min[l]},
        If[y>x || y<0 || 7-m>x, 0, If[x == 0, 1,
        b[x-1, y+1, MapIndexed[#1[[l[[#2[[1]] ]] ]]&,
        {{2, 3, 4, 4, 2, 2, 7},
         {2, 3, 3, 5, 3, 2, 7},
         {2, 3, 3, 2, 6, 3, 7},
         {2, 2, 4, 5, 2, 4, 7},
         {2, 2, 4, 2, 6, 2, 7}}]]] +
        b[x-1, y-1, MapIndexed[#1[[l[[#2[[1]] ]] ]]&,
        {{1, 1, 1, 5, 6, 7, 7},
         {1, 1, 4, 1, 6, 7, 7},
         {1, 1, 4, 5, 1, 7, 7},
         {1, 3, 1, 3, 6, 7, 7},
         {1, 3, 1, 5, 1, 7, 7}}]]]];
a[n_] := b[2n, 0, {1, 1, 1, 1, 1}];
a /@ Range[0, 35] (* Jean-François Alcover, Jan 26 2021, after Alois P. Heinz *)

A243998 Number T(n,k) of Dyck paths of semilength n with exactly k (possibly overlapping) occurrences of some of the consecutive patterns of Dyck paths of semilength 3; triangle T(n,k), n>=0, 0<=k<=max(0,n-2), read by rows.

Original entry on oeis.org

1, 1, 2, 0, 5, 1, 11, 2, 1, 33, 7, 1, 4, 90, 30, 7, 1, 11, 245, 142, 24, 6, 1, 29, 680, 570, 121, 24, 5, 1, 81, 1884, 2176, 578, 112, 25, 5, 1, 220, 5265, 7935, 2649, 580, 116, 25, 5, 1, 608, 14747, 28022, 11827, 2825, 602, 124, 25, 5, 1

Offset: 0

Alois P. Heinz, Jun 17 2014

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

			T(3,1) = 5: 101010, 101100, 110010, 110100, 111000.
T(4,0) = 1: 11001100.
T(4,2) = 2: 10101010, 10110010.
T(5,0) = 1: 1110011000.
T(6,3) = 7: 101010101100, 101010110010, 101100101010, 101100101100, 110010101010, 110010110010, 110101010100.
Triangle T(n,k) begins:
:  0 :   1;
:  1 :   1;
:  2 :   2;
:  3 :   0,    5;
:  4 :   1,   11,    2;
:  5 :   1,   33,    7,    1;
:  6 :   4,   90,   30,    7,   1;
:  7 :  11,  245,  142,   24,   6,   1;
:  8 :  29,  680,  570,  121,  24,   5,  1;
:  9 :  81, 1884, 2176,  578, 112,  25,  5, 1;
: 10 : 220, 5265, 7935, 2649, 580, 116, 25, 5, 1;

Alois P. Heinz, Rows n = 0..142, flattened

Column k=0 gives A243986.
Row sums give A000108.
Cf. A014486, A063171, A243966.

b:= proc(x, y, t) option remember; `if`(y<0 or y>x, 0,
      `if`(x=0, 1, expand(add(b(x-1, y-1+2*j, irem(2*t+j, 32))*
      `if`(2*t+j in {42, 44, 50, 52, 56}, z, 1), j=0..1))))
    end:
T:= n-> (p-> seq(coeff(p, z, i), i=0..degree(p)))(b(2*n, 0, 0)):
seq(T(n), n=0..14);

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]]*
     Switch[2t+j, 42|44|50|52|56, z, _, 1], {j, 0, 1}]]]];
T[n_] := CoefficientList[b[2n, 0, 0], z];
Table[T[n], {n, 0, 14}] // Flatten (* Jean-François Alcover, Apr 30 2022, after Alois P. Heinz *)

cp's OEIS Frontend

A243966 Number of Dyck paths of semilength n such that all five consecutive patterns of Dyck paths of semilength 3 occur at least once.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica