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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000081 Number of unlabeled rooted trees with n nodes (or connected functions with a fixed point).
(Formerly M1180 N0454)
488

%I M1180 N0454

%S 0,1,1,2,4,9,20,48,115,286,719,1842,4766,12486,32973,87811,235381,

%T 634847,1721159,4688676,12826228,35221832,97055181,268282855,

%U 743724984,2067174645,5759636510,16083734329,45007066269,126186554308,354426847597

%N Number of unlabeled rooted trees with n nodes (or connected functions with a fixed point).

%C Also, number of ways of arranging n-1 nonoverlapping circles: e.g., there are 4 ways to arrange 3 circles, as represented by ((O)), (OO), (O)O, OOO, also see example. (Of course the rules here are different from the usual counting parentheses problems - compare A000108, A001190, A001699.) See Sloane's link for a proof and Vogeler's link for illustration of a(7) as arrangement of 6 circles.

%C Take a string of n x's and insert n-1 ^'s and n-1 pairs of parentheses in all possible legal ways (cf. A003018). Sequence gives number of distinct functions. The single node tree is "x". Making a node f2 a child of f1 represents f1^f2. Since (f1^f2)^f3 is just f1^(f2*f3) we can think of it as f1 raised to both f2 and f3, that is, f1 with f2 and f3 as children. E.g., for n=4 the distinct functions are ((x^x)^x)^x; (x^(x^x))^x; x^((x^x)^x); x^(x^(x^x)). - _W. Edwin Clark_ and _Russ Cox_ Apr 29, 2003; corrected by Keith Briggs (keith.briggs(AT)bt.com), Nov 14 2005

%C Also, number of connected multigraphs of order n without cycles except for one loop. - _Washington Bomfim_, Sep 04 2010

%C Also, number of planted trees with n+1 nodes.

%C Also called "Polya trees" by Genitrini (2016). - _N. J. A. Sloane_, Mar 24 2017

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

%D N. L. Biggs et al., Graph Theory 1736-1936, Oxford, 1976, p. 42, 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. 451).

%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, pp. 54 and 244.

%D Alexander S. Karpenko, Łukasiewicz Logics and Prime Numbers, Luniver Press, Beckington, 2006, p. 82.

%D D. E. Knuth, The Art of Computer Programming, Vol. 1: Fundamental Algorithms, 3d Ed. 1997, pp. 386-388.

%D D. E. Knuth, The Art of Computer Programming, vol. 1, 3rd ed., Fundamental Algorithms, p. 395, ex. 2.

%D D. E. Knuth, TAOCP, Vol. 4, Section 7.2.1.6.

%D G. Polya and R. C. Read, Combinatorial Enumeration of Groups, Graphs and Chemical Compounds, Springer-Verlag, 1987, p. 63.

%D R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998. [Comment from Neven Juric: Page 64 incorrectly gives a(21)=35224832.]

%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 N. J. A. Sloane and Robert G. Wilson v, <a href="/A000081/b000081.txt">Table of n, a(n) for n = 0..1000</a> the first 201 terms from N. J. A. Sloane.

%H M. J. H. Al-Kaabi, D. Manchon, F. Patras, <a href="https://arxiv.org/abs/1708.08312">Monomial bases and pre-Lie structure for free Lie algebras</a>, arXiv:1708.08312 [math.RA], 2017, See p. 5.

%H Winfried Auzinger, H Hofstaetter, O Koch, <a href="http://arxiv.org/abs/1605.00453">Symbolic Manipulation of Flows of Nonlinear Evolution Equations, with Application in the Analysis of Split-Step Time Integrators</a>, arXiv preprint arXiv:1605.00453 [math.NA], 2016.

%H Roland Bacher, <a href="http://hal.archives-ouvertes.fr/hal-01025881">Counting invertible Schrodinger Operators over Finite Fields for Trees Cycles and Complete Graphs</a>, preprint, 2015.

%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 P. Flajolet, S. Gerhold and B. Salvy, <a href="https://arxiv.org/abs/math/0501379">On the non-holonomic character of logarithms, powers and the n-th prime function</a>, arXiv:math/0501379 [math.CO], 2005.

%H P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see page 71

%H A. Genitrini, <a href="http://arxiv.org/abs/1605.00837">Full asymptotic expansion for Polya structures</a>, arXiv:1605.00837 [math.CO], May 03 2016, p. 6.

%H Bernhard Gittenberger, Emma Yu Jin, Michael Wallner, <a href="https://arxiv.org/abs/1707.02144">On the shape of random Pólya structures</a>, arXiv|1707.02144 [math.CO], 2017-2018; Discrete Math., 341 (2018), 896-911.

%H F. Goebel, <a href="http://dx.doi.org/10.1016/0095-8956(80)90049-0">On a 1-1-correspondence between rooted trees and natural numbers</a>, J. Combin. Theory, B 29 (1980), 141-143.

%H F. Goebel and R. P. Nederpelt, <a href="http://www.jstor.org/stable/2316312">The number of numerical outcomes of iterated powers</a>, Amer. Math. Monthly, 80 (1971), 1097-1103.

%H Ivan Gutman and Yeong-Nan Yeh, <a href="http://www.emis.de/journals/PIMB/067/3.html">Deducing properties of trees from their Matula numbers</a>, Publications de l'Institut Mathématique (Beograd) (N.S.), Vol. 53(67), pp. 17--22 (1993).

%H R. K. Guy, <a href="/A000081/a000081.pdf">Letter to N. J. A. Sloane, 1988-04-12</a> (annotated scanned copy)

%H R. K. Guy and J. L. Selfridge, <a href="/A003018/a003018.pdf">The nesting and roosting habits of the laddered parenthesis</a> (annotated cached copy)

%H R. K. Guy and J. L. Selfridge, <a href="http://www.jstor.org/stable/2319392">The nesting and roosting habits of the laddered parenthesis</a>, Amer. Math. Monthly 80 (8) (1973), 868-876.

%H F. Harary, G. Prins, <a href="http://dx.doi.org/10.1007/BF0255954">The number of homeomorphically irreducible trees, and other species</a>, Acta Math. 101 (1-2) (1959) 141-161, see page 146.

%H F. Harary & R. W. Robinson, <a href="/A000108/a000108_18.pdf">The number of achiral trees</a>, Jnl. Reine Angewandte Mathematik 278 (1975), 322-335. (Annotated scanned copy)

%H R. Harary, R. W. Robinson, <a href="http://dx.doi.org/10.1007/BF02579217">Isomorphic factorizations VIII: bisectable trees</a>, Combinatorica 4 (2) (1984) 169-179, eq. (4.3)

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=57">Encyclopedia of Combinatorial Structures 57</a>

%H E. Kalinowski and W. Gluza, <a href="http://arxiv.org/abs/1106.4938">Evaluation of High Order Terms for the Hubbard Model in the Strong-Coupling Limit</a>, arXiv:1106.4938 [cond-mat.str-el], 2011 (Physical Review B 85, 045105, Jan 2012).

%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 Math Overflow, <a href="http://mathoverflow.net/questions/79442/number-of-distinct-values-taken-by-xx-x-with-parentheses-inserted-in-all-pos">Discussion</a>

%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 D. Matula, <a href="http://www.jstor.org/stable/2027327?seq=30">A natural rooted tree enumeration by prime factorization</a>, SIAM Rev. 10 (1968) 273.

%H R. I. McLachlan, K. Modin, H. Munthe-Kaas, O. Verdier, <a href="http://arxiv.org/abs/1512.00906">What are Butcher series, really? The story of rooted trees and numerical methods for evolution equations</a>, arXiv preprint arXiv:1512.00906 [math.NA], 2015.

%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 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 G. Polya, <a href="http://dx.doi.org/10.1007/BF02546665">Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen</a>, Acta Mathematica, vol.68, no.1, pp.145-254, (1937).

%H R. W. Robinson, <a href="/A000055/a000055.png">Letter to N. J. A. Sloane, Jul 29 1980</a>

%H F. Ruskey, <a href="http://www.theory.cs.uvic.ca/~cos/inf/tree/RootedTree.html">Information on Rooted Trees</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="/A000081/a000081.html">Illustration of initial terms</a>

%H N. J. A. Sloane, <a href="/A000081/a000081b.txt">Bijection between rooted trees and arrangements of circles</a>

%H Peter Steinbach, <a href="/A000088/a000088_17.pdf">Field Guide to Simple Graphs, Volume 1</a>, Part 17 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)

%H Peter Steinbach, <a href="/A000055/a000055_10.pdf">Field Guide to Simple Graphs, Volume 3</a>, Part 10 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)

%H Peter Steinbach, <a href="/A000055/a000055_12.pdf">Field Guide to Simple Graphs, Volume 3</a>, Part 12 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)

%H Roger Vogeler, <a href="/A000081/a000081.jpg">Six Circles</a>, 2015 (illustration for a(7) as the number of arrangements of six circles).

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/RootedTree.html">Rooted Tree</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PlantedTree.html">Planted Tree</a>

%H G. Xiao, <a href="http://wims.unice.fr/~wims/en_tool~number~contfrac.en.html">Contfrac</a>

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

%H <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>

%H <a href="/index/Tra#trees">Index entries for sequences related to trees</a>

%H <a href="/index/Par#parens">Index entries for sequences related to parenthesizing</a>

%H <a href="/index/Con#confC">Index entries for continued fractions for constants</a>

%F G.f. A(x) satisfies A(x) = x*exp(A(x)+A(x^2)/2+A(x^3)/3+A(x^4)/4+...) [Polya]

%F Also A(x) = Sum_{n>=1} a(n)*x^n = x / Product_{n>=1} (1-x^n)^a(n).

%F Recurrence: a(n+1) = (1/n) * Sum_{k=1..n} ( Sum_{d|k} d*a(d) ) * a(n-k+1).

%F Asymptotically c * d^n * n^(-3/2), where c = A187770 = 0.439924... and d = A051491 = 2.955765... [Polya; Knuth, section 7.2.1.6].

%F Euler transform is sequence itself with offset -1. - _Michael Somos_, Dec 16 2001

%F For n > 1, a(n) = A087803(n) - A087803(n-1). - _Vladimir Reshetnikov_, Nov 06 2015

%F For n > 1, a(n) = A123467(n-1). - _Falk Hüffner_, Nov 26 2015

%e G.f. = x + x^2 + 2*x^3 + 4*x^4 + 9*x^5 + 20*x^6 + 48*x^7 + 115*x^8 + ...

%e From _Joerg Arndt_, Jun 29 2014: (Start)

%e The a(6) = 20 trees with 6 nodes have the following level sequences (with level of root =0) and parenthesis words:

%e 01: [ 0 1 2 3 4 5 ] (((((())))))

%e 02: [ 0 1 2 3 4 4 ] ((((()()))))

%e 03: [ 0 1 2 3 4 3 ] ((((())())))

%e 04: [ 0 1 2 3 4 2 ] ((((()))()))

%e 05: [ 0 1 2 3 4 1 ] ((((())))())

%e 06: [ 0 1 2 3 3 3 ] (((()()())))

%e 07: [ 0 1 2 3 3 2 ] (((()())()))

%e 08: [ 0 1 2 3 3 1 ] (((()()))())

%e 09: [ 0 1 2 3 2 3 ] (((())(())))

%e 10: [ 0 1 2 3 2 2 ] (((())()()))

%e 11: [ 0 1 2 3 2 1 ] (((())())())

%e 12: [ 0 1 2 3 1 2 ] (((()))(()))

%e 13: [ 0 1 2 3 1 1 ] (((()))()())

%e 14: [ 0 1 2 2 2 2 ] ((()()()()))

%e 15: [ 0 1 2 2 2 1 ] ((()()())())

%e 16: [ 0 1 2 2 1 2 ] ((()())(()))

%e 17: [ 0 1 2 2 1 1 ] ((()())()())

%e 18: [ 0 1 2 1 2 1 ] ((())(())())

%e 19: [ 0 1 2 1 1 1 ] ((())()()())

%e 20: [ 0 1 1 1 1 1 ] (()()()()())

%e (End)

%p N := 30: a := [1,1]; for n from 3 to N do x*mul( (1-x^i)^(-a[i]), i=1..n-1); series(%,x,n+1); b := coeff(%,x,n); a := [op(a),b]; od: a; A000081 := proc(n) if n=0 then 1 else a[n]; fi; end; G000081 := series(add(a[i]*x^i,i=1..N),x,N+2); # also used in A000055

%p spec := [ T, {T=Prod(Z,Set(T))} ]; A000081 := n-> combstruct[count](spec,size=n); [seq(combstruct[count](spec,size=n), n=0..40)];

%p # a much more efficient method for computing the result with Maple. It uses two procedures:

%p a := proc(n) local k; a(n) := add(k*a(k)*s(n-1,k), k=1..n-1)/(n-1) end proc:

%p a(0) := 0: a(1) := 1: s := proc(n,k) local j; s(n,k) := add(a(n+1-j*k), j=1..iquo(n,k)); # Joe Riel (joer(AT)san.rr.com), Jun 23 2008

%p # even more efficient, uses the Euler transform:

%p with(numtheory): a:= proc(n) option remember; local d, j; `if`(n<=1, n, (add(add(d*a(d), d=divisors(j)) *a(n-j), j=1..n-1))/ (n-1)) end:

%p seq(a(n), n=0..50); # _Alois P. Heinz_, Sep 06 2008

%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 ], {i, 1, 30} ] (* _Robert A. Russell_ *)

%t a[n_] := a[n] = If[n <= 1, n, Sum[Sum[d*a[d], {d, Divisors[j]}]*a[n-j], {j, 1, n-1}]/(n-1)]; Table[a[n], {n, 0, 30}] (* _Jean-François Alcover_, Feb 17 2014, after _Alois P. Heinz_ *)

%t a[n_] := a[n] = If[n <= 1, n, Sum[a[n - j] DivisorSum[j, # a[#] &], {j, n - 1}]/(n - 1)]; Table[a[n], {n, 0, 30}] (* _Jan Mangaldan_, May 07 2014, after _Alois P. Heinz_ *)

%t (* first do *) << NumericalDifferentialEquationAnalysis`; (* then *)

%t ButcherTreeCount[30] (* v8 onward _Robert G. Wilson v_, Sep 16 2014 *)

%t a[n:0|1] := n; a[n_] := a[n] = Sum[m a[m] a[n-k*m], {m, n-1}, {k, (n-1)/m}]/(n-1); Table[a[n], {n, 0, 30}] (* _Vladimir Reshetnikov_, Nov 06 2015 *)

%t terms = 31; A[_] = 0; Do[A[x_] = x*Exp[Sum[A[x^k]/k, {k, 1, j}]] + O[x]^j // Normal, {j, 1, terms}]; CoefficientList[A[x], x] (* _Jean-François Alcover_, Jan 11 2018 *)

%o (PARI) {a(n) = local(A = x); if( n<1, 0, for( k=1, n-1, A /= (1 - x^k + x * O(x^n))^polcoeff(A, k)); polcoeff(A, n))}; /* _Michael Somos_, Dec 16 2002 */

%o (PARI) {a(n) = local(A, A1, an, i); if( n<1, 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]) + polcoeff( if( m%2, A *= (A1 - x^i)^-an[i], A), m-1)); an[n])}; /* _Michael Somos_, Sep 05 2003 */

%o (PARI) 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 concat([0], A) \\ _Joerg Arndt_, Apr 17 2014

%o (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; A000081 := [0] cat Eltseq(G); // Geoff Bailey (geoff(AT)maths.usyd.edu.au), Nov 30 2009

%o (Maxima)

%o g(m):= block([si,v],s:0,v:divisors(m), for si in v do (s:s+r(m/si)/si),s);

%o r(n):=if n=1 then 1 else sum(Co(n-1,k)/k!,k,1,n-1);

%o Co(n,k):=if k=1 then g(n) else sum(g(i+1)*Co(n-i-1,k-1),i,0,n-k);

%o makelist(r(n),n,1,12); /*_Vladimir Kruchinin_, Jun 15 2012 */

%o (Haskell)

%o import Data.List (genericIndex)

%o a000081 = genericIndex a000081_list

%o a000081_list = 0 : 1 : f 1 [1,0] where

%o f x ys = y : f (x + 1) (y : ys) where

%o y = sum (zipWith (*) (map h [1..x]) ys) `div` x

%o h = sum . map (\d -> d * a000081 d) . a027750_row

%o -- _Reinhard Zumkeller_, Jun 17 2013

%o (Sage)

%o @CachedFunction

%o def a(n):

%o if n < 2: return n

%o return add(add(d*a(d) for d in divisors(j))*a(n-j) for j in (1..n-1))/(n-1)

%o [a(n) for n in (0..30)] # _Peter Luschny_, Jul 18 2014 after _Alois P. Heinz_

%Y Cf. A000041 (partitions), A000055 (unrooted trees), A000169, A001858, A005200, A027750, A051491, A051492, A093637, A187770, A199812, A255170.

%Y Row sums of A144963. - _Gary W. Adamson_, Sep 27 2008

%Y Cf. A209397 (log(A(x)/x)).

%Y Cf. A000106 (self-convolution).

%Y Cf. A087803 (partial sums).

%K nonn,easy,core,nice,eigen

%O 0,4

%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 | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 21 04:21 EST 2018. Contains 317428 sequences. (Running on oeis4.)