0,4

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. - Washington Bomfim, Sep 04 2010

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

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.

Alexander S. Karpenko, Lukasiewicz Logics and Prime Numbers, Luniver Press, Beckington, 2006, p. 82.

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.

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

N. J. A. Sloane and Robert G. Wilson v, Table of n, a(n) for n = 0..1000 the first 201 terms from N. J. A. Sloane.

Roland Bacher, Counting invertible Schrodinger Operators over Finite Fields for Trees Cycles and Complete Graphs, preprint, 2015.

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, Letter to N. J. A. Sloane, 1988-04-12 (annotated scanned copy)

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

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

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

R. W. Robinson, Letter to N. J. A. Sloane, Jul 29 1980

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

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

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)

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)];

# 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)); # Joe Riel (joer(AT)san.rr.com), Jun 23 2008

# 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

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

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

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

ButcherTreeCount[30] (* v8 onward Robert G. Wilson v, Sep 16 2014 *)

(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); // 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

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

Row sums of A144963. - 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

nonn,easy,core,nice,eigen,changed

N. J. A. Sloane

approved