|
| |
|
|
A000312
|
|
Number of labeled mappings from n points to themselves (endofunctions): n^n.
(Formerly M3619 N1469)
|
|
251
|
|
|
|
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. - From 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
|
|
|
REFERENCES
|
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]
F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Cambridge, 1998, pp. 62, 63, 87.
C. Chauve, S. Dulucq and O. Guibert, Enumeration of some labeled trees, Proceedings of FPSAC/SFCA 2000 (Moscow), Springer, p 146-157.
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
H. Bottomley, Illustration of initial terms
F. Ellermann, Illustration of binomial transforms
N. Hobson, Exponential equation.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 36
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...
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..oo} x^n/n^n. Then as x -> oo, f(x) ~ exp(x/e)*sqrt(2*Pi*x/e). - Philippe Flajolet, Sep 11 2008
E.g.f.: 1-exp(W(-x)), W(x) - principal branch of Lambert's function. [From 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). [From Vladimir Shevelev, Sep 30 2010]
Row sums of A066324.
With an offset of 1, the e.g.f. is the compositional inverse ((x-1)*ln(1-x))^(-1) = x + x^2/2!+ 4*x^3/3! + 27*x^4/4! + .... - Peter Bala, Dec 09, 2011
|
|
|
MAPLE
|
A000312 := n->n^n;
|
|
|
MATHEMATICA
|
Array[ #^# &, 16] (from Vladimir Joseph Stephan Orlovsky, May 01 2008)
a[n + 1]/(a[n] E)== Limit[Product[x^(1/k), {x, n - 1 + 1/k, n, 1/k}], k -> Infinity], Replace n>=1 with a integer for solving in Mathematica 7. [From Deep Blue (dblue2001(AT)hotmail.com), Dec 28 2008]
a[n + 1]/(a[n] E)== Limit[Product[x^k, {x, n - 1 + k, n, k}], k -> 0] (* Replace n>=1 with an integer for solving in Mathematica 7. [From Deep Blue (dblue2001(AT)hotmail.com), Dec 28 2008] *)
Table[Sum[StirlingS2[n, i] i! Binomial[n, i], {i, 0, n}], {n, 0, 20}] [From Geoffrey Critzer, Mar 17 2009]
Table[Hyperfactorial[n]/Hyperfactorial[n - 1], {n, 0, 17}] [From Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Jul 10 2009]
|
|
|
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
(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.
Sequence in context: A067040 A070271 * A177885 A086783 A050764 A177379
Adjacent sequences: A000309 A000310 A000311 * A000313 A000314 A000315
|
|
|
KEYWORD
|
nonn,easy,core,nice
|
|
|
AUTHOR
|
N. J. A. Sloane.
|
|
|
EXTENSIONS
|
Cf. A002109 (partial products).
|
|
|
STATUS
|
approved
|
| |
|
|
