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. (Of course the rules here are different from the usual counting parentheses problems - compare A000108, A001190, A001699.) See link below for proof.

Euler transform is sequence itself with offset -1.

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

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, Amer. J. Math., 4 (1881), 266-268.

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

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.

J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 526.

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

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, TAOCP, Vol. 4, Section 7.2.1.6.

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

N. Pippenger, Enumeration of equicolorable trees, SIAM J. Discrete Math., 14 (2001), 93-115.

G. Polya, Kombinatorische Anzahlbestimmungen fuer Gruppen, Graphen und chemische Verbindungen, Acta Math. 68 (1937), 145-254.

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.

R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Proposition 5.3.1, p. 23.

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

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

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

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

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 57

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, Link to a section of The World of Mathematics (1).

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics (2).

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

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

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)

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)

<<NumericalMath`Butcher`; ButcherTreeCount[30]

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

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

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

Sequence in context: A034825 A034826 A123467 this_sequence A124497 A093637 A068051

Adjacent sequences: A000078 A000079 A000080 this_sequence A000082 A000083 A000084

nonn,easy,core,nice,eigen

njas