A063170 Schenker sums with n-th term.

1, 2, 10, 78, 824, 10970, 176112, 3309110, 71219584, 1727242866, 46602156800, 1384438376222, 44902138752000, 1578690429731402, 59805147699103744, 2428475127395631750, 105224992014096760832, 4845866591896268695010, 236356356027029797011456

Offset: 0

Author

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

Keywords

• nonn
• easy

Comments

Urn, n balls, with replacement: how many selections if we stop after a ball is chosen that was chosen already? Expected value is a(n)/n^n.

Conjectures: The exponent in the power of 2 in the prime factorization of a(n) (its 2-adic valuation) equals 1 if n is odd and equals n - A000120(n) if n is even. - Gerald McGarvey, Nov 17 2007, Jun 29 2012

Amdeberhan, Callan, and Moll (2012) have proved McGarvey's conjectures. - Jonathan Sondow, Jul 16 2012

a(n), for n >= 1, is the number of colored labeled mappings from n points to themselves, where each component is one of two colors. - Steven Finch, Nov 28 2021

Examples

			a(4) = (1*2*3*4) + 4*(2*3*4) + 4*4*(3*4) + 4*4*4*(4) + 4*4*4*4.
G.f. = 1 + 2*x + 10*x^2 + 78*x^3 + 824*x^4 + 10970*x^5 + 176112*x^6 + ...
		

References

• D. E. Knuth, The Art of Computer Programming, 3rd ed. 1997, Vol. 1, Addison-Wesley, p. 123, Exercise Section 1.2.11.3 18.

Links

• G. C. Greubel, Table of n, a(n) for n = 0..385
• Max Alekseyev, Recursion for A063170, answer to question on MathOverflow (2025).
• T. Amdeberhan, D. Callan, and V. Moll, p-adic analysis and combinatorics of truncated exponential sums, preprint, 2012.
• T. Amdeberhan, D. Callan and V. Moll, Valuations and combinatorics of truncated exponential sums, INTEGERS 13 (2013), #A21.
• Steven Finch, Rounds, Color, Parity, Squares, arXiv:2111.14487 [math.CO], 2021.
• Helmut Prodinger, An identity conjectured by Lacasse via the tree function, Electronic Journal of Combinatorics, 20(3) (2013), #P7.
• David M. Smith and Geoffrey Smith, Tight Bounds on Information Leakage from Repeated Independent Runs, 2017 IEEE 30th Computer Security Foundations Symposium (CSF).
• Marijke van Gans, Schenker sums
• Eric Weisstein, Exponential Sum Function.

Crossrefs

Cf. A000312, A134095, A090878, A036505, A120266, A214402, A219546 (Schenker primes).

Programs

Maple

seq(simplify(GAMMA(n+1,n)*exp(n)),n=0..20); # Vladeta Jovovic, Jul 21 2005

Mathematica

a[n_] := Round[ Gamma[n+1, n]*Exp[n]]; Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Feb 16 2012, after Vladeta Jovovic *)
a[ n_] := If[ n < 1, Boole[n == 0], n! Sum[ n^k / k!, {k, 0, n}]]; (* Michael Somos, Jun 05 2014 *)
a[ n_] := If[ n < 0, 0, n! Normal[ Exp[x] + x O[x]^n] /. x -> n]; (* Michael Somos, Jun 05 2014 *)

PARI

{a(n) = if( n<0, 0, n! * sum( k=0, n, n^k / k!))};

PARI

{a(n) = sum( k=0, n, binomial(n, k) * k^k * (n - k)^(n - k))}; /* Michael Somos, Jun 09 2004 */

PARI

for(n=0,17,print1(round(intnum(x=0,[oo,1],exp(-x)*(n+x)^n)),", ")) \\ Gerald McGarvey, Nov 17 2007

Python

from math import comb
def A063170(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<<1) if n else 1 # Chai Wah Wu, Apr 26 2023

UBASIC

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

Formula

a(n) = Sum_{k=0..n} n^k n!/k!.

a(n)/n! = Sum_{k=0..n} n^k/k!. (First n+1 terms of e^n power series.)

a(n) = A063169(n) + n^n.

E.g.f.: 1/(1-T)^2, where T=T(x) is Euler's tree function (see A000169).

E.g.f.: 1 / (1 - F), where F = F(x) is the e.g.f. of A003308. - Michael Somos, May 27 2012

a(n) = Sum_{k=0..n} binomial(n,k)*(n+k)^k*(-k)^(n-k). - Vladeta Jovovic, Oct 11 2007

Asymptotics of the coefficients: sqrt(Pi*n/2)*n^n. - N-E. Fahssi, Jan 25 2008

a(n) = A120266(n)*A214402(n) for n > 0. - Jonathan Sondow, Jul 16 2012

a(n) = Integral_{0..oo} exp(-x) * (n + x)^n dx. - Michael Somos, May 18 2004

a(n) = Integral_{0..oo} exp(-x)*(1+x/n)^n dx * n^n = A090878(n)/A036505(n-1) * n^n. - Gerald McGarvey, Nov 17 2007

EXP-CONV transform of A000312. - Tilman Neumann, Dec 13 2008

a(n) = n! * [x^n] exp(n*x)/(1 - x). - Ilya Gutkovskiy, Sep 23 2017

a(n) = (n+1)! - Sum_{k=0..n-1} binomial(n, k)*a(k)*(-k)^(n-k) for n > 0 with a(0) = 1 (see Max Alekseyev link). - Mikhail Kurkov, Jan 14 2025