A243838 Number T(n,k) of Dyck paths of semilength n having exactly k (possibly overlapping) occurrences of the consecutive steps UDUUDDUUUUDUDDDDUDUD (with U=(1,1), D=(1,-1)); triangle T(n,k), n>=0, 0<=k<=max(0,floor((n-1)/9)), 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, 477614390, 24310, 1767170813, 92376, 1, 6563767708, 352708, 4, 24464914958, 1352046, 16, 91477363405, 5200170, 65

Offset

0,3

Comments

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

Links

Alois P. Heinz, Rows n = 0..350, 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 :   477614390,   24310;
: 19 :  1767170813,   92376,  1;
: 20 :  6563767708,  352708,  4;
: 21 : 24464914958, 1352046, 16;

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, 2, 4,
       8, 9, 10, 11, 2, 13, 5, 4, 2, 2, 18, 2, 20, 5][t])
      +`if`(t=20, z, 1) *b(x-1, y-1, [1, 3, 1, 3, 6, 7,
       1, 3, 3, 3, 12, 1, 14, 15, 16, 17, 1, 19, 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..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, 2, 4, 5, 2, 4, 8, 9, 10, 11, 2, 13, 5, 4, 2, 2, 18, 2, 20, 5}[[t]]]] + If[t == 20, z, 1]*If[y == 0, 0, b[x - 1, y - 1, {1, 3, 1, 3, 6, 7, 1, 3, 3, 3, 12, 1, 14, 15, 16, 17, 1, 19, 1, 3}[[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(736522,k) = A243752(736522,k).

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

Cf. A243820.

Sequence in context: A261591 A291823 A287972 * A242450 A211216 A261592

Adjacent sequences: A243835 A243836 A243837 * A243839 A243840 A243841

Keyword

nonn,tabf

Author

Alois P. Heinz, Jun 11 2014

Status

approved