OFFSET
0,2
LINKS
FORMULA
T(n,0) = 2^n, T(n,k) = 0 if k < 0 or n <= k, otherwise T(n,k) = n^(n-1) if k=n-1, otherwise T(n,k) = Sum_{j=0..k} C(n-1,j)*T(j+1,j)*T(n-1-j,k-j).
EXAMPLE
T(3,1) = 12, because there are 12 forests of labeled rooted trees on 3 or fewer nodes using a subset of labels 1..3 and 1 edge:
.1<2. .2<1. .1<3. .3<1. .2<3. .3<2. .1<2. .2<1. .1<3. .3<1. .2<3. .3<2.
..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... .....
..... ..... ..... ..... ..... ..... .3... .3... .2... .2... .1... .1...
Triangle begins:
1;
2, 0;
4, 2, 0;
8, 12, 9, 0;
16, 48, 84, 64, 0;
32, 160, 480, 820, 625, 0;
MAPLE
T:= proc(n, k) option remember;
if k=0 then 2^n
elif k<0 or n<=k then 0
elif k=n-1 then n^(n-1)
else add(binomial(n-1, j) *T(j+1, j) *T(n-1-j, k-j), j=0..k)
fi
end:
seq(seq(T(n, k), k=0..n), n=0..11);
MATHEMATICA
T[n_, k_] := T[n, k] = Which[k == 0, 2^n, k<0 || n <= k, 0, k == n-1, n^(n-1), True, Sum[Binomial[n-1, j]*T[j+1, j]*T[n-1-j, k-j], {j, 0, k}]]; Table[Table[T[n, k], {k, 0, n}], {n, 0, 11}] // Flatten (* Jean-François Alcover, Jan 21 2014, translated from Alois P. Heinz's Maple code *)
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Alois P. Heinz, Sep 17 2008
STATUS
approved