%dh.tex: Two Proofs that $\sum_{k=0}^{n} (-1)^k k!S(n,k)=(-1)^n$
%%a Plain TeX file by Doron Zeilberger (1 page)

%begin macros
\def\L{{\cal L}}
\baselineskip=14pt
\parskip=10pt
\nopagenumbers
\def\halmos{\hbox{\vrule height0.15cm width0.01cm\vbox{\hrule height
  0.01cm width0.2cm \vskip0.15cm \hrule height 0.01cm width0.2cm}\vrule
  height0.15cm width 0.01cm}}
\font\eightrm=cmr8 \font\sixrm=cmr6
\font\eighttt=cmtt8
\magnification=\magstephalf
\def\P{{\cal P}}
\def\Q{{\cal Q}}
\def\1{{\overline{1}}}
\def\2{{\overline{2}}}
\parindent=0pt
\overfullrule=0in
\def\Tilde{\char126\relax}
\def\frac#1#2{{#1 \over #2}}
%\headline={\rm  \ifodd\pageno  \RightHead  \else  \LeftHead  \fi}
%\def\RightHead{\centerline{
%Title
%}}
%\def\LeftHead{ \centerline{Doron Zeilberger}}
%end macros
\bf
\centerline
{
Two Proofs that $\sum_{k=0}^{n} (-1)^k k!S(n,k)=(-1)^n$
}

\rm
\bigskip
\centerline{ {\it
Doron 
ZEILBERGER}\footnote{$^1$}
{\eightrm  \raggedright
Department of Mathematics, Rutgers University (New Brunswick),
Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway,
NJ 08854-8019, USA.
%\break
{\eighttt zeilberg  at math dot rutgers dot edu} ,
\hfill \break
{\eighttt 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 
({\eighttt http://www.math.rutgers.edu/\~{}zeilberg/pj.html}) .
Supported in part by the NSF.
}
}
{\bf 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
$\sum_{k=0}^{\infty} (-1)^k(e^x-1)^k=1/(1+(e^x-1))=e^{-x}$, that equals $n! \cdot (-1)^n/n!=(-1)^n$ \halmos .

{\bf Proof 2}: $k!S(n,k)$ is the number of ways of placing $n$ balls (labeled $1, \dots, 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 {\it even} number of boxes is ``almost'' the same as doing it with an {\it 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 $\ell$, where $\ell\ne1$, move it to box $\ell-1$
(and discard box $\ell$).
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 \halmos .


\end

















