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
KEYWORD
nonn,easy,nice
AUTHOR
Marijke van Gans (marijke(AT)maxwellian.demon.co.uk)
STATUS
approved