A066324 -id:A066324 - cp's OEIS frontend

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

1, 1, 4, 27, 256, 3125, 46656, 823543, 16777216, 387420489, 10000000000, 285311670611, 8916100448256, 302875106592253, 11112006825558016, 437893890380859375, 18446744073709551616, 827240261886336764177, 39346408075296537575424, 1978419655660313589123979

Offset: 0

N. J. A. Sloane

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, 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
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) 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
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
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
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
Satisfies Benford's law [Miller, 2015]. - N. J. A. Sloane, Feb 12 2017
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
From Juhani Heino, May 07 2019: (Start)
n^n is both Sum_{i=0..n} binomial(n,i)*(n-1)^(n-i)
  and Sum_{i=0..n} binomial(n,i)*(n-1)^(n-i)*i.
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.
Examples:
2-sided dice (2 coins): 4 = 1 + 2 + 1 = 1*0 + 2*1 + 1*2 (0 omitted from now on);
3-sided dice (3 long triangular prisms): 27 = 8 + 12 + 6 + 1 = 12*1 + 6*2 + 1*3;
4-sided dice (4 long square prisms or 4 tetrahedrons): 256 = 81 + 108 + 54 + 12 + 1 = 108*1 + 54*2 + 12*3 + 1*4;
5-sided dice (5 long pentagonal prisms): 3125 = 1024 + 1280 + 640 + 160 + 20 + 1 = 1280*1 + 640*2 + 160*3 + 20*4 + 1*5;
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.
(End)
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
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
Also, dimension of the unique cohomology group of the smallest interval containing the poset of partitions decorated by Perm, i.e. the poset of pointed partitions. - Bérénice Delcroix-Oger, Jun 25 2025

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

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

Kenny Lau, Table of n, a(n) for n = 0..385 [First 100 terms computed by T. D. Noe]
Taylor Ball, David Galvin, Katie Hyry, and Kyle Weingartner, Independent set and matching permutations, arXiv:1901.06579 [math.CO], 2019.
Arthur T. Benjamin and Fritz Juhnke, Another way of counting n^n, SIAM J. Discrete Math., Vol. 5, No. 3 (1992), pp. 377-379. - _N. J. A. Sloane_, Jun 09 2011
H. Bottomley, Illustration of initial terms.
H. J. Brothers and J. A. Knox, New closed-form approximations to the logarithmic constant e, The Mathematical Intelligencer, Vol. 20 (4), 1998, pp. 25-29. (Sequence appears as formula in Eq. (8))
C. Chauve, S. Dulucq and O. Guibert, Enumeration of some labeled trees, Proceedings of FPSAC/SFCA 2000 (Moscow), Springer, pp. 146-157.
Bérénice Delcroix-Oger and Clément Dupont, Lie-operads and operadic modules from poset cohomology, arXiv:2505.06094 [math.CO], 2025. See p. 34.
Frank Ellermann, Illustration of binomial transforms.
José María Grau and Antonio M. Oller-Marcén, On the last digit and the last non-zero digit of n^n in base b, Bulletin of the Korean Mathematical Society, Vol. 51, No. 5 (2014), pp. 1325-1337; arXiv preprint, arXiv:1203.4066 [math.NT], 2012.
Nick Hobson, Solution to puzzle 48: Exponential equation.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 36.
Steven J. Miller (ed.), Exercises to "The Theory and Applications of Benford's Law", Princeton University Press, 2015.
Mustafa Obaid et al., The number of complete exceptional sequences for a Dynkin algebra, arXiv preprint arXiv:1307.7573 [math.RT], 2013.
Franck Ramaharo, A generating polynomial for the pretzel knot, arXiv:1805.10680 [math.CO], 2018.
E. Vigren (Proposer), Problem 12432, Amer. Math. Monthly 130 (2023), p. 953.
Elena L. Wang and Guoce Xin, On Ward Numbers and Increasing Schröder Trees, arXiv:2507.15654 [math.CO], 2025. See pp. 12-13.
Eric Weisstein's World of Mathematics, Hadamard's Maximum Determinant Problem.
Eric Weisstein's World of Mathematics, Hankel Matrix.
Dimitri 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
Index entries for sequences related to Benford's law

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. A001923 (partial sums), A002109 (partial products), A007781 (first differences), A066588 (sum of digits).
Cf. A056665, A081721, A130293, A168658, A275549-A275558 (various classes of endofunctions).
Cf. A174824, A204688.
Cf. A055137, A083648.

a000312 n = n ^ n
a000312_list = zipWith (^) [0..] [0..]  -- Reinhard Zumkeller, Jul 07 2012

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

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

A000312[n]:=if n=0 then 1 else n^n$
makelist(A000312[n],n,0,30); /* Martin Ettl, Oct 29 2012 */

PARI
```
{a(n) = n^n};
```

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

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

def A000312(n): return n**n # Chai Wah Wu, Nov 07 2022

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
E.g.f.: 1/(1 + W(-x)), W(x) = principal branch of Lambert's function.
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
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} 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} binomial(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) = denominator((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
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->infinity} k*(n^(1+1/k) - n). - Richard R. Forberg, Feb 04 2015
From Ilya Gutkovskiy, Jun 18 2016: (Start)
Sum_{n>=1} 1/a(n) = 1.291285997... = A073009.
Sum_{n>=1} 1/a(n)^2 = 1.063887103... = A086648.
Sum_{n>=1} n!/a(n) = 1.879853862... = A094082. (End)
A000169(n+1)/a(n) -> e, as n -> oo. - Daniel Suteu, Jul 23 2016
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
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
Sum_{n>=1} (-1)^(n+1)/a(n) = A083648. - Amiram Eldar, Jun 25 2021
Limit_{n->oo} (a(n+1)/a(n) - a(n)/a(n-1)) = e (see Brothers/Knox link). - Harlan J. Brothers, Oct 24 2021
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 19 2022

A001864 Total height of rooted trees with n labeled nodes.

Original entry on oeis.org

0, 2, 24, 312, 4720, 82800, 1662024, 37665152, 952401888, 26602156800, 813815035000, 27069937855488, 972940216546896, 37581134047987712, 1552687346633913000, 68331503866677657600, 3191386068123595166656, 157663539876436721860608

Offset: 1

N. J. A. Sloane

a(n) is the total number of nonrecurrent elements mapped into a recurrent element in all functions f:{1,2,...,n}->{1,2,...,n}. a(n) = Sum_{k=1..n-1} A216971(n,k)*k. - Geoffrey Critzer, Jan 01 2013

a(n) is the sum of the lengths of all cycles over all functions f:{1,2,...,n}->{1,2,...,n}. Fixed points are taken to have length zero. a(n) = Sum_{k=2..n} A066324(n,k)*(k-1). - Geoffrey Critzer, Aug 19 2013

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

T. D. Noe, Table of n, a(n) for n = 1..100
Hien D. Nguyen and G. J. McLachlan, Progress on a Conjecture Regarding the Triangular Distribution, arXiv preprint arXiv:1607.04807 [stat.OT], 2016.
J. Riordan, Letter to N. J. A. Sloane, Aug. 1970
J. Riordan and N. J. A. Sloane, Enumeration of rooted trees by total height, J. Austral. Math. Soc., vol. 10 pp. 278-282, 1969.
N. J. A. Sloane, Illustration of terms a(3) and a(4) in A000435
D. Zvonkine, Home Page
D. Zvonkine, An algebra of power series arising in the intersection theory of moduli spaces of curves and in the enumeration of ramified coverings of the sphere, arXiv:0403092v2 [math.AG], 2004.
D. Zvonkine, Enumeration of ramified coverings of the sphere and 2-dimensional gravity, arXiv:math/0506248 [math.AG], 2005.
D. Zvonkine, Counting ramified coverings and intersection theory on Hurwitz spaces II (local structure of Hurwitz spaces and combinatorial results), Moscow Mathematical Journal, vol. 7 (2007), no. 1, 135-162.
Index entries for sequences related to rooted trees
Index entries for sequences related to trees

Cf. A000435, A001863.

A001864 := proc(n) local k; add(n!*n^k/k!, k=0..n-2); end;

Table[Sum[Binomial[n,k](n-k)^(n-k) k^k,{k,1,n-1}],{n,20}] (* Harvey P. Dale, Oct 10 2011 *)
a[n_] := n*(n-1)*Exp[n]*Gamma[n-1, n] // Round; Table[a[n], {n, 1, 18}]  (* Jean-François Alcover, Jun 24 2013 *)

a(n)=sum(k=1,n-1,binomial(n,k)*(n-k)^(n-k)*k^k)

from math import comb
def A001864(n): return (sum(comb(n,k)*(n-k)**(n-k)*k**k for k in range(1,(n+1>>1)))<<1) + (0 if n&1 else comb(n,m:=n>>1)*m**n) # Chai Wah Wu, Apr 25-26 2023

a(n) = n*A000435(n).
E.g.f: (LambertW(-x)/(1+LambertW(-x)))^2. - Vladeta Jovovic, Apr 10 2001
a(n) = Sum_{k=1..n-1} binomial(n, k)*(n-k)^(n-k)*k^k. - Benoit Cloitre, Mar 22 2003
a(n) ~ sqrt(Pi/2)*n^(n+1/2). - Vaclav Kotesovec, Aug 07 2013
a(n) = n! * Sum_{k=0..n-2} n^k/k!. - Jianing Song, Aug 08 2022

A190314 The number of cycles in the digraph representation of all endofunctions on {1,2,...,n}.

Original entry on oeis.org

0, 1, 5, 38, 390, 5049, 78960, 1447886, 30461872, 723267369, 19130274880, 557794986814, 17775137850624, 614607897664305, 22917282895782912, 916671255921364950, 39152092883971954688, 1778431981539189344177, 85607684151779322519552, 4353142694568849287025142, 233169669255877689516032000

Offset: 0

Geoffrey Critzer, May 08 2011

nonn

Equivalently, since each component contains exactly one cycle, a(n) is the number of connected components in all endofuntions on {1,2,...,n}.  An endofunction on {1,2,...,n} is a function from {1,2,...,n} into {1,2,...,n}. Here we are counting self loops as a cycle.
The total number of j-cycles over all functions on {1,2,...,n} is (j-1)!*binomial(n,j)*n^(n-j). - Geoffrey Critzer, Dec 26 2012
a(n) was "not easy to estimate" in 1953 according to the Metropolis-Ulam reference. - David Callan, Jun 15 2018

			a(2) = 5 because there are four functions from {1,2} into {1,2} but only one of these is not connected: 1->1,2->2 so there is a total of 5 components in all. - _Geoffrey Critzer_, Mar 22 2012

Alois P. Heinz, Table of n, a(n) for n = 0..150
Giulio Cerbai and Anders Claesson, Counting fixed-point-free Cayley permutations, arXiv:2507.09304 [math.CO], 2025. See p. 23.
N. Metropolis and S. Ulam, A Property of Randomness of an Arithmetical Function, American Mathematical Monthly, Vol. 60, No. 4 (Apr., 1953), pp. 252-253.

Cf. A060281.

a:= n-> add((k-1)!*binomial(n, k)*n^(n-k), k=1..n):
seq(a(n), n=0..20);  # Alois P. Heinz, Dec 26 2012

f[list_] := Total[Table[i * list[[i]], {i,1,Length[list]}]]; t=Sum[n^(n-1)x^n/n!, {n,1,20}]; Map[f,Transpose[Table[Drop[Range[0,20]! CoefficientList[Series[Log[1/(1-t)]^k/k!, {x,0,20}], x], 1], {k,0,20}]]]
nmax = 20; CoefficientList[Series[-Log[1 + LambertW[-x]]/(1 + LambertW[-x]), {x, 0, nmax}], x] * Range[0, nmax]! (* Vaclav Kotesovec, Jun 09 2019 *)

E.g.f.: Log[1/(1-T(x))]/(1-T(x)) where T(x) is the e.g.f. for A000169. - Geoffrey Critzer, Mar 22 2012
a(n) = Sum_{k=1..n} (k-1)!*C(n,k)*n^(n-k). - Geoffrey Critzer, Dec 26 2012
a(n) ~ n^n*(log(2*n) + gamma)/2, where gamma is the Euler-Mascheroni constant (A001620). - Vaclav Kotesovec, Oct 08 2013
a(n) = Sum_{k=1..n} A066324(n,k)*H(k) where H(k) is the k-th harmonic number. - Geoffrey Critzer, Nov 02 2014
a(n) = n! * [x^n] -exp(n*x)*log(1 - x). - Ilya Gutkovskiy, Jan 18 2018
a(n) = Sum_{k=1..n} k * A060281(n,k). - Alois P. Heinz, Dec 15 2021
Conjectures from Velin Yanev, Apr 14 2024: (Start)
a(n) = (n^n)*Integral_{t=0..oo} ((t + 1)^n - 1)/(t*e^(n*t)) dt for n > 0.
a(n) = (e^n)*Gamma(n) + (n^n)*(n*hypergeom([1, 1], [2, n + 2], n)/(n + 1) - ((-1)^n)*Gamma(n)*Gamma(1 - n, -n) + log(n) - polygamma(n) - 1/n + i*Pi) for n > 0, where polygamma is the digamma function and the bivariate gamma function is the upper incomplete gamma function. (End)

A063169 a(n) = n*A001865(n).

Original entry on oeis.org

1, 6, 51, 568, 7845, 129456, 2485567, 54442368, 1339822377, 36602156800, 1099126705611, 35986038303744, 1275815323139149, 48693140873545728, 1990581237014772375, 86778247940387209216, 4018626330009931930833, 197009947951733259436032, 10193206233792610863520867

Offset: 1

Marijke van Gans (marijke(AT)maxwellian.demon.co.uk)

Schenker sums without n-th term.
a(n)/n^n = Q(n) (called Ramanujan's function by Knuth).
Urn, n balls, with replacement: how many selections before a ball is chosen that was chosen already? Expected value is a(n)/n^n.
a(n) is the total number of recurrent elements over all endofunctions on n labeled points. a(n) = Sum_{k=1..n} A066324(n,k)*k. - Geoffrey Critzer, Dec 05 2011

			a(4) = (1*2*3*4) + 4*(2*3*4) + 4*4*(3*4) + 4*4*4*(4) = 568.

D. E. Knuth, The Art of Computer Programming, 3rd ed. 1997, Vol. 1, Addison-Wesley, Reading, MA, 1.2.11.3 p. 116

Alois P. Heinz, Table of n, a(n) for n = 1..150
Marijke van Gans, Schenker sums
Don Zagier, Partitions, Modular Forms and Moduli Spaces, Youtube video of a lecture at Institut Henri Poincaré, Feb 28 2017.

Cf. A001865, A066324, A219706.

Flatten[Range[0, 20]! CoefficientList[Series[D[1/(1 - y t), y] /. y -> 1, {x, 0, 20}], {x, y}]]
(* Second program: *)
a[n_] := Exp[n]*Gamma[n+1, n] - n^n; Array[a, 19] (* Jean-François Alcover, Jan 25 2018 *)

a(n)=sum(k=1,n,binomial(n,k)*n^(n-k)*k!) /* Michael Somos, Jun 09 2004 */

a(n)=sum(k=1,n,binomial(n,k)*(n-k)^(n-k)*k^k) \\ Paul D. Hanna, Jul 04 2013

a(n)=sum(k=0,n-1,n!/k!*n^k) \\ Ruud H.G. van Tol, Jan 14 2023

from math import comb
def A063169(n): return (sum(comb(n,k)*(n-k)**(n-k)*k**k for k in range(1,(n+1>>1)))<<1) + (0 if n&1 else comb(n,m:=n>>1)*m**n) + n**n # Chai Wah Wu, Apr 25-26 2023

10 for N=1 to 42 : T=N^N : S=0
20 for K=N to 1 step -1 : T/=N : T*=K : S+=T : next K
30 print N,S : next N

a(n) = Sum_{k=0..n-1} n^k * n!/k!.
a(n)/n! = Sum_{k=0..n-1} n^k/k! (first n terms of e^n power series).
E.g.f.: T/(1-T)^2, where T=T(x) is Euler's tree function (see A000169) - Len Smiley, Nov 28 2001
E.g.f.: -LambertW(-x)/(1+LambertW(-x))^2. - Alois P. Heinz, Nov 16 2011
a(n) = A063170(n) - n^n.
a(n) = Sum_{k=1..n} C(n,k) * (n-k)^(n-k) * k^k. - Paul D. Hanna, Jul 04 2013
a(n) ~ n^(n+1/2)*sqrt(Pi/2). - Vaclav Kotesovec, Oct 05 2013
a(n) = Sum_{k=1..n} (n!/(n-k)!) * k^2 * n^(n-k-1). - Brian P Hawkins, Feb 07 2024

A122525 Triangle read by rows: G(s, rho) = ((s-1)!/s)Sum_{i=0..s-1} ((s-i)/i!)(s*rho)^i.

Original entry on oeis.org

1, 1, 1, 2, 4, 3, 6, 18, 24, 16, 24, 96, 180, 200, 125, 120, 600, 1440, 2160, 2160, 1296, 720, 4320, 12600, 23520, 30870, 28812, 16807, 5040, 35280, 120960, 268800, 430080, 516096, 458752, 262144, 40320, 322560, 1270080, 3265920, 6123600, 8817984, 9920232, 8503056, 4782969

Offset: 1

Arie Harel, Sep 14 2006

When s is a positive integer and 0 < rho < 1 then C(s,rho):=(s*rho)^s/G(s,rho)/s is the well-known Erlang delay (or the Erlang's C) formula. This measure is a basic formula of queueing theory. The applications of this formula are in diverse systems where queueing phenomena arise, including telecommunications, production, and service systems. The formula gives the steady-state probability of delay in the M/M/s queueing system. The number of servers is denoted by s and the traffic intensity is denoted by rho, 0 < rho < 1, where rho=(arrival rate)/(service rate)/s.

With offset = 0, T(n,n-k) is the number of partial functions on {1,2,...,n} with exactly k recurrent elements for 0 <= k <= n. Row sums = (n+1)^n. - Geoffrey Critzer, Sep 08 2012

			G(5, rho) = 24 + 96*rho + 180*rho^2 + 200*rho^3 + 125*rho^4. The coefficients (24, 96, 180, 200, 125) give the 5th line of the triangle.
Triangle begins:
      1;
      1,      1;
      2,      4,       3;
      6,     18,      24,      16;
     24,     96,     180,     200,     125;
    120,    600,    1440,    2160,    2160,    1296;
    720,   4320,   12600,   23520,   30870,   28812,   16807;
   5040,  35280,  120960,  268800,  430080,  516096,  458752,  262144;
  40320, 322560, 1270080, 3265920, 6123600, 8817984, 9920232, 8503056, 4782969;

Cooper, R. B. 1981, Introduction to Queueing Theory. Second ed., North Holland, New York.
Harel, A. 1988. Sharp Bounds and Simple Approximations for the Erlang Delay and Loss Formulas. Management Science, Vol. 34, 959-972.
Harel, A. and P. Zipkin. 1987a. Strong Convexity Results for Queueing Systems. Operations Research, Vol. 35, No. 3, 405-418.
Harel, A. and P. Zipkin. 1987b. The Convexity of a General Performance Measure for the Multi-Server Queues. Journal of Applied Probability, Vol. 24, 725-736.
Jagers, A. A. and E. A. van Doorn, 1991. Convexity of functions which are generalizations of the Erlang loss function and the Erlang delay function. SIAM Review. Vol. 33 (2), 281-282.
Lee, H. L. and M. A. Cohen. 1983. A Note on the Convexity of Performance Measures of M/M/c Queueing Systems. Journal of Applied Probability, Vol. 20, 920-923.
Medhi, J. 2003. Stochastic Models in Queueing Theory. Second ed., Academic Press, New York.
Smith, D.R. and W. Whitt. 1981. Resource Sharing for Efficiency in Traffic Systems. Bell System Technical Journal, Vol. 60, No. 1, 39-55.

Alois P. Heinz, Rows n = 1..141, flattened
C. W. J. Beenakker, Entropy and singular-value moments of products of truncated random unitary matrices, arXiv:2501.11085 [quant-ph], 2025. See p. 6.
E. Brockmeyer, H. L. Halstrøm and Arne Jensen, The Life and Works of A.K. Erlang

Cf. A066324, A137216, A137227.

G:= proc(s) G(s):= (s-1)!/s*add((s-i)/i!*(s*rho)^i, i=0..(s-1)) end:
T:= n-> coeff(G(n), rho, k):
seq(seq(T(n, k), k=0..n-1), n=1..10);  # Alois P. Heinz, Sep 08 2012

(* First program *)
nn=6; t=Sum[n^(n-1)x^n/n!,{n,1,nn}]; f[list_]:=Select[list,#>0&]; Map[f,Map[Reverse,Range[0,nn]!CoefficientList[Series[Exp[t]/(1-y t),{x,0,nn}],{x,y}]]]//Grid  (* Geoffrey Critzer, Sep 08 2012 *)
(* Second program *)
T[n_, k_]:= Coefficient[Series[((n-1)!/n)*Sum[(n-j)*(n*x)^j/j!, {j,0,n-1}], {x,0,30}], x, k];
Table[T[n, k], {n,10}, {k,0,n-1}]//Flatten (* G. C. Greubel, Jan 06 2022 *)

def A122525(n,k): return ( (factorial(n-1)/n)*sum((n-j)*(n*x)^j/factorial(j) for j in (0..n-1)) ).series(x, n+1).list()[k]
flatten([[A122525(n,k) for k in (0..n-1)] for n in (1..12)]) # G. C. Greubel, Jan 06 2022

An equivalent expression for G(s, rho) that is often used is: G(s, rho) = (1-rho)*(s-1)!*Sum_{i=0..s-1} (s^i*rho^i/i!) + rho^s*s^(s-1).
For s > 0 and rho > 0 one can use the expression: G(s, rho) = (exp(s*rho)*s*rho*(1-rho)*(s-1)*Gamma(s-1, s*rho) + rho^s*s^s)/(s*rho).
For s > 0 and rho > 0 one can also use the integral representation G(s, rho) = ((s*rho)^s/s)*Integral_{t=0..oo} rho*s*exp(-rho*s*t)*t*(1+t)^(s-1) dt.
Multiplying the n-th row entries by n+1 results in triangle A066324 in row reversed form. - Peter Bala, Sep 30 2011
Row generating polynomials are given by (1/n)*D^n(1/(1-x*t)) evaluated at x = 0, where D is the operator exp(x)/(1-x)*d/dx. - Peter Bala, Dec 27 2011

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Maxima

PARI

PARI

PARI

Python

Formula

A001864 Total height of rooted trees with n labeled nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

A190314 The number of cycles in the digraph representation of all endofunctions on {1,2,...,n}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A063169 a(n) = n*A001865(n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

PARI

PARI

Python

UBASIC

Formula

A122525 Triangle read by rows: G(s, rho) = ((s-1)!/s)*Sum_{i=0..s-1} ((s-i)/i!)*(s*rho)^i.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Sage

Formula

A243203 Terms of a particular integer decomposition of N^N.

Views

Author

A122525 Triangle read by rows: G(s, rho) = ((s-1)!/s)Sum_{i=0..s-1} ((s-i)/i!)(s*rho)^i.