Evaluating $\sum_{i=0}^{30}(-1)^i {{30} \choose {i}}(30-i)^{31}$ As the title says, I've been asked to evaluate this sum: $$\sum_{i=0}^{30}(-1)^i {{30} \choose {i}}(30-i)^{31}$$ and have been unable to do so. The possible answers are $$\frac {30\cdot31!} 2, \frac {31!} 2, \frac {31!} 3, \frac {30\cdot31!} 3$$
and I don't even see where the factorial could come from. I tried expanding the inner binomial expression but that didn't yield anything helpful. Help would be appreciated.

Evaluating $$\sum_{q=0}^n (-1)^q {n\choose q} (n-q)^{n+1}$$ we find
$$(n+1)! [z^{n+1}] \sum_{q=0}^n (-1)^q {n\choose q} \exp((n-q)z)
\\ = (n+1)! [z^{n+1}] (\exp(z)-1)^n
\\ = (n+1)! [z^{n+1}] (z+z^2/2+\cdots)^n
\\ = (n+1)! \frac{1}{2} {n\choose 1}.$$
With $n=30$ this yields $$31! \times \frac{30}{2}.$$
For a combinatorial interpretation we recognize the Stirling number multiple $n! \times {n+1\brace n}.$ We have ${n+1\choose 2}$ ways to partition $[n+1]$ into $n$ disjoint sets by choosing the single pair. We get $n! \times  {n+1\choose 2},$ the same as before.
