login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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
Alois P. Heinz, Table of n, a(n) for n = 1..1000 (first 200 terms from T. D. Noe)
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)
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.)
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
Sequence in context: A066708 A034464 A116696 * A244705 A319643 A092641
KEYWORD
nonn,nice
AUTHOR
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 20:05 EDT 2024. Contains 371254 sequences. (Running on oeis4.)