# 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.

• This smells like inclusion-exclusion. I guess that the point of the quesiton is not to use algebra, but to come up with a combinatorical problem. Jan 29, 2021 at 21:17
• As per @Eminem's suggestion, what are the number of functions from $\{0,1,2,\dots,30\}$ to $\{1,2,\dots,30\}$ that are surjective? (1) By counting directly. (2) By inclusion exclusion over the events that some collection of $i$ of the elements were not mapped to. Jan 29, 2021 at 21:24
• I expect there is some convenient way to word this using summation by parts as well, but I haven't spotted it just yet. Jan 29, 2021 at 21:25

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.

• That's a really cute way to organize it, +1! Jan 29, 2021 at 21:39

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.