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

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]

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.

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

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

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

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)

Contribution from Alois P. Heinz (heinz(AT)hs-heilbronn.de), Sep 06 2008: (Start)

# even more efficient, uses the Euler transform:

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)

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.

A144963 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Sep 27 2008]

Sequence in context: A145548 A145549 A145550 this_sequence A124497 A093637 A068051

Adjacent sequences: A000078 A000079 A000080 this_sequence A000082 A000083 A000084

nonn,easy,core,nice,eigen

N. J. A. Sloane (njas(AT)research.att.com).

Corrected typo in arxiv number R. J. Mathar (mathar(AT)strw.leidenuniv.nl), Mar 06 2009

1,3

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

Index entries for sequences related to parenthesizing

Cf. A002845, A003018, A003019, A145545, A145546, A145548, A145549, A145550, A000081.

Sequence in context: A034825 A145546 A034826 this_sequence A123467 A145548 A145549

Adjacent sequences: A145544 A145545 A145546 this_sequence A145548 A145549 A145550

more,nonn

Jon E. Schoenfield (jonscho(AT)hiwaay.net), Oct 13 2008

1,3

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

Index entries for sequences related to parenthesizing

Cf. A002845, A003018, A003019, A145545, A145546, A145547, A145549, A145550, A000081.

Sequence in context: A034826 A145547 A123467 this_sequence A145549 A145550 A000081

Adjacent sequences: A145545 A145546 A145547 this_sequence A145549 A145550 A145551

more,nonn

Jon E. Schoenfield (jonscho(AT)hiwaay.net), Oct 13 2008

1,3

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

Index entries for sequences related to parenthesizing

Cf. A002845, A003018, A003019, A145545, A145546, A145547, A145548, A145550, A000081.

Sequence in context: A145547 A123467 A145548 this_sequence A145550 A000081 A124497

Adjacent sequences: A145546 A145547 A145548 this_sequence A145550 A145551 A145552

more,nonn

Jon E. Schoenfield (jonscho(AT)hiwaay.net), Oct 13 2008

1,3

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

Index entries for sequences related to parenthesizing

Cf. A002845, A003018, A003019, A145545, A145546, A145547, A145548, A145549, A000081.

Sequence in context: A123467 A145548 A145549 this_sequence A000081 A124497 A093637

Adjacent sequences: A145547 A145548 A145549 this_sequence A145551 A145552 A145553

more,nonn

Jon E. Schoenfield (jonscho(AT)hiwaay.net), Oct 13 2008

0,4

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

N. J. A. Sloane, Transforms

Index entries for sequences related to rooted trees

Take Euler transform of A034825 and shift right. (Christian G. Bower (bowerc(AT)usa.net)).

For Maple program see link in A000235.

with (numtheory): etr:= proc(p) local b; b:=proc(n) option remember; local d, j; if n=0 then 1 else add (add (d*p(d), d=divisors(j)) *b(n-j), j=1..n)/n fi end end: shr:= proc(p) n->`if`(n=0, 1, p(n-1)) end: b[0]:= etr(n->1): for j from 1 to 7 do b[j]:= etr (shr(b[j-1])) od: a:= shr(b[7]): seq (a(n), n=0..31); [From Alois P. Heinz (heinz(AT)hs-heilbronn.de), Sep 08 2008]

See A001383 for details.

Sequence in context: A145545 A034825 A145546 this_sequence A145547 A123467 A145548

Adjacent sequences: A034823 A034824 A034825 this_sequence A034827 A034828 A034829

nonn

N. J. A. Sloane (njas(AT)research.att.com).

1,2

Is this the same as A000081 with a different offset?

S. Hougardy, Classes of perfect graphs, Discr. Math. 306 (2006), 2529-2571.

S. Hougardy, Home Page

Sequence in context: A145546 A034826 A145547 this_sequence A145548 A145549 A145550

Adjacent sequences: A123464 A123465 A123466 this_sequence A123468 A123469 A123470

nonn

N. J. A. Sloane (njas(AT)research.att.com), Oct 18 2006