login
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.
13
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,3
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
LINKS
EXAMPLE
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;
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 *)
CROSSREFS
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).
Sequence in context: A135331 A135329 A114508 * A139023 A241758 A173620
KEYWORD
nonn,tabf
AUTHOR
Alois P. Heinz, Jun 03 2014
STATUS
approved