# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/

Search: id:a000055
Showing 1-1 of 1

%I A000055 M0791 N0299 #353 Oct 04 2024 11:19:01
%S A000055 1,1,1,1,2,3,6,11,23,47,106,235,551,1301,3159,7741,19320,48629,123867,
%T A000055 317955,823065,2144505,5623756,14828074,39299897,104636890,279793450,
%U A000055 751065460,2023443032,5469566585,14830871802,40330829030,109972410221,300628862480,823779631721,2262366343746,6226306037178
%N A000055 Number of trees with n unlabeled nodes.
%C A000055 Also, number of unlabeled 2-gonal 2-trees with n 2-gons.
%C A000055 Main diagonal of A054924.
%C A000055 Left border of A157905. - _Gary W. Adamson_, Mar 08 2009
%C A000055 From _Robert Munafo_, Jan 24 2010: (Start)
%C A000055 Also counts classifications of n items that require exactly n-1 binary partitions; see Munafo link at A005646, also A171871 and A171872.
%C A000055 The 11 trees for n = 7 are illustrated at the Munafo web link.
%C A000055 Link to A171871/A171872 conjectured by _Robert Munafo_, then proved by _Andrew Weimholt_ and _Franklin T. Adams-Watters_ on Dec 29 2009. (End)
%C A000055 This is also "Number of tree perfect graphs on n nodes" [see Hougardy]. - _N. J. A. Sloane_, Dec 04 2015
%C A000055 For n > 0, a(n) is the number of ways to arrange n-1 unlabeled non-intersecting circles on a sphere. - _Vladimir Reshetnikov_, Aug 25 2016
%C A000055 All trees for n=1 through n=12 are depicted in Chapter 1 of the Steinbach reference. On p. 6 appear encircled two trees (with n=10) which seem inequivalent only when considered as ordered (planar) trees. Earlier instances of such possibly (in)equivalent trees could appear from n=6 on (and from n=9 on without equivalence modulo plane symmetry) but are not drawn separately there. - _M. F. Hasler_, Aug 29 2017
%D A000055 F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Camb. 1998, p. 279.
%D A000055 Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 55.
%D A000055 N. L. Biggs et al., Graph Theory 1736-1936, Oxford, 1976, p. 49.
%D A000055 A. Cayley, On the analytical forms called trees, with application to the theory of chemical combinations, Reports British Assoc. Advance. Sci. 45 (1875), 257-305 = Math. Papers, Vol. 9, 427-460 (see p. 459).
%D A000055 S. R. Finch, Mathematical Constants, Cambridge, 2003, pp. 295-316.
%D A000055 J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 526.
%D A000055 F. Harary, Graph Theory. Addison-Wesley, Reading, MA, 1969, p. 232.
%D A000055 F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 58 and 244.
%D A000055 D. E. Knuth, Fundamental Algorithms, 3d Ed. 1997, pp. 386-88.
%D A000055 R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.
%D A000055 J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 138.
%D A000055 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A000055 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A000055 R. J. Mathar and Robert G. Wilson v, <a href="/A000055/b000055.txt">Table of n, a(n) for n = 0..1000</a>
%H A000055 Jeremy C. Adcock, Sam Morley-Short, Joshua W. Silverstone, and Mark G. Thompson, <a href="https://arxiv.org/abs/1806.03263">Hard limits on the postselectability of optical graph states</a>, arXiv:1806.03263 [quant-ph], 2018.
%H A000055 H. R. Afshar, E. A. Bergshoeff, and W. Merbis, <a href="http://arxiv.org/abs/1410.6164">Interacting spin-2 fields in three dimensions</a>, arXiv preprint arXiv:1410.6164 [hep-th], 2014-2015.
%H A000055 Ruggero Bandiera and Florian Schaetz, <a href="https://arxiv.org/abs/1702.08907">Eulerian idempotent, pre-Lie logarithm and combinatorics of trees</a>, arXiv:1702.08907 [math.CO], 2017. Mentions this sequence.
%H A000055 Madeleine Burkhart and Joel Foisy, <a href="https://doi.org/10.7566/JPSJ.86.104003">Enumerating spherical n-links</a>, Involve, Vol. 11 (2018), No. 2, 195-206.
%H A000055 P. J. Cameron, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/groups.html">Sequences realized by oligomorphic permutation groups</a>, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
%H A000055 A. Cayley, <a href="http://www.jstor.org/stable/2369158">On the analytical forms called trees</a>, Amer. J. Math., 4 (1881), 266-268.
%H A000055 CombOS - Combinatorial Object Server, <a href="http://combos.org/nauty">Generate graphs</a>
%H A000055 R. Ferrer-i-Cancho, <a href="http://arxiv.org/abs/1411.2645">Non-crossing dependencies: least effort, not grammar</a>, arXiv preprint arXiv:1411.2645 [cs.CL], 2014.
%H A000055 S. R. Finch, <a href="http://web.archive.org/web/20010207195939/http://www.mathsoft.com/asolve/constant/otter/otter.html">Otter's Tree Enumeration Constants</a>
%H A000055 P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see page 481.
%H A000055 Andrew Gainer-Dewar, <a href="https://doi.org/10.37236/2615">Gamma-Species and the Enumeration of k-Trees</a>, Electronic Journal of Combinatorics, Volume 19 (2012), #P45 and <a href="http://arxiv.org/abs/1208.5993">arXiv:1208.5993</a> [math.CO], 2012.
%H A000055 Xiangrui Gao, Song He, and Yong Zhang, <a href="https://arxiv.org/abs/1708.08701">Labelled tree graphs, Feynman diagrams and disk integrals</a> arxiv:1708.08701 [hep-th], 2017, see p. 4.
%H A000055 Ira M. Gessel, <a href="https://arxiv.org/abs/2305.03157">Good Will Hunting's Problem: Counting Homeomorphically Irreducible Trees</a>, arXiv:2305.03157 [math.CO], 2023.
%H A000055 D. D. Grant, <a href="http://dx.doi.org/10.1007/BFb0057373">The stability index of graphs</a>, pp. 29-52 of Combinatorial Mathematics (Proceedings 2nd Australian Conf.), Lect. Notes Math. 403, 1974. Gives first 45 terms.
%H A000055 Paul E. Gunnells, <a href="https://arxiv.org/abs/2102.05121">Generalized Catalan numbers from hypergraphs</a>, arXiv:2102.05121 [math.CO], 2021. Mentions this sequence p. 3.
%H A000055 T. Hoppe and A. Petrone, <a href="http://arxiv.org/abs/1408.3644">Integer sequence discovery from small graphs</a>, arXiv preprint arXiv:1408.3644 [math.CO], 2014.
%H A000055 S. Hougardy, <a href="http://dx.doi.org/10.1016/j.disc.2006.05.021">Classes of perfect graphs</a>, Discr. Math. 306 (2006), 2529-2571.
%H A000055 House of Graphs, <a href="https://houseofgraphs.org/meta-directory/trees">Trees</a>
%H A000055 Andrew Jobbings, <a href="https://web.archive.org/web/20171109081050 /http://www.arbelos.co.uk/Papers/Enumerating-nets.pdf">Enumerating nets</a>, Preprint 2015.
%H A000055 Elena V. Konstantinova and Maxim V. Vidyuk, <a href="http://dx.doi.org/10.1021/ci025659y">Discriminating tests of information and topological indices. Animals and trees</a>, J. Chem. Inf. Comput. Sci. 43 (2003), 1860-1871. See Table 15, column 1 on page 1868.
%H A000055 G. Labelle, C. Lamathe and P. Leroux, <a href="https://arxiv.org/abs/math/0312424">Labeled and unlabeled enumeration of k-gonal 2-trees</a>, arXiv:math/0312424 [math.CO], 2003.
%H A000055 Steve Lawford and Yll Mehmeti, <a href="https://arxiv.org/abs/1806.05866">Cliques and a new measure of clustering: with application to U.S. domestic airlines</a>, arXiv:1806.05866 [cs.SI], 2018.
%H A000055 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 A000055 Gang Li, <a href="http://webhome.cs.uvic.ca/~ruskey/Theses/GangLiMScThesis.pdf">Generation of Rooted Trees and Free Trees</a>, Comp. Sci. MSc thesis paper, 1996.
%H A000055 R. J. Mathar, <a href="http://arxiv.org/abs/1603.00077">Topologically Distinct Sets of Non-intersecting Circles in the Plane</a>, arXiv:1603.00077 [math.CO], 2016.
%H A000055 Richard J. Mathar, <a href="https://arxiv.org/abs/1808.06264">Counting Connected Graphs without Overlapping Cycles</a>, arXiv:1808.06264 [math.CO], 2018.
%H A000055 Robert Munafo, <a href="http://mrob.com/pub/seq/a005646.html#trees">Relation to Tree Graphs</a>
%H A000055 R. Otter, <a href="http://www.jstor.org/stable/1969046">The number of trees</a>, Ann. of Math. (2) 49 (1948), 583-599.
%H A000055 Igor Pak, <a href="https://arxiv.org/abs/1803.06636">Complexity problems in enumerative combinatorics</a>, arXiv:1803.06636 [math.CO], 2018.
%H A000055 E. M. Palmer and A. J. Schwenk, <a href="http://dx.doi.org/10.1016/0095-8956(79)90073-X">On the number of trees in a random forest</a>, J. Combin. Theory, B 27 (1979), 109-121.
%H A000055 Sebastian Piec, Krzysztof Malarz and Krzysztof Kulakowski. <a href="http://arxiv.org/abs/cond-mat/0501594">How to count trees?</a>, arXiv:cond-mat/0501594 [cond-mat.stat-mech], 2005; Int. J. Modern Phys., C16 (2005) 1527-1534.
%H A000055 N. Pippenger, <a href="http://dx.doi.org/10.1137/S0895480100368463">Enumeration of equicolorable trees</a>, SIAM J. Discrete Math., 14 (2001), 93-115.
%H A000055 J. M. Plotkin and J. W. Rosenthal, <a href="https://doi.org/10.1017/S1446788700034777">How to obtain an asymptotic expansion of a sequence from an analytic identity satisfied by its generating function</a>, J. Austral. Math. Soc. (Series A), Vol. 56 (1994), 131-143.
%H A000055 E. M. Rains and N. J. A. Sloane, <a href="https://cs.uwaterloo.ca/journals/JIS/cayley.html">On Cayley's Enumeration of Alkanes (or 4-Valent Trees)</a>, J. Integer Sequences, Vol. 2 (1999), Article 99.1.1.
%H A000055 R. W. Robinson, <a href="/A000055/a000055.png">Letter to N. J. A. Sloane, Jul 29 1980</a>
%H A000055 Sage, <a href="http://doc.sagemath.org/html/en/reference/graphs/sage/graphs/graph_generators.html">Common Graphs</a>
%H A000055 A. J. Schwenk, <a href="/A002988/a002988.pdf">Letter to N. J. A. Sloane, Aug 1972</a>
%H A000055 N. J. A. Sloane, <a href="/A000055/a000055.gif">Illustration of initial terms</a>
%H A000055 Peter Steinbach, <a href="/A000055/a000055.txt">Field Guide to Simple Graphs, Volume 3, Overview of the following parts</a>: <a href="/A000055/a000055_1.pdf">Cover</a>, <a href="/A000055/a000055_2.pdf">Front matter</a>, <a href="/A000055/a000055_3.pdf">Chapter 1: Trees</a>, <a href="/A000055/a000055_4.pdf">Trees (cont'd: pt.2)</a>, <a href="/A000055/a000055_6.pdf">Trees (cont'd: pt.3)</a>, <a href="/A000055/a000055_7.pdf">Chapter 2: Centers and Centroids</a>, <a href="/A000055/a000055_8.pdf">Chap.2 (cont'd)</a>, <a href="/A000055/a000055_9.pdf">Chapter 3: Random Trees</a>, <a href="/A000055/a000055_10.pdf">Chapter 4: Rooted Trees</a>, <a href="/A000055/a000055_11.pdf">Chapter 5: Homeomorphically Irreducible Trees</a>, <a href="/A000055/a000055_12.pdf">Chapter 6: Tables</a> (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
%H A000055 Tanay Wakhare, Eric Wityk, and Charles R. Johnson. <a href="https://doi.org/10.1016/j.disc.2020.112008">The proportion of trees that are linear</a>, Discrete Mathematics 343.10 (2020): 112008. Also arXiv:<a href="https://arxiv.org/abs/1901.08502">1901.08502</a> [math.CO], 2019-2020. See Tables 1 and 2 (but beware errors).
%H A000055 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Tree.html">Tree</a>
%H A000055 Pascal Welke, Tamás Horváth, and Stefan Wrobel, <a href="https://doi.org/10.1007/s10994-019-05779-1">Probabilistic and exact frequent subtree mining in graphs beyond forests</a>, Machine Learning (2019), 1-28.
%H A000055 Robert Alan Wright, Bruce Richmond, Andrew Odlyzko, and Brendan D. McKay, <a href="https://doi.org/10.1137/0215039">Constant Time Generation of Free Trees</a>, SIAM Journal of Computing, vol. 15, no. 2, pp. 540-548, (1986) [<a href="https://www.researchgate.net/publication/234811301">preprint</a>].
%H A000055 <a href="/index/Tra#trees">Index entries for sequences related to trees</a>
%H A000055 <a href="/index/Cor#core">Index entries for "core" sequences</a>
%F A000055 G.f.: A(x) = 1 + T(x) - T^2(x)/2 + T(x^2)/2, where T(x) = x + x^2 + 2*x^3 + ... is the g.f. for A000081.
%F A000055 a(n) ~ A086308 * A051491^n * n^(-5/2). - _Vaclav Kotesovec_, Jan 04 2013
%F A000055 a(n) = A000081(n) - A217420(n+1), n > 0. - _R. J. Mathar_, Sep 19 2016
%F A000055 a(n) = A000676(n) + A000677(n). - _R. J. Mathar_, Aug 13 2018
%F A000055 a(n) = A000081(n) - (Sum_{1<=i<=j, i+j=n} A000081(i)*A000081(j)) + (1-(-1)^(n-1)) * binomial(A000081(n/2)+1,2) / 2 [Li, equation 4.2]. - _Walt Rorie-Baety_, Jul 05 2021
%e A000055 a(1) = 1 [o]; a(2) = 1 [o-o]; a(3) = 1 [o-o-o];
%e A000055 a(4) = 2 [o-o-o and o-o-o-o]
%e A000055             |
%e A000055             o
%e A000055 G.f. = 1 + x + x^2 + x^3 + 2*x^4 + 3*x^5 + 6*x^6 + 11*x^7 + 23*x^8 + ...
%p A000055 G000055 := series(1+G000081-G000081^2/2+subs(x=x^2,G000081)/2,x,31); A000055 := n->coeff(G000055,x,n); # where G000081 is g.f. for A000081 starting with n=1 term
%p A000055 with(numtheory): b:= proc(n) option remember; `if`(n<=1, n, (add(add(d*b(d), d=divisors(j)) *b(n-j), j=1..n-1))/ (n-1)) end: a:= n-> `if`(n=0, 1, b(n) -(add(b(k) *b(n-k), k=0..n) -`if`(irem(n, 2)=0, b(n/2), 0))/2):
%p A000055 seq(a(n), n=0..50);
%p A000055 # _Alois P. Heinz_, Aug 21 2008
%p A000055 # Program to create b-file b000055.txt:
%p A000055 A000081 := proc(n) option remember; local d, j;
%p A000055 if n <= 1 then n else
%p A000055     add(add(d*procname(d),d=numtheory[divisors](j))*procname(n-j),j=1..n-1)/(n-1);
%p A000055 fi end:
%p A000055 A000055 := proc(nmax) local a81, n, t, a, j, i ;
%p A000055 a81 := [seq(A000081(i), i=0..nmax)] ; a := [] ;
%p A000055 for n from 0 to nmax do
%p A000055     if n = 0 then
%p A000055         t := 1+op(n+1, a81) ;
%p A000055     else
%p A000055         t := op(n+1, a81) ;
%p A000055     fi;
%p A000055     if type(n, even) then
%p A000055         t := t-op(1+n/2, a81)^2/2 ;
%p A000055         t := t+op(1+n/2, a81)/2 ;
%p A000055     fi;
%p A000055     for j from 0 to (n-1)/2 do
%p A000055         t := t-op(j+1, a81)*op(n-j+1, a81) ;
%p A000055     od:
%p A000055     a := [op(a), t] ;
%p A000055 od:
%p A000055 a end:
%p A000055 L := A000055(1000) ;
%p A000055 #  _R. J. Mathar_, Mar 06 2009
%t A000055 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_ *)
%t A000055 b[0] = 0; b[1] = 1; b[n_] := b[n] = Sum[d*b[d]*b[n-j], {j, 1, n-1}, {d, Divisors[j]}]/(n-1); a[0] = 1; a[n_] := b[n] - (Sum[b[k]*b[n-k], {k, 0, n}] - If[Mod[n, 2] == 0, b[n/2], 0])/2; Table[a[n], {n, 0, 50}] (* _Jean-François Alcover_, Apr 09 2014, after _Alois P. Heinz_ *)
%o A000055 (PARI) {a(n) = local(A, A1, an, i, t); if( n<2, n>=0, an = Vec(A = A1 = 1 + O('x^n)); for(m=2, n, i=m\2; an[m] = sum(k=1, i, an[k] * an[m-k]) + (t = polcoeff( if( m%2, A *= (A1 - 'x^i)^-an[i], A), m-1))); t + if( n%2==0, binomial( -polcoeff(A, i-1), 2)))}; /* _Michael Somos_ */
%o A000055 (PARI)
%o A000055 N=66;  A=vector(N+1, j, 1);
%o A000055 for (n=1, N, A[n+1] = 1/n * sum(k=1, n, sumdiv(k, d, d * A[d]) * A[n-k+1] ) );
%o A000055 A000081=concat([0], A);
%o A000055 H(t)=subst(Ser(A000081, 't), 't, t);
%o A000055 x='x+O('x^N);
%o A000055 Vec( 1 + H(x) - 1/2*( H(x)^2 - H(x^2) ) )
%o A000055 \\ _Joerg Arndt_, Jul 10 2014
%o A000055 (Magma)
%o A000055 N := 30; P<x> := PowerSeriesRing(Rationals(),N+1); f := func< A | x*&*[Exp(Evaluate(A,x^k)/k) : k in [1..N]]>; G := x; for i in [1..N] do G := f(G); end for; G000081 := G; G000055 := 1 + G - G^2/2 + Evaluate(G,x^2)/2; A000055 := Eltseq(G000055); // Geoff Baileu (geoff(AT)maths.usyd.edu.au), Nov 30 2009
%o A000055 (SageMath)
%o A000055 [len(list(graphs.trees(n))) for n in range(16)] # _Peter Luschny_, Mar 01 2020
%o A000055 (Haskell)
%o A000055 import Data.List (generic_index)
%o A000055 import Math.OEIS (getSequenceByID)
%o A000055 triangle x = (x * x + x) `div` 2
%o A000055 a000055 n = let {r = genericIndex (fromJust (getSequenceByID "A000081")); (m, nEO) = divMod n 2}
%o A000055             in  r n - sum (zipWith (*) (map r [0..m]) (map r [n, n-1..]))
%o A000055                 + (1-nEO) * (triangle (r m + 1))
%o A000055 -- _Walt Rorie-Baety_, Jun 12 2021
%o A000055 (Python)
%o A000055 # uses function from A000081
%o A000055 def A000055(n): return 1 if n == 0 else A000081(n)-sum(A000081(i)*A000081(n-i) for i in range(1,n//2+1)) + (0 if n % 2 else (A000081(n//2)+1)*A000081(n//2)//2) # _Chai Wah Wu_, Feb 03 2022
%Y A000055 Cf. A000676 (centered trees), A000677 (bicentered trees), A027416 (trees with a centroid), A102011 (trees with a bicentroid), A034853 (refined by diameter), A238414 (refined by maximum vertex degree).
%Y A000055 Cf. A000081 (rooted trees), A000272 (labeled trees), A000169 (labeled rooted trees), A212809 (radius of convergence).
%Y A000055 Cf. A036361 (labeled 2-trees), A036362 (labeled 3-trees), A036506 (labeled 4-trees), A054581 (unlabeled 2-trees).
%Y A000055 Cf. A157904, A157905, A005195 (Euler transform = forests), A095133 (multisets).
%Y A000055 Column 0 of A335362 and A034799.
%Y A000055 Related to A005646; see A171871 and A171872.
%Y A000055 Cf. also A000088, A008406, A051491, A086308.
%K A000055 nonn,easy,nice,core
%O A000055 0,5
%A A000055 _N. J. A. Sloane_

# Content is available under The OEIS End-User License Agreement: http://oeis.org/LICENSE