A243881 Number T(n,k) of Dyck paths of semilength n having exactly k (possibly overlapping) occurrences of the consecutive steps UDUUUDDDUD (with U=(1,1), D=(1,-1)); triangle T(n,k), n>=0, 0<=k<=max(0,floor((n-1)/4)), read by rows.

1, 1, 2, 5, 14, 41, 1, 129, 3, 419, 10, 1395, 35, 4737, 124, 1, 16338, 454, 4, 57086, 1684, 16, 201642, 6305, 65, 718855, 23781, 263, 1, 2583149, 90209, 1077, 5, 9346594, 343809, 4419, 23, 34023934, 1315499, 18132, 105, 124519805, 5050144, 74368, 472, 1

Offset: 0

Author

Alois P. Heinz, Jun 13 2014

Keywords

• nonn
• tabf

Comments

UDUUUDDDUD is the only Dyck path of semilength 5 that contains all eight consecutive step patterns of length 3.

Examples

			Triangle T(n,k) begins:
:  0 :        1;
:  1 :        1;
:  2 :        2;
:  3 :        5;
:  4 :       14;
:  5 :       41,       1;
:  6 :      129,       3;
:  7 :      419,      10;
:  8 :     1395,      35;
:  9 :     4737,     124,     1;
: 10 :    16338,     454,     4;
: 11 :    57086,    1684,    16;
: 12 :   201642,    6305,    65;
: 13 :   718855,   23781,   263,   1;
: 14 :  2583149,   90209,  1077,   5;
: 15 :  9346594,  343809,  4419,  23;
: 16 : 34023934, 1315499, 18132, 105;
		

Links

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

Crossrefs

Columns k=0-10 give: A243870, A243871, A243872, A243873, A243874, A243875, A243876, A243877, A243878, A243879, A243880.

Row sums give A000108.

T(738,k) = A243752(738,k).

T(n,0) = A243753(n,738).

Cf. A243882.

Programs

Maple

b:= proc(x, y, t) option remember; `if`(y<0 or y>x, 0, `if`(x=0, 1,
     expand(b(x-1, y+1, [2, 2, 4, 5, 6, 2, 4, 2, 10, 2][t])+`if`(t=10,
      z, 1)*b(x-1, y-1, [1, 3, 1, 3, 3, 7, 8, 9, 1, 3][t]))))
    end:
T:= n-> (p-> seq(coeff(p, z, i), i=0..degree(p)))(b(2*n, 0, 1)):
seq(T(n), n=0..20);

Mathematica

b[x_, y_, t_] := b[x, y, t] = If[y<0 || y>x, 0, If[x==0, 1, Expand[b[x-1, y+1, {2, 2, 4, 5, 6, 2, 4, 2, 10, 2}[[t]]] + If[t==10, z, 1]*b[x-1, y-1, {1, 3, 1, 3, 3, 7, 8, 9, 1, 3}[[t]]]]]]; T[n_] := Function[{p}, Table[Coefficient[p, z, i], {i, 0, Exponent[p, z]}]][b[2*n, 0, 1]]; Table[T[n], {n, 0, 20}] // Flatten (* Jean-François Alcover, Mar 31 2015, after Alois P. Heinz *)