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

 

Logo

Invitation: celebrating 50 years of OEIS, 250000 sequences, and Sloane's 75th, there will be a conference at DIMACS, Rutgers, Oct 9-10 2014.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000055 Number of trees with n unlabeled nodes.
(Formerly M0791 N0299)
111
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 K 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)

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

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.

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.

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

R. Munafo, Relation to Tree Graphs [From Robert Munafo, Jan 24 2010]

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?, Internal. 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.

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

Eric Weisstein's World of Mathematics, Tree

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

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

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. [From Gary W. Adamson, Mar 08 2009]

Related to A005646; see A171871 and A171872. [From Robert Munafo, Jan 24 2010]

Cf. A051491, A086308.

Sequence in context: A211694 A130131 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 | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified August 28 07:22 EDT 2014. Contains 246162 sequences.