Evaluating $\sum_{i=0}^{30}(-1)^i {{30} \choose {i}}(30-i)^{31}$

Question

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.

Answer 1

The expression can be recognized as inclusion-exclusion count for the number of ways to place 31 balls into 30 bins in such a way that no bin is empty.

Clearly this can be performed only by filling 29 bins with one ball and one bin with two balls. Thus the number in question can be alternatively computed as: $$\binom{30}1\binom{31}2 29!, $$ where the strategy to perform the task is the following: first choose a bin for two balls, then choose the two balls, and finally distribute the remaining balls between the remaining bins.

Answer 2

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.