|
Search: id:A000220
|
|
|
| A000220 |
|
Number of asymmetric trees with n nodes (also called identity trees).
(Formerly M2583 N1022)
|
|
+0
8
|
|
| 1, 0, 0, 0, 0, 0, 1, 1, 3, 6, 15, 29, 67, 139, 310, 667, 1480, 3244, 7241, 16104, 36192, 81435, 184452, 418870, 955860, 2187664, 5025990, 11580130, 26765230, 62027433, 144133676, 335731381, 783859852, 1834104934, 4300433063, 10102854473
(list; graph; listen)
|
|
|
OFFSET
|
1,9
|
|
|
REFERENCES
|
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Camb. 1998, p. 330.
F. Harary, Graph Theory. Addison-Wesley, Reading, MA, 1969, p. 232.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 66, Eq. (3.3.22).
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, 3d Ed. 1997, pp. 386-88 describes methodology for generating similar sequence rapidly.
R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.
A. J. Schwenk, personal communication.
|
|
LINKS
|
T. D. Noe, Table of n, a(n) for n=1..200
E. Friedman, Illustration of initial terms
Index entries for sequences related to trees
|
|
FORMULA
|
G.f.: A(x)-A^2(x)/2-A(x^2)/2, where A(x) is g.f. for A004111
|
|
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 ]-Sum[ a[ j ]a[ i-j ], {j, 1, i/2} ]+If[ OddQ[ i ], 0, a[ i/2 ](a[ i/2 ]-1)/2 ], {i, 1, 50} ] (from Robert A. Russell)
|
|
CROSSREFS
|
Cf. A000055, A000081.
Sequence in context: A066708 A034464 A116696 this_sequence A092641 A077449 A152232
Adjacent sequences: A000217 A000218 A000219 this_sequence A000221 A000222 A000223
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
N. J. A. Sloane (njas(AT)research.att.com).
|
|
|
Search completed in 0.002 seconds
|
