Is this Inclusion-Exclusion: $m$ balls colored $n$ colors such that each color is represented?

Question

Suppose you have $m$ balls each of which can be colored by $n<m$ different colors, and your paint cans are unlimited. I want to count the number of ways that you can color balls such that each color is represented at least once. I reasoned that this can be counted by something that seems ... "philosophically" similar to inclusion-exclusion. But when I try to actually align this counting method with the actual inclusion-exclusion method, I can't seem to perfectly describe how this counting method is an application of inclusion-exclusion.

Here's my solution: First over-estimate the number of colorings by all possible assignments of colors to balls: $n^m$.

Next we subtract out those colorings in which some color is absent. There are $\binom n 1$ choices of one color, and for each, we can color each ball by $(n-1)^m$ colors. So our new estimate is

$$ n^m - \binom n 1 (n-1)^m $$

However, there are some colorings that are double-counted by this subtraction. In particular the colorings which are lacking two colors are double-counted (and the colorings missing three colors are triple-counted, and so on). So to correct for this we add back in $\binom n 2 (n-2)^m$.

$$ n^m - \binom n 1 (n-1)^m + \binom n 2 (n-2)^m $$

We continue the process until, with just one color left, double-countings no longer occur. So the number is

$$ \sum_{i=0}^{n-1} (-1)^i \binom{n}{n-i}(n-i)^m $$

Edit: I tried searching for this in the recommendations that StackExchange gives, and didn't see anything that looked very relevant. But now on the sidebar I see this link: Coloring m things with k colors, using each color at least once.

So this is a known problem, but is there a way to view it as an instance of inclusion-exclusion, or is the similarity just superficial?

Answer 1

I would leave it as

$$\sum_{i=0}^{n-1}(-1)^i\binom{n}i(n-i)^m$$

or even

$$\sum_{i=0}^n(-1)^i\binom{n}i(n-i)^m\,,$$

but what you’ve done is fine and is exactly an inclusion-exclusion argument. The Stirling numbers mentioned in the answer to the earlier question that you found can be calculated by essentially the same inclusion-exclusion argument.