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

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000312 a(n) = n^n; number of labeled mappings from n points to themselves (endofunctions).
(Formerly M3619 N1469)
539
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 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

REFERENCES

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

LINKS

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.

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.

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

FORMULA

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 03 and 19 2022

EXAMPLE

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

MAPLE

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

MATHEMATICA

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

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

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

(Maxima) A000312[n]:=if n=0 then 1 else n^n$

makelist(A000312[n], n, 0, 30); /* Martin Ettl, Oct 29 2012 */

CROSSREFS

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. A002109 (partial products).

Cf. A001923 (partial sums).

Cf. A056665, A081721, A130293, A168658, A275549-A275558 (various classes of endofunctions).

Cf. A174824, A204688.

Cf. A055137, A083648.

Sequence in context: A324809 A245414 A177885 * A086783 A301742 A050764

Adjacent sequences:  A000309 A000310 A000311 * A000313 A000314 A000315

KEYWORD

nonn,easy,core,nice

AUTHOR

N. J. A. Sloane

STATUS

approved

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 September 26 08:00 EDT 2022. Contains 356987 sequences. (Running on oeis4.)