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,3

Comments

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

Links

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

Example

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;

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

Crossrefs

Row sums give A000108.

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

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

Cf. A243820.

Sequence in context: A291823 A287972 A243838 * A211216 A261592 A291824

Adjacent sequences: A242447 A242448 A242449 * A242451 A242452 A242453

Keyword

nonn,tabf

Author

Alois P. Heinz, Jun 12 2014

Status

approved