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

A000169 Number of labeled rooted trees with n nodes: n^(n-1).

Original entry on oeis.org

1, 2, 9, 64, 625, 7776, 117649, 2097152, 43046721, 1000000000, 25937424601, 743008370688, 23298085122481, 793714773254144, 29192926025390625, 1152921504606846976, 48661191875666868481, 2185911559738696531968, 104127350297911241532841, 5242880000000000000000000

Offset: 1

N. J. A. Sloane

Also the number of connected transitive subtree acyclic digraphs on n vertices. - Robert Castelo, Jan 06 2001
For any given integer k, a(n) is also the number of functions from {1,2,...,n} to {1,2,...,n} such that the sum of the function values is k mod n. - Sharon Sela (sharonsela(AT)hotmail.com), Feb 16 2002
The n-th term of a geometric progression with first term 1 and common ratio n: a(1) = 1 -> 1,1,1,1,... a(2) = 2 -> 1,2,... a(3) = 9 -> 1,3,9,... a(4) = 64 -> 1,4,16,64,... - Amarnath Murthy, Mar 25 2004
All rational solutions to the equation x^y = y^x, with x < y, are given by x = A000169(n+1)/A000312(n), y = A000312(n+1)/A007778(n), where n = 1, 2, 3, ... . - Nick Hobson, Nov 30 2006
a(n+1) is also the number of partial functions on n labeled objects. - Franklin T. Adams-Watters, Dec 25 2006
In other words, if A is a finite set of size n-1, then a(n) is the number of binary relations on A that are also functions. Note that a(n) = Sum_{k=0..n-1} binomial(n-1,k)*(n-1)^k = n^(n-1), where binomial(n-1,k) is the number of ways to select a domain D of size k from A and (n-1)^k is the number of functions from D to A. - Dennis P. Walsh, Apr 21 2011
This is the fourth member of a set of which the other members are the symmetric group, full transformation semigroup, and symmetric inverse semigroup. For the first three, see A000142, A000312, A002720. - Peter J. Cameron, Nov 03 2024.
More generally, consider the class of sequences of the form a(n) = (n*c(1)*...*c(i))^(n-1). This sequence has c(1)=1. A052746 has a(n) = (2*n)^(n-1), A052756 has a(n) = (3*n)^(n-1), A052764 has a(n) = (4*n)^(n-1), A052789 has a(n) = (5*n)^(n-1) for n>0. These sequences have a combinatorial structure like simple grammars. - Ctibor O. Zizka, Feb 23 2008
a(n) is equal to the logarithmic transform of the sequence b(n) = n^(n-2) starting at b(2). - Kevin Hu (10thsymphony(AT)gmail.com), Aug 23 2010
Also, number of labeled connected multigraphs of order n without cycles except one loop. See link below to have a picture showing the bijection between rooted trees and multigraphs of this kind. (Note that there are no labels in the picture, but the bijection remains true if we label the nodes.) - Washington Bomfim, Sep 04 2010
a(n) is also the number of functions f:{1,2,...,n} -> {1,2,...,n} such that f(1) = 1.
For a signed version of A000169 arising from the Vandermonde determinant of (1,1/2,...,1/n), see the Mathematica section. - Clark Kimberling, Jan 02 2012
Numerator of (1+1/(n-1))^(n-1) for n>1. - Jean-François Alcover, Jan 14 2013
Right edge of triangle A075513. - Michel Marcus, May 17 2013
a(n+1) is the number of n x n binary matrices with no more than a single one in each row. Partitioning the set of such matrices by the number k of rows with a one, we obtain a(n+1) = Sum_{k=0..n} binomial(n,k)*n^k = (n+1)^n. - Dennis P. Walsh, May 27 2014
Central terms of triangle A051129: a(n) = A051129(2*n-1,n). - Reinhard Zumkeller, Sep 14 2014
a(n) is the row sum of the n-th rows of A248120 and A055302, so it enumerates the monomials in the expansion of [x(1) + x(2) + ... + x(n)]^(n-1). - Tom Copeland, Jul 17 2015
For any given integer k, a(n) is the number of sums x_1 + ... + x_m = k (mod n) such that: x_1, ..., x_m are nonnegative integers less than n, the order of the summands does not matter, and each integer appears fewer than n times as a summand. - Carlo Sanna, Oct 04 2015
a(n) is the number of words of length n-1 over an alphabet of n letters. - Joerg Arndt, Oct 07 2015
a(n) is the number of parking functions whose largest element is n and length is n. For example, a(3) = 9 because there are nine such parking functions, namely (1,2,3), (1,3,2), (2,3,1), (2,1,3), (3,1,2), (3,2,1), (1,1,3), (1,3,1), (3,1,1). - Ran Pan, Nov 15 2015
Consider the following problem: n^2 cells are arranged in a square array. A step can be defined as going from one cell to the one directly above it, to the right of it or under it. A step above cannot be followed by a step below and vice versa. Once the last column of the square array is reached, you can only take steps down. a(n) is the number of possible paths (i.e., sequences of steps) from the cell on the bottom left to the cell on the bottom right. - Nicolas Nagel, Oct 13 2016
The rationals c(n) = a(n+1)/a(n), n >= 1, appear in the proof of G. Pólya's "elementary, but not too elementary, theorem": Sum_{n>=1} (Product_{k=1..n} a_k)^(1/n) < exp(1)*Sum_{n>=1} a_n, for n >= 1, with the sequence {a_k}{k>=1} of nonnegative terms, not all equal to 0. - _Wolfdieter Lang, Mar 16 2018
Coefficients of the generating series for the preLie operadic algebra. Cf. p. 417 of the Loday et al. paper. - Tom Copeland, Jul 08 2018
a(n)/2^(n-1) is the square of the determinant of the n X n matrix M_n with elements m(j,k) = cos(Pi*j*k/n). See Zhi-Wei Sun, Petrov link. - Hugo Pfoertner, Sep 19 2021
a(n) is the determinant of the n X n matrix P_n such that, when indexed [0, n), P(0, j) = 1, P(i <= j) = i, and P(i > j) = i-n. - C.S. Elder, Mar 11 2024

			For n=3, a(3)=9 because there are exactly 9 binary relations on A={1, 2} that are functions, namely: {}, {(1,1)}, {(1,2)}, {(2,1)}, {(2,2)}, {(1,1),(2,1)}, {(1,1),(2,2)}, {(1,2),(2,1)} and {(1,2),(2,2)}. - _Dennis P. Walsh_, Apr 21 2011
G.f. = x + 2*x^2 + 9*x^3 + 64*x^4 + 625*x^5 + 7776*x^6 + 117649*x^7 + ...

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 169.
Jonathan L. Gross and Jay Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 524.
Hannes Heikinheimo, Heikki Mannila and Jouni K. Seppnen, Finding Trees from Unordered 01 Data, in Knowledge Discovery in Databases: PKDD 2006, Lecture Notes in Computer Science, Volume 4213/2006, Springer-Verlag. - N. J. A. Sloane, Jul 09 2009
Clifford A. Pickover, A Passion for Mathematics, Wiley, 2005; see p. 63.
John Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 128.
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).
Richard P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see page 25, Prop. 5.3.2, and p. 37, (5.52).

N. J. A. Sloane, Table of n, a(n) for n = 1..100
Paul Barry and Aoife Hennessy, Generalized Narayana Polynomials, Riordan Arrays, and Lattice Paths, Journal of Integer Sequences, Vol. 15, 2012, #12.4.8. - _N. J. A. Sloane_, Oct 08 2012
Washington Bomfim, Bijection between rooted forests and multigraphs without cycles except one loop in each connected component. [From _Washington Bomfim_, Sep 04 2010]
David Callan, A Combinatorial Derivation of the Number of Labeled Forests, J. Integer Seqs., Vol. 6, 2003.
Peter J. Cameron and Philippe Cara, Independent generating sets and geometries for symmetric groups, J. Algebra, Vol. 258, no. 2 (2002), 641-650.
Robert Castelo and Arno Siebes, A characterization of moral transitive directed acyclic graph Markov models as trees, Technical Report CS-2000-44, Faculty of Computer Science, University of Utrecht.
Robert Castelo and Arno Siebes, A characterization of moral transitive acyclic directed graph Markov models as labeled trees, Journal of Statistical Planning and Inference, Vol. 115, No. 1 (2003), pp. 235-259; alternative link.
Frédéric Chapoton, Florent Hivert and Jean-Christophe Novelli, A set-operad of formal fractions and dendriform-like sub-operads, Journal of Algebra, Vol. 465 (2016), pp. 322-355; arXiv preprint, arXiv:1307.0092 [math.CO], 2013.
Ali Chouria, Vlad-Florin Drǎgoi, Jean-Gabriel Luque, On recursively defined combinatorial classes and labelled trees, arXiv:2004.04203 [math.CO], 2020.
R. M. Corless, G. H. Gonnet, D. E. G. Hare, D. J. Jeffrey and D. E. Knuth, On the Lambert W Function, Advances in Computational Mathematics, VOl. 5 (1996), pp. 329-359; alternative link.
Nick Hobson, Solution to puzzle 48: Exponential equation.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 67.
Qipeng Kuang, Ondřej Kuželka, Yuanhong Wang, and Yuyi Wang, Bridging Weighted First Order Model Counting and Graph Polynomials, arXiv:2407.11877 [cs.LO], 2024. See p. 33.
Jean-Louis Loday and Bruno Vallette, Algebraic Operads, version 0.99, 2012.
G. Pólya, With, or Without, Motivation?, Amer. Math. Monthly, Vol. 56, No. 10 (1949), pp. 684-691. Reprinted in "A Century of Mathematics", John Ewing (ed.), Math. Assoc. of Amer., 1994, pp. 195-200 (the reference there is wrong).
Gwenaël Richomme, Characterization of infinite LSP words and endomorphisms preserving the LSP property, International Journal of Foundations of Computer Science, Vol. 30, No. 1 (2019), pp. 171-196; arXiv preprint, arXiv:1808.02680 [cs.DM], 2018.
Marko Riedel, math.stackexchange.com, Proof of an identity relating the tree function T(z) and the second order Eulerian numbers. Feb. 28, 2021.
Marko Riedel, math.stackexchange.com, Asymptotics of tree function statistics using Pusieux series
Frank Ruskey, Information on Rooted Trees.
N. J. A. Sloane, Illustration of initial terms
Zhi-Wei Sun, Fedor Petrov, A surprising identity, discussion in MathOverflow, Jan 17 2019.
Elena L. Wang and Guoce Xin, On Ward Numbers and Increasing Schröder Trees, arXiv:2507.15654 [math.CO], 2025. See p. 12.
Eric Weisstein's World of Mathematics, Graph Vertex.
Dimitri Zvonkine, An algebra of power series arising in the intersection theory of moduli spaces of curves and in the enumeration of ramified coverings of the sphere, arXiv:math/0403092 [math.AG], 2004.
Index entries for sequences related to rooted trees
Index entries for sequences related to trees
Index entries for "core" sequences

Cf. A000055, A000081, A000142, A000272, A000312, A002720, A007778, A007830, A008785-A008791, A055860, A002061, A052746, A052756, A052764, A052789, A051129, A098686, A247363, A055302, A248120, A130293, A053506-A053509, A262974.

Other classes of endofunctions: A275549-A275558.

a000169 n = n ^ (n - 1)  -- Reinhard Zumkeller, Sep 14 2014

[n^(n-1): n in [1..20]]; // Vincenzo Librandi, Jul 17 2015

A000169 := n -> n^(n-1);
# second program:
spec := [A, {A=Prod(Z, Set(A))}, labeled]; [seq(combstruct[count](spec, size=n), n=1..20)];
# third program:
A000169 := n -> add((-1)^(n+k-1)*pochhammer(n, k)*Stirling2(n-1, k), k = 0..n-1):
seq(A000169(n), n = 1 .. 23);  # Mélika Tebni, May 07 2023

Table[n^(n - 1), {n, 1, 20}] (* Stefan Steinerberger, Apr 01 2006 *)
Range[0, 18]! CoefficientList[ Series[ -LambertW[-x], {x, 0, 18}], x] // Rest (* Robert G. Wilson v, updated by Jean-François Alcover, Oct 14 2019 *)
(* Next, a signed version A000169 from the Vandermonde determinant of (1,1/2,...,1/n) *)
f[j_] := 1/j; z = 12;
v[n_] := Product[Product[f[k] - f[j], {j, 1, k - 1}], {k, 2, n}]
Table[v[n], {n, 1, z}]
1/%  (* A203421 *)
Table[v[n]/v[n + 1], {n, 1, z - 1}]  (* A000169 signed *)
(* Clark Kimberling, Jan 02 2012 *)
a[n_]:=Det[Table[If[i==0,1,If[i<=j,i,i-n]],{i,0,n-1},{j,0,n-1}]]; Array[a,20] (* Stefano Spezia, Mar 12 2024 *)

n^(n-1) $ n=1..20 /* Zerinvary Lajos, Apr 01 2007 */

PARI
```
a(n) = n^(n-1)
```

def a(n): return n**(n-1)
print([a(n) for n in range(1, 21)]) # Michael S. Branicky, Sep 19 2021

from sympy import Matrix
def P(n): return [[ (i-n if i > j else i) + (i == 0) for j in range(n) ] for i in range(n)]
print(*(Matrix(P(n)).det() for n in range(1, 21)), sep=', ') # C.S. Elder, Mar 12 2024

The e.g.f. T(x) = Sum_{n>=1} n^(n-1)*x^n/n! satisfies T(x) = x*exp(T(x)), so T(x) is the functional inverse (series reversion) of x*exp(-x).
Also T(x) = -LambertW(-x) where W(x) is the principal branch of Lambert's function.
T(x) is sometimes called Euler's tree function.
a(n) = A000312(n-1)*A128434(n,1)/A128433(n,1). - Reinhard Zumkeller, Mar 03 2007
E.g.f.: LambertW(x)=x*G(0); G(k) = 1 - x*((2*k+2)^(2*k))/(((2*k+1)^(2*k)) - x*((2*k+1)^(2*k))*((2*k+3)^(2*k+1))/(x*((2*k+3)^(2*k+1)) - ((2*k+2)^(2*k+1))/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Dec 30 2011
a(n) = Sum_{i=1..n} binomial(n-1,i-1)*i^(i-2)*(n-i)^(n-i). - Dmitry Kruchinin, Oct 28 2013
Limit_{n->oo} a(n)/A000312(n-1) = e. - Daniel Suteu, Jul 23 2016
From Amiram Eldar, Nov 20 2020: (Start)
Sum_{n>=1} 1/a(n) = A098686.
Sum_{n>=1} (-1)^(n+1)/a(n) = A262974. (End)
a(n) = Sum_{k=0..n-1} (-1)^(n+k-1)*Pochhammer(n, k)*Stirling2(n-1, k). - Mélika Tebni, May 07 2023
In terms of Eulerian numbers A340556(n,k) of the second order Sum_{m>=1} m^(m+n) z^m/m! = 1/(1-T(z))^(2n+1) * Sum_{k=0..n} A2(n,k) T(z)^k. - Marko Riedel, Jan 10 2024

A000272 Number of trees on n labeled nodes: n^(n-2) with a(0)=1.

Original entry on oeis.org

1, 1, 1, 3, 16, 125, 1296, 16807, 262144, 4782969, 100000000, 2357947691, 61917364224, 1792160394037, 56693912375296, 1946195068359375, 72057594037927936, 2862423051509815793, 121439531096594251776, 5480386857784802185939, 262144000000000000000000, 13248496640331026125580781

Offset: 0

N. J. A. Sloane

Number of spanning trees in complete graph K_n on n labeled nodes.
Robert Castelo, Jan 06 2001, observes that n^(n-2) is also the number of transitive subtree acyclic digraphs on n-1 vertices.
a(n) is also the number of ways of expressing an n-cycle in the symmetric group S_n as a product of n-1 transpositions, see example. - Dan Fux (dan.fux(AT)OpenGaia.com or danfux(AT)OpenGaia.com), Apr 12 2001
Also counts parking functions, critical configurations of the chip firing game, allowable pairs sorted by a priority queue [Hamel].
The parking functions of length n can be described as all permutations of all words [d(1),d(2), ..., d(n)] where 1 <= d(k) <= k; see example. There are (n+1)^(n-1) = a(n+1) parking functions of length n. - Joerg Arndt, Jul 15 2014
a(n+1) is the number of endofunctions with no cycles of length > 1; number of forests of rooted labeled trees on n vertices. - Mitch Harris, Jul 06 2006
a(n) is also the number of nilpotent partial bijections (of an n-element set). Equivalently, the number of nilpotents in the partial symmetric semigroup, P sub n. - Abdullahi Umar, Aug 25 2008
a(n) is also the number of edge-labeled rooted trees on n nodes. - Nikos Apostolakis, Nov 30 2008
a(n+1) is the number of length n sequences on an alphabet of {1,2,...,n} that have a partial sum equal to n. For example a(4)=16 because there are 16 length 3 sequences on {1,2,3} in which the terms (beginning with the first term and proceeding sequentially) sum to 3 at some point in the sequence. {1, 1, 1}, {1, 2, 1}, {1, 2, 2}, {1, 2, 3}, {2, 1, 1}, {2, 1, 2}, {2, 1, 3}, {3, 1, 1}, {3, 1, 2}, {3, 1, 3}, {3, 2, 1}, {3, 2, 2}, {3, 2, 3}, {3, 3, 1}, {3, 3, 2}, {3, 3, 3}. - Geoffrey Critzer, Jul 20 2009
a(n) is the number of acyclic functions from {1,2,...,n-1} to {1,2,...,n}. An acyclic function f satisfies the following property: for any x in the domain, there exists a positive integer k such that (f^k)(x) is not in the domain. Note that f^k denotes the k-fold composition of f with itself, e.g., (f^2)(x)=f(f(x)). - Dennis P. Walsh, Mar 02 2011
a(n) is the absolute value of the discriminant of the polynomial x^{n-1}+...+x+1. More precisely, a(n) = (-1)^{(n-1)(n-2)/2} times the discriminant. - Zach Teitler, Jan 28 2014
For n > 2, a(n+2) is the number of nodes in the canonical automaton for the affine Weyl group of type A_n. - Tom Edgar, May 12 2016
The tree formula a(n) = n^(n-2) is due to Cayley (see the first comment). - Jonathan Sondow, Jan 11 2018
a(n) is the number of topologically distinct lines of play for the game Planted Brussels Sprouts on n vertices. See Ji and Propp link. - Caleb Ji, May 11 2018
a(n+1) is also the number of bases of R^n, that can be made from the n(n+1)/2 vectors of the form [0 ... 0 1 ... 1 0 ... 0]^T, where the initial or final zeros are optional, but at least one 1 has to be included. - Nicolas Nagel, Jul 31 2018
Cooper et al. show that every connected k-chromatic graph contains at least k^(k-2) spanning trees. - Michel Marcus, May 14 2020

			a(7)=matdet([196, 175, 140, 98, 56, 21; 175, 160, 130, 92, 53, 20; 140, 130, 110, 80, 47, 18; 98, 92, 80, 62, 38, 15; 56, 53, 47, 38, 26, 11; 21, 20, 18, 15, 11, 6])=16807
a(3)=3 since there are 3 acyclic functions f:[2]->[3], namely, {(1,2),(2,3)}, {(1,3),(2,1)}, and {(1,3),(2,3)}.
From _Joerg Arndt_ and Greg Stevenson, Jul 11 2011: (Start)
The following products of 3 transpositions lead to a 4-cycle in S_4:
  (1,2)*(1,3)*(1,4);
  (1,2)*(1,4)*(3,4);
  (1,2)*(3,4)*(1,3);
  (1,3)*(1,4)*(2,3);
  (1,3)*(2,3)*(1,4);
  (1,4)*(2,3)*(2,4);
  (1,4)*(2,4)*(3,4);
  (1,4)*(3,4)*(2,3);
  (2,3)*(1,2)*(1,4);
  (2,3)*(1,4)*(2,4);
  (2,3)*(2,4)*(1,2);
  (2,4)*(1,2)*(3,4);
  (2,4)*(3,4)*(1,2);
  (3,4)*(1,2)*(1,3);
  (3,4)*(1,3)*(2,3);
  (3,4)*(2,3)*(1,2).  (End)
The 16 parking functions of length 3 are 111, 112, 121, 211, 113, 131, 311, 221, 212, 122, 123, 132, 213, 231, 312, 321. - _Joerg Arndt_, Jul 15 2014
G.f. = 1 + x + x^2 + 3*x^3 + 16*x^4 + 125*x^5 + 1296*x^6 + 16807*x^7 + ...

M. Aigner and G. M. Ziegler, Proofs from The Book, Springer-Verlag, Berlin, 1999; see p. 142.
Anders Björner and Francesco Brenti, Combinatorics of Coxeter groups. Graduate Texts in Mathematics, 231. Springer, New York, 2005.
Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 311.
J. Dénes, The representation of a permutation as the product of a minimal number of transpositions and its connection with the theory of graphs, Pub. Math. Inst. Hung. Acad. Sci., 4 (1959), 63-70.
I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, John Wiley and Sons, N.Y., 1983, ex. 3.3.33.
J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 524.
F. Harary, J. A. Kabell, and F. R. McMorris (1992), Subtree acyclic digraphs, Ars Comb., vol. 34:93-95.
A. P. Prudnikov, Yu. A. Brychkov and O.I. Marichev, "Integrals and Series", Volume 1: "Elementary Functions", Chapter 4: "Finite Sums", New York, Gordon and Breach Science Publishers, 1986-1992, Eq. (4.2.2.37)
H. Prüfer, Neuer Beweis eines Satzes über Permutationen, Archiv der Mathematik und Physik, (3) 27 (1918), 142-144.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 128.
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 page 25, Prop. 5.3.2.
J. H. van Lint and R. M. Wilson, A Course in Combinatorics, Cambridge Univ. Press, 1992.

Seiichi Manyama, Table of n, a(n) for n = 0..388 (terms 0..100 from N. J. A. Sloane)
Federico Ardila, Matthias Beck, and Jodi McWhirter, The Arithmetic of Coxeter Permutahedra, arXiv:2004.02952 [math.CO], 2020.
M. D. Atkinson and R. Beals, Priority queues and permutations, SIAM J. Comput. 23 (1994), 1225-1230.
M. Beck, A. Berrizbeitia, M. Dairyko, C. Rodriguez, A. Ruiz, and S. Veeneman., Parking functions, Shi arrangements, and mixed graphs, Amer. Math. Monthly, 122 (2015), 660-673.
Norman L. Biggs, Chip-firing and the critical group of a graph, J. Algeb. Combin., 9 (1999), 25-45.
Norman L. Biggs, E. Keith Lloyd, and Robin J. Wilson, Graph Theory 1736-1936, Oxford, 1976, p. 51.
Richard P. Brent, M. L. Glasser, and Anthony J. Guttmann, A Conjectured Integer Sequence Arising From the Exponential Integral, arXiv:1812.00316 [math.NT], 2018.
Alexander Burstein and Louis W. Shapiro, Pseudo-involutions in the Riordan group, arXiv:2112.11595 [math.CO], 2021.
David Callan, A Combinatorial Derivation of the Number of Labeled Forests, J. Integer Seqs., Vol. 6, 2003.
Saverio Caminiti and Emanuele G. Fusco, On the Number of Labeled k-arch Graphs, Journal of Integer Sequences, Vol 10 (2007), Article 07.7.5
Peter Cameron's Blog, Cycles and trees, Posted Dec 17 2015.
Huantian Cao, AutoGF: An Automated System to Calculate Coefficients of Generating Functions, thesis, 2002. [Archived copy]
Huantian Cao, AutoGF: An Automated System to Calculate Coefficients of Generating Functions, thesis, 2002.
Huantian Cao, AutoGF: An Automated System to Calculate Coefficients of Generating Functions, thesis, 2002 [Local copy, with permission]
Huantian Cao, AutoGF: An Automated System to Calculate Coefficients of Generating Functions. [Broken link]
R. Castelo and A. Siebes, A characterization of moral transitive directed acyclic graph Markov models as labeled trees, Report CS-2000-44, Department of Computer Science, Univ. Utrecht.
R. Castelo and A. Siebes, A characterization of moral transitive acyclic directed graph Markov models as labeled trees, J. Statist. Planning Inference, 115(1):235-259, 2003.
A. Cayley, A theorem on trees, Quart. J. Pure and Applied Math., 23 (1889), 376-378.
Jacob W. Cooper, Adam Kabela, Daniel Král', and Théo Pierron, Hadwiger meets Cayley, arXiv:2005.05989 [math.CO], 2020.
S. Coulomb and M. Bauer, On vertex covers, matchings and random trees, arXiv:math/0407456 [math.CO], 2004.
FindStat - Combinatorial Statistic Finder, Parking functions
J. Gilbey and L. Kalikow, Parking functions, valet functions and priority queues, Discrete Math., 197 (1999), 351-375.
M. Golin and S. Zaks, Labeled trees and pairs of input-output permutations in priority queues, Theoret. Comput. Sci., 205 (1998), 99-114.
I. P. Goulden and S. Pepper, Labelled trees and factorizations of a cycle into transpositions, Discrete Math., 113 (1993), 263-268.
I. P. Goulden and A. Yong, Tree-like properties of cycle factorizations, J. Combin. Theory, A 98 (2002), 106-117.
Suresh Govindarajan, Notes on higher-dimensional partitions, arXiv preprint arXiv:1203.4419 [math.CO], 2012.
Vsevolod Gubarev, Rota-Baxter operators on a sum of fields, arXiv:1811.08219 [math.RA], 2018.
F. A. Haight, Overflow at a traffic light, Biometrika, 46 (1959), 420-424. (Annotated scanned copy)
F. A. Haight, Letter to N. J. A. Sloane, n.d.
A. M. Hamel, Priority queue sorting and labeled trees, Annals Combin., 7 (2003), 49-54.
Angela Hicks, Combinatorics of the Diagonal Harmonics, in Recent Trends in Algebraic Combinatorics, part of the Association for Women in Mathematics Series (2019) Vol 16. Springer, Cham, 159-188.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 78 [Dead link]
D. M. Jackson, Some Combinatorial Problems Associated with Products of Conjugacy Classes of the Symmetric Group, Journal of Combinatorial Theory, Series A, 49 363-369(1988).
S. Janson, D. E. Knuth, T. Łuczak and B. Pittel, The Birth of the Giant Component, Random Structures and Algorithms Vol. 4 (1993), 233-358.
C. Ji and J. Propp, Brussels Sprouts, Noncrossing Trees, and Parking Functions, arXiv preprint arXiv:1805.03608 [math.CO], 2018.
L. Kalikow, Symmetries in trees and parking functions, Discrete Math., 256 (2002), 719-741.
C. Lamathe, The Number of Labelled k-Arch Graphs, Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.1.
A. Laradji and A. Umar, On the number of nilpotents in the partial symmetric semigroup, Comm. Algebra 32 (2004), 3017-3023. From _Abdullahi Umar_, Aug 25 2008
C. J. Liu and Yutze Chow, On operator and formal sum methods for graph enumeration problems, SIAM J. Algebraic Discrete Methods, 5 (1984), no. 3, 384--406. MR0752043 (86d:05059). See Eq. (47). - From _N. J. A. Sloane_, Apr 09 2014
G. Martens, Polynomial Equations of Degree n, arXiv:math/0605183 [math.GM], 2006.
G. Martens, On Algebraic Solutions of Polynomial Equations of Degree n in one Variable, GH Consulting EPI-01-06 preprint, arXiv:math/0605183 [math.GM], 2006.
Mustafa A. A. Obaid, S. Khalid Nauman, Wafa S. Al Shammakh, Wafaa M. Fakieh, and Claus Michael Ringel, The number of complete exceptional sequences for a Dynkin algebra, arXiv preprint arXiv:1307.7573 [math.RT], 2013.
J. Pitman, Coalescent Random Forests, J. Combin. Theory, A85 (1999), 165-193.
J.-B. Priez and A. Virmaux, Non-commutative Frobenius characteristic of generalized parking functions: Application to enumeration, arXiv preprint arXiv:1411.4161 [math.CO], 2014.
S. Ramanujan, Question 738, J. Ind. Math. Soc.
J. Riordan, Forests of labeled trees, J. Combin. Theory, 5 (1968), 90-103. See Table 1.
M. P. Schützenberger, On an Enumeration Problem, Journal of Combinatorial Theory 4, 219-221 (1968). [A 1-1 correspondence between maps under permutations and acyclic maps.]
Alok Shukla, A short proof of Cayley's tree formula, Amer. Math. Monthly, 125 (2018), 65-68.
Stefano Spezia, A determinantal formula for the number of trees on n labeled nodes, 2023.
R. P. Stanley, Recent Progress in Algebraic Combinatorics, Bull. Amer. Math. Soc., 40 (2003), 55-68.
Dennis Walsh, Notes on acyclic functions and their directed graphs [Archived copy]
Eric Weisstein's World of Mathematics, Complete Graph, Labeled Tree, and Spanning Tree
D. Zeilberger, The n^(n-2)-th Proof Of The Formula For The Number Of Labeled Trees
D. Zeilberger, The n^(n-2)-th Proof Of The Formula For The Number Of Labeled Trees [Local copy]
D. Zeilberger, Yet Another Proof For The Enumeration Of Labeled Trees
D. Zeilberger, Yet Another Proof For The Enumeration Of Labeled Trees [Local copy]
D. Zvonkine, An algebra of power series arising in the intersection theory of moduli spaces of curves and in the enumeration of ramified coverings of the sphere, arXiv:math/0403092 [math.AG], 2004.
D. Zvonkine, Home Page [Dead link]
Index entries for sequences related to trees
Index entries for "core" sequences

Cf. A000169, A000254, A000312, A007778, A007830, A008785-A008791, A052750, A081048, A083483, A097170, A239910.
a(n) = A033842(n-1, 0) (first column of triangle).
a(n) = A058127(n-1, n) (right edge of triangle).
Cf. A000272 (labeled trees), A036361 (labeled 2-trees), A036362 (labeled 3-trees), A036506 (labeled 4-trees), A000055 (unlabeled trees), A054581 (unlabeled 2-trees).
Column m=1 of A105599. - Alois P. Heinz, Apr 10 2014

a000272 0 = 1; a000272 1 = 1
a000272 n = n ^ (n - 2)  -- Reinhard Zumkeller, Jul 07 2013

[ n^(n-2) : n in [1..10]]; // Sergei Haller (sergei(AT)sergei-haller.de), Dec 21 2006

A000272 := n -> ifelse(n=0, 1, n^(n-2)): seq(A000272(n), n = 0..20); # Peter Luschny, Jun 12 2022

<< DiscreteMath`Combinatorica` Table[NumberOfSpanningTrees[CompleteGraph[n]], {n, 1, 20}] (* Artur Jasinski, Dec 06 2007 *)
Join[{1},Table[n^(n-2),{n,20}]] (* Harvey P. Dale, Nov 28 2012 *)
a[ n_] := If[ n < 1, Boole[n == 0], n^(n - 2)]; (* Michael Somos, May 25 2014 *)
a[ n_] := If[ n < 0, 0, n! SeriesCoefficient[ 1 - LambertW[-x] - LambertW[-x]^2 / 2, {x, 0, n}]]; (* Michael Somos, May 25 2014 *)
a[ n_] := If[ n < 1, Boole[n == 0], With[ {m = n - 1}, m! SeriesCoefficient[ Exp[ -LambertW[-x]], {x, 0, m}]]]; (* Michael Somos, May 25 2014 *)
a[ n_] := If[ n < 2, Boole[n >= 0], With[ {m = n - 1}, m! SeriesCoefficient[ InverseSeries[ Series[ Log[1 + x] / (1 + x), {x, 0, m}]], m]]]; (* Michael Somos, May 25 2014 *)
a[ n_] := If[ n < 1, Boole[n == 0], With[ {m = n - 1}, m! SeriesCoefficient[ Nest[ 1 + Integrate[ #^2 / (1 - x #), x] &, 1 + O[x], m], {x, 0, m}]]]; (* Michael Somos, May 25 2014 *)

A000272[n]:=if n=0 then 1 else n^(n-2)$
makelist(A000272[n],n,0,30); /* Martin Ettl, Oct 29 2012 */

{a(n) = if( n<1, n==0, n^(n-2))}; /* Michael Somos, Feb 16 2002 */

{a(n) = my(A); if( n<1, n==0, n--; A = 1 + O(x); for(k=1, n, A = 1 + intformal( A^2 / (1 - x * A))); n! * polcoeff( A, n))}; /* Michael Somos, May 25 2014 */

/* GP Function for Determinant of Hermitian (square symmetric) matrix for univariate polynomial of degree n by Gerry Martens: */
Hn(n=2)= {local(H=matrix(n-1,n-1),i,j); for(i=1,n-1, for(j=1,i, H[i,j]=(n*i^3-3*n*(n+1)*i^2/2+n*(3*n+1)*i/2+(n^4-n^2)/2)/6-(i^2-(2*n+1)*i+n*(n+1))*(j-1)*j/4; H[j,i]=H[i,j]; ); ); print("a(",n,")=matdet(",H,")"); print("Determinant H =",matdet(H)); return(matdet(H)); } { print(Hn(7)); } /* Gerry Martens, May 04 2007 */

def A000272(n): return 1 if n <= 1 else n**(n-2) # Chai Wah Wu, Feb 03 2022

E.g.f.: 1 + T - (1/2)*T^2; where T=T(x) is Euler's tree function (see A000169, also A001858). - Len Smiley, Nov 19 2001
Number of labeled k-trees on n nodes is binomial(n, k) * (k*(n-k)+1)^(n-k-2).
E.g.f. for b(n)=a(n+2): ((W(-x)/x)^2)/(1+W(-x)), where W is Lambert's function (principal branch). [Equals d/dx (W(-x)/(-x)). - Wolfdieter Lang, Oct 25 2022]
Determinant of the symmetric matrix H generated for a polynomial of degree n by: for(i=1,n-1, for(j=1,i, H[i,j]=(n*i^3-3*n*(n+1)*i^2/2+n*(3*n+1)*i/2+(n^4-n^2)/2)/6-(i^2-(2*n+1)*i+n*(n+1))*(j-1)*j/4; H[j,i]=H[i,j]; ); );. - Gerry Martens, May 04 2007
a(n+1) = Sum_{i=1..n} i * n^(n-1-i) * binomial(n, i). - Yong Kong (ykong(AT)curagen.com), Dec 28 2000
For n >= 1, a(n+1) = Sum_{i=1..n} n^(n-i)*binomial(n-1,i-1). - Geoffrey Critzer, Jul 20 2009
E.g.f. for b(n)=a(n+1): exp(-W(-x)), where W is Lambert's function satisfying W(x)*exp(W(x))=x. Proof is contained in link "Notes on acyclic functions..." - Dennis P. Walsh, Mar 02 2011
From Sergei N. Gladkovskii, Sep 18 2012: (Start)
E.g.f.: 1 + x + x^2/(U(0) - x) where U(k) = x*(k+1)*(k+2)^k + (k+1)^k*(k+2) - x*(k+2)^2*(k+3)*((k+1)*(k+3))^k/U(k+1); (continued fraction).
G.f.: 1 + x + x^2/(U(0)-x) where U(k) = x*(k+1)*(k+2)^k + (k+1)^k - x*(k+2)*(k+3)*((k+1)*(k+3))^k/E(k+1); (continued fraction). (End)
Related to A000254 by Sum_{n >= 1} a(n+1)*x^n/n! = series reversion( 1/(1 + x)*log(1 + x) ) = series reversion(x - 3*x^2/2! + 11*x^3/3! - 50*x^4/4! + ...). Cf. A052750. - Peter Bala, Jun 15 2016
For n >= 3 and 2 <= k <= n-1, the number of trees on n vertices with exactly k leaves is binomial(n,k)*S(n-2,n-k)(n-k)! where S(a,b) is the Stirling number of the second kind. Therefore a(n) = Sum_{k=2..n-1} binomial(n,k)*S(n-2,n-k)(n-k)! for n >= 3. - Jonathan Noel, May 05 2017

A000088 Number of simple graphs on n unlabeled nodes.

Original entry on oeis.org

1, 1, 2, 4, 11, 34, 156, 1044, 12346, 274668, 12005168, 1018997864, 165091172592, 50502031367952, 29054155657235488, 31426485969804308768, 64001015704527557894928, 245935864153532932683719776, 1787577725145611700547878190848, 24637809253125004524383007491432768

Offset: 0

N. J. A. Sloane

Euler transform of the sequence A001349.

Also, number of equivalence classes of sign patterns of totally nonzero symmetric n X n matrices.

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 430.
J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 519.
F. Harary, Graph Theory. Addison-Wesley, Reading, MA, 1969, p. 214.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 240.
Thomas Boyer-Kassem, Conor Mayo-Wilson, Scientific Collaboration and Collective Knowledge: New Essays, New York, Oxford University Press, 2018, see page 47.
M. Kauers and P. Paule, The Concrete Tetrahedron, Springer 2011, p. 54.
Lupanov, O. B. Asymptotic estimates of the number of graphs with n edges. (Russian) Dokl. Akad. Nauk SSSR 126 1959 498--500. MR0109796 (22 #681).
M. D. McIlroy, Calculation of numbers of structures of relations on finite sets, Massachusetts Institute of Technology, Research Laboratory of Electronics, Quarterly Progress Reports, No. 17, Sep. 15, 1955, pp. 14-22.
R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.
R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1976.
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).

Keith M. Briggs, Table of n, a(n) for n = 0..87 (From link below)
R. Absil and H. Mélot, Digenes: genetic algorithms to discover conjectures about directed and undirected graphs, arXiv preprint arXiv:1304.7993 [cs.DM], 2013.
Natalie Arkus, Vinothan N. Manoharan and Michael P. Brenner. Deriving Finite Sphere Packings, arXiv:1011.5412 [cond-mat.soft], Nov 24, 2010. (See Table 1.)
Leonid Bedratyuk and Anna Bedratyuk, A new formula for the generating function of the numbers of simple graphs, Comptes rendus de l'Académie Bulgare des Sciences, Tome 69, No 3, 2016, p.259-268.
Benjamin A. Blumer, Michael S. Underwood and David L. Feder, Single-qubit unitary gates by graph scattering, arXiv:1111.5032 [quant-ph], 2011.
Keith M. Briggs, Combinatorial Graph Theory [Gives first 140 terms]
Gunnar Brinkmann, Kris Coolsaet, Jan Goedgebeur and Hadrien Melot, House of Graphs: a database of interesting graphs, arXiv preprint arXiv:1204.3549 [math.CO], 2012.
P. Butler and R. W. Robinson, On the computer calculation of the number of nonseparable graphs, pp. 191 - 208 of Proc. Second Caribbean Conference Combinatorics and Computing (Bridgetown, 1977). Ed. R. C. Read and C. C. Cadogan. University of the West Indies, Cave Hill Campus, Barbados, 1977. vii+223 pp. [Annotated scanned copy]
P. J. Cameron, Some sequences of integers, Discrete Math., 75 (1989), 89-102.
P. J. Cameron, Some sequences of integers, in "Graph Theory and Combinatorics 1988", ed. B. Bollobas, Annals of Discrete Math., 43 (1989), 89-102.
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
P. J. Cameron and C. R. Johnson, The number of equivalence patterns of symmetric sign patterns, Discr. Math., 306 (2006), 3074-3077.
Gi-Sang Cheon, Jinha Kim, Minki Kim and Sergey Kitaev, On k-11-representable graphs, arXiv:1803.01055 [math.CO], 2018.
CombOS - Combinatorial Object Server, Generate graphs
Karen M. Daehli, Sarah A Obead, Hsuan-Yin Lin, and Eirik Rosnes, Improved Capacity Outer Bound for Private Quadratic Monomial Computation, arXiv:2401.06125 [cs.IR], 2024.
R. L. Davis, The number of structures of finite relations, Proc. Amer. Math. Soc. 4 (1953), 486-495.
J. P. Dolch, Names of Hamiltonian graphs, Proc. 4th S-E Conf. Combin., Graph Theory, Computing, Congress. Numer. 8 (1973), 259-271. (Annotated scanned copy of 3 pages)
Peter Dukes, Notes for Math 422: Enumeration and Ramsey Theory, University of Victoria BC Canada (2019). See page 36.
D. S. Dummit, E. P. Dummit and H. Kisilevsky, Characterizations of quadratic, cubic, and quartic residue matrices, arXiv preprint arXiv:1512.06480 [math.NT], 2015.
Steven R. Finch, Mathematical Constants II, Encyclopedia of Mathematics and Its Applications, Cambridge University Press, Cambridge, 2018.
Mareike Fischer, Michelle Galla, Lina Herbst, Yangjing Long, and Kristina Wicke, Non-binary treebased unrooted phylogenetic networks and their relations to binary and rooted ones, arXiv:1810.06853 [q-bio.PE], 2018.
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 105.
E. Friedman, Illustration of small graphs
Harald Fripertinger, Graphs
Scott Garrabrant and Igor Pak, Pattern Avoidance is Not P-Recursive, preprint, 2015.
Lee M. Gunderson and Gecia Bravo-Hermsdorff, Introducing Graph Cumulants: What is the Variance of Your Social Network?, arXiv:2002.03959 [math.ST], 2020.
P. Hegarty, On the notion of balance in social network analysis, arXiv preprint arXiv:1212.4303 [cs.SI], 2012.
S. Hougardy, Home Page
S. Hougardy, Classes of perfect graphs, Discr. Math. 306 (2006), 2529-2571.
Richard Hua and Michael J. Dinneen, Improved QUBO Formulation of the Graph Isomorphism Problem, SN Computer Science (2020) Vol. 1, No. 19.
A. Itzhakov and M. Codish, Breaking Symmetries in Graph Search with Canonizing Sets, arXiv preprint arXiv:1511.08205 [cs.AI], 2015-2016.
Dan-Marian Joiţa and Lorentz Jäntschi, Extending the Characteristic Polynomial for Characterization of C_20 Fullerene Congeners, Mathematics (2017), 5(4), 84.
Vladeta Jovovic, Formulae for the number T(n,k) of n-multigraphs on k nodes
Maksim Karev, The space of framed chord diagrams as a Hopf module, arXiv preprint arXiv:1404.0026 [math.GT], 2014.
J. M. Larson, Cheating Because They Can: Social Networks and Norm Violators, 2014. See Footnote 11.
Steffen Lauritzen, Alessandro Rinaldo and Kayvan Sadeghi, On Exchangeability in Network Models, arXiv:1709.03885 [math.ST], 2017.
O. B. Lupanov, On asymptotic estimates of the number of graphs and networks with n edges, Problems of Cybernetics [in Russian], Moscow 4 (1960): 5-21.
M. D. McIlroy, Calculation of numbers of structures of relations on finite sets, Massachusetts Institute of Technology, Research Laboratory of Electronics, Quarterly Progress Reports, No. 17, Sep. 15, 1955, pp. 14-22. [Annotated scanned copy]
B. D. McKay, Maple program (used to redirect to here).
B. D. McKay, Maple program [Cached copy, with permission]
B. D. McKay, Simple graphs
A. Milicevic and N. Trinajstic, Combinatorial Enumeration in Chemistry, Chem. Modell., Vol. 4, (2006), pp. 405-469.
Angelo Monti and Blerina Sinaimeri, Effects of graph operations on star pairwise compatibility graphs, arXiv:2410.16023 [cs.DM], 2024. See p. 16.
W. Oberschelp, Kombinatorische Anzahlbestimmungen in Relationen, Math. Ann., 174 (1967), 53-78.
M. Petkovsek and T. Pisanski, Counting disconnected structures: chemical trees, fullerenes, I-graphs and others, Croatica Chem. Acta, 78 (2005), 563-567.
G. Pfeiffer, Counting Transitive Relations, Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.2.
E. M. Palmer, Letter to N. J. A. Sloane, no date
Marko Riedel, Nonisomorphic graphs.
Marko Riedel, Compact Maple code for cycle index, sequence values and ordinary generating function by the number of edges.
R. W. Robinson, Enumeration of non-separable graphs, J. Combin. Theory 9 (1970), 327-356.
Sage, Common Graphs (Graph Generators)
S. S. Skiena, Generating graphs
N. J. A. Sloane, Illustration of initial terms
Quico Spaen, Christopher Thraves Caro and Mark Velednitsky, The Dimension of Valid Distance Drawings of Signed Graphs, Discrete & Computational Geometry (2019), 1-11.
P. R. Stein, On the number of graphical partitions, pp. 671-684 of Proc. 9th S-E Conf. Combinatorics, Graph Theory, Computing, Congr. Numer. 21 (1978). [Annotated scanned copy]
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Overview of the 17 Parts (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 1
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 2
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 3
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 4
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 5
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 6
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 7
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 8
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 9
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 10
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 11
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 12
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 13
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 14
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 15
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 16
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 17
J. M. Tangen and N. J. A. Sloane, Correspondence, 1976-1976
James Turner and William H. Kautz, A survey of progress in graph theory in the Soviet Union SIAM Rev. 12 1970 suppl. iv+68 pp. MR0268074 (42 #2973). See p. 18.
S. Uijlen and B. Westerbaan, A Kochen-Specker system has at least 22 vectors, arXiv preprint arXiv:1412.8544 [cs.DM], 2014.
Mark Velednitsky, New Algorithms for Three Combinatorial Optimization Problems on Graphs, Ph. D. Dissertation, University of California, Berkeley (2020).
Eric Weisstein's World of Mathematics, Simple Graph
Eric Weisstein's World of Mathematics, Connected Graph
Eric Weisstein's World of Mathematics, Degree Sequence
E. M. Wright, The number of graphs on many unlabelled nodes, Mathematische Annalen, December 1969, Volume 183, Issue 4, 250-253
E. M. Wright, The number of unlabelled graphs with many nodes and edges Bull. Amer. Math. Soc. Volume 78, Number 6 (1972), 1032-1034.
Chris Ying, Enumerating Unique Computational Graphs via an Iterative Graph Invariant, arXiv:1902.06192 [cs.DM], 2019.
Index entries for "core" sequences

Partial sums of A002494.
Cf. A000666 (graphs with loops), A001349 (connected graphs), A002218, A006290, A003083.
Column k=1 of A063841.
Column k=2 of A309858.
Row sums of A008406.
Cf. also A000055, A000664.
Partial sums are A006897.

# To produce all graphs on 4 nodes, for example:
with(GraphTheory):
L:=[NonIsomorphicGraphs](4,output=graphs,outputform=adjacency): # N. J. A. Sloane, Oct 07 2013
seq(GraphTheory[NonIsomorphicGraphs](n,output=count),n=1..10); # Juergen Will, Jan 02 2018
# alternative Maple program:
b:= proc(n, i, l) `if`(n=0 or i=1, 1/n!*2^((p-> add(ceil((p[j]-1)/2)
      +add(igcd(p[k], p[j]), k=1..j-1), j=1..nops(p)))([l[], 1$n])),
       add(b(n-i*j, i-1, [l[], i$j])/j!/i^j, j=0..n/i))
    end:
a:= n-> b(n$2, []):
seq(a(n), n=0..20);  # Alois P. Heinz, Aug 14 2019

Needs["Combinatorica`"]
Table[NumberOfGraphs[n], {n, 0, 19}] (* Geoffrey Critzer, Mar 12 2011 *)
permcount[v_] := Module[{m = 1, s = 0, k = 0, t}, For[i = 1, i <= Length[v], i++, t = v[[i]]; k = If[i > 1 && t == v[[i - 1]], k + 1, 1]; m *= t*k; s += t]; s!/m];
edges[v_] := Sum[GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i - 1}] + Total[Quotient[v, 2]];
a[n_] := Module[{s = 0}, Do[s += permcount[p]*2^edges[p], {p, IntegerPartitions[n]}]; s/n!];
Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Jul 05 2018, after Andrew Howroyd *)
b[n_, i_, l_] := If[n==0 || i==1, 1/n!*2^(Function[p, Sum[Ceiling[(p[[j]]-1 )/2]+Sum[GCD[p[[k]], p[[j]]], {k, 1, j-1}], {j, 1, Length[p]}]][Join[l, Table[1, {n}]]]), Sum[b[n-i*j, i-1, Join[l, Table[i, {j}]]]/j!/i^j, {j, 0, n/i}]];
a[n_] := b[n, n, {}];
a /@ Range[0, 20] (* Jean-François Alcover, Dec 03 2019, after Alois P. Heinz *)

permcount(v) = {my(m=1,s=0,k=0,t); for(i=1,#v,t=v[i]; k=if(i>1&&t==v[i-1],k+1,1); m*=t*k;s+=t); s!/m}
edges(v) = {sum(i=2, #v, sum(j=1, i-1, gcd(v[i],v[j]))) + sum(i=1, #v, v[i]\2)}
a(n) = {my(s=0); forpart(p=n, s+=permcount(p)*2^edges(p)); s/n!} \\ Andrew Howroyd, Oct 22 2017

from itertools import combinations
from math import prod, factorial, gcd
from fractions import Fraction
from sympy.utilities.iterables import partitions
def A000088(n): return int(sum(Fraction(1<>1)*r+(q*r*(r-1)>>1) for q, r in p.items()),prod(q**r*factorial(r) for q, r in p.items())) for p in partitions(n))) # Chai Wah Wu, Jul 02 2024

def a(n):
    return len(list(graphs(n)))
# Ralf Stephan, May 30 2014

a(n) = 2^binomial(n, 2)/n!*(1+(n^2-n)/2^(n-1)+8*n!/(n-4)!*(3*n-7)*(3*n-9)/2^(2*n)+O(n^5/2^(5*n/2))) (see Harary, Palmer reference). - Vladeta Jovovic and Benoit Cloitre, Feb 01 2003
a(n) = 2^binomial(n, 2)/n!*[1+2*n$2*2^{-n}+8/3*n$3*(3n-7)*2^{-2n}+64/3*n$4*(4n^2-34n+75)*2^{-3n}+O(n^8*2^{-4*n})] where n$k is the falling factorial: n$k = n(n-1)(n-2)...(n-k+1). - Keith Briggs, Oct 24 2005
From David Pasino (davepasino(AT)yahoo.com), Jan 31 2009: (Start)
a(n) = a(n, 2), where a(n, t) is the number of t-uniform hypergraphs on n unlabeled nodes (cf. A000665 for t = 3 and A051240 for t = 4).
a(n, t) = Sum_{c : 1*c_1+2*c_2+...+n*c_n=n} per(c)*2^f(c), where:
..per(c) = 1/(Product_{i=1..n} c_i!*i^c_i);
..f(c) = (1/ord(c)) * Sum_{r=1..ord(c)} Sum_{x : 1*x_1+2*x_2+...+t*x_t=t} Product_{k=1..t} binomial(y(r, k; c), x_k);
..ord(c) = lcm{i : c_i>0};
..y(r, k; c) = Sum_{s|r : gcd(k, r/s)=1} s*c_(k*s) is the number of k-cycles of the r-th power of a permutation of type c. (End)
a(n) ~ 2^binomial(n,2)/n! [see Flajolet and Sedgewick p. 106, Gross and Yellen, p. 519, etc.]. - N. J. A. Sloane, Nov 11 2013
For asymptotics see also Lupanov 1959, 1960, also Turner and Kautz, p. 18. - N. J. A. Sloane, Apr 08 2014
a(n) = G(1) where G(z) = (1/n!) Sum_g det(I-g z^2)/det(I-g z) and g runs through the natural matrix n X n representation of the pair group A^2_n (for A^2_n see F. Harary and E. M. Palmer, Graphical Enumeration, page 83). - Leonid Bedratyuk, May 02 2015
From Keith Briggs, Jun 24 2016: (Start)
a(n) = 2^binomial(n,2)/n!*(
   1+
   2^(  -n +  1)*n$2+
   2^(-2*n +  3)*n$3*(n-7/3)+
   2^(-3*n +  6)*n$4*(4*n^2/3 - 34*n/3 + 25) +
   2^(-4*n + 10)*n$5*(8*n^3/3 - 142*n^2/3 + 2528*n/9 - 24914/45) +
   2^(-5*n + 15)*n$6*(128*n^4/15 - 2296*n^3/9 + 25604*n^2/9 - 630554*n/45 + 25704) +
   2^(-6*n + 21)*n$7*(2048*n^5/45 - 18416*n^4/9 + 329288*n^3/9 - 131680816*n^2/405 + 193822388*n/135 - 7143499196/2835) + ...),
where n$k is the falling factorial: n$k = n(n-1)(n-2)...(n-k+1), using the method of Wright 1969.
(End)
a(n) = 1/n*Sum_{k=1..n} a(n-k)*A003083(k). - Andrey Zabolotskiy, Aug 11 2020

Harary gives an incorrect value for a(8); compare A007149

A001349 Number of simple connected graphs on n unlabeled nodes.

Original entry on oeis.org

1, 1, 1, 2, 6, 21, 112, 853, 11117, 261080, 11716571, 1006700565, 164059830476, 50335907869219, 29003487462848061, 31397381142761241960, 63969560113225176176277, 245871831682084026519528568, 1787331725248899088890200576580, 24636021429399867655322650759681644

Offset: 0

N. J. A. Sloane

The singleton graph K_1 is considered connected even though it is conventionally taken to have vertex connectivity 0. - Eric W. Weisstein, Jul 21 2020

Inverse Euler transform of A000088 but with a(0) omitted so that Sum_{k>=0} A000088(n) * x^n = Product_{k>0} (1 - x^k)^-a(k). It is debatable if there is a connected graph with 0 nodes and so a(0)=0 or better start from a(1)=1. - Michael Somos, Jun 01 2013. [As Harary once remarked in a famous paper ("Is the null-graph a pointless concept?"), the empty graph has every property, which is why a(0)=1. - N. J. A. Sloane, Apr 08 2014]

			G.f. = 1 + x + x^2 + 2*x^3 + 6*x^4 + 21*x^5 + 112*x^6 + 853*x^7 + ....

P. Butler and R. W. Robinson, On the computer calculation of the number of nonseparable graphs, pp. 191 - 208 of Proc. Second Caribbean Conference Combinatorics and Computing (Bridgetown, 1977). Ed. R. C. Read and C. C. Cadogan. University of the West Indies, Cave Hill Campus, Barbados, 1977. vii+223 pp.
F. Harary and R. C. Read, Is the null-graph a pointless concept?, pp. 37-44 of Graphs and Combinatorics (Washington, Jun 1973), Ed. by R. A. Bari and F. Harary. Lect. Notes Math., Vol. 406. Springer-Verlag, 1974.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, page 48, c(x). Also page 242.
Lupanov, O. B. Asymptotic estimates of the number of graphs with n edges. (Russian) Dokl. Akad. Nauk SSSR 126 1959 498--500. MR0109796 (22 #681).
Lupanov, O. B. "On asymptotic estimates of the number of graphs and networks with n edges." Problems of Cybernetics [in Russian], Moscow 4 (1960): 5-21.
R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.
R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1978.
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).
Robin J. Wilson, Introduction to Graph Theory, Academic Press, 1972. (But see A126060!)

N. J. A. Sloane, Table of n, a(n) for n = 0..75 [Computed using Keith Briggs's values for A000088]
Michal Adamaszek, Small flag complexes with torsion, arXiv:1208.3892 [math.CO], 2012.
C. O. Aguilar and B. Gharesifard, Graph Controllability Classes for the Laplacian Leader-Follower Dynamics, 2014. See Table 1.
Jonathan Baker, Kevin N. Vander Meulen, and Adam Van Tuyl, Shedding vertices of vertex decomposable well-covered graphs, Discrete Mathematics (2018) Vol. 341, Issue 12, 3355-3369. Also arXiv:1606.04447 [math.NT], 2016.
Johannes Bausch and Felix Leditzky, Error Thresholds for Arbitrary Pauli Noise, arXiv:1910.00471 [quant-ph], 2019.
Gunnar Brinkmann, Kris Coolsaet, Jan Goedgebeur and Hadrien Melot, House of Graphs: a database of interesting graphs, arXiv:1204.3549 [math.CO], 2012.
P. Butler and R. W. Robinson, On the computer calculation of the number of nonseparable graphs, pp. 191 - 208 of Proc. Second Caribbean Conference Combinatorics and Computing (Bridgetown, 1977). Ed. R. C. Read and C. C. Cadogan. University of the West Indies, Cave Hill Campus, Barbados, 1977. vii+223 pp. [Annotated scanned copy]
P. J. Cameron, Some sequences of integers, Discrete Math., 75 (1989), 89-102.
P. J. Cameron, Some sequences of integers, in "Graph Theory and Combinatorics 1988", ed. B. Bollobas, Annals of Discrete Math., 43 (1989), 89-102.
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
CombOS - Combinatorial Object Server, Generate graphs
Matt DeVos, Adam Dyck, Jonathan Jedwab, and Samuel Simon, Which graphs occur as gamma-graphs?, arXiv:1810.01583 [math.CO], 2018.
J. P. Dolch, Names of Hamiltonian graphs, Proc. 4th S-E Conf. Combin., Graph Theory, Computing, Congress. Numer. 8 (1973), 259-271. (Annotated scanned copy of 3 pages)
Steven R. Finch, Mathematical Constants II, Encyclopedia of Mathematics and Its Applications, Cambridge University Press, Cambridge, 2018.
E. Friedman, Illustration of small graphs
F. Harary, The number of linear, directed, rooted, and connected graphs, Trans. Am. Math. Soc. 78 (1955) 445-463.
Yoshiaki Horiike and Yuki Kawaguchi, A comprehensive exploration of interaction networks reveals a connection between entanglement and network structure, arXiv:2505.11466 [quant-ph], 2025. See p. 9.
Avraham Itzhakov and Michael Codish, Incremental Symmetry Breaking Constraints for Graph Search Problems, Ben-Gurion University of the Negev (Beer-Sheva, Israel, 2019).
Markus Kirchweger and Stefan Szeider, SAT Modulo Symmetries for Graph Generation and Enumeration, ACM Trans. Comput. Logic (2024). See p. 27.
X. Li, D. S. Stones, H. Wang, H. Deng, X. Liu and G. Wang, NetMODE: Network Motif Detection without Nauty, PLoS ONE 7(12): e50093. - From _N. J. A. Sloane_, Feb 02 2013
Steffen Lauritzen, Alessandro Rinaldo, and Kayvan Sadeghi, On Exchangeability in Network Models, arXiv:1709.03885 [math.ST], 2017.
Richard J. Mathar, Counting Connected Graphs without Overlapping Cycles, arXiv:1808.06264 [math.CO], 2018.
B. D. McKay, Simple Graphs
A. Milicevic and N. Trinajstic, Combinatorial Enumeration in Chemistry, Chem. Modell., Vol. 4, (2006), pp. 405-469.
Marius Möller, Laura Hindersin, and Arne Traulsen, Exploring and mapping the universe of evolutionary graphs, arXiv:1810.12807 [q-bio.PE], 2018.
Marius Möller, Laura Hindersin, and Arne Traulsen, Exploring and mapping the universe of evolutionary graphs identifies structural properties affecting fixation probability and time, Communications Biology 2 (2019), Article number: 137.
L. Naughton and G. Pfeiffer, Integer Sequences Realized by the Subgroup Pattern of the Symmetric Group, J. Int. Seq. 16 (2013) #13.5.8
M. Petkovsek and T. Pisanski, Counting disconnected structures: chemical trees, fullerenes, I-graphs and others, Croatica Chem. Acta, 78 (2005), 563-567.
R. W. Robinson, Enumeration of non-separable graphs, J. Combin. Theory 9 (1970), 327-356.
Gordon Royle, Small graphs
Yoav Spector and Moshe Schwartz, Study of potential Hamiltonians for quantum graphity, arXiv:1808.05632 [cond-mat.stat-mech], 2018.
M. L. Stein and P. R. Stein, Enumeration of Linear Graphs and Connected Linear Graphs up to p = 18 Points. Report LA-3775, Los Alamos Scientific Laboratory of the University of California, Los Alamos, NM, Oct 1967.
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.)
D. Stolee, Isomorph-free generation of 2-connected graphs with applications, arXiv:1104.5261 [math.CO], 2011.
Rodrigo Stange Tessinari, Marcia Helena Moreira Paiva, Maxwell E. Monteiro, Marcelo E. V. Segatto, Anilton Garcia, George T. Kanellos, Reza Nejabati, and Dimitra Simeonidou, On the Impact of the Physical Topology on the Optical Network Performance, IEEE British and Irish Conference on Optics and Photonics (BICOP 2018), London.
James Turner and William H. Kautz, A survey of progress in graph theory in the Soviet Union SIAM Rev. 12 1970 suppl. iv+68 pp. MR0268074 (42 #2973). See p. 18. - _N. J. A. Sloane_, Apr 08 2014
Eric Weisstein's World of Mathematics, Connected Graph.
Eric Weisstein's World of Mathematics, k-Connected Graph
Myung-Gon Yoon, Peter Rowlinson, Dragos Cvetkovic, and Zoran Stanic, Controllability of multi-agent dynamical systems with a broadcasting control signal, Asian J. Control 16 (4) (2014) 1066-1072, Table 1.
Index entries for "core" sequences

Cf. A000088, A002218, A006290, A000719, A201922 (Multiset transform).

Row sums of A054924.

# To produce all connected graphs on 4 nodes, for example (from N. J. A. Sloane, Oct 07 2013):
with(GraphTheory):
L:=[NonIsomorphicGraphs](4,output=graphs,outputform=adjacency, restrictto=connected):

<<"Combinatorica`"; max = 19; A000088 = Table[ NumberOfGraphs[n], {n, 0, max}]; f[x_] = 1 - Product[ 1/(1 - x^k)^a[k], {k, 1, max}]; a[0] = a[1] = a[2] = 1; coes = CoefficientList[ Series[ f[x], {x, 0, max}], x]; sol = First[ Solve[ Thread[ Rest[ coes + A000088 ] == 0]]]; Table[ a[n], {n, 0, max}] /. sol (* Jean-François Alcover, Nov 24 2011 *)
terms = 20;
mob[m_, n_] := If[Mod[m, n] == 0, MoebiusMu[m/n], 0];
EULERi[b_] := Module[{a, c, i, d}, c = {}; For[i = 1, i <= Length[b], i++, c = Append[c, i*b[[i]] - Sum[c[[d]]*b[[i - d]], {d, 1, i - 1}]]]; a = {}; For[i = 1, i <= Length[b], i++, a = Append[a, (1/i)*Sum[mob[i, d]*c[[d]], {d, 1, i}]]]; Return[a]];
permcount[v_] := Module[{m = 1, s = 0, k = 0, t}, For[i = 1, i <= Length[v], i++, t = v[[i]]; k = If[i > 1 && t == v[[i - 1]], k + 1, 1]; m *= t*k; s += t]; s!/m];
edges[v_] := Sum[GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i - 1}] + Total[Quotient[v, 2]];
a88[n_] := Module[{s = 0}, Do[s += permcount[p]*2^edges[p], {p, IntegerPartitions[n]}]; s/n!];
Join[{1}, EULERi[Array[a88, terms]]] (* Jean-François Alcover, Jul 28 2018, after Andrew Howroyd *)

from functools import lru_cache
from itertools import combinations
from fractions import Fraction
from math import prod, gcd, factorial
from sympy import mobius, divisors
from sympy.utilities.iterables import partitions
def A001349(n):
    if n == 0: return 1
    @lru_cache(maxsize=None)
    def b(n): return int(sum(Fraction(1<>1)*r+(q*r*(r-1)>>1) for q, r in p.items()),prod(q**r*factorial(r) for q, r in p.items())) for p in partitions(n)))
    @lru_cache(maxsize=None)
    def c(n): return n*b(n)-sum(c(k)*b(n-k) for k in range(1,n))
    return sum(mobius(n//d)*c(d) for d in divisors(n,generator=True))//n # Chai Wah Wu, Jul 02-03 2024

property=lambda G: G.is_connected()
def a(n):
    return len([1 for G in graphs(n) if property(G)])
# Ralf Stephan, May 30 2014

For asymptotics see Lupanov 1959, 1960, also Turner and Kautz, p. 18. - N. J. A. Sloane, Apr 08 2014

More terms from Ronald C. Read

cp's OEIS Frontend

A328779 a(n) is the number of unlabeled unrooted trees (as in A000055) on n nodes with one designated node (exclusive) or one designated edge.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A006802 Log of e.g.f. for trees A000055(n-1).

Views

Author

Keywords

Links

Crossrefs

A084356 A000055(n+2)-A023359(n).

Views

Author

Keywords

Crossrefs

A085768 Smallest m such that n divides A000055(m).

Views

Author

Keywords

Extensions

A123465 Duplicate of A000055.

Views

Author

Keywords

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

A000169 Number of labeled rooted trees with n nodes: n^(n-1).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

MuPAD

PARI

Python

Python

Formula

A000272 Number of trees on n labeled nodes: n^(n-2) with a(0)=1.

Views

Author

Keywords

Comments

Examples

References

Links