|
Search: id:A144289
|
|
|
| A144289 |
|
Triangle T(n,k), n>=0, 0<=k<=n, read by rows: T(n,k)=number of forests of labeled rooted trees on n or fewer nodes using a subset of labels 1..n and k edges. |
|
+0
2
|
|
| 1, 2, 0, 4, 2, 0, 8, 12, 9, 0, 16, 48, 84, 64, 0, 32, 160, 480, 820, 625, 0, 64, 480, 2160, 6120, 10230, 7776, 0, 128, 1344, 8400, 34720, 94500, 155274, 117649, 0, 256, 3584, 29568, 165760, 647920, 1712592, 2776200, 2097152, 0, 512, 9216, 96768, 701568
(list; table; graph; listen)
|
|
|
OFFSET
|
0,2
|
|
|
LINKS
|
Index entries for sequences related to rooted trees
|
|
FORMULA
|
T(n,0) = 2^n, T(n,k) = 0 if k<0 or n<=k, else T(n,k) = n^(n-1) if k=n-1, else 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 less 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);
|
|
CROSSREFS
|
Columns 0, 1 give: A000079, A001815. First lower diagonal gives: A000169 with first term 2. Row sums give: A088957. Cf. A007318, A000142.
Sequence in context: A008797 A109468 A081880 this_sequence A037035 A159984 A112824
Adjacent sequences: A144286 A144287 A144288 this_sequence A144290 A144291 A144292
|
|
KEYWORD
|
nonn,tabl
|
|
AUTHOR
|
Alois P. Heinz (heinz(AT)hs-heilbronn.de), Sep 17 2008
|
|
|
Search completed in 0.002 seconds
|
