Two Proofs that ∑_{k=0}^{n}(−1)^{k}k!S(n, k) = (−1)^{n}

Doron ZEILBERGER^{1}

Proof 1: k!S(n, k) is n! times the coeff. of x^{n} in (e^{x} − 1)^{k}, so the sum equals n! times the coeff. of x^{n} in ∑_{k=0}^{∞}(−1)^{k}(e^{x} − 1)^{k} = 1/(1 + (e^{x} − 1)) = e^{−x}, that equals n! · (−1)^{n}/n! = (−1)^{n} .

Proof 2: k!S(n, k) is the number of ways of placing n balls (labeled 1, …, n) into k non-empty boxes, lined-up from left to right. The identity of the title says that the number of ways of doing it with an even number of boxes is “almost” the same as doing it with an odd number of boxes, and the difference is 1 (in favor of the evens if n is even and in favor of the odds if n is odd). So we need a parity-changing involution.

If ball 1 is alone in box ℓ, where ℓ ≠ 1, move it to box ℓ−1 (and discard box ℓ). If 1 has box-mates, create a new box immediately to its right and put 1 there.

If 1 is alone in the first box, do the same for ball 2. If 1 is alone in the first box, and 2 is alone in the second box, do it for 3, etc.. Every arrangement can be matched except for the scenario {1}, {2}, ..., {n}, that makes the difference 1 if n is even and −1 if n is odd .

1 Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen

Rd., Piscataway, NJ 08854-8019, USA. zeilberg at math dot rutgers dot edu , http://www.math.rutgers.edu/~zeilberg/ . June 26, 2011. Thanks to Dan Haran for asking the question (and improving the exposition!), and to Richard Stanley for pointing out that this elegant identity is the case x = 0 of Eq. (3.124) of the latest edition of Enumerative Combinatorics v.1, but otherwise that he is not aware of an explicit reference (although it may be somewhere in the works of Bernoulli, Stirling, or Euler.) Exclusively published in The Personal Journal of S.B. Ekhad and D. Zeilberger (http://www.math.rutgers.edu/~zeilberg/pj.html) .

Supported in part by the NSF.