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

1, 1, 2, 5, 13, 1, 37, 5, 112, 19, 1, 352, 70, 7, 1136, 259, 34, 1, 3742, 962, 149, 9, 12529, 3585, 627, 54, 1, 42513, 13399, 2584, 279, 11, 145868, 50201, 10529, 1334, 79, 1, 505234, 188481, 42606, 6092, 474, 13, 1764157, 709001, 171563, 27048, 2561, 109, 1

Offset: 0

Author

Alois P. Heinz, Jun 03 2014

Keywords

• nonn
• tabf

Comments

Conjecture: Generally, column k is asymptotic to c(k) * d^n * n^(k-3/2), where d = 3.8821590268628506747194368909643384... is the root of the equation d^8 - 2*d^7 - 10*d^6 + 12*d^5 - 5*d^4 - 2*d^3 - 5*d^2 - 8*d - 3 = 0, and c(k) are specific constants (independent on n). - Vaclav Kotesovec, Jun 05 2014

Examples

			T(4,1) = 1: UDUUDUDD.
T(5,1) = 5: UDUDUUDUDD, UDUUDUDDUD, UDUUDUDUDD, UDUUDUUDDD, UUDUUDUDDD.
T(6,1) = 19: UDUDUDUUDUDD, UDUDUUDUDDUD, UDUDUUDUDUDD, UDUDUUDUUDDD, UDUUDUDDUDUD, UDUUDUDDUUDD, UDUUDUDUDDUD, UDUUDUDUDUDD, UDUUDUDUUDDD, UDUUDUUDDDUD, UDUUDUUDDUDD, UDUUDUUUDDDD, UUDDUDUUDUDD, UUDUDUUDUDDD, UUDUUDUDDDUD, UUDUUDUDDUDD, UUDUUDUDUDDD, UUDUUDUUDDDD, UUUDUUDUDDDD.
T(6,2) = 1: UDUUDUUDUDDD.
T(7,2) = 7: UDUDUUDUUDUDDD, UDUUDUDUUDUDDD, UDUUDUUDUDDDUD, UDUUDUUDUDDUDD, UDUUDUUDUDUDDD, UDUUDUUDUUDDDD, UUDUUDUUDUDDDD.
T(8,3) = 1: UDUUDUUDUUDUDDDD.
Triangle T(n,k) begins:
:  0 :     1;
:  1 :     1;
:  2 :     2;
:  3 :     5;
:  4 :    13,    1;
:  5 :    37,    5;
:  6 :   112,   19,   1;
:  7 :   352,   70,   7;
:  8 :  1136,  259,  34,  1;
:  9 :  3742,  962, 149,  9;
: 10 : 12529, 3585, 627, 54, 1;
		

Links

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

Crossrefs

Column k=0-10 give: A243412, A243413, A243414, A243415, A243416, A243417, A243418, A243419, A243420, A243421, A243422.

Row sums give A000108.

T(n,floor(n/2)-1) gives A093178(n) for n>3.

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

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

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, 2, 4][t])*
     `if`(t=6, z, 1) +b(x-1, y-1, [1, 3, 1, 3, 6, 1][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, 2, 4}[[t]]]*If[t == 6, z, 1] + b[x-1, y-1, {1, 3, 1, 3, 6, 1}[[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, Feb 05 2015, after Alois P. Heinz *)