|
|
A000220
|
|
Number of asymmetric trees with n nodes (also called identity trees).
(Formerly M2583 N1022)
|
|
14
|
|
|
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, 23778351222
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,9
|
|
REFERENCES
|
F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Camb. 1998, p. 330.
S. R. Finch, Mathematical Constants, Cambridge, 2003, p. 301 and 562.
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).
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.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
LINKS
|
T. D. Noe and Alois P. Heinz, Table of n, a(n) for n = 1..1000 (first 200 terms from T. D. Noe)
E. Friedman, Illustration of initial terms
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.
P. Leroux and B. Miloudi, Généralisations de la formule d'Otter, Ann. Sci. Math. Québec, Vol. 16, No. 1, pp. 53-80, 1992. (Annotated scanned copy)
A. J. Schwenk, Letter to N. J. A. Sloane, Aug 1972
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 17 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
Peter Steinbach, Field Guide to Simple Graphs, Volume 3, Part 12 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
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.
a(n) ~ c * d^n / n^(5/2), where d = A246169 = 2.51754035263200389079535..., c = 0.29938828746578432274375484519722721162... . - Vaclav Kotesovec, Aug 25 2014
|
|
MAPLE
|
with(numtheory):
b:= proc(n) option remember; `if`(n<2, n, add(b(n-k)*add(
b(d)*d*(-1)^(k/d+1), d=divisors(k)), k=1..n-1)/(n-1))
end:
a:= n-> b(n)-(add(b(j)*b(n-j), j=0..n)+
`if`(irem(n, 2)=0, b(n/2), 0))/2:
seq(a(n), n=1..50); # Alois P. Heinz, Feb 24 2015
|
|
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} ] (* Robert A. Russell *)
|
|
CROSSREFS
|
Cf. A000055, A000081.
Cf. A246169, A004111, A035056.
Sequence in context: A066708 A034464 A116696 * A244705 A319643 A092641
Adjacent sequences: A000217 A000218 A000219 * A000221 A000222 A000223
|
|
KEYWORD
|
nonn,nice
|
|
AUTHOR
|
N. J. A. Sloane
|
|
STATUS
|
approved
|
|
|
|