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

 

Logo

Invitation: celebrating 50 years of OEIS, 250000 sequences, and Sloane's 75th, there will be a conference at DIMACS, Rutgers, Oct 9-10 2014.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000081 Number of rooted trees with n nodes (or connected functions with a fixed point).
(Formerly M1180 N0454)
237
0, 1, 1, 2, 4, 9, 20, 48, 115, 286, 719, 1842, 4766, 12486, 32973, 87811, 235381, 634847, 1721159, 4688676, 12826228, 35221832, 97055181, 268282855, 743724984, 2067174645, 5759636510, 16083734329, 45007066269, 126186554308, 354426847597 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,4

COMMENTS

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 link below for proof.

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

Also, number of connected multigraphs of order n without cycles except for one loop. See the Bomfim link for a picture showing the bijection between rooted trees and multigraphs of this kind. [Washington Bomfim, Sep 04 2010]

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

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. 42, 49.

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).

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

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

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

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

D. Matula, A natural rooted tree enumeration by prime factorization, SIAM Rev. 10 (1968).

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

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

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

N. J. A. Sloane, Table of n, a(n) for n = 0..200

A. Cayley, On the analytical forms called trees, Amer. J. Math., 4 (1881), 266-268.

P. Flajolet, S. Gerhold and B. Salvy, On the non-holonomic character of logarithms, powers and the n-th prime function

P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 71

F. Goebel, On a 1-1-correspondence between rooted trees and natural numbers, J. Combin. Theory, B 29 (1980), 141-143.

F. Goebel and R. P. Nederpelt, The number of numerical outcomes of iterated powers, Amer. Math. Monthly, 80 (1971), 1097-1103.

Ivan Gutman and Yeong-Nan Yeh, Deducing properties of trees from their Matula numbers

R. K. Guy and J. L. Selfridge, The nesting and roosting habits of the laddered parenthesis (annotated cached copy)

R. K. Guy and J. L. Selfridge, The nesting and roosting habits of the laddered parenthesis, Amer. Math. Monthly 80 (8) (1973), 868-876.

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 57

E. Kalinowski and W. Gluza, Evaluation of High Order Terms for the Hubbard Model in the Strong-Coupling Limit, arXiv:1106.4938, 2011 (Physical Review B 85, 045105, Jan 2012)

Math Overflow, Discussion

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.

G. Polya, Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen, Acta Mathematica, vol.68, no.1, pp.145-254, (1937).

F. Ruskey, Information on Rooted Trees

N. J. A. Sloane, Illustration of initial terms

N. J. A. Sloane, Bijection between rooted trees and arrangements of circles

Eric Weisstein's World of Mathematics, Rooted Tree

Eric Weisstein's World of Mathematics, Planted Tree

G. Xiao, Contfrac

Index entries for "core" sequences

Index entries for sequences related to rooted trees

Index entries for sequences related to trees

Index entries for sequences related to parenthesizing

Index entries for continued fractions for constants

FORMULA

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

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

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

Asymptotically c * d^n * n^(-3/2), where c = 0.4399... and d = 2.9558... [Polya; Knuth, section 7.2.1.6].

Euler transform is sequence itself with offset -1. - Michael Somos, Dec 16 2001

EXAMPLE

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

From Joerg Arndt, Jun 29 2014: (Start)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(End)

MAPLE

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

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

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.

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

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)

# even more efficient, uses the Euler transform:

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: seq (a(n), n=0..50); # Alois P. Heinz, Sep 06 2008

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

<<NumericalMath`Butcher`; ButcherTreeCount[30]

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

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

PROG

(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 */

(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 */

(PARI) N=66;  A=vector(N+1, j, 1);

for (n=1, N, A[n+1] = 1/n * sum(k=1, n, sumdiv(k, d, d*A[d]) * A[n-k+1] ) );

concat([0], A) \\ Joerg Arndt, Apr 17 2014

(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); [From Geoff Bailey (geoff(AT)maths.usyd.edu.au), Nov 30 2009]

(Maxima)

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

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

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

makelist(r(n), n, 1, 12); [Vladimir Kruchinin, Jun 15 2012]

(Haskell)

import Data.List (genericIndex)

a000081 = genericIndex a000081_list

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

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

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

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

-- Reinhard Zumkeller, Jun 17 2013

(Sage)

@CachedFunction

def a(n):

    if n < 2: return n

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

[a(n) for n in (0..30)] # Peter Luschny, Jul 18 2014 after Alois P. Heinz

CROSSREFS

Cf. A000041 (partitions), A000055 (unrooted trees), A000169, A005200, A051491, A187770, A051492, A093637, A001858.

Row sums of A144963 [From Gary W. Adamson, Sep 27 2008]

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

Cf. A000106 (self-convolution).

Cf. A027750.

Sequence in context: A145548 A145549 A145550 * A124497 A093637 A068051

Adjacent sequences:  A000078 A000079 A000080 * A000082 A000083 A000084

KEYWORD

nonn,easy,core,nice,eigen,changed

AUTHOR

N. J. A. Sloane.

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified July 28 14:32 EDT 2014. Contains 245000 sequences.