|
| |
|
|
A091958
|
|
Triangle read by rows: T(n,k)=number of ordered trees with n edges and k branch nodes at odd height.
|
|
4
|
|
|
|
1, 1, 2, 4, 1, 9, 5, 21, 21, 51, 78, 3, 127, 274, 28, 323, 927, 180, 835, 3061, 954, 12, 2188, 9933, 4510, 165, 5798, 31824, 19734, 1430, 15511, 100972, 81684, 9790, 55, 41835, 317942, 324246, 57876, 1001, 113634, 995088, 1245762, 309036, 10920
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,3
|
|
|
COMMENTS
|
T(3n,n) = binomial(3n,n)/(2n+1) = A001764(n); T(n,0) = A001006(n) (the Motzkin numbers); T(n,1) = A055219(n-3) (n>=3; most probably); Row sums are the Catalan numbers (A000108).
T(n,k) = number of ordered trees on n edges with k vertices of outdegree at least 3; T(n,k) = number of ordered trees on n edges with k vertices V such that V's rightmost descendant leaf is at distance exactly 3 from V. - David Callan, Oct 24 2004
T(n,k) is the number of Dyck n-paths containing k UUUDs. For example, T(6,2) = 3 because UUUDUUUDDDDD, UUUDDUUUDDDD, UUUDDDUUUDDD each contains 2 UUUDs. - David Callan, Nov 04 2004
|
|
|
LINKS
|
|
|
|
FORMULA
|
T(n,k) = binomial((n+1), k)*sum((-1)^j*binomial(n+1-k,j)*binomial(2n-3k-3j, n), j=0..floor(n/3)-k)/(n+1). G.f.: G=G(t,z) satisfies (t-1)z^3 G^3 + zG^2 - G + 1 = 0.
|
|
|
EXAMPLE
|
T(3,1) = 1 because the only tree having 3 edges and 1 branch node at an odd level is the tree having the shape of the letter Y.
Triangle begins:
1;
1;
2;
4, 1;
9, 5;
21, 21;
51, 78, 3;
127, 274, 28;
323, 927, 180;
835, 3061, 954, 12;
2188, 9933, 4510, 165;
|
|
|
MAPLE
|
T := (n, k)->binomial((n+1), k)*sum((-1)^j*binomial(n+1-k, j)*binomial(2*n-3*k-3*j, n), j=0..floor(n/3)-k)/(n+1): seq(seq(T(n, k), k=0..floor(n/3)), n=0..18);
# second Maple program:
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, 3, 4, 4][t])
+b(x-1, y-1, [1, 1, 1, 1][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
|
Clear[a]; a[n_, k_]/; k>n/3 || k<0 := 0; a[n_, 0]/; 0<=n<=1 := 1; a[n_, 0]/; n>=2 := a[n, 0] = ((2*n + 1)*a[n-1, 0] + 3*(n - 1)*a[n-2, 0])/(n + 2); a[n_, k_]/; 1<=k<=n/3 && n>=2 := a[n, k] = ( (12 - 9*k + 3*n)*a[n-2, k-2] - (12 - 18*k + 3*n)*a[ n-2, k-1] - 9*k*a[ n-2, k] + (4 - 6*k + 4*n)*a[n-1, k-1] + 6*k*a[n-1, k] - (2 - k + n)*a[n, k-1] )/k; Table[a[n, k], {n, 0, 16}, {k, 0, n/3}] (Callan)
T[n_, k_] := (2*n-3*k)!*HypergeometricPFQ[{k-n-1, k-n/3, 1/3+k-n/3, 2/3+k-n/3}, {k-2*n/3, 1/3+k-2*n/3, 2/3+k-2*n/3}, 1]/(k!*(n-k+1)!*(n-3*k)!); Table[T[n, k], {n, 0, 15}, {k, 0, n/3}] // Flatten (* Jean-François Alcover, Mar 31 2015 *)
|
|
|
CROSSREFS
|
Topmost entries in each column form A001764=( binomial(3n, n)/(2n+1) )_(n>=0), next to topmost entries form A025174=( binomial(3n+2, n) )_(n>=0), next lower entries are given by ( (n+2)binomial(3n+4, n) )_(n>=0).
|
|
|
KEYWORD
|
nonn,tabf
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
