|
Search: id:A118376
|
|
|
| A118376 |
|
Number of all trees of weight n, where nodes have positive integer weights and the sum of the weights of the children of a node is equal to the weight of the node. |
|
+0
1
|
|
| 1, 2, 6, 24, 112, 568, 3032, 16768, 95200, 551616, 3248704, 19389824, 117021824, 712934784, 4378663296, 27081760768, 168530142720, 1054464293888, 6629484729344
(list; graph; listen)
|
|
|
OFFSET
|
1,2
|
|
|
COMMENT
|
The number of trees with leaf nodes equal to 1 is counted by the sequence A001003 of super-Catalan numbers. The number of binary trees is counted by the sequence A007317 and the number of binary trees with leaf nodes equal to 1 is counted by the sequence A000108 of Catalan numbers.
|
|
REFERENCES
|
J. R. Johnson, M. P\"{u}schel, In search for the optimal Walsh-Hadamard transform, Proc. ICASSP, Vol. 4, 2000, pp. 3347-3350.
Pawel Hitczenko, Jeremy R. Johnson, Hung-Jen Huang, Distribution of a class of divide and conquer recurrences arising from the computation of the Walsh-Hadamard transform, Theoretical Computer Science, Vol. 352, 2006, pp. 8-30.
|
|
FORMULA
|
Recurrence: T(1) = 1; For n > 1, T(n) = 1 + sum_{n=n1+...+nt} T(n1)*...*T(nt) G.F.: (-1+(1-8*z+8*z^2)^(1/2))/(-4+4*z)
|
|
EXAMPLE
|
T(3) = 6 because there are six trees
3 3 3 3 3 3
2 1 2 1 1 2 1 2 1 1 1
1 1 1 1
|
|
MAPLE
|
T := proc(n) option remember; local C, s, p, tp, k, i; if n = 1 then return 1; else s := 1; for k from 2 to n do C := combinat[composition](n, k); for p in C do tp := map(T, p); s := s + mul(tp[i], i=1..nops(tp)); end do; end do; end if; return s; end;
|
|
CROSSREFS
|
Cf. A001003, A007317, A000108.
Sequence in context: A141254 A138020 A046646 this_sequence A085486 A054872 A134664
Adjacent sequences: A118373 A118374 A118375 this_sequence A118377 A118378 A118379
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Jeremy Johnson (jjohnson(AT)cs.drexel.edu), May 15 2006
|
|
|
Search completed in 0.002 seconds
|
