|
| |
|
|
A000081
|
|
Number of rooted trees with n nodes (or connected functions with a fixed point).
(Formerly M1180 N0454)
|
|
211
|
|
|
|
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. (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
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, Sep 27 2008]
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. [From 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, 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.
E. Kalinowski and W. Gluza, Evaluation of high-order terms for the Hubbard model in the strong-coupling limit, Phys. Rev. B 85 (4), 045105 (2012), 8 pages.
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).
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 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).
|
|
|
LINKS
|
N. J. A. Sloane, Table of n, a(n) for n = 0..200
W. Bomfim, Bijection between rooted forests and multigraphs without cycles except one loop in each connected component. [From Washington Bomfim, Sep 04 2010]
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
R. K. Guy and J. L. Selfridge, The nesting and roosting habits of the laddered parenthesis (annotated cached copy)
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 57
Math Overflow, Discussion
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) = x + x^2 + 2*x^3 + 4*x^4 + 9*x^5 + 20*x^6 + 48*x^7 + 115*x^8 + ... 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).
Euler transform is sequence itself with offset -1. - Michael Somos, Dec 16 2001
|
|
|
EXAMPLE
|
Asymptotically c * d^n * n^(-3/2), where c = 0.4399... and d = 2.9558... [Polya; Knuth, section 7.2.1.6].
|
|
|
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} ] (from Robert A. Russell)
<<NumericalMath`Butcher`; ButcherTreeCount[30]
max = 30; f[x_] := Sum[a[k]*x^k, {k, 0, max}]; a[0] = 0; a[1] = a[2] = 1; sol = SolveAlways[ 0 == Series[ f[x] - x/Product[(1 - x^n)^a[n], {n, 1, max}], {x, 0, max}] // Normal, x]; Table[a[k], {k, 0, max}] /. sol // First (* Jean-François Alcover, Jul 17 2012, from g.f. *)
|
|
|
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 */
(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]
|
|
|
CROSSREFS
|
Cf. A000041 (partitions), A000055 (unrooted trees), A000169, A005200, A051491, A187770, A051492, A093637, A001858.
Cf. A144963 [From Gary W. Adamson, Sep 27 2008]
Cf. A209397 (log(A(x)/x)).
Sequence in context: A145548 A145549 A145550 * A124497 A093637 A068051
Adjacent sequences: A000078 A000079 A000080 * A000082 A000083 A000084
|
|
|
KEYWORD
|
nonn,easy,core,nice,eigen
|
|
|
AUTHOR
|
N. J. A. Sloane.
|
|
|
STATUS
|
approved
|
| |
|
|
