|
| |
|
|
A102405
|
|
Triangle read by rows: T(n,k) is number of Dyck paths of semilength n having k ascents of length 1 that start at an odd level.
|
|
5
|
|
|
|
1, 1, 2, 4, 1, 10, 3, 1, 26, 12, 3, 1, 72, 41, 15, 3, 1, 206, 143, 58, 18, 3, 1, 606, 492, 231, 76, 21, 3, 1, 1820, 1693, 891, 335, 95, 24, 3, 1, 5558, 5823, 3403, 1411, 455, 115, 27, 3, 1, 17206, 20040, 12870, 5848, 2061, 591, 136, 30, 3, 1, 53872, 69033, 48318, 23858, 9143, 2850, 743, 158, 33, 3, 1
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,3
|
|
|
COMMENTS
|
T(n,k) is number of Łukasiewicz paths of length n having k level steps at an odd level. A Łukasiewicz path of length n is a path in the first quadrant from (0,0) to (n,0) using rise steps (1,k) for any positive integer k, level steps (1,0) and fall steps (1,-1) (see R. P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge Univ. Press, Cambridge, 1999, p. 223, Exercise 6.19w; the integers are the slopes of the steps). Example: T(3,1)=1 because we have only UHD with exactly one level step at an odd level; here U=(1,1), H=(1,0) and D=(1,-1). Row n has n-1 terms (n>=2). Row sums are the Catalan numbers (A000108). Column 0 yields A102407.
T(n,k) is the number of Dyck paths of semilength n with k DUDU's. - I. Tasoulas (jtas(AT)unipi.gr), Feb 19 2006
|
|
|
LINKS
|
|
|
|
FORMULA
|
G.f.: G=G(t, z) satisfies zG^2-(1+z-z^2-tz+tz^2)G+1+z-tz=0.
|
|
|
EXAMPLE
|
T(4,1) = 3 because we have UDUUD(U)DD, UUD(U)DDUD and UUUDD(U)DD, where U=(1,1), D=(1,-1) and the ascents of length 1 that start at an odd level are shown between parentheses.
Triangle starts:
00 : 1;
01 : 1;
02 : 2;
03 : 4, 1;
04 : 10, 3, 1;
05 : 26, 12, 3, 1;
06 : 72, 41, 15, 3, 1;
07 : 206, 143, 58, 18, 3, 1;
08 : 606, 492, 231, 76, 21, 3, 1;
09 : 1820, 1693, 891, 335, 95, 24, 3, 1;
10 : 5558, 5823, 3403, 1411, 455, 115, 27, 3, 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, May 20 2015, after Alois P. Heinz *)
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,tabf
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
