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

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16795, 1, 58783, 3, 208002, 10, 742865, 35, 2674314, 126, 9694383, 462, 35355954, 1716, 129638355, 6435, 477614391, 24308, 1, 1767170815, 92372, 3, 6563767715, 352694, 11, 24464914983, 1351996, 41, 91477363496, 5199988

Offset: 0

Author

Alois P. Heinz, Jun 12 2014

Keywords

• nonn
• tabf

Comments

UUDDUDUUUUDUDDDDUUDD is a Dyck path that contains all sixteen consecutive step patterns of length 4.

Examples

			Triangle T(n,k) begins:
:  0 :           1;
:  1 :           1;
:  2 :           2;
:  3 :           5;
:  4 :          14;
:  5 :          42;
:  6 :         132;
:  7 :         429;
:  8 :        1430;
:  9 :        4862;
: 10 :       16795,       1;
: 11 :       58783,       3;
: 12 :      208002,      10;
: 13 :      742865,      35;
: 14 :     2674314,     126;
: 15 :     9694383,     462;
: 16 :    35355954,    1716;
: 17 :   129638355,    6435;
: 18 :   477614391,   24308,  1;
: 19 :  1767170815,   92372,  3;
: 20 :  6563767715,  352694, 11;
: 21 : 24464914983, 1351996, 41;
		

Links

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

Crossrefs

Row sums give A000108.

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

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

Cf. A243820.

Programs

Maple

b:= proc(x, y, t) option remember; `if`(x=0, 1,
     expand(`if`(y>=x-1, 0, b(x-1, y+1, [2, 3, 3, 2, 6, 3,
       8, 9, 10, 11, 3, 13, 3, 2, 2, 2, 18, 19, 3, 2][t]))+
     `if`(t=20, z, 1)*`if`(y=0, 0, b(x-1, y-1, [1, 1, 4, 5, 1, 7,
       1, 1, 4, 4, 12, 5, 14, 15, 16, 17, 1, 1, 20, 5][t]))))
    end:
T:= n-> (p-> seq(coeff(p, z, i), i=0..degree(p)))(b(2*n, 0, 1)):
seq(T(n), n=0..30);

Mathematica

b[x_, y_, t_] := b[x, y, t] = If[x == 0, 1, Expand[If[y >= x - 1, 0, b[x - 1, y + 1, {2, 3, 3, 2, 6, 3, 8, 9, 10, 11, 3, 13, 3, 2, 2, 2, 18, 19, 3, 2}[[t]]]] + If[t == 20, z, 1]*If[y == 0, 0, b[x - 1, y - 1, {1, 1, 4, 5, 1, 7, 1, 1, 4, 4, 12, 5, 14, 15, 16, 17, 1, 1, 20, 5}[[t]]]]]];
T[n_] := CoefficientList[b[2n, 0, 1], z];
T /@ Range[0, 30] // Flatten (* Jean-François Alcover, Mar 27 2021, after Alois P. Heinz *)