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

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

Offset

1,2

Comments

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

References

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

Links

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.

Formula

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

Example

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

Mathematica

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

Prog

(UBASIC)
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
(PARI) a(n)=sum(k=1, n, binomial(n, k)*n^(n-k)*k!) /* Michael Somos, Jun 09 2004 */
(PARI) a(n)=sum(k=1, n, binomial(n, k)*(n-k)^(n-k)*k^k) \\ Paul D. Hanna, Jul 04 2013
(PARI) a(n)=sum(k=0, n-1, n!/k!*n^k) \\ Ruud H.G. van Tol, Jan 14 2023
(Python)
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

Crossrefs

Cf. A001865, A066324, A219706.

Sequence in context: A057817 A000405 A113352 * A346667 A246189 A293128

Adjacent sequences: A063166 A063167 A063168 * A063170 A063171 A063172

Keyword

nonn,easy,nice

Author

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

Status

approved