A187770 -id:A187770 - 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

A051491 Decimal expansion of Otter's rooted tree constant: lim_{n->inf} A000081(n+1)/A000081(n).

Original entry on oeis.org

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

Offset: 1

David Broadhurst

A000055(n) ~ A086308 * A051491^n * n^(-5/2), A000081(n) ~ A187770 * A051491^n * n^(-3/2). - Vaclav Kotesovec, Jan 04 2013

Analytic Combinatorics (Flajolet and Sedgewick, 2009, p. 481) has a wrong value of this constant (2.9955765856). - Vaclav Kotesovec, Jan 04 2013

			2.95576528565199497471481752412319458837549230466359659535...

S. R. Finch, Mathematical Constants, Cambridge, 2003, pp. 295-316.

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.
S. R. Finch, Otter's Tree Enumeration Constants [Broken link]
S. R. Finch, Otter's Tree Enumeration Constants [Wayback Machine]
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009, p. 481
Simon Plouffe, Tree-growth constant to 1800 digits
Eric Weisstein's World of Mathematics, Rooted Tree
Eric Weisstein's World of Mathematics, Tree
Index entries for sequences related to trees
Index entries for sequences related to rooted trees

Cf. A000081, A051492, A187770, A000055, A086308, A215978, A274082.

digits = 99; 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}]; eq = Log[c] == 1+Sum[A[c^-k]/k, {k, 2, max}]; alpha = c /. FindRoot[eq, {c, 3}, WorkingPrecision -> digits+5]; RealDigits[alpha, 10, digits] // First (* Jean-François Alcover, Sep 24 2014 *)

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

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

A000106 2nd power of rooted tree enumerator; number of linear forests of 2 rooted trees.

Original entry on oeis.org

1, 2, 5, 12, 30, 74, 188, 478, 1235, 3214, 8450, 22370, 59676, 160140, 432237, 1172436, 3194870, 8741442, 24007045, 66154654, 182864692, 506909562, 1408854940, 3925075510, 10959698606, 30665337738, 85967279447, 241433975446, 679192039401, 1913681367936, 5399924120339

Offset: 2

N. J. A. Sloane

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 150.
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 = 2..1000 (terms n = 2..200 from T. D. Noe)
Vsevolod Gubarev, Rota-Baxter operators on a sum of fields, arXiv:1811.08219 [math.RA], 2018.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 385
Index entries for sequences related to rooted trees

Column d=1 of A335362.
Column 2 of A339067.
Cf. A000081, A000242, A000300, A000343, A000395, A027852 (forests of 2 rooted trees).

a000106 n = a000106_list !! (n-2)
a000106_list = drop 2 $ conv a000081_list [] where
   conv (v:vs) ws = (sum $ zipWith (*) ws' $ reverse ws') : conv vs ws'
                    where ws' = v : ws
-- Reinhard Zumkeller, Jun 17 2013

b:= proc(n) option remember; if n<=1 then n else add(k*b(k)* s(n-1, k), k=1..n-1)/(n-1) fi end: s:= proc(n,k) option remember; add(b(n+1-j*k), j=1..iquo(n,k)) end: B:= proc(n) option remember; add(b(k)*x^k, k=1..n) end: a:= n-> coeff(series(B(n-1)^2, x=0, n+1), x,n): seq(a(n), n=2..35); # Alois P. Heinz, Aug 21 2008

<Jean-François Alcover, Nov 02 2011 *)
b[n_] := b[n] = If[n <= 1, n, Sum[k*b[k]*s[n-1, k], {k, 1, n-1}]/(n-1)]; s[n_, k_] := s[n, k] = Sum[b[n+1-j*k], {j, 1, Quotient[n, k]}]; B[n_] := B[n] = Sum[b[k]*x^k, {k, 1, n}]; a[n_] := SeriesCoefficient[B[n-1]^2, {x, 0, n}]; Table[a[n], {n, 2, 35}] (* Jean-François Alcover, Dec 01 2016, after Alois P. Heinz *)

Self-convolution of rooted trees A000081.
a(n) ~ c * d^n / n^(3/2), where d = A051491 = 2.9557652856519949747148..., c = 0.87984802514205060808180678... . - Vaclav Kotesovec, Sep 11 2014
In the asymptotics above the constant c = 2 * A187770. - Vladimir Reshetnikov, Aug 13 2016

More terms from Christian G. Bower, Nov 15 1999

A000226 Number of n-node unlabeled connected graphs with one cycle of length 3.

Original entry on oeis.org

1, 1, 3, 7, 18, 44, 117, 299, 793, 2095, 5607, 15047, 40708, 110499, 301541, 825784, 2270211, 6260800, 17319689, 48042494, 133606943, 372430476, 1040426154, 2912415527, 8167992598, 22947778342, 64577555147, 182009003773, 513729375064, 1452007713130

Offset: 3

N. J. A. Sloane

Number of rooted trees on n+1 nodes where root has degree 3. - Christian G. Bower
Third column of A033185. - Michael Somos, Aug 20 2018
From Washington Bomfim, Dec 22 2020: (Start)
Number of forests of 3 rooted trees with a total of n nodes.
Number of unicyclic graphs with a cycle of length 3 and a total of n nodes.
(End)

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 150.
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 = 3..1000 (first 198 terms from Vincenzo Librandi)
Sergei Abramovich, Partitions of integers, Ferrers-Young diagrams, and representational efficacy of spreadsheet modeling, Spreadsheets in Education (eJSiE): Vol. 5: Iss. 2, Article 1, p. 5
Washington Bomfim, Illustration of initial terms
F. Ruskey, Combinatorial Generation, Eq.(4.27), 2003
Eric Weisstein's World of Mathematics, Rooted Tree
Index entries for sequences related to rooted trees

Column 3 of A033185 and A217781.
Cf. A000081, A001429.
For n >= 3 a(n) = A217781(n, 3) = A058879(n, n-2) = A033185(n, 3).

b:= proc(n) option remember; if n<=1 then n else add(k*b(k)* s(n-1, k), k=1..n-1)/(n-1) fi end: s:= proc(n,k) option remember; add(b(n+1-j*k), j=1..iquo(n,k)) end: B:= proc(n) option remember; unapply(add(b(k)*x^k, k=1..n),x) end: a:= n-> coeff(series((B(n-2)(x)^3+ 3*B(n-2)(x)* B(n-2)(x^2)+ 2*B(n-2)(x^3))/6, x=0, n+1), x,n): seq(a(n), n=3..40); # Alois P. Heinz, Aug 21 2008

terms = 30; r[] = 0; Do[r[x] = x *Exp[Sum[r[x^k]/k, {k, 1, j}]] + O[x]^j // Normal, {j, 1, terms+3}]; A[x_] = (r[x]^3 + 3*r[x]*r[x^2] + 2*r[x^3])/6 + O[x]^(terms+3); Drop[CoefficientList[A[x], x], 3] (* Jean-François Alcover, Nov 23 2011, updated Jan 11 2018 *)

seq(max_n) = {my(a = f = vector(max_n), s, D); 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=3,max_n,s=0;forpart(P=n,D=Set(P);if(#D==3,s+=f[P[1]]*f[P[2]]*f[P[3]];next());
if(#D==1, s+= binomial(f[P[1]]+2, 3); next());
if(P[1] == P[2], s += binomial(f[P[1]]+1, 2) * f[P[3]],
s += binomial(f[P[2]]+1, 2) * f[P[1]]),[1,n],[3,3]); a[n] = s ); a[3..max_n] }; \\ Washington Bomfim, Dec 22 2020

G.f.: (r(x)^3+3*r(x)*r(x^2)+2*r(x^3))/6 where r(x) is g.f. for rooted trees (A000081).
a(n) = Sum_{j1+2j2+···= n} (Product_{i=1..n} binomial(A000081(i) + j_i -1, j_i)) [(4.27) of [F. Ruskey] with n replaced by n+1]. - Washington Bomfim, Dec 22 2020
a(n) ~ (A187770 + A339986) * A051491^n / (2 * n^(3/2)). - Vaclav Kotesovec, Dec 25 2020

More terms from Vladeta Jovovic, Apr 19 2000

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

A051491 Decimal expansion of Otter's rooted tree constant: lim_{n->inf} A000081(n+1)/A000081(n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Sage

Formula

Extensions

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A000106 2nd power of rooted tree enumerator; number of linear forests of 2 rooted trees.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Formula

Extensions

A000226 Number of n-node unlabeled connected graphs with one cycle of length 3.

Views

Author

Keywords

Comments