|
|
A191314
|
|
Triangle read by rows: T(n,k) is the number of dispersed Dyck paths (i.e., Motzkin paths with no (1,0) steps at positive heights) of length n and height k.
|
|
6
|
|
|
1, 1, 1, 1, 1, 2, 1, 4, 1, 1, 7, 2, 1, 12, 6, 1, 1, 20, 12, 2, 1, 33, 27, 8, 1, 1, 54, 53, 16, 2, 1, 88, 108, 44, 10, 1, 1, 143, 208, 88, 20, 2, 1, 232, 405, 208, 65, 12, 1, 1, 376, 768, 415, 130, 24, 2, 1, 609, 1459, 908, 350, 90, 14, 1, 1, 986, 2734, 1804, 700, 180, 28, 2, 1, 1596, 5117, 3776, 1700, 544, 119, 16, 1
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,6
|
|
COMMENTS
|
Row n has 1 + floor(n/2) entries.
Sum of entries in row n is binomial(n, floor(n/2)) = A001405(n).
T(n,1) = A000071(n+1) (Fibonacci numbers minus 1).
Sum_{k>=0} k * T(n,k) = A191315(n).
|
|
LINKS
|
|
|
FORMULA
|
G.f.: The g.f. of column k is z^{2k}/(F[k]*F[k+1]), where F[k] are polynomials in z defined by F[0]=1, F[1]=1-z, F[k]=F[k-1]-z^2*F[k-2] for k>=2. The coefficients of these polynomials form the triangle A108299.
Rows may be obtained by taking finite differences of A205573 columns from the top -> down. - Gary W. Adamson, Feb 01 2012
|
|
EXAMPLE
|
T(5,2) = 2 because we have HUUDD and UUDDH, where U=(1,1), D=(1,-1), H=(1,0).
Triangle starts:
1;
1;
1, 1;
1, 2;
1, 4, 1;
1, 7, 2;
1, 12, 6, 1;
1, 20, 12, 2;
1, 33, 27, 8, 1;
|
|
MAPLE
|
F[0] := 1: F[1] := 1-z: for k from 2 to 12 do F[k] := sort(expand(F[k-1]-z^2*F[k-2])) end do: for k from 0 to 11 do h[k] := z^(2*k)/(F[k]*F[k+1]) end do: T := proc (n, k) options operator, arrow: coeff(series(h[k], z = 0, 20), z, n) end proc: for n from 0 to 16 do seq(T(n, k), k = 0 .. floor((1/2)*n)) end do; # yields sequence in triangular form
# second Maple program:
b:= proc(x, y) option remember; `if`(y>x or y<0, 0, `if`(x=0, 1,
(p->add(coeff(p, z, i)*z^max(i, y), i=0..degree(p, z)))
(b(x-1, y-1))+ b(x-1, y+1)+`if`(y=0, b(x-1, y), 0)))
end:
T:= n-> (p-> seq(coeff(p, z, i), i=0..degree(p)))(b(n, 0)):
|
|
MATHEMATICA
|
b[x_, y_] := b[x, y] = If[y>x || y<0, 0, If[x==0, 1, Function [{p}, Sum[ Coefficient[p, z, i]*z^Max[i, y], {i, 0, Exponent[p, z]}]][b[x-1, y-1]] + b[x-1, y+1] + If[y==0, b[x-1, y], 0]]]; T[n_] := Function[{p}, Table[Coefficient[p, z, i], {i, 0, Exponent[p, z]}]][b[n, 0]]; Table[T[n], {n, 0, 14}] // Flatten (* Jean-François Alcover, Mar 31 2015, after Alois P. Heinz *)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,tabf
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|