|
%I M1180 N0454 #352 Oct 27 2023 18:20:42
%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,997171512998
%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_, 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, pp. 42, 49.
%D Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, pages 305, 998.
%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 Robert G. Wilson v, <a href="/A000081/b000081.txt">Table of n, a(n) for n = 0..1000</a> (first 201 terms from N. J. A. Sloane)
%H M. J. H. Al-Kaabi, D. Manchon and 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 Lluís Alemany-Puig and Ramon Ferrer-i-Cancho, <a href="https://arxiv.org/abs/2107.03277">Linear-time calculation of the expected sum of edge lengths in random projective linearizations of trees</a>, arXiv:2107.03277 [cs.CL], 2021.
%H Winfried Auzinger, H Hofstaetter and 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 Bartomeu Fiol, Jairo Martínez-Montoya and Alan Rios Fukelman, <a href="https://arxiv.org/abs/2003.02879">The planar limit of N=2 superconformal field theories</a>, arXiv:2003.02879 [hep-th], 2020.
%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 Loïc Foissy, <a href="https://arxiv.org/abs/1811.07572">Algebraic structures on typed decorated rooted trees</a>, arXiv:1811.07572 [math.RA], 2018.
%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 Ira M. Gessel, <a href="https://arxiv.org/abs/2305.03157">Good Will Hunting's Problem: Counting Homeomorphically Irreducible Trees</a>, arXiv:2305.03157 [math.CO], 2023.
%H Bernhard Gittenberger, Emma Yu Jin and 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 Mika Göös and Jukka Suomela, <a href="https://doi.org/10.4086/toc.2016.v012a019">Locally checkable proofs in distributed computing</a> Theory Comput. 12, Paper No. 19, 33 p. (2016).
%H Vsevolod Gubarev, <a href="https://arxiv.org/abs/1811.08219">Rota-Baxter operators on a sum of fields</a>, arXiv:1811.08219 [math.RA], 2018.
%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 and 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 and 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 and 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 Dominique Manchon, <a href="https://www.puremath.no/wp-content/uploads/2019/09/Manchon-BFS2019-final.pdf">On the mathematics of rooted trees</a>, Université Clermont-Auvergne (France, 2019).
%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 and 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 N. J. A. Sloane, <a href="https://arxiv.org/abs/2301.03149">"A Handbook of Integer Sequences" Fifty Years Later</a>, arXiv:2301.03149 [math.NT], 2023, p. 1.
%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 range(31)] # _Peter Luschny_, Jul 18 2014 after _Alois P. Heinz_
%o (Sage) [0]+[RootedTrees(n).cardinality() for n in range(1,31)] # _Freddy Barrera_, Apr 07 2019
%o (Python)
%o from functools import lru_cache
%o from sympy import divisors
%o @lru_cache(maxsize=None)
%o def divisor_tuple(n): # cached unordered tuple of divisors
%o return tuple(divisors(n,generator=True))
%o @lru_cache(maxsize=None)
%o def A000081(n): return n if n <= 1 else sum(sum(d*A000081(d) for d in divisor_tuple(k))*A000081(n-k) for k in range(1,n))//(n-1) # _Chai Wah Wu_, Jan 14 2022
%Y Cf. A000041 (partitions), A000055 (unrooted trees), A000169, A001858, A005200, A027750, A051491, A051492, A093637, A187770, A199812, A255170, A087803 (partial sums).
%Y Row sums of A144963. - _Gary W. Adamson_, Sep 27 2008
%Y Cf. A209397 (log(A(x)/x)).
%Y Cf. A000106 (self-convolution).
%Y Column k=1 of A033185 and A034799; column k=0 of A008295.
%K nonn,easy,core,nice,eigen
%O 0,4
%A _N. J. A. Sloane_
| 