

A000312


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


574



1, 1, 4, 27, 256, 3125, 46656, 823543, 16777216, 387420489, 10000000000, 285311670611, 8916100448256, 302875106592253, 11112006825558016, 437893890380859375, 18446744073709551616, 827240261886336764177, 39346408075296537575424, 1978419655660313589123979
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

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 ith partition of n, d(i) = the number of different parts of the ith partition of n, p(j, i) = the jth part of the ith partition of n, m(i, j) = multiplicity of the jth part of the ith 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
a(n) is the total number of leaves in all (n+1)^(n1) 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^(n1), 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 lengthn 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(q1))*x^(q1)*E(x, q, 1), with q >= 1, lead to this sequence, see A163931, A274181 and A008276.  Johannes W. Meijer, Jun 17 2016
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(n1)/2)*n^n = A057077(n)*a(n) is always a 2nth power residue modulo p.  Jianing Song, Sep 05 2018
n^n is both Sum_{i=0..n} binomial(n,i)*(n1)^(ni)
and Sum_{i=0..n} binomial(n,i)*(n1)^(ni)*i.
The former is the familiar binomial distribution of a throw of n nsided 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:
2sided dice (2 coins): 4 = 1 + 2 + 1 = 1*0 + 2*1 + 1*2 (0 omitted from now on);
3sided dice (3 long triangular prisms): 27 = 8 + 12 + 6 + 1 = 12*1 + 6*2 + 1*3;
4sided dice (4 long square prisms or 4 tetrahedrons): 256 = 81 + 108 + 54 + 12 + 1 = 108*1 + 54*2 + 12*3 + 1*4;
5sided dice (5 long pentagonal prisms): 3125 = 1024 + 1280 + 640 + 160 + 20 + 1 = 1280*1 + 640*2 + 160*3 + 20*4 + 1*5;
6sided 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


REFERENCES

F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and TreeLike 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, 19861992, 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).


LINKS

E. Vigren (Proposer), Problem 12432, Amer. Math. Monthly 130 (2023), p. 953.


FORMULA

a(n1) = Sum_{i=1..n} (1)^i*i*n^(n1i)*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.
E.g.f.: 1/(1  T), where T = T(x) is Euler's tree function (see A000169).
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) = (n1)*a(n1) + Sum_{i=1..n} binomial(n, i)*a(i1)*a(ni).  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) = (n1)^(n1)*(2*n) + Sum_{i=1..n2} binomial(n, i)*(i^i*(ni1)^(ni1)), n > 1, a(0) = 1, a(1) = 1.  Vladimir Kruchinin, Nov 28 2014
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)
a(n1) = abs(p_n(2n)), for n > 2, the single local extremum of the nth row polynomial of A055137 with Bagula's sign convention.  Tom Copeland, Nov 15 2019
Limit_{n>oo} (a(n+1)/a(n)  a(n)/a(n1)) = e (see Brothers/Knox link).  Harlan J. Brothers, Oct 24 2021


EXAMPLE

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


MAPLE



MATHEMATICA

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


PROG

(PARI) {a(n) = n^n};
(PARI) 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
(PARI) {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 */
(Haskell)
a000312 n = n ^ n
(Maxima) A000312[n]:=if n=0 then 1 else n^n$
(Python)


CROSSREFS

Cf. A000107, A000169, A000272, A001372, A007778, A007830, A008785A008791, A019538, A048993, A008279, A085741, A062206, A212333.


KEYWORD

nonn,easy,core,nice


AUTHOR



STATUS

approved



