|
| |
|
|
A000055
|
|
Number of trees with n unlabeled nodes.
(Formerly M0791 N0299)
|
|
99
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,5
|
|
|
COMMENTS
|
Also, number of unlabeled 2-gonal 2-trees with n 2-gons.
Equals INVERTi transform of A157904: (1, 2, 4, 8, 17, 36, 78, 170,...). [From Gary W. Adamson, Mar 08 2009]
Equals left border of triangle A157905 [From Gary W. Adamson, Mar 08 2009]
Contribution 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, Amer. J. Math., 4 (1881), 266-268.
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.
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.
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.
Elena V. Konstantinova and Maxim V. Vidyuk, "Discriminating tests of information and topological indices. Animals and trees", J. Chem. Inf. Comput. Sci., (2003), vol. 43, 1860-1871. See Table 15, column 1 on page 1868.
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.
N. Pippenger, Enumeration of equicolorable trees, SIAM J. Discrete Math., 14 (2001), 93-115.
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.
S. R. Finch, Otter's Tree Enumeration Constants
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 481
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]
Sebastian Piec, Krzysztof Malarz and Krzysztof Kulakowski. How to count trees?, Internal. J. Modern Phys., C16 (2005) 1527-1534.
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 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 ..............
|
|
|
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; local d, j; `if` (n<=1, n, (add (add (d*b(d), d=divisors(j)) *b(n-j), j=1..n-1))/ (n-1)) end: a:= proc(n) option remember; local k; `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) end:
seq (a(n), n=0..50); # Alois P. Heinz, Aug 21 2008
# Another version: create b-file b000055.txt, from R. J. Mathar, Mar 06 2009 (Start)
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 ;
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:
# maximum b-file elements: 1000
L := A000055(1000) ; # (End)
|
|
|
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 *)
|
|
|
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
(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).
Main diagonal of A054924.
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
|
| |
|
|
