|
|
A000312
|
|
Number of labeled mappings from n points to themselves (endofunctions): n^n.
(Formerly M3619 N1469)
|
|
335
|
|
|
1, 1, 4, 27, 256, 3125, 46656, 823543, 16777216, 387420489, 10000000000, 285311670611, 8916100448256, 302875106592253, 11112006825558016, 437893890380859375, 18446744073709551616, 827240261886336764177
(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, sum_{i=1}^{p(n)} = sum over i and prod_{j=1}^{d(i)} = product over j one has: a(n) = sum_{i=1}^{p(n)} (n!/(prod_{j=1}^{p(i)}p(i, j)!)) * ((n!/(n-p(i)))!/(prod_{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) = 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
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
Denominator of (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
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
|
|
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
|
T. D. Noe, Table of n, a(n) for n = 0..100
A. T. Benjamin and F. Juhnke, Another way of counting n^n, SIAM J. Discrete Math., 5 (1992). 377-379. [From N. J. A. Sloane, Jun 09 2011]
H. Bottomley, Illustration of initial terms
C. Chauve, S. Dulucq and O. Guibert, Enumeration of some labeled trees, Proceedings of FPSAC/SFCA 2000 (Moscow), Springer, pp. 146-157.
F. Ellermann, Illustration of binomial transforms
N. Hobson, Exponential equation.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 36
Mustafa Obaid et al., The number of complete exceptional sequences for a Dynkin algebra, arXiv preprint arXiv:1307.7573, 2013
Eric Weisstein's World of Mathematics, Hadamard's Maximum Determinant Problem
Eric Weisstein's World of Mathematics, Hankel Matrix
D. 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
|
|
FORMULA
|
a(n-1) = -sum( (-1)^i * i * n^(n-1-i)*binomial(n, i), i=1..n). - 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, C(n, k)*Stirling2(n, k)*k!) = Sum(k>=0, A008279(n, k)*A048993(n, k)) = Sum(k>=0, A019538(n, k)*A07318(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..infinity} 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}C(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) = (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->Inf} k*(n^(1+1/k) - n). - Richard R. Forberg, Feb 04 2015
|
|
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;
|
|
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 *)
Table[Hyperfactorial[n]/Hyperfactorial[n - 1], {n, 0, 17}] (* Zerinvary Lajos, Jul 10 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).
Sequence in context: A070271 A245414 * A177885 A086783 A050764 A240582
Adjacent sequences: A000309 A000310 A000311 * A000313 A000314 A000315
|
|
KEYWORD
|
nonn,easy,core,nice
|
|
AUTHOR
|
N. J. A. Sloane
|
|
STATUS
|
approved
|
|
|
|