login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000055 Number of trees with n unlabeled nodes.
(Formerly M0791 N0299)
166
1, 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551, 1301, 3159, 7741, 19320, 48629, 123867, 317955, 823065, 2144505, 5623756, 14828074, 39299897, 104636890, 279793450, 751065460, 2023443032, 5469566585, 14830871802, 40330829030, 109972410221, 300628862480, 823779631721, 2262366343746, 6226306037178 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,5

COMMENTS

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

Main diagonal of A054924.

Left border of A157905. - Gary W. Adamson, Mar 08 2009

From Robert Munafo, Jan 24 2010: (Start)

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

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

Link to A171871/A171872 conjectured by Robert Munafo, then proved by Andrew Weimholt and Franklin T. Adams-Watters on Dec 29 2009. (End)

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

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

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

REFERENCES

F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Camb. 1998, p. 279.

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

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

S. R. Finch, Mathematical Constants, Cambridge, 2003, pp. 295-316.

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

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

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

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

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

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

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

R. J. Mathar and Robert G. Wilson v, Table of n, a(n) for n = 0..1000

H. R. Afshar, E. A. Bergshoeff, W. Merbis, Interacting spin-2 fields in three dimensions, arXiv preprint arXiv:1410.6164 [hep-th], 2014-015.

Ruggero Bandiera, Florian Schaetz, Eulerian idempotent, pre-Lie logarithm and combinatorics of trees, arXiv:1702.08907 [math.CO], 2017. Mentions this sequence.

P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.

A. Cayley, On the analytical forms called trees, Amer. J. Math., 4 (1881), 266-268.

R. Ferrer-i-Cancho, Non-crossing dependencies: least effort, not grammar, arXiv preprint arXiv:1411.2645 [cs.CL], 2014.

S. R. Finch, Otter's Tree Enumeration Constants

P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 481

Andrew Gainer-Dewar, Gamma-Species and the Enumeration of k-Trees, Electronic Journal of Combinatorics, Volume 19 (2012), #P45. - From N. J. A. Sloane, Dec 15 2012

D. D. Grant, The stability index of graphs, pp. 29-52 of Combinatorial Mathematics (Proceedings 2nd Australian Conf.), Lect. Notes Math. 403, 1974. Gives first 45 terms.

T. Hoppe, A. Petrone, Integer sequence discovery from small graphs, arXiv preprint arXiv:1408.3644 [math.CO], 2014.

S. Hougardy, Classes of perfect graphs, Discr. Math. 306 (2006), 2529-2571.

House of Graphs, Trees

Andrew Jobbings, Enumerating nets, Preprint 2015.

Elena V. Konstantinova and Maxim V. Vidyuk, Discriminating tests of information and topological indices. Animals and trees, J. Chem. Inf. Comput. Sci. 43 (2003), 1860-1871. See Table 15, column 1 on page 1868.

G. Labelle, C. Lamathe and P. Leroux, Labeled and unlabeled enumeration of k-gonal 2-trees, arXiv:math/0312424 [math.CO], 2003.

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)

R. J. Mathar, Topologically Distinct Sets of Non-intersecting Circles in the Plane, arXiv:1603.00077, 2016.

R. Munafo, Relation to Tree Graphs

R. Otter, The number of trees, Ann. of Math. (2) 49 (1948), 583-599.

E. M. Palmer and A. J. Schwenk, On the number of trees in a random forest, J. Combin. Theory, B 27 (1979), 109-121.

Sebastian Piec, Krzysztof Malarz and Krzysztof Kulakowski. How to count trees?, arXiv:cond-mat/0501594 [cond-mat.stat-mech], 2005; Int. J. Modern Phys., C16 (2005) 1527-1534.

N. Pippenger, Enumeration of equicolorable trees, SIAM J. Discrete Math., 14 (2001), 93-115.

E. M. Rains and N. J. A. Sloane, On Cayley's Enumeration of Alkanes (or 4-Valent Trees), J. Integer Sequences, Vol. 2 (1999), Article 99.1.1.

R. W. Robinason, Letter to N. J. A. Sloane, Jul 29 1980

Sage, Common Graphs

A. J. Schwenk, Letter to N. J. A. Sloane, Aug 1972

N. J. A. Sloane, Illustration of initial terms

Peter Steinbach, Field Guide to Simple Graphs, Volume 3, Overview of the following 12 Parts: Cover, Front matter, Chapter 1: Trees, Trees (cont'd: pt.2), Trees (cont'd: pt.3), Trees (cont'd: pt.4), Chapter 2: Centers and Centroids, Chap.2 (cont'd), Chapter 3: Random Trees, Chapter 4: Rooted Trees, Chapter 5: Homeomorphically Irreducible Trees, Chapter 6: Tables (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)

Eric Weisstein's World of Mathematics, Tree

Robert Alan Wright, Bruce Richmond, Andrew Odlyzko, Brendan D. McKay, Constant Time Generation of Free Trees, SIAM Journal of Computing, vol. 15, no. 2, pp. 540-548, (1986) [preprint].

Index entries for sequences related to trees

Index entries for "core" sequences

FORMULA

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.

a(n) = A000081(n) - A217420(n+1), n>0. - R. J. Mathar, Sep 19 2016

EXAMPLE

a(1) = 1 [o]; a(2) = 1 [o-o]; a(3) = 1 [o-o-o];

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

........... | ..............

........... o ..............

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

MAPLE

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

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

seq(a(n), n=0..50);

# Alois P. Heinz, Aug 21 2008

# Program to create b-file b000055.txt:

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

if n <= 1 then n else

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

fi end:

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

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

for n from 0 to nmax do

    if n = 0 then

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

    else

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

    fi;

    if type(n, even) then

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

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

    fi;

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

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

    od:

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

od:

a end:

L := A000055(1000) ;

#  R. J. Mathar, Mar 06 2009

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

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

PROG

(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 */

(PARI)

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

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

A000081=concat([0], A);

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

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

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

\\ Joerg Arndt, Jul 10 2014

(MAGMA) 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

CROSSREFS

Cf. A000676 (centered trees), A000677 (bicentered trees), A027416 (trees with a centroid), A102011 (trees with a bicentroid), A034853 (refined by diameter), A238414 (refined by max vert degree).

Cf. A000081 (rooted trees), A000272 (labeled trees), A000169 (labeled rooted trees), A212809 (radius of convergence).

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

Cf. A157904, A157905.

Related to A005646; see A171871 and A171872.

Cf. also A000088, A008406, A051491, A086308.

Sequence in context: A130131 A277796 A123465 * A217312 A006787 A176425

Adjacent sequences:  A000052 A000053 A000054 * A000056 A000057 A000058

KEYWORD

nonn,easy,nice,core

AUTHOR

N. J. A. Sloane

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy .

Last modified December 14 11:57 EST 2017. Contains 295981 sequences.