cp's OEIS Frontend

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

%I A000169 M1946 N0771 #327 Jul 30 2025 11:13:03
%S A000169 1,2,9,64,625,7776,117649,2097152,43046721,1000000000,25937424601,
%T A000169 743008370688,23298085122481,793714773254144,29192926025390625,
%U A000169 1152921504606846976,48661191875666868481,2185911559738696531968,104127350297911241532841,5242880000000000000000000
%N A000169 Number of labeled rooted trees with n nodes: n^(n-1).
%C A000169 Also the number of connected transitive subtree acyclic digraphs on n vertices. - _Robert Castelo_, Jan 06 2001
%C A000169 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
%C A000169 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
%C A000169 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
%C A000169 a(n+1) is also the number of partial functions on n labeled objects. - _Franklin T. Adams-Watters_, Dec 25 2006
%C A000169 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
%C A000169 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.
%C A000169 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
%C A000169 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
%C A000169 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
%C A000169 a(n) is also the number of functions f:{1,2,...,n} -> {1,2,...,n} such that f(1) = 1.
%C A000169 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
%C A000169 Numerator of (1+1/(n-1))^(n-1) for n>1. - _Jean-François Alcover_, Jan 14 2013
%C A000169 Right edge of triangle A075513. - _Michel Marcus_, May 17 2013
%C A000169 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
%C A000169 Central terms of triangle A051129: a(n) = A051129(2*n-1,n). - _Reinhard Zumkeller_, Sep 14 2014
%C A000169 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
%C A000169 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
%C A000169 a(n) is the number of words of length n-1 over an alphabet of n letters. - _Joerg Arndt_, Oct 07 2015
%C A000169 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
%C A000169 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
%C A000169 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
%C A000169 Coefficients of the generating series for the preLie operadic algebra. Cf. p. 417 of the Loday et al. paper. - _Tom Copeland_, Jul 08 2018
%C A000169 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
%C A000169 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
%D A000169 Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 169.
%D A000169 Jonathan L. Gross and Jay Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 524.
%D A000169 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
%D A000169 Clifford A. Pickover, A Passion for Mathematics, Wiley, 2005; see p. 63.
%D A000169 John Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 128.
%D A000169 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A000169 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D A000169 Richard P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see page 25, Prop. 5.3.2, and p. 37, (5.52).
%H A000169 N. J. A. Sloane, <a href="/A000169/b000169.txt">Table of n, a(n) for n = 1..100</a>
%H A000169 Paul Barry and Aoife Hennessy, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL15/Barry2/barry190r.html">Generalized Narayana Polynomials, Riordan Arrays, and Lattice Paths</a>, Journal of Integer Sequences, Vol. 15, 2012, #12.4.8. - _N. J. A. Sloane_, Oct 08 2012
%H A000169 Washington Bomfim, <a href="http://en.wikipedia.org/wiki/File:Bijecao.gif">Bijection between rooted forests and multigraphs without cycles except one loop in each connected component.</a> [From _Washington Bomfim_, Sep 04 2010]
%H A000169 David Callan, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL6/Callan/callan10.html">A Combinatorial Derivation of the Number of Labeled Forests</a>, J. Integer Seqs., Vol. 6, 2003.
%H A000169 Peter J. Cameron and Philippe Cara, <a href="http://dx.doi.org/10.1016/S0021-8693(02)00550-1">Independent generating sets and geometries for symmetric groups</a>, J. Algebra, Vol. 258, no. 2 (2002), 641-650.
%H A000169 Robert Castelo and Arno Siebes, <a href="http://dspace.library.uu.nl/handle/1874/1914">A characterization of moral transitive directed acyclic graph Markov models as trees</a>, Technical Report CS-2000-44, Faculty of Computer Science, University of Utrecht.
%H A000169 Robert Castelo and Arno Siebes, <a href="https://doi.org/10.1016/S0378-3758(02)00143-X">A characterization of moral transitive acyclic directed graph Markov models as labeled trees</a>, Journal of Statistical Planning and Inference, Vol. 115, No. 1 (2003), pp. 235-259; <a href="https://www.researchgate.net/publication/2537096_A_Characterization_of_Moral_Transitive_Directed_Acyclic_Graph_Markov_models_as_trees_and_its_properties">alternative link</a>.
%H A000169 Frédéric Chapoton, Florent Hivert and Jean-Christophe Novelli, <a href="https://doi.org/10.1016/j.jalgebra.2016.07.001">A set-operad of formal fractions and dendriform-like sub-operads</a>, Journal of Algebra, Vol. 465 (2016), pp. 322-355; <a href="https://arxiv.org/abs/1307.0092">arXiv preprint</a>, arXiv:1307.0092 [math.CO], 2013.
%H A000169 Ali Chouria, Vlad-Florin Drǎgoi, Jean-Gabriel Luque, <a href="https://arxiv.org/abs/2004.04203">On recursively defined combinatorial classes and labelled trees</a>, arXiv:2004.04203 [math.CO], 2020.
%H A000169 R. M. Corless, G. H. Gonnet, D. E. G. Hare, D. J. Jeffrey and D. E. Knuth, <a href="http://dx.doi.org/10.1007/BF02124750">On the Lambert W Function</a>, Advances in Computational Mathematics, VOl. 5 (1996), pp. 329-359; <a href="https://www.uwo.ca/apmaths/faculty/jeffrey/pdfs/W-adv-cm.pdf">alternative link</a>.
%H A000169 Nick Hobson, <a href="https://web.archive.org/web/20160413232742/http://www.qbyte.org/puzzles/p048s.html">Solution to puzzle 48: Exponential equation</a>.
%H A000169 INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=67">Encyclopedia of Combinatorial Structures 67</a>.
%H A000169 Qipeng Kuang, Ondřej Kuželka, Yuanhong Wang, and Yuyi Wang, <a href="https://arxiv.org/abs/2407.11877">Bridging Weighted First Order Model Counting and Graph Polynomials</a>, arXiv:2407.11877 [cs.LO], 2024. See p. 33.
%H A000169 Jean-Louis Loday and Bruno Vallette, <a href="http://irma.math.unistra.fr/~loday/PAPERS/LodayVallette.pdf">Algebraic Operads</a>, version 0.99, 2012.
%H A000169 G. Pólya, <a href="http://www.jstor.org/stable/2305566">With, or Without, Motivation?</a>, 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).
%H A000169 Gwenaël Richomme, <a href="https://doi.org/10.1142/S0129054119400082">Characterization of infinite LSP words and endomorphisms preserving the LSP property</a>, International Journal of Foundations of Computer Science, Vol. 30, No. 1 (2019), pp. 171-196; <a href="https://arxiv.org/abs/1808.02680">arXiv preprint</a>, arXiv:1808.02680 [cs.DM], 2018.
%H A000169 Marko Riedel, math.stackexchange.com, <a href="https://math.stackexchange.com/questions/4040942/">Proof of an identity relating the tree function T(z) and the second order Eulerian numbers.</a> Feb. 28, 2021.
%H A000169 Marko Riedel, math.stackexchange.com, <a href="https://math.stackexchange.com/questions/4838962/">Asymptotics of tree function statistics using Pusieux series</a>
%H A000169 Frank Ruskey, <a href="https://web.archive.org/web/20160714032428/http://theory.cs.uvic.ca/inf/tree/RootedTree.html">Information on Rooted Trees</a>.
%H A000169 N. J. A. Sloane, <a href="/A000081/a000081.html">Illustration of initial terms</a>
%H A000169 Zhi-Wei Sun, Fedor Petrov, <a href="https://mathoverflow.net/questions/321098/">A surprising identity</a>, discussion in MathOverflow, Jan 17 2019.
%H A000169 Elena L. Wang and Guoce Xin, <a href="https://arxiv.org/abs/2507.15654">On Ward Numbers and Increasing Schröder Trees</a>, arXiv:2507.15654 [math.CO], 2025. See p. 12.
%H A000169 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/GraphVertex.html">Graph Vertex</a>.
%H A000169 Dimitri Zvonkine, <a href="https://arxiv.org/abs/math/0403092">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</a>, arXiv:math/0403092 [math.AG], 2004.
%H A000169 <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%H A000169 <a href="/index/Tra#trees">Index entries for sequences related to trees</a>
%H A000169 <a href="/index/Cor#core">Index entries for "core" sequences</a>
%F A000169 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).
%F A000169 Also T(x) = -LambertW(-x) where W(x) is the principal branch of Lambert's function.
%F A000169 T(x) is sometimes called Euler's tree function.
%F A000169 a(n) = A000312(n-1)*A128434(n,1)/A128433(n,1). - _Reinhard Zumkeller_, Mar 03 2007
%F A000169 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
%F A000169 a(n) = Sum_{i=1..n} binomial(n-1,i-1)*i^(i-2)*(n-i)^(n-i). - _Dmitry Kruchinin_, Oct 28 2013
%F A000169 Limit_{n->oo} a(n)/A000312(n-1) = e. - _Daniel Suteu_, Jul 23 2016
%F A000169 From _Amiram Eldar_, Nov 20 2020: (Start)
%F A000169 Sum_{n>=1} 1/a(n) = A098686.
%F A000169 Sum_{n>=1} (-1)^(n+1)/a(n) = A262974. (End)
%F A000169 a(n) = Sum_{k=0..n-1} (-1)^(n+k-1)*Pochhammer(n, k)*Stirling2(n-1, k). - _Mélika Tebni_, May 07 2023
%F A000169 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
%e A000169 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
%e A000169 G.f. = x + 2*x^2 + 9*x^3 + 64*x^4 + 625*x^5 + 7776*x^6 + 117649*x^7 + ...
%p A000169 A000169 := n -> n^(n-1);
%p A000169 # second program:
%p A000169 spec := [A, {A=Prod(Z, Set(A))}, labeled]; [seq(combstruct[count](spec, size=n), n=1..20)];
%p A000169 # third program:
%p A000169 A000169 := n -> add((-1)^(n+k-1)*pochhammer(n, k)*Stirling2(n-1, k), k = 0..n-1):
%p A000169 seq(A000169(n), n = 1 .. 23);  # _Mélika Tebni_, May 07 2023
%t A000169 Table[n^(n - 1), {n, 1, 20}] (* _Stefan Steinerberger_, Apr 01 2006 *)
%t A000169 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 *)
%t A000169 (* Next, a signed version A000169 from the Vandermonde determinant of (1,1/2,...,1/n) *)
%t A000169 f[j_] := 1/j; z = 12;
%t A000169 v[n_] := Product[Product[f[k] - f[j], {j, 1, k - 1}], {k, 2, n}]
%t A000169 Table[v[n], {n, 1, z}]
%t A000169 1/%  (* A203421 *)
%t A000169 Table[v[n]/v[n + 1], {n, 1, z - 1}]  (* A000169 signed *)
%t A000169 (* _Clark Kimberling_, Jan 02 2012 *)
%t A000169 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 *)
%o A000169 (PARI) a(n) = n^(n-1)
%o A000169 (MuPAD) n^(n-1) $ n=1..20 /* _Zerinvary Lajos_, Apr 01 2007 */
%o A000169 (Haskell) a000169 n = n ^ (n - 1)  -- _Reinhard Zumkeller_, Sep 14 2014
%o A000169 (Magma) [n^(n-1): n in [1..20]]; // _Vincenzo Librandi_, Jul 17 2015
%o A000169 (Python)
%o A000169 def a(n): return n**(n-1)
%o A000169 print([a(n) for n in range(1, 21)]) # _Michael S. Branicky_, Sep 19 2021
%o A000169 (Python)
%o A000169 from sympy import Matrix
%o A000169 def P(n): return [[ (i-n if i > j else i) + (i == 0) for j in range(n) ] for i in range(n)]
%o A000169 print(*(Matrix(P(n)).det() for n in range(1, 21)), sep=', ') # _C.S. Elder_, Mar 12 2024
%Y A000169 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.
%Y A000169 Other classes of endofunctions: A275549-A275558.
%K A000169 easy,core,nonn,nice
%O A000169 1,2
%A A000169 _N. J. A. Sloane_