A000312 - OEIS

%I M3619 N1469 #327 Dec 04 2024 18:45:18

%S 1,1,4,27,256,3125,46656,823543,16777216,387420489,10000000000,

%T 285311670611,8916100448256,302875106592253,11112006825558016,

%U 437893890380859375,18446744073709551616,827240261886336764177,39346408075296537575424,1978419655660313589123979

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

%C Also number of labeled pointed rooted trees (or vertebrates) on n nodes.

%C 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

%C 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

%C 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

%C 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 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

%C 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

%C Also smallest k such that binomial(k, n) is divisible by n^(n-1), n > 0. - _Michel Lagneau_, Jul 29 2013

%C For n >= 2 a(n) is represented in base n as "one followed by n zeros". - _R. J. Cano_, Aug 22 2014

%C Number of length-n words over the alphabet of n letters. - _Joerg Arndt_, May 15 2015

%C Number of prime parking functions of length n+1. - _Rui Duarte_, Jul 27 2015

%C 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

%C Satisfies Benford's law [Miller, 2015]. - _N. J. A. Sloane_, Feb 12 2017

%C 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

%C From _Juhani Heino_, May 07 2019: (Start)

%C n^n is both Sum_{i=0..n} binomial(n,i)*(n-1)^(n-i)

%C   and Sum_{i=0..n} binomial(n,i)*(n-1)^(n-i)*i.

%C 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.

%C Examples:

%C 2-sided dice (2 coins): 4 = 1 + 2 + 1 = 1*0 + 2*1 + 1*2 (0 omitted from now on);

%C 3-sided dice (3 long triangular prisms): 27 = 8 + 12 + 6 + 1 = 12*1 + 6*2 + 1*3;

%C 4-sided dice (4 long square prisms or 4 tetrahedrons): 256 = 81 + 108 + 54 + 12 + 1 = 108*1 + 54*2 + 12*3 + 1*4;

%C 5-sided dice (5 long pentagonal prisms): 3125 = 1024 + 1280 + 640 + 160 + 20 + 1 = 1280*1 + 640*2 + 160*3 + 20*4 + 1*5;

%C 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.

%C (End)

%C 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

%C 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

%D F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Cambridge, 1998, pp. 62, 63, 87.

%D L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 173, #39.

%D 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)

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Kenny Lau, <a href="/A000312/b000312.txt">Table of n, a(n) for n = 0..385</a> [First 100 terms computed by T. D. Noe]

%H Taylor Ball, David Galvin, Katie Hyry, and Kyle Weingartner, <a href="https://arxiv.org/abs/1901.06579">Independent set and matching permutations</a>, arXiv:1901.06579 [math.CO], 2019.

%H Arthur T. Benjamin and Fritz Juhnke, <a href="http://dx.doi.org/10.1137/0405028">Another way of counting n^n</a>, SIAM J. Discrete Math., Vol. 5, No. 3 (1992), pp. 377-379. - _N. J. A. Sloane_, Jun 09 2011

%H H. Bottomley, <a href="/A000312/a000312.gif">Illustration of initial terms</a>.

%H H. J. Brothers and J. A. Knox, <a href="http://www.brotherstechnology.com/docs/mi_paper1.pdf">New closed-form approximations to the logarithmic constant e</a>, The Mathematical Intelligencer,  Vol. 20 (4), 1998, pp. 25-29. (Sequence appears as formula in Eq. (8))

%H C. Chauve, S. Dulucq and O. Guibert, <a href="http://www.cecm.sfu.ca/~cchauve/Publications/SFCA00.ps">Enumeration of some labeled trees</a>, Proceedings of FPSAC/SFCA 2000 (Moscow), Springer, pp. 146-157.

%H Frank Ellermann, <a href="/A001792/a001792.txt">Illustration of binomial transforms</a>.

%H José María Grau and Antonio M. Oller-Marcén, <a href="https://doi.org/10.4134/BKMS.2014.51.5.1325">On the last digit and the last non-zero digit of n^n in base b</a>, Bulletin of the Korean Mathematical Society, Vol. 51, No. 5 (2014), pp. 1325-1337; <a href="http://arxiv.org/abs/1203.4066">arXiv preprint</a>, arXiv:1203.4066 [math.NT], 2012.

%H 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 INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=36">Encyclopedia of Combinatorial Structures 36</a>.

%H Steven J. Miller (ed.), <a href="https://web.williams.edu/Mathematics/sjmiller/public_html/benford/BenfordBook_final_homework20.pdf">Exercises to “The Theory and Applications of Benford’s Law”</a>, Princeton University Press, 2015.

%H Mustafa Obaid et al., <a href="https://arxiv.org/abs/1307.7573">The number of complete exceptional sequences for a Dynkin algebra</a>, arXiv preprint arXiv:1307.7573 [math.RT], 2013.

%H Franck Ramaharo, <a href="https://arxiv.org/abs/1805.10680">A generating polynomial for the pretzel knot</a>, arXiv:1805.10680 [math.CO], 2018.

%H E. Vigren (Proposer), <a href="https://www.tandfonline.com/doi/full/10.1080/00029890.2023.2252314">Problem 12432</a>, Amer. Math. Monthly 130 (2023), p. 953.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/HadamardsMaximumDeterminantProblem.html">Hadamard's Maximum Determinant Problem</a>.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/HankelMatrix.html">Hankel Matrix</a>.

%H Dimitri Zvonkine, <a href="https://arxiv.org/abs/math/0403092">An algebra of power series...</a>, arXiv:math/0403092 [math.AG], 2004.

%H <a href="/index/Cor#core">Index entries for "core" sequences</a>

%H <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>

%H <a href="/index/Be#Benford">Index entries for sequences related to Benford's law</a>

%F 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

%F E.g.f.: 1/(1 + W(-x)), W(x) = principal branch of Lambert's function.

%F 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

%F E.g.f.: 1/(1 - T), where T = T(x) is Euler's tree function (see A000169).

%F a(n) = A000169(n+1)*A128433(n+1,1)/A128434(n+1,1). - _Reinhard Zumkeller_, Mar 03 2007

%F 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

%F 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

%F 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

%F 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

%F a(n) = denominator((1 + 1/n)^n) for n > 0. - _Jean-François Alcover_, Jan 14 2013

%F a(n) = A089072(n,n) for n > 0. - _Reinhard Zumkeller_, Mar 18 2013

%F 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

%F log(a(n)) = lim_{k->infinity} k*(n^(1+1/k) - n). - _Richard R. Forberg_, Feb 04 2015

%F From _Ilya Gutkovskiy_, Jun 18 2016: (Start)

%F Sum_{n>=1} 1/a(n) = 1.291285997... = A073009.

%F Sum_{n>=1} 1/a(n)^2 = 1.063887103... = A086648.

%F Sum_{n>=1} n!/a(n) = 1.879853862... = A094082. (End)

%F A000169(n+1)/a(n) -> e, as n -> oo. - _Daniel Suteu_, Jul 23 2016

%F 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

%F 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

%F Sum_{n>=1} (-1)^(n+1)/a(n) = A083648. - _Amiram Eldar_, Jun 25 2021

%F Limit_{n->oo} (a(n+1)/a(n) - a(n)/a(n-1)) = e (see Brothers/Knox link). - _Harlan J. Brothers_, Oct 24 2021

%F 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

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

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

%t Array[ #^# &, 16] (* _Vladimir Joseph Stephan Orlovsky_, May 01 2008 *)

%t Table[Sum[StirlingS2[n, i] i! Binomial[n, i], {i, 0, n}], {n, 0, 20}] (* _Geoffrey Critzer_, Mar 17 2009 *)

%t a[ n_] := If[ n < 1, Boole[n == 0], n^n]; (* _Michael Somos_, May 24 2014 *)

%t a[ n_] := If[ n < 0, 0, n! SeriesCoefficient[ 1 / (1 + LambertW[-x]), {x, 0, n}]]; (* _Michael Somos_, May 24 2014 *)

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

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

%o (PARI) {a(n) = n^n};

%o (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

%o (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 */

%o (Haskell)

%o a000312 n = n ^ n

%o a000312_list = zipWith (^) [0..] [0..]  -- _Reinhard Zumkeller_, Jul 07 2012

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

%o makelist(A000312[n],n,0,30); /* _Martin Ettl_, Oct 29 2012 */

%o (Python)

%o def A000312(n): return n**n # _Chai Wah Wu_, Nov 07 2022

%Y Cf. A000107, A000169, A000272, A001372, A007778, A007830, A008785-A008791, A019538, A048993, A008279, A085741, A062206, A212333.

%Y First column of triangle A055858. Row sums of A066324.

%Y Cf. A001923 (partial sums), A002109 (partial products), A007781 (first differences), A066588 (sum of digits).

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

%Y Cf. A174824, A204688.

%Y Cf. A055137, A083648.

%K nonn,easy,core,nice

%O 0,3

%A _N. J. A. Sloane_