A000220 Number of asymmetric trees with n nodes (also called identity trees).

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

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• nice

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)
• 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

Crossrefs

Cf. A000055, A000081.

Cf. A246169, A004111, A035056.

Programs

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 *)

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