|
| |
|
|
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, 2, 6, 24, 112, 568, 3032, 16768, 95200, 551616, 3248704, 19389824, 117021824, 712934784, 4378663296, 27081760768, 168530142720, 1054464293888, 6629484729344
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 1,2
|
|
|
COMMENTS
| 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.
|
|
|
LINKS
| Vladimir Kruchinin, Compositae and their properties , arXiv:1103.2582
|
|
|
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)
O.g.f A(x)=1/(1-A001003(x)). a(n)=sum(binomial(n-1,k-1)*A001003(k),k,1,n), n>0 [From Kruchinin Vladimir (kru(AT)ie.tusur.ru), Sep 03 2010]
|
|
|
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: A177521 A152322 A168490 * A085486 A152318 A152328
Adjacent sequences: A118373 A118374 A118375 * A118377 A118378 A118379
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| Jeremy Johnson (jjohnson(AT)cs.drexel.edu), May 15 2006
|
| |
|
|
