%I A000081 M1180 N0454
%S A000081 0,1,1,2,4,9,20,48,115,286,719,1842,4766,12486,32973,87811,235381,
%T A000081 634847,1721159,4688676,12826228,35221832,97055181,268282855,743724984,
%U A000081 2067174645,5759636510,16083734329,45007066269,126186554308,354426847597
%N A000081 Number of rooted trees with n nodes (or connected functions with a fixed 
               point).
%C A000081 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. (Of course the rules here are different from the usual counting 
               parentheses problems - compare A000108, A001190, A001699.) See link 
               below for proof.
%C A000081 Euler transform is sequence itself with offset -1.
%C A000081 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 )). - Edwin Clark (eclark(AT)math.usf.edu) 
               and Russ Cox (rsc(AT)swtch.com) Apr 29, 2003; corrected by Keith 
               Briggs (keith.briggs(AT)bt.com), Nov 14 2005
%C A000081 Triangle A144963: row sums = (1, 2, 4, 9, 20,...), right border = (1, 
               1, 2, 4, 9,...); and left border = A051573: (1, 1, 1, 2, 3, 8, 16,
               ...). [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Sep 27 2008]
%D A000081 F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like 
               Structures, Camb. 1998, p. 279.
%D A000081 N. L. Biggs et al., Graph Theory 1736-1936, Oxford, 1976, p. 42, 49.
%D A000081 A. Cayley, On the analytical forms called trees, Amer. J. Math., 4 (1881), 
               266-268.
%D A000081 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 A000081 F. Goebel, On a 1-1-correspondence between rooted trees and natural numbers, 
               J. Combin. Theory, B 29 (1980), 141-143.
%D A000081 F. Goebel and R. P. Nederpelt, The number of numerical outcomes of iterated 
               powers, Amer. Math. Monthly, 80 (1971), 1097-1103.
%D A000081 J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 
               2004; p. 526.
%D A000081 R. K. Guy and J. L. Selfridge, The nesting and roosting habits of the 
               laddered parenthesis. Amer. Math. Monthly 80 (1973), 868-876.
%D A000081 F. Harary, Graph Theory. Addison-Wesley, Reading, MA, 1969, p. 232.
%D A000081 F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 
               1973, pp. 54 and 244.
%D A000081 D. E. Knuth, The Art of Computer Programming, Vol. 1: Fundamental Algorithms, 
               3d Ed. 1997, pp. 386-388.
%D A000081 D. E. Knuth, TAOCP, Vol. 4, Section 7.2.1.6.
%D A000081 D. Matula, A natural rooted tree enumeration by prime factorization, 
               SIAM Rev. 10 (1968).
%D A000081 N. Pippenger, Enumeration of equicolorable trees, SIAM J. Discrete Math., 
               14 (2001), 93-115.
%D A000081 G. Polya, Kombinatorische Anzahlbestimmungen fuer Gruppen, Graphen und 
               chemische Verbindungen, Acta Math. 68 (1937), 145-254.
%D A000081 G. Polya and R. C. Read, Combinatorial Enumeration of Groups, Graphs 
               and Chemical Compounds, Springer-Verlag, 1987, p. 63.
%D A000081 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 A000081 J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 
               138.
%D A000081 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 
               (includes this sequence).
%D A000081 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, 
               Academic Press, 1995 (includes this sequence).
%D A000081 R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see 
               Proposition 5.3.1, p. 23.
%D A000081 D. E. Knuth, The Art of Computer Programming, vol. 1, 3rd ed., Fundamental 
               Algorithms, p. 395, ex. 2.
%H A000081 N. J. A. Sloane, <a href="b000081.txt">Table of n, a(n) for n = 0..200</
               a>
%H A000081 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>
%H A000081 P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/
               Publications/books.html">Analytic Combinatorics</a>, 2009; see page 
               71
%H A000081 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 A000081 INRIA Algorithms Project, <a href="http://algo.inria.fr/bin/encyclopedia?Search=ECSnb&argsearch=57">
               Encyclopedia of Combinatorial Structures 57</a>
%H A000081 F. Ruskey, <a href="http://www.theory.cs.uvic.ca/~cos/inf/tree/RootedTree.html">
               Information on Rooted Trees</a>
%H A000081 N. J. A. Sloane, <a href="a81.html">Illustration of initial terms</a>
%H A000081 N. J. A. Sloane, <a href="a81b.txt">Bijection between rooted trees and 
               arrangements of circles</a>
%H A000081 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
               RootedTree.html">Link to a section of The World of Mathematics (1).</
               a>
%H A000081 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
               PlantedTree.html">Link to a section of The World of Mathematics (2).</
               a>
%H A000081 G. Xiao, <a href="http://wims.unice.fr/~wims/en_tool~number~contfrac.en.html">
               Contfrac</a>
%H A000081 <a href="Sindx_Cor.html#core">Index entries for "core" sequences</a>
%H A000081 <a href="Sindx_Ro.html#rooted">Index entries for sequences related to 
               rooted trees</a>
%H A000081 <a href="Sindx_Tra.html#trees">Index entries for sequences related to 
               trees</a>
%H A000081 <a href="Sindx_Par.html#parens">Index entries for sequences related to 
               parenthesizing</a>
%H A000081 <a href="Sindx_Con.html#confC">Index entries for continued fractions 
               for constants</a>
%F A000081 G.f. A(x) = x + x^2 + 2*x^3 + 4*x^4 + ... satisfies A(x) = x exp(A(x)+A(x^2)/
               2+A(x^3)/3+A(x^4)/4+...) [Polya]
%F A000081 Also A(x) = Sum_{n >= 1} a(n)*x^n = x / Product_{n >= 1} (1-x^n)^a(n).
%F A000081 Recurrence: a(n+1) = (1/n) * sum_{k=1..n} ( sum_{d|k} d*a(d) ) * a(n-k+1).
%e A000081 Asymptotically c * d^n * n^(-3/2), where c = 0.4399... and d = 2.9558... 
               [Polya; Knuth, section 7.2.1.6].
%p A000081 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 A000081 spec := [ T, {T=Prod(Z,Set(T))} ]; A000081 := n-> combstruct[count](spec,
               size=n); [seq(combstruct[count](spec,size=n), n=0..40)];
%p A000081 Comment from Joe Riel (joer(AT)san.rr.com), Jun 23 2008; (Start) Here 
               is a much more efficient method for computing the result with Maple. 
               It uses two procedures.
%p A000081 a := proc(n) local k; a(n) := add(k*a(k)*s(n-1,k), k=1..n-1)/(n-1) end 
               proc:
%p A000081 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)); (End)
%p A000081 Contribution from Alois P. Heinz (heinz(AT)hs-heilbronn.de), Sep 06 2008: 
               (Start)
%p A000081 # even more efficient, uses the Euler transform:
%p A000081 with (numtheory): a:= proc(n) option remember; local d,j; if n<=1 then 
               n else (add (d*a(d), d=divisors(n-1)) +add (add (d*a(d), d=divisors(j)) 
               *a(n-j), j=1..n-2))/ (n-1) fi end: seq (a(n), n=0..50); (End)
%t A000081 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} ] (from Robert A. Russell)
%t A000081 <<NumericalMath`Butcher`; ButcherTreeCount[30]
%o A000081 (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))
%o A000081 (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])
%Y A000081 Cf. A000041 (partitions), A000055 (unrooted trees), A000169, A005200, 
               A051491, A051492, A093637, A001858.
%Y A000081 A144963 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Sep 27 2008]
%Y A000081 Sequence in context: A145548 A145549 A145550 this_sequence A124497 A093637 
               A068051
%Y A000081 Adjacent sequences: A000078 A000079 A000080 this_sequence A000082 A000083 
               A000084
%K A000081 nonn,easy,core,nice,eigen
%O A000081 0,4
%A A000081 N. J. A. Sloane (njas(AT)research.att.com).
%E A000081 Corrected typo in arxiv number R. J. Mathar (mathar(AT)strw.leidenuniv.nl), 
               Mar 06 2009