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!)
A000081 Number of unlabeled rooted trees with n nodes (or connected functions with a fixed point).
(Formerly M1180 N0454)
310

%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 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-01025881v3">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="http://arXiv.org/abs/math.CO/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 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>

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

%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, A051491, 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 December 11 21:15 EST 2017. Contains 295919 sequences.