login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000312 Number of labeled mappings from n points to themselves (endofunctions): n^n.
(Formerly M3619 N1469)
318
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

REFERENCES

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

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

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

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)*ln(1-x))^(-1) = x + x^2/2!+ 4*x^3/3! + 27*x^4/4! + .... - Peter Bala, Dec 09, 2011

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

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

Content is available under The OEIS End-User License Agreement .

Last modified October 21 00:03 EDT 2014. Contains 248371 sequences.