|
|
A094507
|
|
Triangle read by rows: T(n,k) is number of Dyck paths of semilength n and having k UDUD's (here U=(1,1), D=(1,-1)).
|
|
6
|
|
|
1, 1, 1, 1, 3, 1, 1, 7, 5, 1, 1, 19, 14, 7, 1, 1, 53, 46, 22, 9, 1, 1, 153, 150, 82, 31, 11, 1, 1, 453, 495, 299, 127, 41, 13, 1, 1, 1367, 1651, 1087, 507, 181, 52, 15, 1, 1, 4191, 5539, 3967, 1991, 781, 244, 64, 17, 1, 1, 13015, 18692, 14442, 7824, 3271, 1128, 316, 77, 19
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,5
|
|
COMMENTS
|
Row sums are the Catalan numbers (A000108).
|
|
LINKS
|
|
|
FORMULA
|
G.f.: G=G(t, z) satisfies the equation z(1+z-tz)G^2-(1+z+z^2-tz-tz^2)G+1+z-tz=0.
|
|
EXAMPLE
|
T(3,0) = 3 because UDUUDD, UUDDUD and UUUDDD are the only Dyck paths of semilength 3 and having no UDUD in them.
Triangle begins:
1;
1;
1, 1;
3, 1, 1;
7, 5, 1, 1;
19, 14, 7, 1, 1;
53, 46, 22, 9, 1, 1;
153, 150, 82, 31, 11, 1, 1;
453, 495, 299, 127, 41, 13, 1, 1;
1367, 1651, 1087, 507, 181, 52, 15, 1, 1;
4191, 5539, 3967, 1991, 781, 244, 64, 17, 1, 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, 2][t])
+b(x-1, y-1, [1, 3, 1, 3][t])*`if`(t=4, z, 1))))
end:
T:= n-> (p-> seq(coeff(p, z, i), i=0..degree(p)))(b(2*n, 0, 1)):
|
|
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, 2}[[t]]] + b[x-1, y-1, {1, 3, 1, 3}[[t]]]*If[t == 4, z, 1]]]]; T[n_] := Function[{p}, Table[Coefficient[p, z, i], {i, 0, Exponent[p, z]}]][b[2*n, 0, 1] ]; Table[T[n], {n, 0, 15}] // Flatten (* Jean-François Alcover, Apr 29 2015, after Alois P. Heinz *)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,tabf
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|