|
Search: id:A004111
|
|
|
| A004111 |
|
Number of rooted identity trees with n nodes (trees with distinct subtrees).
(Formerly M0796)
|
|
+0
24
|
|
| 0, 1, 1, 1, 2, 3, 6, 12, 25, 52, 113, 247, 548, 1226, 2770, 6299, 14426, 33209, 76851, 178618, 416848, 976296, 2294224, 5407384, 12780394, 30283120, 71924647, 171196956, 408310668, 975662480, 2335443077, 5599508648, 13446130438
(list; graph; listen)
|
|
|
OFFSET
|
0,5
|
|
|
COMMENT
|
Shifts left under WEIGH transform. - Franklin T. Adams-Watters (FrankTAW(AT)Netscape.net), Jan 17 2007
|
|
REFERENCES
|
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Camb. 1998, p. 330.
P. J. Cameron, Some sequences of integers, Discrete Math., 75 (1989), 89-102; also in "Graph Theory and Combinatorics 1988", ed. B. Bollobas, Annals of Discrete Math., 43 (1989), 89-102.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 64, Eq. (3.3.15); p. 80, Problem 3.10.
F. Harary, R. W. Robinson and A. J. Schwenk, Twenty-step algorithm for determining the asymptotic number of trees of various species, J. Austral. Math. Soc., Series A, 20 (1975), 483-503. Errata: Vol. A 41 (1986), p. 325.
D. E. Knuth, Fundamental Algorithms, 3rd Ed., 1997, pp. 386-388.
|
|
LINKS
|
T. D. Noe, Table of n, a(n) for n=0..200
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 56
Index entries for sequences related to rooted trees
|
|
FORMULA
|
Recurrence: a(n+1) = (1/n) * sum_{k=1..n} ( sum_{d|k} (-1)^(k/d+1) d*a(d) ) * a(n-k+1). - Mitchell Harris, Dec 02, 2004
G.f.: A(x) = x exp(A(x)-A(x^2)/2+A(x^3)/3-A(x^4)/4+...)
Also A(x) = Sum_{n >= 1} a(n)*x^n = x * Product_{n >= 1} (1+x^n)^a(n).
|
|
MAPLE
|
spec := [ A, {A=Prod(Z, PowerSet(A))} ]: [ seq(combstruct[count](spec, size=n), n=0..52) ];
|
|
MATHEMATICA
|
s[ n_, k_ ] := s[ n, k ]=a[ n+1-k ]+If[ n<2k, 0, -s[ n-k, k ] ]; a[ 1 ]=1; a[ n_ ] := a[ n ]=Sum[ a[ i ]s[ n-1, i ]i, {i, 1, n-1} ]/(n-1); Table[ a[ i ], {i, 1, 30} ] (from Robert A. Russell)
|
|
CROSSREFS
|
Cf. A000009, A000081, A000220.
Adjacent sequences: A004108 A004109 A004110 this_sequence A004112 A004113 A004114
Sequence in context: A038087 A116379 A116380 this_sequence A032235 A162985 A052523
|
|
KEYWORD
|
nonn,easy,nice,eigen
|
|
AUTHOR
|
N. J. A. Sloane (njas(AT)research.att.com).
|
|
|
Search completed in 0.002 seconds
|
