The OEIS is supported by the many generous donors to the OEIS Foundation.


(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000169 Number of labeled rooted trees with n nodes: n^(n-1).
(Formerly M1946 N0771)
1, 2, 9, 64, 625, 7776, 117649, 2097152, 43046721, 1000000000, 25937424601, 743008370688, 23298085122481, 793714773254144, 29192926025390625, 1152921504606846976, 48661191875666868481, 2185911559738696531968, 104127350297911241532841, 5242880000000000000000000 (list; graph; refs; listen; history; text; internal format)



Also the number of connected transitive subtree acyclic digraphs on n vertices. - Robert Castelo (rcastelo(AT)imim.es), Jan 06 2001

For any given integer k, a(n) is also is 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

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 number of 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 Zi-Whei Sun, Petrov link. - Hugo Pfoertner, Sep 19 2021


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.


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, Exponential equation.

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 67.

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, Proof of an identity relating the tree function T(z) and the second order Eulerian numbers. Feb. 28, 2021.

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.

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


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

a(n)/A000312(n-1) -> e, as n -> oo. - 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)


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


A000169 := n-> n^(n-1);

spec := [A, {A=Prod(Z, Set(A))}, labeled]; [seq(combstruct[count](spec, size=n), n=1..20)];

for n to 7 do ST := [seq(seq(i, j = 1 .. n), i = 1 .. n)]; PST := powerset(ST); Result[n] := nops(PST) end do; seq(Result[n], n = 1 .. 7); # Thomas Wieder, Feb 07 2010


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


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

(PARI) N=66; x='x+O('x^N); egf=serreverse(x*exp(-x)); Vec(serlaplace(egf)) \\ Computation via e.g.f. by series reversion of x*exp(-x). - Joerg Arndt, May 25 2011

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

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

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


def a(n): return n**(n-1)

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


Cf. A000055, A000081, A000272, A000312, 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.

Sequence in context: A055860 A152917 A213236 * A112319 A232552 A038038

Adjacent sequences:  A000166 A000167 A000168 * A000170 A000171 A000172




N. J. A. Sloane



Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 20 07:54 EDT 2022. Contains 353852 sequences. (Running on oeis4.)