A275558 -id:A275558 - cp's OEIS frontend

A000312 a(n) = n^n; number of labeled mappings from n points to themselves (endofunctions).

1, 1, 4, 27, 256, 3125, 46656, 823543, 16777216, 387420489, 10000000000, 285311670611, 8916100448256, 302875106592253, 11112006825558016, 437893890380859375, 18446744073709551616, 827240261886336764177, 39346408075296537575424, 1978419655660313589123979

Offset: 0

N. J. A. Sloane

Also number of labeled pointed rooted trees (or vertebrates) on n nodes.
For n >= 1 a(n) is also the number of n X n (0,1) matrices in which each row contains exactly one entry equal to 1. - Avi Peretz (njk(AT)netvision.net.il), Apr 21 2001
Also the number of labeled rooted trees on (n+1) nodes such that the root is lower than its children. Also the number of alternating labeled rooted ordered trees on (n+1) nodes such that the root is lower than its children. - Cedric Chauve (chauve(AT)lacim.uqam.ca), Mar 27 2002
With p(n) = the number of integer partitions of n, p(i) = the number of parts of the i-th partition of n, d(i) = the number of different parts of the i-th partition of n, p(j, i) = the j-th part of the i-th partition of n, m(i, j) = multiplicity of the j-th part of the i-th partition of n, one has: a(n) = Sum_{i=1..p(n)} (n!/(Product_{j=1..p(i)} p(i, j)!)) * ((n!/(n - p(i)))!/(Product_{j=1..d(i)} m(i, j)!)). - Thomas Wieder, May 18 2005
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) is the total number of leaves in all (n+1)^(n-1) trees on {0,1,2,...,n} rooted at 0. For example, with edges directed away from the root, the trees on {0,1,2} are {0->1,0->2},{0->1->2},{0->2->1} and contain a total of a(2)=4 leaves. - David Callan, Feb 01 2007
Limit_{n->infinity} A000169(n+1)/a(n) = exp(1). Convergence is slow, e.g., it takes n > 74 to get one decimal place correct and n > 163 to get two of them. - Alonso del Arte, Jun 20 2011
Also smallest k such that binomial(k, n) is divisible by n^(n-1), n > 0. - Michel Lagneau, Jul 29 2013
For n >= 2 a(n) is represented in base n as "one followed by n zeros". - R. J. Cano, Aug 22 2014
Number of length-n words over the alphabet of n letters. - Joerg Arndt, May 15 2015
Number of prime parking functions of length n+1. - Rui Duarte, Jul 27 2015
The probability density functions p(x, m=q, n=q, mu=1) = A000312(q)*E(x, q, q) and p(x, m=q, n=1, mu=q) = (A000312(q)/A000142(q-1))*x^(q-1)*E(x, q, 1), with q >= 1, lead to this sequence, see A163931, A274181 and A008276. - Johannes W. Meijer, Jun 17 2016
Satisfies Benford's law [Miller, 2015]. - N. J. A. Sloane, Feb 12 2017
A signed version of this sequence apart from the first term (1, -4, -27, 256, 3125, -46656, ...), has the following property: for every prime p == 1 (mod 2n), (-1)^(n(n-1)/2)*n^n = A057077(n)*a(n) is always a 2n-th power residue modulo p. - Jianing Song, Sep 05 2018
From Juhani Heino, May 07 2019: (Start)
n^n is both Sum_{i=0..n} binomial(n,i)*(n-1)^(n-i)
  and Sum_{i=0..n} binomial(n,i)*(n-1)^(n-i)*i.
The former is the familiar binomial distribution of a throw of n n-sided dice, according to how many times a required side appears, 0 to n. The latter is the same but each term is multiplied by its amount. This means that if the bank pays the player 1 token for each die that has the chosen side, it is always a fair game if the player pays 1 token to enter - neither bank nor player wins on average.
Examples:
2-sided dice (2 coins): 4 = 1 + 2 + 1 = 1*0 + 2*1 + 1*2 (0 omitted from now on);
3-sided dice (3 long triangular prisms): 27 = 8 + 12 + 6 + 1 = 12*1 + 6*2 + 1*3;
4-sided dice (4 long square prisms or 4 tetrahedrons): 256 = 81 + 108 + 54 + 12 + 1 = 108*1 + 54*2 + 12*3 + 1*4;
5-sided dice (5 long pentagonal prisms): 3125 = 1024 + 1280 + 640 + 160 + 20 + 1 = 1280*1 + 640*2 + 160*3 + 20*4 + 1*5;
6-sided dice (6 cubes): 46656 = 15625 + 18750 + 9375 + 2500 + 375 + 30 + 1 = 18750*1 + 9375*2 + 2500*3 + 375*4 + 30*5 + 1*6.
(End)
For each n >= 1 there is a graph on a(n) vertices whose largest independent set has size n and whose independent set sequence is constant (specifically, for each k=1,2,...,n, the graph has n^n independent sets of size k). There is no graph of smaller order with this property (Ball et al. 2019). - David Galvin, Jun 13 2019
For n >= 2 and 1 <= k <= n, a(n)*(n + 1)/4 + a(n)*(k - 1)*(n + 1 - k)/2*n is equal to the sum over all words w = w(1)...w(n) of length n over the alphabet {1, 2, ..., n} of the following quantity: Sum_{i=1..w(k)} w(i). Inspired by Problem 12432 in the AMM (see links). - Sela Fried, Dec 10 2023
Also, dimension of the unique cohomology group of the smallest interval containing the poset of partitions decorated by Perm, i.e. the poset of pointed partitions. - Bérénice Delcroix-Oger, Jun 25 2025

			G.f. = 1 + x + 4*x^2 + 27*x^3 + 256*x^4 + 3125*x^5 + 46656*x^6 + 823543*x^7 + ...

F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Cambridge, 1998, pp. 62, 63, 87.
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 173, #39.
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)
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).

Kenny Lau, Table of n, a(n) for n = 0..385 [First 100 terms computed by T. D. Noe]
Taylor Ball, David Galvin, Katie Hyry, and Kyle Weingartner, Independent set and matching permutations, arXiv:1901.06579 [math.CO], 2019.
Arthur T. Benjamin and Fritz Juhnke, Another way of counting n^n, SIAM J. Discrete Math., Vol. 5, No. 3 (1992), pp. 377-379. - _N. J. A. Sloane_, Jun 09 2011
H. Bottomley, Illustration of initial terms.
H. J. Brothers and J. A. Knox, New closed-form approximations to the logarithmic constant e, The Mathematical Intelligencer, Vol. 20 (4), 1998, pp. 25-29. (Sequence appears as formula in Eq. (8))
C. Chauve, S. Dulucq and O. Guibert, Enumeration of some labeled trees, Proceedings of FPSAC/SFCA 2000 (Moscow), Springer, pp. 146-157.
Bérénice Delcroix-Oger and Clément Dupont, Lie-operads and operadic modules from poset cohomology, arXiv:2505.06094 [math.CO], 2025. See p. 34.
Frank Ellermann, Illustration of binomial transforms.
José María Grau and Antonio M. Oller-Marcén, On the last digit and the last non-zero digit of n^n in base b, Bulletin of the Korean Mathematical Society, Vol. 51, No. 5 (2014), pp. 1325-1337; arXiv preprint, arXiv:1203.4066 [math.NT], 2012.
Nick Hobson, Solution to puzzle 48: Exponential equation.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 36.
Steven J. Miller (ed.), Exercises to "The Theory and Applications of Benford's Law", Princeton University Press, 2015.
Mustafa Obaid et al., The number of complete exceptional sequences for a Dynkin algebra, arXiv preprint arXiv:1307.7573 [math.RT], 2013.
Franck Ramaharo, A generating polynomial for the pretzel knot, arXiv:1805.10680 [math.CO], 2018.
E. Vigren (Proposer), Problem 12432, Amer. Math. Monthly 130 (2023), p. 953.
Elena L. Wang and Guoce Xin, On Ward Numbers and Increasing Schröder Trees, arXiv:2507.15654 [math.CO], 2025. See pp. 12-13.
Eric Weisstein's World of Mathematics, Hadamard's Maximum Determinant Problem.
Eric Weisstein's World of Mathematics, Hankel Matrix.
Dimitri Zvonkine, An algebra of power series..., arXiv:math/0403092 [math.AG], 2004.
Index entries for "core" sequences
Index entries for sequences related to rooted trees
Index entries for sequences related to Benford's law

Cf. A000107, A000169, A000272, A001372, A007778, A007830, A008785-A008791, A019538, A048993, A008279, A085741, A062206, A212333.
First column of triangle A055858. Row sums of A066324.
Cf. A001923 (partial sums), A002109 (partial products), A007781 (first differences), A066588 (sum of digits).
Cf. A056665, A081721, A130293, A168658, A275549-A275558 (various classes of endofunctions).
Cf. A174824, A204688.
Cf. A055137, A083648.

a000312 n = n ^ n
a000312_list = zipWith (^) [0..] [0..]  -- Reinhard Zumkeller, Jul 07 2012

A000312 := n->n^n: seq(A000312(n), n=0..17);

Array[ #^# &, 16] (* Vladimir Joseph Stephan Orlovsky, May 01 2008 *)
Table[Sum[StirlingS2[n, i] i! Binomial[n, i], {i, 0, n}], {n, 0, 20}] (* Geoffrey Critzer, Mar 17 2009 *)
a[ n_] := If[ n < 1, Boole[n == 0], n^n]; (* Michael Somos, May 24 2014 *)
a[ n_] := If[ n < 0, 0, n! SeriesCoefficient[ 1 / (1 + LambertW[-x]), {x, 0, n}]]; (* Michael Somos, May 24 2014 *)
a[ n_] := If[n < 0, 0, n! SeriesCoefficient[ Nest[ 1 / (1 - x / (1 - Integrate[#, x])) &, 1 + O[x], n], {x, 0, n}]]; (* Michael Somos, May 24 2014 *)
a[ n_] := If[ n < 0, 0, With[{m = n + 1}, m! SeriesCoefficient[ InverseSeries[ Series[ (x - 1) Log[1 - x], {x, 0, m}]], m]]]; (* Michael Somos, May 24 2014 *)

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

PARI
```
{a(n) = n^n};
```

is(n)=my(b,k=ispower(n,,&b));if(k,for(e=1,valuation(k,b), if(k/b^e == e, return(1)))); n==1 \\ Charles R Greathouse IV, Jan 14 2013

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

def A000312(n): return n**n # Chai Wah Wu, Nov 07 2022

a(n-1) = -Sum_{i=1..n} (-1)^i*i*n^(n-1-i)*binomial(n, i). - Yong Kong (ykong(AT)curagen.com), Dec 28 2000
E.g.f.: 1/(1 + W(-x)), W(x) = principal branch of Lambert's function.
a(n) = Sum_{k>=0} binomial(n, k)*Stirling2(n, k)*k! = Sum_{k>=0} A008279(n,k)*A048993(n,k) = Sum_{k>=0} A019538(n,k)*A007318(n,k). - Philippe Deléham, Dec 14 2003
E.g.f.: 1/(1 - T), where T = T(x) is Euler's tree function (see A000169).
a(n) = A000169(n+1)*A128433(n+1,1)/A128434(n+1,1). - Reinhard Zumkeller, Mar 03 2007
Comment on power series with denominators a(n): Let f(x) = 1 + Sum_{n>=1} x^n/n^n. Then as x -> infinity, f(x) ~ exp(x/e)*sqrt(2*Pi*x/e). - Philippe Flajolet, Sep 11 2008
E.g.f.: 1 - exp(W(-x)) with an offset of 1 where W(x) = principal branch of Lambert's function. - Vladimir Kruchinin, Sep 15 2010
a(n) = (n-1)*a(n-1) + Sum_{i=1..n} binomial(n, i)*a(i-1)*a(n-i). - Vladimir Shevelev, Sep 30 2010
With an offset of 1, the e.g.f. is the compositional inverse ((x - 1)*log(1 - x))^(-1) = x + x^2/2! + 4*x^3/3! + 27*x^4/4! + .... - Peter Bala, Dec 09 2011
a(n) = denominator((1 + 1/n)^n) for n > 0. - Jean-François Alcover, Jan 14 2013
a(n) = A089072(n,n) for n > 0. - Reinhard Zumkeller, Mar 18 2013
a(n) = (n-1)^(n-1)*(2*n) + Sum_{i=1..n-2} binomial(n, i)*(i^i*(n-i-1)^(n-i-1)), n > 1, a(0) = 1, a(1) = 1. - Vladimir Kruchinin, Nov 28 2014
log(a(n)) = lim_{k->infinity} k*(n^(1+1/k) - n). - Richard R. Forberg, Feb 04 2015
From Ilya Gutkovskiy, Jun 18 2016: (Start)
Sum_{n>=1} 1/a(n) = 1.291285997... = A073009.
Sum_{n>=1} 1/a(n)^2 = 1.063887103... = A086648.
Sum_{n>=1} n!/a(n) = 1.879853862... = A094082. (End)
A000169(n+1)/a(n) -> e, as n -> oo. - Daniel Suteu, Jul 23 2016
a(n) = n!*Product_{k=1..n} binomial(n, k)/Product_{k=1..n-1} binomial(n-1, k) = n!*A001142(n)/A001142(n-1). - Tony Foster III, Sep 05 2018
a(n-1) = abs(p_n(2-n)), for n > 2, the single local extremum of the n-th row polynomial of A055137 with Bagula's sign convention. - Tom Copeland, Nov 15 2019
Sum_{n>=1} (-1)^(n+1)/a(n) = A083648. - Amiram Eldar, Jun 25 2021
Limit_{n->oo} (a(n+1)/a(n) - a(n)/a(n-1)) = e (see Brothers/Knox link). - Harlan J. Brothers, Oct 24 2021
Conjecture: a(n) = Sum_{i=0..n} A048994(n, i) * A048993(n+i, n) for n >= 0; proved by Mike Earnest, see link at A354797. - Werner Schulte, Jun 19 2022

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

A056665 Number of equivalence classes of n-valued Post functions of 1 variable under action of complementing group C(1,n).

Original entry on oeis.org

1, 3, 11, 70, 629, 7826, 117655, 2097684, 43046889, 1000010044, 25937424611, 743008623292, 23298085122493, 793714780783770, 29192926025492783, 1152921504875290696, 48661191875666868497, 2185911559749720272442, 104127350297911241532859

Offset: 1

Vladeta Jovovic, Aug 09 2000

Diagonal of arrays defined in A054630 and A054631.
Given n colors, a(n) = number of necklaces with n beads and 1 up to n colors effectively assigned to them (super_labeled: which also generates n different monochrome necklaces). - Wouter Meeussen, Aug 09 2002
Number of endofunctions on a set with n objects up to cyclic permutation (rotation). E.g., for n = 3, the 11 endofunctions are 1,1,1; 2,2,2; 3,3,3; 1,1,2; 1,2,2; 1,1,3; 1,3,3; 2,2,3; 2,3,3; 1,2,3; and 1,3,2. - Franklin T. Adams-Watters, Jan 17 2007
Also number of pre-necklaces in Sigma(n,n) (see Ruskey and others). - Peter Luschny, Aug 12 2012
From Olivier Gérard, Aug 01 2016: (Start)
Decomposition of the endofunctions by class size.
.
  n |  1   2   3   4    5     6       7
  --+----------------------------------
  1 |  1
  2 |  2   1
  3 |  3   0   8
  4 |  4   6   0  60
  5 |  5   0   0   0  624
  6 |  6  15  70   0    0  7735
  7 |  7   0   0   0    0     0  117648
.
The right diagonal gives the number of Lyndon Words or aperiodic necklaces, A075147. By multiplying each column by the corresponding size and summing, one gets A000312.
(End)

			The 11 necklaces for n=3 are (grouped by partition of 3): (RRR,GGG,BBB),(RRG,RGG, RRB,RBB, GGB,GBB), (RGB,RBG).

D. E. Knuth. Generating All Tuples and Permutations. The Art of Computer Programming, Vol. 4, Fascicle 2, 7.2.1.1. Addison-Wesley, 2005.

Alois P. Heinz, Table of n, a(n) for n = 1..200
M. A. Harrison and R. G. High, On the cycle index of a product of permutation groups, J. Combin. Theory, 4 (1968), 277-299.
F. Ruskey, C. Savage, and T. M. Y. Wang, Generating necklaces, Journal of Algorithms, 13(3), 414 - 430, 1992.
Index entries for sequences related to groups

Cf. A001323, A001324, A001372, A000312.
Diagonal of arrays defined in A054630, A054631 and A075195.
Cf. A075147 Aperiodic necklaces, a subset of this sequence.
Cf. A000169 Classes under translation mod n
Cf. A168658 Classes under complement to n+1
Cf. A130293 Classes under translation and rotation
Cf. A081721 Classes under rotation and reversal
Cf. A275549 Classes under reversal
Cf. A275550 Classes under reversal and complement
Cf. A275551 Classes under translation and reversal
Cf. A275552 Classes under translation and complement
Cf. A275553 Classes under translation, complement and reversal
Cf. A275554 Classes under translation, rotation and complement
Cf. A275555 Classes under translation, rotation and reversal
Cf. A275556 Classes under translation, rotation, complement and reversal
Cf. A275557 Classes under rotation and complement
Cf. A275558 Classes under rotation, complement and reversal
Cf. A228640.

with(numtheory):
a:= n-> add(phi(d)*n^(n/d), d=divisors(n))/n:
seq(a(n), n=1..25);  # Alois P. Heinz, Jun 18 2013

Table[Fold[ #1+EulerPhi[ #2] n^(n/#2)&, 0, Divisors[n]]/n, {n, 7}]

a(n) = sum(k=1,n,n^gcd(k,n)) / n; \\ Joerg Arndt, Mar 19 2017

# This algorithm counts all n-ary n-tuples (a_1,..,a_n) such that the string a_1...a_n is preprime. It is algorithm F in Knuth 7.2.1.1.
def A056665_list(n):
    C = []
    for m in (1..n):
        a = [0]*(n+1); a[0]=-1;
        j = 1; count = 0
        while(true):
            if m%j == 0 : count += 1;
            j = n
            while a[j] >= m-1 : j -= 1
            if j == 0 : break
            a[j] += 1
            for k in (j+1..n): a[k] = a[k-j]
        C.append(count)
    return C

def A056665(n): return sum(euler_phi(d)*n^(n//d)//n for d in divisors(n))
[A056665(n) for n in (1..18)] # Peter Luschny, Aug 12 2012

a(n) = Sum_{d|n} phi(d)*n^(n/d)/n.
a(n) ~ n^(n-1). - Vaclav Kotesovec, Sep 11 2014
a(n) = (1/n) * Sum_{k=1..n} n^gcd(k,n). - Joerg Arndt, Mar 19 2017
a(n) = [x^n] -Sum_{k>=1} phi(k)*log(1 - n*x^k)/k. - Ilya Gutkovskiy, Mar 21 2018
From Richard L. Ollerton, May 07 2021: (Start)
a(n) = (1/n)*Sum_{k=1..n} n^(n/gcd(n,k))*phi(gcd(n,k))/phi(n/gcd(n,k)).
a(n) = (1/n)*A228640(n). (End)

A081721 Number of bracelets of n beads in up to n colors.

Original entry on oeis.org

1, 3, 10, 55, 377, 4291, 60028, 1058058, 21552969, 500280022, 12969598086, 371514016094, 11649073935505, 396857785692525, 14596464294191704, 576460770691256356, 24330595997127372497, 1092955780817066765469, 52063675152021153895330, 2621440000054016000176044

Offset: 1

N. J. A. Sloane, based on information supplied by Gary W. Adamson, Apr 05 2003

nonn

T(n,n), T given in A081720.
From Olivier Gérard, Aug 01 2016: (Start)
Number of classes of functions of [n] to [n] under rotation and reversal.
.
Classes can be of size between 1 and 2n
depending on divisibility properties of n.
.
n   1   2   3   4    5         n     2n
----------------------------------------
1   1
2   2   1
3   3   0   6                         1
4   4   6   0                 30     15
5   5   0   0                120    252
6   6  15  30                725   3515
7   7   0   0               2394  57627
.
(End)

Alois P. Heinz, Table of n, a(n) for n = 1..200

Cf. A000312 All endofunctions
Cf. A000169 Classes under translation mod n
Cf. A001700 Classes under sort
Cf. A056665 Classes under rotation
Cf. A168658 Classes under complement to n+1
Cf. A130293 Classes under translation and rotation
Cf. A275549 Classes under reversal
Cf. A275550 Classes under reversal and complement
Cf. A275551 Classes under translation and reversal
Cf. A275552 Classes under translation and complement
Cf. A275553 Classes under translation, complement and reversal
Cf. A275554 Classes under translation, rotation and complement
Cf. A275555 Classes under translation, rotation and reversal
Cf. A275556 Classes under translation, rotation, complement and reversal
Cf. A275557 Classes under rotation and complement
Cf. A275558 Classes under rotation, complement and reversal
Row sums of partition array A213941.
Main diagonal of A321791.

Table[CycleIndex[DihedralGroup[n],s]/.Table[s[i]->n,{i,1,n}],{n,1,20}] (* Geoffrey Critzer, Jun 18 2013 *)
t[n_, k_] := (For[t1 = 0; d = 1, d <= n, d++, If[Mod[n, d] == 0, t1 = t1 + EulerPhi[d]*k^(n/d)]]; If[EvenQ[n], (t1 + (n/2)*(1 + k)*k^(n/2))/(2*n), (t1 + n*k^((n + 1)/2))/(2*n)]); a[n_] := t[n, n]; Array[a, 20] (* Jean-François Alcover, Nov 02 2017, after Maple code for A081720 *)

a(n) ~ n^(n-1) / 2. - Vaclav Kotesovec, Mar 18 2017

Name changed by Olivier Gérard, Aug 05 2016

Name revised by Álvar Ibeas, Apr 20 2018

A275549 Number of classes of endofunctions of [n] under reversal.

Original entry on oeis.org

1, 1, 3, 18, 136, 1625, 23436, 412972, 8390656, 193739769, 5000050000, 142656721086, 4458051717120, 151437584670385, 5556003465485760, 218946946471875000, 9223372039002259456, 413620131002462320337, 19673204037747448432896, 989209827833222327690890

Offset: 0

Olivier Gérard, Aug 01 2016

f and g are in the same class if function g(i) = f(n+1-i) for all i.
Decomposition by class size
.
n    1      2
---------------
1    1      0
2    2      1
3    9      9
4    16     120
5    125    1500
6    216    23220
7    2401   410571
.
Demonstration for the formula: the classes are either of size 1 or 2.
The classes of size 1 is for functions invariant by reversal. They are specified by half their values, including one more if n is odd. Their number is n^(ceiling(n/2)).
So the number of classes under this symmetry is half (the number of functions + the number of classes of size 1).
a(n) is the number of unoriented length n strings with a maximum of n colors. - Andrew Howroyd, Sep 13 2019

Andrew Howroyd, Table of n, a(n) for n = 0..200

Main diagonal of A277504.
Cf. A000312 All endofunctions
Cf. A000169 Classes under translation mod n
Cf. A001700 Classes under sort
Cf. A056665 Classes under rotation
Cf. A168658 Classes under complement to n+1
Cf. A130293 Classes under translation and rotation
Cf. A081721 Classes under rotation and reversal
Cf. A275550 Classes under reversal and complement
Cf. A275551 Classes under translation and reversal
Cf. A275552 Classes under translation and complement
Cf. A275553 Classes under translation, complement and reversal
Cf. A275554 Classes under translation, rotation and complement
Cf. A275555 Classes under translation, rotation and reversal
Cf. A275556 Classes under translation, rotation, complement and reversal
Cf. A275557 Classes under rotation and complement
Cf. A275558 Classes under rotation, complement and reversal
Cf. A078707 Endofunctions symmetric around their middle (stable by reversal).

a(n) = {(n^n + n^((n+1)\2))/2} \\ Andrew Howroyd, Sep 13 2019

a(n) = (n^n+n^ceiling(n/2))/2.

A130293 Number of necklaces of n beads with up to n colors, with cyclic permutation {1,..,n} of the colors taken to be equivalent.

Original entry on oeis.org

1, 2, 5, 20, 129, 1316, 16813, 262284, 4783029, 100002024, 2357947701, 61917406672, 1792160394049, 56693913450992, 1946195068379933, 72057594071484456, 2862423051509815809, 121439531097819321972, 5480386857784802185957, 262144000000051200072048, 13248496640331026150086281

Offset: 1

Wouter Meeussen, Aug 06 2007, Aug 14 2007

nonn

From Olivier Gérard, Aug 01 2016: (Start)
Equivalent to the definition: number of classes of endofunctions of [n] under rotation and translation mod n.
Classes can be of size between n and n^2 depending on divisibility properties of n.
  n   n   2n   3n  ...  n^2
  --------------------------
  1   1
  2   2
  3   3                   2
  4   4    2             14
  5   5    0            124
  6   6    6   22      1282
  7   7    0          16806
For prime n, the only possible class sizes are n and n^2, the classes of size n are the n arithmetical progression modulo n so #(c-n)=n, #(c-n^2)=(n^n - n*n)/n^2 = n^(n-2)-1 and a(n) = n^(n-2)+n-1.
(End)

			The 5 necklaces for n=3 are: 000, 001, 002, 012 and 021.

Stefano Spezia, Table of n, a(n) for n = 1..350
Darij Grinberg and Peter Mao, Necklaces over a group with identity product, arXiv:2405.08937 [math.CO], 2024. See p. 22.

Cf. A002075-A002076.
Cf. A081720.
Cf. A000312: All endofunctions.
Cf. A000169: Classes under translation mod n.
Cf. A001700: Classes under sort.
Cf. A056665: Classes under rotation.
Cf. A168658: Classes under complement to n+1.
Cf. A130293: Classes under translation and rotation.
Cf. A081721: Classes under rotation and reversal.
Cf. A275549: Classes under reversal.
Cf. A275550: Classes under reversal and complement.
Cf. A275551: Classes under translation and reversal.
Cf. A275552: Classes under translation and complement.
Cf. A275553: Classes under translation, complement and reversal.
Cf. A275554: Classes under translation, rotation and complement.
Cf. A275555: Classes under translation, rotation and reversal.
Cf. A275556: Classes under translation, rotation, complement and reversal.
Cf. A275557: Classes under rotation and complement.
Cf. A275558: Classes under rotation, complement and reversal.

tor8={};ru8=Thread[ i_ ->Table[ Mod[i+k,8],{k,8}]];Do[idi=IntegerDigits[k,8,8];try= Function[w, First[temp=Union[Join @@(Table[RotateRight[w,k],{k,8}]/.#&)/@ ru8]]][idi];If[idi===try, tor8=Flatten[ {tor8,{{Length[temp],idi}}},1] ],{k,0,8^8-1}];
a[n_]:=Sum[d EulerPhi[d]n^(n/d),{d,Divisors[n]}]/n^2; Array[a,21] (* Stefano Spezia, May 21 2024 *)

a(n) = sumdiv(n, d, d*eulerphi(d)*n^(n/d))/n^2; \\ Michel Marcus, Aug 05 2016

a(n) = (1/n^2)*Sum_{d|n} d*phi(d)*n^(n/d). - Vladeta Jovovic, Aug 14 2007, Aug 24 2007

cp's OEIS Frontend

A000312 a(n) = n^n; number of labeled mappings from n points to themselves (endofunctions).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Maxima

PARI

PARI

PARI

Python

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

A056665 Number of equivalence classes of n-valued Post functions of 1 variable under action of complementing group C(1,n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Sage

Sage

Formula

A081721 Number of bracelets of n beads in up to n colors.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A275549 Number of classes of endofunctions of [n] under reversal.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A130293 Number of necklaces of n beads with up to n colors, with cyclic permutation {1,..,n} of the colors taken to be equivalent.

Views

Author

Keywords