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.

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

Author

Alois P. Heinz, Jun 17 2014

Keywords

• nonn
• tabf

Comments

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

Examples

			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;
		

Links

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

Crossrefs

Column k=0 gives A243986.

Row sums give A000108.

Cf. A014486, A063171, A243966.

Programs

Maple

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);

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]]*
     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 *)