login
This site is supported by donations 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)
434

%I M3619 N1469

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

%T 285311670611,8916100448256,302875106592253,11112006825558016,

%U 437893890380859375,18446744073709551616,827240261886336764177

%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) = 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 Lim_{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 Denominator of (1 + 1/n)^n for n > 0. - _Jean-François Alcover_, Jan 14 2013

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

%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

%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 A. T. Benjamin and F. Juhnke, <a href="http://dx.doi.org/10.1137/0405028">Another way of counting n^n</a>, SIAM J. Discrete Math., 5 (1992). 377-379. - _N. J. A. Sloane_, Jun 09 2011

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

%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 F. Ellermann, <a href="/A001792/a001792.txt">Illustration of binomial transforms</a>

%H José María Grau and Antonio M. Oller-Marcén, <a href="http://arxiv.org/abs/1203.4066">On the last digit and the last non-zero digit of n^n in base b</a>, arXiv:1203.4066 [math.NT], 2012.

%H N. Hobson, <a href="http://www.qbyte.org/puzzles/p048s.html">Exponential equation</a>.

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

%H S. J. Miller, SJ (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>, 2015.

%H Mustafa Obaid et al., <a href="http://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 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 D. Zvonkine, <a href="http://www.arXiv.org/abs/math.AG/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) = (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->inf} 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

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

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

%Y Cf. A001923 (partial sums).

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

%Y Cf. A174824, A204688.

%K nonn,easy,core,nice

%O 0,3

%A _N. J. A. Sloane_

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 20 18:08 EDT 2018. Contains 316401 sequences. (Running on oeis4.)