cp's OEIS Frontend

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

%I A000220 M2583 N1022 #49 Oct 27 2023 18:22:09
%S A000220 1,0,0,0,0,0,1,1,3,6,15,29,67,139,310,667,1480,3244,7241,16104,36192,
%T A000220 81435,184452,418870,955860,2187664,5025990,11580130,26765230,
%U A000220 62027433,144133676,335731381,783859852,1834104934,4300433063,10102854473,23778351222
%N A000220 Number of asymmetric trees with n nodes (also called identity trees).
%D A000220 F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Camb. 1998, p. 330.
%D A000220 S. R. Finch, Mathematical Constants, Cambridge, 2003, p. 301 and 562.
%D A000220 F. Harary, Graph Theory. Addison-Wesley, Reading, MA, 1969, p. 232.
%D A000220 F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 66, Eq. (3.3.22).
%D A000220 D. E. Knuth, Fundamental Algorithms, 3d Ed. 1997, pp. 386-88 describes methodology for generating similar sequence rapidly.
%D A000220 R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.
%D A000220 A. J. Schwenk, personal communication.
%D A000220 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A000220 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A000220 Alois P. Heinz, <a href="/A000220/b000220.txt">Table of n, a(n) for n = 1..1000</a> (first 200 terms from T. D. Noe)
%H A000220 E. Friedman, <a href="/A000220/a000220.gif">Illustration of initial terms</a>
%H A000220 F. Harary, R. W. Robinson and A. J. Schwenk, <a href="https://doi.org/10.1017/S1446788700016190">Twenty-step algorithm for determining the asymptotic number of trees of various species</a>, J. Austral. Math. Soc., Series A, 20 (1975), 483-503. <a href="https://doi.org/10.1017/S1446788700033760">Errata</a>: Vol. A 41 (1986), p. 325.
%H A000220 P. Leroux and B. Miloudi, <a href="/A000081/a000081_2.pdf">Généralisations de la formule d'Otter</a>, Ann. Sci. Math. Québec, Vol. 16, No. 1, pp. 53-80, 1992. (Annotated scanned copy)
%H A000220 A. J. Schwenk, <a href="/A002988/a002988.pdf">Letter to N. J. A. Sloane, Aug 1972</a>
%H A000220 Peter Steinbach, <a href="/A000088/a000088_17.pdf">Field Guide to Simple Graphs, Volume 1</a>, Part 17 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
%H A000220 Peter Steinbach, <a href="/A000055/a000055_12.pdf">Field Guide to Simple Graphs, Volume 3</a>, Part 12 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
%H A000220 <a href="/index/Tra#trees">Index entries for sequences related to trees</a>
%F A000220 G.f.: A(x)-A^2(x)/2-A(x^2)/2, where A(x) is g.f. for A004111.
%F A000220 a(n) ~ c * d^n / n^(5/2), where d = A246169 = 2.51754035263200389079535..., c = 0.29938828746578432274375484519722721162... . - _Vaclav Kotesovec_, Aug 25 2014
%p A000220 with(numtheory):
%p A000220 b:= proc(n) option remember; `if`(n<2, n, add(b(n-k)*add(
%p A000220       b(d)*d*(-1)^(k/d+1), d=divisors(k)), k=1..n-1)/(n-1))
%p A000220     end:
%p A000220 a:= n-> b(n)-(add(b(j)*b(n-j), j=0..n)+
%p A000220        `if`(irem(n, 2)=0, b(n/2), 0))/2:
%p A000220 seq(a(n), n=1..50);  # _Alois P. Heinz_, Feb 24 2015
%t A000220 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_ *)
%Y A000220 Cf. A000055, A000081.
%Y A000220 Cf. A246169, A004111, A035056.
%K A000220 nonn,nice
%O A000220 1,9
%A A000220 _N. J. A. Sloane_