A051491 -id:A051491 - cp's OEIS frontend

A000081 Number of unlabeled rooted trees with n nodes (or connected functions with a fixed point).

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, 997171512998

Offset: 0

N. J. A. Sloane

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 Sloane's link for a proof and Vogeler's link for illustration of a(7) as arrangement of 6 circles.
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, 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.
Also called "Polya trees" by Genitrini (2016). - N. J. A. Sloane, Mar 24 2017

			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)

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, pp. 42, 49.
Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, pages 305, 998.
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, Łukasiewicz 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).

Robert G. Wilson v, Table of n, a(n) for n = 0..1000 (first 201 terms from N. J. A. Sloane)
M. J. H. Al-Kaabi, D. Manchon and F. Patras, Monomial bases and pre-Lie structure for free Lie algebras, arXiv:1708.08312 [math.RA], 2017, See p. 5.
Lluís Alemany-Puig and Ramon Ferrer-i-Cancho, Linear-time calculation of the expected sum of edge lengths in random projective linearizations of trees, arXiv:2107.03277 [cs.CL], 2021.
Winfried Auzinger, H. Hofstaetter and O. Koch, Symbolic Manipulation of Flows of Nonlinear Evolution Equations, with Application in the Analysis of Split-Step Time Integrators, arXiv preprint arXiv:1605.00453 [math.NA], 2016.
Roland Bacher, Counting invertible Schrodinger Operators over Finite Fields for Trees Cycles and Complete Graphs, preprint, 2015.
David Broadhurst, Resurgent Integer Sequences, Rutgers Experimental Math Seminar, Feb 06 2025; Slides.
A. Cayley, On the analytical forms called trees, Amer. J. Math., 4 (1881), 266-268.
Bartomeu Fiol, Jairo Martínez-Montoya and Alan Rios Fukelman, The planar limit of N=2 superconformal field theories, arXiv:2003.02879 [hep-th], 2020.
P. Flajolet, S. Gerhold and B. Salvy, On the non-holonomic character of logarithms, powers and the n-th prime function, arXiv:math/0501379 [math.CO], 2005.
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 71.
Loïc Foissy, Algebraic structures on typed decorated rooted trees, arXiv:1811.07572 [math.RA], 2018.
A. Genitrini, Full asymptotic expansion for Polya structures, arXiv:1605.00837 [math.CO], May 03 2016, p. 6.
Ira M. Gessel, Good Will Hunting's Problem: Counting Homeomorphically Irreducible Trees, arXiv:2305.03157 [math.CO], 2023.
Bernhard Gittenberger, Emma Yu Jin and Michael Wallner, On the shape of random Pólya structures, arXiv|1707.02144 [math.CO], 2017-2018; Discrete Math., 341 (2018), 896-911.
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.
Mika Göös and Jukka Suomela, Locally checkable proofs in distributed computing Theory Comput. 12, Paper No. 19, 33 p. (2016).
Vsevolod Gubarev, Rota-Baxter operators on a sum of fields, arXiv:1811.08219 [math.RA], 2018.
Ivan Gutman and Yeong-Nan Yeh, Deducing properties of trees from their Matula numbers, Publications de l'Institut Mathématique (Beograd) (N.S.), Vol. 53(67), pp. 17--22 (1993).
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.
F. Harary and G. Prins, The number of homeomorphically irreducible trees, and other species, Acta Math. 101 (1-2) (1959) 141-161, see page 146.
F. Harary and R. W. Robinson, The number of achiral trees, Jnl. Reine Angewandte Mathematik 278 (1975), 322-335. (Annotated scanned copy)
R. Harary and R. W. Robinson, Isomorphic factorizations VIII: bisectable trees, Combinatorica 4 (2) (1984) 169-179, eq. (4.3)
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 [cond-mat.str-el], 2011 (Physical Review B 85, 045105, Jan 2012).
P. Leroux and B. Miloudi, Généralisations de la formule d'Otter, Ann. Sci. Math. Québec, Vol. 16, No. 1, pp. 53-80, 1992. (Annotated scanned copy)
Dominique Manchon, On the mathematics of rooted trees, Université Clermont-Auvergne (France, 2019).
Math Overflow, Discussion
R. J. Mathar, Topologically Distinct Sets of Non-intersecting Circles in the Plane, arXiv:1603.00077 [math.CO], 2016.
D. Matula, A natural rooted tree enumeration by prime factorization, SIAM Rev. 10 (1968) 273.
R. I. McLachlan, K. Modin, H. Munthe-Kaas and O. Verdier, What are Butcher series, really? The story of rooted trees and numerical methods for evolution equations, arXiv preprint arXiv:1512.00906 [math.NA], 2015.
Igor Pak, Complexity problems in enumerative combinatorics, arXiv:1803.06636 [math.CO], 2018.
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
Frank Ruskey, Information on Rooted Trees
A. J. Schwenk, Letter to N. J. A. Sloane, Aug 1972
N. J. A. Sloane, Illustration of initial terms
N. J. A. Sloane, Bijection between rooted trees and arrangements of circles
N. J. A. Sloane, "A Handbook of Integer Sequences" Fifty Years Later, arXiv:2301.03149 [math.NT], 2023, p. 1.
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 17 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
Peter Steinbach, Field Guide to Simple Graphs, Volume 3, Part 10 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
Peter Steinbach, Field Guide to Simple Graphs, Volume 3, Part 12 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
Roger Vogeler, Six Circles, 2015 (illustration for a(7) as the number of arrangements of six 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

Cf. A000041 (partitions), A000055 (unrooted trees), A000169, A001858, A005200, A027750, A051491, A051492, A093637, A187770, A199812, A255170, A087803 (partial sums).
Row sums of A144963. - Gary W. Adamson, Sep 27 2008
Cf. A209397 (log(A(x)/x)).
Cf. A000106 (self-convolution), A002861 (rings of these).
Column k=1 of A033185 and A034799; column k=0 of A008295.

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

N := 30; P := 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

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 *)
a[n:0|1] := n; a[n_] := a[n] = Sum[m a[m] a[n-k*m], {m, n-1}, {k, (n-1)/m}]/(n-1); Table[a[n], {n, 0, 30}] (* Vladimir Reshetnikov, Nov 06 2015 *)
terms = 31; A[] = 0; Do[A[x] = x*Exp[Sum[A[x^k]/k, {k, 1, j}]] + O[x]^j // Normal, {j, 1, terms}]; CoefficientList[A[x], x] (* Jean-François Alcover, Jan 11 2018 *)

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

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

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

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

from functools import lru_cache
from sympy import divisors
@lru_cache(maxsize=None)
def divisor_tuple(n): # cached unordered tuple of divisors
    return tuple(divisors(n,generator=True))
@lru_cache(maxsize=None)
def A000081(n): return n if n <= 1 else sum(sum(d*A000081(d) for d in divisor_tuple(k))*A000081(n-k) for k in range(1,n))//(n-1) # Chai Wah Wu, Jan 14 2022

@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 range(31)] # Peter Luschny, Jul 18 2014 after Alois P. Heinz

[0]+[RootedTrees(n).cardinality() for n in range(1,31)] # Freddy Barrera, Apr 07 2019

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 = A187770 = 0.439924... and d = A051491 = 2.955765... [Polya; Knuth, section 7.2.1.6].
Euler transform is sequence itself with offset -1. - Michael Somos, Dec 16 2001
For n > 1, a(n) = A087803(n) - A087803(n-1). - Vladimir Reshetnikov, Nov 06 2015
For n > 1, a(n) = A123467(n-1). - Falk Hüffner, Nov 26 2015

A000055 Number of trees with n unlabeled nodes.

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551, 1301, 3159, 7741, 19320, 48629, 123867, 317955, 823065, 2144505, 5623756, 14828074, 39299897, 104636890, 279793450, 751065460, 2023443032, 5469566585, 14830871802, 40330829030, 109972410221, 300628862480, 823779631721, 2262366343746, 6226306037178

Offset: 0

N. J. A. Sloane

Also, number of unlabeled 2-gonal 2-trees with n-1 2-gons, for n>0. [Corrected by Andrei Zabolotskii, Jul 29 2025]
Main diagonal of A054924.
Left border of A157905. - Gary W. Adamson, Mar 08 2009
From Robert Munafo, Jan 24 2010: (Start)
Also counts classifications of n items that require exactly n-1 binary partitions; see Munafo link at A005646, also A171871 and A171872.
The 11 trees for n = 7 are illustrated at the Munafo web link.
Link to A171871/A171872 conjectured by Robert Munafo, then proved by Andrew Weimholt and Franklin T. Adams-Watters on Dec 29 2009. (End)
This is also "Number of tree perfect graphs on n nodes" [see Hougardy]. - N. J. A. Sloane, Dec 04 2015
For n > 0, a(n) is the number of ways to arrange n-1 unlabeled non-intersecting circles on a sphere. - Vladimir Reshetnikov, Aug 25 2016
All trees for n=1 through n=12 are depicted in Chapter 1 of the Steinbach reference. On p. 6 appear encircled two trees (with n=10) which seem inequivalent only when considered as ordered (planar) trees. Earlier instances of such possibly (in)equivalent trees could appear from n=6 on (and from n=9 on without equivalence modulo plane symmetry) but are not drawn separately there. - M. F. Hasler, Aug 29 2017

			a(1) = 1 [o]; a(2) = 1 [o-o]; a(3) = 1 [o-o-o];
a(4) = 2 [o-o-o and o-o-o-o]
            |
            o
G.f. = 1 + x + x^2 + x^3 + 2*x^4 + 3*x^5 + 6*x^6 + 11*x^7 + 23*x^8 + ...

F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Camb. 1998, p. 279.
Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 55.
N. L. Biggs et al., Graph Theory 1736-1936, Oxford, 1976, p. 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. 459).
S. R. Finch, Mathematical Constants, Cambridge, 2003, pp. 295-316.
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, p. 58 and 244.
D. E. Knuth, Fundamental Algorithms, 3d Ed. 1997, pp. 386-88.
R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.
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. J. Mathar and Robert G. Wilson v, Table of n, a(n) for n = 0..1000
Jeremy C. Adcock, Sam Morley-Short, Joshua W. Silverstone, and Mark G. Thompson, Hard limits on the postselectability of optical graph states, arXiv:1806.03263 [quant-ph], 2018.
H. R. Afshar, E. A. Bergshoeff, and W. Merbis, Interacting spin-2 fields in three dimensions, arXiv preprint arXiv:1410.6164 [hep-th], 2014-2015.
Ruggero Bandiera and Florian Schaetz, Eulerian idempotent, pre-Lie logarithm and combinatorics of trees, arXiv:1702.08907 [math.CO], 2017. Mentions this sequence.
Madeleine Burkhart and Joel Foisy, Enumerating spherical n-links, Involve, Vol. 11 (2018), No. 2, 195-206.
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
A. Cayley, On the analytical forms called trees, Amer. J. Math., 4 (1881), 266-268.
CombOS - Combinatorial Object Server, Generate graphs
Benjamin Côté, Hélène Cossette, and Etienne Marceau, Centrality and topology properties in a tree-structured Markov random field, arXiv:2410.20240 [math.ST], 2024. See p. 18.
Antoine Dailly and Tuomo Lehtilä, Reconstructing graphs with subgraph compositions, arXiv:2504.00169 [math.CO], 2025. See p. 28.
R. Ferrer-i-Cancho, Non-crossing dependencies: least effort, not grammar, arXiv preprint arXiv:1411.2645 [cs.CL], 2014.
S. R. Finch, Otter's Tree Enumeration Constants
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 481.
Andrew Gainer-Dewar, Gamma-Species and the Enumeration of k-Trees, Electronic Journal of Combinatorics, Volume 19 (2012), #P45 and arXiv:1208.5993 [math.CO], 2012.
Xiangrui Gao, Song He, and Yong Zhang, Labelled tree graphs, Feynman diagrams and disk integrals arxiv:1708.08701 [hep-th], 2017, see p. 4.
Ira M. Gessel, Good Will Hunting's Problem: Counting Homeomorphically Irreducible Trees, arXiv:2305.03157 [math.CO], 2023.
D. D. Grant, The stability index of graphs, pp. 29-52 of Combinatorial Mathematics (Proceedings 2nd Australian Conf.), Lect. Notes Math. 403, 1974. Gives first 45 terms.
Paul E. Gunnells, Generalized Catalan numbers from hypergraphs, arXiv:2102.05121 [math.CO], 2021. Mentions this sequence p. 3.
T. Hoppe and A. Petrone, Integer sequence discovery from small graphs, arXiv preprint arXiv:1408.3644 [math.CO], 2014.
S. Hougardy, Classes of perfect graphs, Discr. Math. 306 (2006), 2529-2571.
House of Graphs, Trees
Andrew Jobbings, Enumerating nets, Preprint 2015.
Mithra Karamchedu and Lucas Bang, Generating the Spanning Trees of Series-Parallel Graphs up to Graph Automorphism, arXiv:2508.13480 [cs.DS], 2025. See p. 4.
Elena V. Konstantinova and Maxim V. Vidyuk, Discriminating tests of information and topological indices. Animals and trees, J. Chem. Inf. Comput. Sci. 43 (2003), 1860-1871. See Table 15, column 1 on page 1868.
G. Labelle, C. Lamathe and P. Leroux, Labeled and unlabeled enumeration of k-gonal 2-trees, arXiv:math/0312424 [math.CO], 2003.
Steve Lawford and Yll Mehmeti, Cliques and a new measure of clustering: with application to U.S. domestic airlines, arXiv:1806.05866 [cs.SI], 2018.
P. Leroux and B. Miloudi, Généralisations de la formule d'Otter, Ann. Sci. Math. Québec, Vol. 16, No. 1, pp. 53-80, 1992. (Annotated scanned copy)
Gang Li, Generation of Rooted Trees and Free Trees, Comp. Sci. MSc thesis paper, 1996.
R. J. Mathar, Topologically Distinct Sets of Non-intersecting Circles in the Plane, arXiv:1603.00077 [math.CO], 2016.
Richard J. Mathar, Counting Connected Graphs without Overlapping Cycles, arXiv:1808.06264 [math.CO], 2018.
Robert Munafo, Relation to Tree Graphs
R. Otter, The number of trees, Ann. of Math. (2) 49 (1948), 583-599.
Igor Pak, Complexity problems in enumerative combinatorics, arXiv:1803.06636 [math.CO], 2018.
E. M. Palmer and A. J. Schwenk, On the number of trees in a random forest, J. Combin. Theory, B 27 (1979), 109-121.
Sebastian Piec, Krzysztof Malarz and Krzysztof Kulakowski. How to count trees?, arXiv:cond-mat/0501594 [cond-mat.stat-mech], 2005; Int. J. Modern Phys., C16 (2005) 1527-1534.
N. Pippenger, Enumeration of equicolorable trees, SIAM J. Discrete Math., 14 (2001), 93-115.
J. M. Plotkin and J. W. Rosenthal, How to obtain an asymptotic expansion of a sequence from an analytic identity satisfied by its generating function, J. Austral. Math. Soc. (Series A), Vol. 56 (1994), 131-143.
E. M. Rains and N. J. A. Sloane, On Cayley's Enumeration of Alkanes (or 4-Valent Trees), J. Integer Sequences, Vol. 2 (1999), Article 99.1.1.
R. W. Robinson, Letter to N. J. A. Sloane, Jul 29 1980
Yaniv Sadeh, Haim Kaplan, and Uri Zwick, Search Trees on Trees via LP, arXiv:2501.17563 [cs.DS], 2025. See p. 12.
Sage, Common Graphs
A. J. Schwenk, Letter to N. J. A. Sloane, Aug 1972
N. J. A. Sloane, Illustration of initial terms
Peter Steinbach, Field Guide to Simple Graphs, Volume 3, Overview of the following parts: Cover, Front matter, Chapter 1: Trees, Trees (cont'd: pt.2), Trees (cont'd: pt.3), Chapter 2: Centers and Centroids, Chap.2 (cont'd), Chapter 3: Random Trees, Chapter 4: Rooted Trees, Chapter 5: Homeomorphically Irreducible Trees, Chapter 6: Tables (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
Ivan Stošić and Ivan Damnjanović, An efficient algorithm for generating transmission irregular trees, arXiv:2502.15453 [cs.DM], 2025. See p. 11.
Tanay Wakhare, Eric Wityk, and Charles R. Johnson. The proportion of trees that are linear, Discrete Mathematics 343.10 (2020): 112008. Also arXiv:1901.08502 [math.CO], 2019-2020. See Tables 1 and 2 (but beware errors).
Eric Weisstein's World of Mathematics, Tree
Pascal Welke, Tamás Horváth, and Stefan Wrobel, Probabilistic and exact frequent subtree mining in graphs beyond forests, Machine Learning (2019), 1-28.
Robert Alan Wright, Bruce Richmond, Andrew Odlyzko, and Brendan D. McKay, Constant Time Generation of Free Trees, SIAM Journal of Computing, vol. 15, no. 2, pp. 540-548, (1986) [preprint].
Index entries for sequences related to trees
Index entries for "core" sequences

Cf. A000676 (centered trees), A000677 (bicentered trees), A027416 (trees with a centroid), A102011 (trees with a bicentroid), A034853 (refined by diameter), A238414 (refined by maximum vertex degree).
Cf. A000081 (rooted trees), A000272 (labeled trees), A000169 (labeled rooted trees), A212809 (radius of convergence).
Cf. A036361 (labeled 2-trees), A036362 (labeled 3-trees), A036506 (labeled 4-trees), A054581 (unlabeled 2-trees).
Cf. A157904, A157905, A005195 (Euler transform = forests), A095133 (multisets).
Column 0 of A335362 and A034799.
Related to A005646; see A171871 and A171872.
Cf. also A000088, A008406, A051491, A086308.

import Data.List (generic_index)
import Math.OEIS (getSequenceByID)
triangle x = (x * x + x) `div` 2
a000055 n = let {r = genericIndex (fromJust (getSequenceByID "A000081")); (m, nEO) = divMod n 2}
            in  r n - sum (zipWith (*) (map r [0..m]) (map r [n, n-1..]))
                + (1-nEO) * (triangle (r m + 1))
-- Walt Rorie-Baety, Jun 12 2021

N := 30; P := 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; G000055 := 1 + G - G^2/2 + Evaluate(G,x^2)/2; A000055 := Eltseq(G000055); // Geoff Baileu (geoff(AT)maths.usyd.edu.au), Nov 30 2009

G000055 := series(1+G000081-G000081^2/2+subs(x=x^2,G000081)/2,x,31); A000055 := n->coeff(G000055,x,n); # where G000081 is g.f. for A000081 starting with n=1 term
with(numtheory): b:= proc(n) option remember; `if`(n<=1, n, (add(add(d*b(d), d=divisors(j)) *b(n-j), j=1..n-1))/ (n-1)) end: a:= n-> `if`(n=0, 1, b(n) -(add(b(k) *b(n-k), k=0..n) -`if`(irem(n, 2)=0, b(n/2), 0))/2):
seq(a(n), n=0..50);
# Alois P. Heinz, Aug 21 2008
# Program to create b-file b000055.txt:
A000081 := proc(n) option remember; local d, j;
if n <= 1 then n else
    add(add(d*procname(d),d=numtheory[divisors](j))*procname(n-j),j=1..n-1)/(n-1);
fi end:
A000055 := proc(nmax) local a81, n, t, a, j, i ;
a81 := [seq(A000081(i), i=0..nmax)] ; a := [] ;
for n from 0 to nmax do
    if n = 0 then
        t := 1+op(n+1, a81) ;
    else
        t := op(n+1, a81) ;
    fi;
    if type(n, even) then
        t := t-op(1+n/2, a81)^2/2 ;
        t := t+op(1+n/2, a81)/2 ;
    fi;
    for j from 0 to (n-1)/2 do
        t := t-op(j+1, a81)*op(n-j+1, a81) ;
    od:
    a := [op(a), t] ;
od:
a end:
L := A000055(1000) ;
#  R. J. Mathar, Mar 06 2009

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] - Sum[a[j] a[i-j], {j, 1, i/2}] + If[OddQ[i], 0, a[i/2] (a[i/2] + 1)/2], {i, 1, 50}] (* Robert A. Russell *)
b[0] = 0; b[1] = 1; b[n_] := b[n] = Sum[d*b[d]*b[n-j], {j, 1, n-1}, {d, Divisors[j]}]/(n-1); a[0] = 1; a[n_] := b[n] - (Sum[b[k]*b[n-k], {k, 0, n}] - If[Mod[n, 2] == 0, b[n/2], 0])/2; Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Apr 09 2014, after Alois P. Heinz *)

{a(n) = local(A, A1, an, i, t); if( n<2, n>=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]) + (t = polcoeff( if( m%2, A *= (A1 - 'x^i)^-an[i], A), m-1))); t + if( n%2==0, binomial( -polcoeff(A, i-1), 2)))}; /* Michael Somos */

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] ) );
A000081=concat([0], A);
H(t)=subst(Ser(A000081, 't), 't, t);
x='x+O('x^N);
Vec( 1 + H(x) - 1/2*( H(x)^2 - H(x^2) ) )
\\ Joerg Arndt, Jul 10 2014

# uses function from A000081
def A000055(n): return 1 if n == 0 else A000081(n)-sum(A000081(i)*A000081(n-i) for i in range(1,n//2+1)) + (0 if n % 2 else (A000081(n//2)+1)*A000081(n//2)//2) # Chai Wah Wu, Feb 03 2022

[len(list(graphs.trees(n))) for n in range(16)] # Peter Luschny, Mar 01 2020

G.f.: A(x) = 1 + T(x) - T^2(x)/2 + T(x^2)/2, where T(x) = x + x^2 + 2*x^3 + ... is the g.f. for A000081.
a(n) ~ A086308 * A051491^n * n^(-5/2). - Vaclav Kotesovec, Jan 04 2013
a(n) = A000081(n) - A217420(n+1), n > 0. - R. J. Mathar, Sep 19 2016
a(n) = A000676(n) + A000677(n). - R. J. Mathar, Aug 13 2018
a(n) = A000081(n) - (Sum_{1<=i<=j, i+j=n} A000081(i)*A000081(j)) + (1-(-1)^(n-1)) * binomial(A000081(n/2)+1,2) / 2 [Li, equation 4.2]. - Walt Rorie-Baety, Jul 05 2021

A005195 Number of forests with n unlabeled nodes.

Original entry on oeis.org

1, 1, 2, 3, 6, 10, 20, 37, 76, 153, 329, 710, 1601, 3658, 8599, 20514, 49905, 122963, 307199, 775529, 1977878, 5086638, 13184156, 34402932, 90328674, 238474986, 632775648, 1686705630, 4514955632, 12132227370, 32717113805, 88519867048, 240235675303

Offset: 0

N. J. A. Sloane

Same as "Number of forests with n nodes that are perfect graphs" [see Hougardy]. - N. J. A. Sloane, Dec 04 2015

Number of unlabeled acyclic graphs on n vertices. The labeled version is A001858. The covering case is A144958, connected A000055. - Gus Wiseman, Apr 29 2024

			From _Gus Wiseman_, Apr 29 2024: (Start)
Edge-sets of non-isomorphic representatives of the a(0) = 1 through a(5) = 10 forests:
  {}  {}  {}    {}       {}          {}
          {12}  {12}     {12}        {12}
                {13,23}  {12,34}     {12,34}
                         {13,23}     {13,23}
                         {13,24,34}  {12,35,45}
                         {14,24,34}  {13,24,34}
                                     {14,24,34}
                                     {13,24,35,45}
                                     {14,25,35,45}
                                     {15,25,35,45}
(End)

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, pp. 58-59.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 0..1000 (first 201 terms from T. D. Noe)
S. Hougardy, Classes of perfect graphs, Discr. Math. 306 (2006), 2529-2571.
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. J. A. Sloane, Transforms
Peter Steinbach, Field Guide to Simple Graphs, Volume 3, Part 12 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
Peter Steinbach, Field Guide to Simple Graphs, Volume 4, Part 5 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
Eric Weisstein's World of Mathematics, Forest.
Index entries for sequences related to forests

Cf. A095133 (by number of trees), A136605 (by number of edges).
A diagonal of A144215.
The connected case is A000055.
The labeled version is A001858.
The covering case is A144958, labeled A105784.
For triangles instead of cycles we have A006785, covering A372169.
Unique cycle: A236570 (labeled A372193), covering A372191 (labeled A372195).
A006125 counts simple graphs, unlabeled A000088.
A006129 counts covering graphs, unlabeled A002494.
Cf. A000272, A002807, A054548, A137917, A367863, A372176.

EulerTransform[ seq_List ] := With[{m = Length[seq]}, CoefficientList[ Series[ Times @@ (1/(1 - x^Range[m])^seq), {x, 0, m}], x]];
b[n_] := b[n] = If[n <= 1, n, Sum[ Sum[ d*b[d], {d, Divisors[j]}]*b[n - j], {j, 1, n - 1}]/(n - 1)];
a55[n_] := a55[n] = If[n == 0, 1, b[n] - (Sum[ b[k]*b[n - k], {k, 0, n}] - If[Mod[n, 2] == 0, b[n/2], 0])/2]; A000055 = Table[ a55[n], {n, 1, 31}]; EulerTransform[ A000055 ] (* Jean-François Alcover, Mar 15 2012 *)

Euler transform of A000055: Product_{n>0} (1-x^n)^(-A000055(n)). a(n) = 1/n*Sum_{k=1..n} b(k)*a(n-k), where b(k) = Sum_{d divides k} d*A000055(d). - Vladeta Jovovic, Sep 05 2002
G.f.: exp(sum_{k>0} B(x^k)/k ), where B(x) = x + x^2 + x^3 + 2*x^4 + 3*x^5 + 6*x^6 + 11*x^7 + ... = C(x)-1 and C is the g.f. for A000055.
a(n) ~ c * d^n / n^(5/2), where d = A051491 = 2.9557652856519949747148..., c = 1.023158422... . - Vaclav Kotesovec, Nov 16 2014
First differences are A144958. - Gus Wiseman, Apr 29 2024

More terms from Vladeta Jovovic, Sep 05 2002

A001372 Number of unlabeled mappings (or mapping patterns) from n points to themselves; number of unlabeled endofunctions.

Original entry on oeis.org

1, 1, 3, 7, 19, 47, 130, 343, 951, 2615, 7318, 20491, 57903, 163898, 466199, 1328993, 3799624, 10884049, 31241170, 89814958, 258604642, 745568756, 2152118306, 6218869389, 17988233052, 52078309200, 150899223268, 437571896993, 1269755237948, 3687025544605, 10712682919341, 31143566495273, 90587953109272, 263627037547365

Offset: 0

N. J. A. Sloane

			The a(3) = 7 mappings are:
1->1, 2->2, 3->3
1->1, 2->2, 3->1 (equiv. to 1->1, 2->2, 3->2, or 1->1, 2->1, 3->3, etc.)
1->1, 2->3, 3->2
1->1, 2->1, 3->2
1->1, 2->1, 3->1
1->2, 2->3, 3->1
1->2, 2->1, 3->1

F. Bergeron, G. Labelle, and P. Leroux, Combinatorial Species and Tree-Like Structures, Cambridge, 1998, pp. 41, 209.
S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 5.6.6.
R. A. Fisher, Contributions to Mathematical Statistics, Wiley, 1950, 41.401.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 70, Table 3.4.1.
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).

Alois P. Heinz, Table of n, a(n) for n = 0..1000 (first 501 terms from Christian G. Bower)
A. L. Agore, A. Chirvasitu, and G. Militaru, The set-theoretic Yang-Baxter equation, Kimura semigroups and functional graphs, arXiv:2303.06700 [math.QA], 2023.
N. G. de Bruijn, Enumeration of mapping patterns, J. Combin. Theory, 12 (1972), 14-20.
N. G. de Bruijn and D. A. Klarner, Multisets of aperiodic cycles, SIAM J. Algebraic Discrete Methods 3 (1982), no. 3, 359--368. MR0666861(84i:05008).
Robert L. Davis, The number of structures of finite relations, Proc. Amer. Math. Soc. 4 (1953), 486-495.
Oscar Defrain, Antonio E. Porreca and Ekaterina Timofeeva, Polynomial-delay generation of functional digraphs up to isomorphism, arXiv:2302.13832 [cs.DS], 2023-2024.
Oscar Defrain, Antonio E. Porreca and Ekaterina Timofeeva, Polynomial-delay generation of functional digraphs up to isomorphism, Disc. Appl. Math., vol 357 (2024), pp. 24-33.
Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, 2009; see page 480
Alexander Heaton, Songpon Sriwongsa, and Jeb F. Willenbring, Branching from the General Linear Group to the Symmetric Group and the Principal Embedding, Algebraic Combinatorics, vol. 4, issue 2 (2021), p. 189-200.
Florent Hivert, Jean-Christophe Novelli, and Jean-Yves Thibon, Commutative combinatorial Hopf algebras, arXiv:math/0605262 [math.CO], 2006.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 144
Sujoy Mukherjee and Petr Vojtěchovský, Minimal representatives of endofunctions, Univ. Denver (2024).
Ronald C. Read, Note on number of functional digraphs, Math. Ann., vol. 143 (1961), pp. 109-111.
Marko Riedel, stackexchange.com, Enumeration of functions by Simultaneous Power Group Enumeration (SPGE)
Marko Riedel, Maple code for sequence using SPGE
Sara Riva, Factorisation of Discrete Dynamical Systems, Ph.D. Thesis, Univ. Côte d'Azur (France 2023).
N. J. A. Sloane, Illustration of initial terms
N. J. A. Sloane, Transforms
P. R. Stein, Letter to N. J. A. Sloane, Jun 02 1971

Cf. A000312, A002861, A006961, A001373, A054050, A054745.

with(combstruct): M[ 2671 ] := [ F,{F=Set(K), K=Cycle(T), T=Prod(Z,Set(T))},unlabeled ]:
a:=seq(count(M[2671],size=n),n=0..27); # added by W. Edwin Clark, Nov 23 2010

Needs["Combinatorica`"];
nn=30;s[n_,k_]:=s[n,k]=a[n+1-k]+If[n<2 k,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);rt=Table[a[i],{i,1,nn}];c=Drop[Apply[Plus,Table[Take[CoefficientList[CycleIndex[CyclicGroup[n],s]/.Table[s[j]->Table[Sum[rt[[i]] x^(k*i),{i,1,nn}],{k,1,nn}][[j]],{j,1,nn}],x],nn],{n,1,30}]],1];CoefficientList[Series[Product[1/(1-x^i)^c[[i]],{i,1,nn-1}],{x,0,nn}],x]  (* after code given by Robert A. Russell in A000081 *) (* Geoffrey Critzer, Oct 12 2012 *)
max = 40; A[n_] := A[n] = If[n <= 1, n, Sum[DivisorSum[j, #*A[#]&]*A[n-j], {j, 1, n-1}]/(n-1)]; H[t_] := Sum[A[n]*t^n, {n, 0, max}]; F = 1 / Product[1 - H[x^n], {n, 1, max}] + O[x]^max; CoefficientList[F, x] (* Jean-François Alcover, Dec 01 2015, after Joerg Arndt *)

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] ) );
A000081=concat([0], A);
H(t)=subst(Ser(A000081, 't), 't, t);
x='x+O('x^N);
F=1/prod(n=1,N, 1 - H(x^n));
Vec(F)
\\ Joerg Arndt, Jul 10 2014

Euler transform of A002861.

a(n) ~ c * d^n / sqrt(n), where d = A051491 = 2.9557652856519949747148... (Otter's rooted tree constant), c = 0.442876769782206479836... (for a closed form see "Mathematical Constants", p.308). - Vaclav Kotesovec, Mar 17 2015

More terms etc. from Paul Zimmermann, Mar 15 1996

Name edited by Keith J. Bauer, Jan 07 2024

A087803 Number of unlabeled rooted trees with at most n nodes.

Original entry on oeis.org

1, 2, 4, 8, 17, 37, 85, 200, 486, 1205, 3047, 7813, 20299, 53272, 141083, 376464, 1011311, 2732470, 7421146, 20247374, 55469206, 152524387, 420807242, 1164532226, 3231706871, 8991343381, 25075077710, 70082143979, 196268698287, 550695545884, 1547867058882

Offset: 1

Hugo Pfoertner, Oct 12 2003

nonn

Number of equations (order conditions) that must be satisfied to achieve order n in the construction of a Runge-Kutta method for the numerical solution of an ordinary differential equation. - Hugo Pfoertner, Oct 12 2003

Butcher, J. C., The Numerical Analysis of Ordinary Differential Equations, (1987) Wiley, Chichester
See link for more references.

Alois P. Heinz, Table of n, a(n) for n = 1..1000
A. Cayley, On the analytical forms called trees, Amer. J. Math., 4 (1881), 266-268.
I. Th. Famelis, S. N. Papakostas and Ch. Tsitouras, Symbolic Derivation of Runge-Kutta Order Conditions.
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.
Florian Ingels, Revisiting Tree Isomorphism: An Algorithmic Bric-à-Brac, arXiv:2309.14441 [cs.DS], 2023-2024. See p. 17.
Eric Weisstein's World of Mathematics, Rooted Tree.
Index entries for sequences related to rooted trees.

a(n) = Sum_(k=1..n) A000081(k).

Cf. A255170, A187770, A051491.

with(numtheory):
b:= proc(n) option remember; local d, j; `if`(n<=1, n,
      (add(add(d*b(d), d=divisors(j))*b(n-j), j=1..n-1))/(n-1))
    end:
a:= proc(n) option remember; b(n) +`if`(n<1, 0, a(n-1)) end:
seq(a(n), n=1..50);  # Alois P. Heinz, Aug 21 2012

b[0] = 0; b[1] = 1; b[n_] := b[n] = Sum[b[n - j]* DivisorSum[j, # *b[#]&], {j, 1, n-1}]/(n-1); a[1] = 1; a[n_] := a[n] = b[n] + a[n-1]; Table[a[n], {n, 1, 50}] (* Jean-François Alcover, Nov 10 2015, after Alois P. Heinz *)
t[1] = a[1] = 1; t[n_] := t[n] = Sum[k t[k] t[n - k m]/(n-1), {k, n}, {m, (n-1)/k}]; a[n_] := a[n] = a[n-1] + t[n]; Table[a[n], {n, 40}] (* Vladimir Reshetnikov, Aug 12 2016 *)
Needs["NumericalDifferentialEquationAnalysis`"]
Drop[Accumulate[Join[{0},ButcherTreeCount[20]]],1] (* Peter Luschny, Aug 18 2016 *)

a000081(k) = local(A = x); if( k<1, 0, for( j=1, k-1, A /= (1 - x^j + x * O(x^k))^polcoeff(A, j)); polcoeff(A, k));
a(n) = sum(k=1, n, a000081(k)) \\ Altug Alkan, Nov 10 2015

def A087803_list(len):
    a, t = [1], [0,1]
    for n in (1..len-1):
        S = [t[n-k+1]*sum(d*t[d] for d in divisors(k)) for k in (1..n)]
        t.append(sum(S)//n)
        a.append(a[-1]+t[-1])
    return a
A087803_list(20) # Peter Luschny, Aug 18 2016

a(n) ~ c * d^n / n^(3/2), where d = A051491 = 2.9557652856519949747148..., c = 0.664861031240097088000569... . - Vaclav Kotesovec, Sep 11 2014

In the asymptotics above the constant c = A187770 / (1 - 1 / A051491). - Vladimir Reshetnikov, Aug 12 2016

Corrected and extended by Alois P. Heinz, Aug 21 2012

Renamed (old name is in comments) by Vladimir Reshetnikov, Aug 23 2016

A187770 Decimal expansion of Otter's asymptotic constant beta for the number of rooted trees.

Original entry on oeis.org

4, 3, 9, 9, 2, 4, 0, 1, 2, 5, 7, 1, 0, 2, 5, 3, 0, 4, 0, 4, 0, 9, 0, 3, 3, 9, 1, 4, 3, 4, 5, 4, 4, 7, 6, 4, 7, 9, 8, 0, 8, 5, 4, 0, 7, 9, 4, 0, 1, 1, 9, 8, 5, 7, 6, 5, 3, 4, 9, 3, 5, 4, 5, 0, 2, 2, 6, 3, 5, 4, 0, 0, 4, 2, 0, 4, 7, 6, 4, 6, 0, 5, 3, 7, 9, 8, 6

Offset: 0

Vaclav Kotesovec, Jan 04 2013

A000081(n) ~ 0.439924012571 * alpha^n * n^(-3/2), alpha = 2.95576528565199497... (see A051491)

			0.43992401257102530404090339143454476479808540794...

Steven R. Finch, Mathematical Constants, Cambridge, 2003, Section 5.6., p.296
D. E. Knuth, Fundamental Algorithms, 3d Ed. 1997, p. 396.

Vaclav Kotesovec, Table of n, a(n) for n = 0..1799, (this constant was computed by David Broadhurst in November 1999)
David Broadhurst, Resurgent Integer Sequences, Rutgers Experimental Math Seminar, Feb 06 2025; Slides.
Amirmohammad Farzaneh, Mihai-Alin Badiu, and Justin P. Coon, On Random Tree Structures, Their Entropy, and Compression, arXiv:2309.09779 [cs.IT], 2023.
Eric Weisstein's World of Mathematics, Rooted Tree

Cf. A000081, A051491, A000055, A086308.

digits = 87; max = 250; s[n_, k_] := s[n, k] = a[n+1-k] + If[n < 2*k, 0, s[n-k, k]]; a[1] = 1; a[n_] := a[n] = Sum[a[k]*s[n-1, k]*k, {k, 1, n-1}]/(n-1); A[x_] := Sum[a[k]*x^k, {k, 0, max}]; APrime[x_] := Sum[k*a[k]*x^(k-1), {k, 0, max}]; eq = Log[c] == 1 + Sum[A[c^(-k)]/k, {k, 2, max}]; alpha = c /. FindRoot[eq, {c, 3}, WorkingPrecision -> digits+5]; b = Sqrt[(1 + Sum[APrime[alpha^-k]/alpha^k, {k, 2, max}])/(2*Pi)]; RealDigits[b, 10, digits] // First (* Jean-François Alcover, Sep 24 2014 *)

A027852 Number of connected functions on n points with a loop of length 2.

Original entry on oeis.org

0, 1, 1, 3, 6, 16, 37, 96, 239, 622, 1607, 4235, 11185, 29862, 80070, 216176, 586218, 1597578, 4370721, 12003882, 33077327, 91433267, 253454781, 704429853, 1962537755, 5479855546, 15332668869, 42983656210, 120716987723, 339596063606, 956840683968

Offset: 1

Christian G. Bower, Dec 14 1997

nonn

Number of unordered pairs of rooted trees with a total of n nodes.
Equivalently, the number of rooted trees on n+1 nodes where the root has degree 2.
Number of trees on n nodes rooted at an edge. - Washington Bomfim, Jul 06 2012
Guy (1988) calls these tadpole graphs. - N. J. A. Sloane, Nov 04 2014
Number of unicyclic graphs of n nodes with a cycle length of two (in other words, a double edge). - Washington Bomfim, Dec 02 2020

Alois P. Heinz, Table of n, a(n) for n = 1..2136
Washington Bomfim, Illustration of initial terms
R. K. Guy, Letter to N. J. A. Sloane, 1988-04-12 (annotated scanned copy) Includes illustrations for n <= 6.
R. J. Mathar, Topologically distinct sets of non-intersecting circles in the plane, arXiv:1603.00077 [math.CO] (2016), Eq. (75).
Index entries for sequences related to rooted trees

Column 2 of A033185 (forests of rooted trees), A217781 (unicyclic graphs), A339303 (unoriented linear forests) and A339428 (connected functions).

Cf. A000081, A000106, A000226, A000631, A001372, A002861.

with(numtheory): b:= proc(n) option remember; local d, j; `if`(n<=1, n, (add(add(d*b(d), d=divisors(j)) *b(n-j), j=1..n-1))/ (n-1)) end: a:= n-> (add(b(i) *b(n-i), i=0..n) +`if`(irem(n, 2)=0, b(n/2), 0))/2: seq(a(n), n=1..50);  # Alois P. Heinz, Aug 22 2008, revised Oct 07 2011
# second, re-usable version
A027852 := proc(N::integer)
    local dh, Nprime;
    dh := 0 ;
    for Nprime from 0 to N do
        dh := dh+A000081(Nprime)*A000081(N-Nprime) ;
    end do:
    if type(N,'even') then
        dh := dh+A000081(N/2) ;
    end if;
    dh/2 ;
end proc: # R. J. Mathar, Mar 06 2017

Needs["Combinatorica`"];nn = 30; s[n_, k_] := s[n, k] = a[n + 1 - k] + If[n < 2 k, 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); rt = Table[a[i], {i, 1, nn}]; Take[CoefficientList[CycleIndex[DihedralGroup[2], s] /. Table[s[j] -> Table[Sum[rt[[i]] x^(k*i), {i, 1, nn}], {k, 1, nn}][[j]], {j, 1, nn}], x], {2, nn}]  (* Geoffrey Critzer, Oct 12 2012, after code given by Robert A. Russell in A000081 *)
b[n_] := b[n] = If[n <= 1, n, (Sum[Sum[d b[d], {d, Divisors[j]}] b[n-j], {j, 1, n-1}])/(n-1)];
a[n_] := (Sum[b[i] b[n-i], {i, 0, n}] + If[Mod[n, 2] == 0, b[n/2], 0])/2;
Table[a[n], {n, 1, 50}] (* Jean-François Alcover, Oct 30 2018, after Alois P. Heinz *)

seq(max_n)= { my(V = f = vector(max_n), i=1,s); f[1]=1;
for(j=1, max_n - 1, f[j+1] = 1/j * sum(k=1, j, sumdiv(k,d, d * f[d]) * f[j-k+1]));
for(n = 1, max_n, s = sum(k = 1, (n-1)/2, ( f[k] * f[n-k] ));
if(n % 2 == 1, V[i] = s, V[i] = s + (f[n/2]^2 + f[n/2])/2); i++); V };
\\ Washington Bomfim, Jul 06 2012 and Dec 01 2020

G.f.: A(x) = (B(x)^2 + B(x^2))/2 where B(x) is g.f. of A000081.
a(n) = Sum_{k=1..(n-1)/2}( f(k)*f(n-k) ) + [n mod 2 = 0] * ( f(n/2)^2+f(n/2) ) /2, where f(n) = A000081(n). - Washington Bomfim, Jul 06 2012 and Dec 01 2020
a(n) ~ c * d^n / n^(3/2), where d = A051491 = 2.9557652856519949747148..., c = A187770 = 0.43992401257102530404090339... . - Vaclav Kotesovec, Sep 12 2014
2*a(n) = A000106(n) + A000081(n/2), where A(.)=0 if the argument is non-integer. - R. J. Mathar, Jun 04 2020

Edited by Christian G. Bower, Feb 12 2002

A242249 Number A(n,k) of rooted trees with n nodes and k-colored non-root nodes; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 2, 2, 0, 0, 1, 3, 7, 4, 0, 0, 1, 4, 15, 26, 9, 0, 0, 1, 5, 26, 82, 107, 20, 0, 0, 1, 6, 40, 188, 495, 458, 48, 0, 0, 1, 7, 57, 360, 1499, 3144, 2058, 115, 0, 0, 1, 8, 77, 614, 3570, 12628, 20875, 9498, 286, 0, 0, 1, 9, 100, 966, 7284, 37476, 111064, 142773, 44947, 719, 0

Offset: 0

Alois P. Heinz, May 09 2014

From Vaclav Kotesovec, Aug 26 2014: (Start)
Column k > 0 is asymptotic to c(k) * d(k)^n / n^(3/2), where constants c(k) and d(k) are dependent only on k. Conjecture: d(k) ~ k * exp(1). Numerically:
d(1)   =   2.9557652856519949747148175... (A051491)
d(2)   =   5.6465426162329497128927135... (A245870)
d(3)   =   8.3560268792959953682760695...
d(4)   =  11.0699628777593263124193026...
d(5)   =  13.7856511100846851989303249...
d(6)   =  16.5022088446930015657112211...
d(7)   =  19.2192613290638657575973462...
d(8)   =  21.9366222112987115910888213...
d(9)   =  24.6541883249893084812976812...
d(10)  =  27.3718979186642404090999595...
d(100) = 272.0126359583480733207362718...
d(101) = 274.7309127032967881125015217...
d(200) = 543.8405620978790523837823296...
d(201) = 546.5588426492458787468860222...
d(101)-d(100) = 2.718276744...
d(201)-d(200) = 2.718280551...
(End)

			Square array A(n,k) begins:
  0,  0,    0,     0,      0,      0,       0,       0, ...
  1,  1,    1,     1,      1,      1,       1,       1, ...
  0,  1,    2,     3,      4,      5,       6,       7, ...
  0,  2,    7,    15,     26,     40,      57,      77, ...
  0,  4,   26,    82,    188,    360,     614,     966, ...
  0,  9,  107,   495,   1499,   3570,    7284,   13342, ...
  0, 20,  458,  3144,  12628,  37476,   91566,  195384, ...
  0, 48, 2058, 20875, 111064, 410490, 1200705, 2984142, ...

Alois P. Heinz, Antidiagonals n = 0..140, flattened
L. Foissy, Algebraic structures on typed decorated rooted trees, arXiv:1811.07572 (2018), doi SIGMA 17 (2021)

Columns k=0-10 give: A063524, A000081, A000151, A006964, A052763, A052788, A246235, A246236, A246237, A246238, A246239.
Rows n=0-3 give: A000004, A000012, A001477, A005449.
Lower diagonal gives A242375.
Cf. A255517, A256064.

with(numtheory):
A:= proc(n, k) option remember; `if`(n<2, n, (add(add(d*
      A(d, k), d=divisors(j))*A(n-j, k)*k, j=1..n-1))/(n-1))
    end:
seq(seq(A(n, d-n), n=0..d), d=0..12);

nn = 10; t[x_] := Sum[a[n] x^n, {n, 1, nn}]; Transpose[ Table[Flatten[ sol = SolveAlways[ 0 == Series[ t[x] - x Product[1/(1 - x^i)^(n a[i]), {i, 1, nn}], {x, 0, nn}], x]; Flatten[{0, Table[a[n], {n, 1, nn}]}] /. sol], {n, 0, nn}]] // Grid (* Geoffrey Critzer, Nov 11 2014 *)
A[n_, k_] := A[n, k] = If[n<2, n, Sum[Sum[d*A[d, k], {d, Divisors[j]}] *A[n-j, k]*k, {j, 1, n-1}]/(n-1)]; Table[Table[A[n, d-n], {n, 0, d}], {d, 0, 12}] // Flatten (* Jean-François Alcover, Dec 04 2014, translated from Maple *)

\\ ColGf gives column generating function
ColGf(N,k) = {my(A=vector(N, j, 1)); for (n=1, N-1, A[n+1] = k/n * sum(i=1, n, sumdiv(i, d, d*A[d]) * A[n-i+1] ) ); x*Ser(A)}
Mat(vector(8, k, concat(0, Col(ColGf(7, k-1))))) \\ Andrew Howroyd, May 12 2018

G.f. for column k: x*Product_{n>=1} 1/(1 - x^n)^(k*A(n,k)). - Geoffrey Critzer, Nov 13 2014

cp's OEIS Frontend

A000081 Number of unlabeled rooted trees with n nodes (or connected functions with a fixed point).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

Maxima

PARI

PARI

PARI

Python

Sage

Sage

Formula

A000055 Number of trees with n unlabeled nodes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

Python

SageMath

Formula

A005195 Number of forests with n unlabeled nodes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A001372 Number of unlabeled mappings (or mapping patterns) from n points to themselves; number of unlabeled endofunctions.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A087803 Number of unlabeled rooted trees with at most n nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica