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!)
A000055 Number of trees with n unlabeled nodes.
(Formerly M0791 N0299)
225

%I M0791 N0299 #342 Oct 12 2023 01:52:59

%S 1,1,1,1,2,3,6,11,23,47,106,235,551,1301,3159,7741,19320,48629,123867,

%T 317955,823065,2144505,5623756,14828074,39299897,104636890,279793450,

%U 751065460,2023443032,5469566585,14830871802,40330829030,109972410221,300628862480,823779631721,2262366343746,6226306037178

%N Number of trees with n unlabeled nodes.

%C Also, number of unlabeled 2-gonal 2-trees with n 2-gons.

%C Main diagonal of A054924.

%C Left border of A157905. - _Gary W. Adamson_, Mar 08 2009

%C From _Robert Munafo_, Jan 24 2010: (Start)

%C Also counts classifications of n items that require exactly n-1 binary partitions; see Munafo link at A005646, also A171871 and A171872.

%C The 11 trees for n = 7 are illustrated at the Munafo web link.

%C Link to A171871/A171872 conjectured by _Robert Munafo_, then proved by _Andrew Weimholt_ and _Franklin T. Adams-Watters_ on Dec 29 2009. (End)

%C This is also "Number of tree perfect graphs on n nodes" [see Hougardy]. - _N. J. A. Sloane_, Dec 04 2015

%C 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 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 F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Camb. 1998, p. 279.

%D Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 55.

%D N. L. Biggs et al., Graph Theory 1736-1936, Oxford, 1976, p. 49.

%D 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 S. R. Finch, Mathematical Constants, Cambridge, 2003, pp. 295-316.

%D J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 526.

%D F. Harary, Graph Theory. Addison-Wesley, Reading, MA, 1969, p. 232.

%D F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 58 and 244.

%D D. E. Knuth, Fundamental Algorithms, 3d Ed. 1997, pp. 386-88.

%D R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.

%D J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 138.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H R. J. Mathar and Robert G. Wilson v, <a href="/A000055/b000055.txt">Table of n, a(n) for n = 0..1000</a>

%H 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 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 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 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 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 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 CombOS - Combinatorial Object Server, <a href="http://combos.org/nauty">Generate graphs</a>

%H 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 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 P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see page 481.

%H 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 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 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 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 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 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 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 House of Graphs, <a href="https://houseofgraphs.org/meta-directory/trees">Trees</a>

%H 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 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 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 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 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 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 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 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 R. Munafo, <a href="http://mrob.com/pub/seq/a005646.html#trees">Relation to Tree Graphs</a>

%H R. Otter, <a href="http://www.jstor.org/stable/1969046">The number of trees</a>, Ann. of Math. (2) 49 (1948), 583-599.

%H Igor Pak, <a href="https://arxiv.org/abs/1803.06636">Complexity problems in enumerative combinatorics</a>, arXiv:1803.06636 [math.CO], 2018.

%H 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 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 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 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 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 R. W. Robinason, <a href="/A000055/a000055.png">Letter to N. J. A. Sloane, Jul 29 1980</a>

%H Sage, <a href="http://doc.sagemath.org/html/en/reference/graphs/sage/graphs/graph_generators.html">Common Graphs</a>

%H A. J. Schwenk, <a href="/A002988/a002988.pdf">Letter to N. J. A. Sloane, Aug 1972</a>

%H N. J. A. Sloane, <a href="/A000055/a000055.gif">Illustration of initial terms</a>

%H Peter Steinbach, <a href="/A000055/a000055.txt">Field Guide to Simple Graphs, Volume 3, Overview of the following 12 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_5.pdf">Trees (cont'd: pt.3)</a>, <a href="/A000055/a000055_6.pdf">Trees (cont'd: pt.4)</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 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 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Tree.html">Tree</a>

%H 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 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 <a href="/index/Tra#trees">Index entries for sequences related to trees</a>

%H <a href="/index/Cor#core">Index entries for "core" sequences</a>

%F 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 a(n) ~ A086308 * A051491^n * n^(-5/2). - _Vaclav Kotesovec_, Jan 04 2013

%F a(n) = A000081(n) - A217420(n+1), n > 0. - _R. J. Mathar_, Sep 19 2016

%F a(n) = A000676(n)+A000677(n). - _R. J. Mathar_, Aug 13 2018

%F 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 a(1) = 1 [o]; a(2) = 1 [o-o]; a(3) = 1 [o-o-o];

%e a(4) = 2 [o-o-o and o-o-o-o]

%e |

%e o

%e G.f. = 1 + x + x^2 + x^3 + 2*x^4 + 3*x^5 + 6*x^6 + 11*x^7 + 23*x^8 + ...

%p 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 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 seq(a(n), n=0..50);

%p # _Alois P. Heinz_, Aug 21 2008

%p # Program to create b-file b000055.txt:

%p A000081 := proc(n) option remember; local d, j;

%p if n <= 1 then n else

%p add(add(d*procname(d),d=numtheory[divisors](j))*procname(n-j),j=1..n-1)/(n-1);

%p fi end:

%p A000055 := proc(nmax) local a81, n, t, a, j, i ;

%p a81 := [seq(A000081(i), i=0..nmax)] ; a := [] ;

%p for n from 0 to nmax do

%p if n = 0 then

%p t := 1+op(n+1, a81) ;

%p else

%p t := op(n+1, a81) ;

%p fi;

%p if type(n, even) then

%p t := t-op(1+n/2, a81)^2/2 ;

%p t := t+op(1+n/2, a81)/2 ;

%p fi;

%p for j from 0 to (n-1)/2 do

%p t := t-op(j+1, a81)*op(n-j+1, a81) ;

%p od:

%p a := [op(a), t] ;

%p od:

%p a end:

%p L := A000055(1000) ;

%p # _R. J. Mathar_, Mar 06 2009

%t 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 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 (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 (PARI)

%o N=66; A=vector(N+1, j, 1);

%o for (n=1, N, A[n+1] = 1/n * sum(k=1, n, sumdiv(k, d, d * A[d]) * A[n-k+1] ) );

%o A000081=concat([0], A);

%o H(t)=subst(Ser(A000081, 't), 't, t);

%o x='x+O('x^N);

%o Vec( 1 + H(x) - 1/2*( H(x)^2 - H(x^2) ) )

%o \\ _Joerg Arndt_, Jul 10 2014

%o (Magma)

%o 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 (SageMath)

%o [len(list(graphs.trees(n))) for n in range(16)] # _Peter Luschny_, Mar 01 2020

%o (Haskell)

%o import Data.List (generic_index)

%o import Math.OEIS (getSequenceByID)

%o triangle x = (x * x + x) `div` 2

%o a000055 n = let {r = genericIndex (fromJust (getSequenceByID "A000081")); (m, nEO) = divMod n 2}

%o in r n - sum (zipWith (*) (map r [0..m]) (map r [n, n-1..]))

%o + (1-nEO) * (triangle (r m + 1))

%o -- _Walt Rorie-Baety_, Jun 12 2021

%o (Python)

%o # uses function from A000081

%o 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 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 Cf. A000081 (rooted trees), A000272 (labeled trees), A000169 (labeled rooted trees), A212809 (radius of convergence).

%Y Cf. A036361 (labeled 2-trees), A036362 (labeled 3-trees), A036506 (labeled 4-trees), A054581 (unlabeled 2-trees).

%Y Cf. A157904, A157905, A005195 (Euler transform = forests), A095133 (multisets).

%Y Column 0 of A335362 and A034799.

%Y Related to A005646; see A171871 and A171872.

%Y Cf. also A000088, A008406, A051491, A086308.

%K nonn,easy,nice,core

%O 0,5

%A _N. J. A. Sloane_

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 14:38 EDT 2024. Contains 371254 sequences. (Running on oeis4.)