## Placing balls

We wish to place $$k$$ balls into $$n$$ pigeonholes. Fill in the following table with the numbers of possible choices:

Balls
have
Each pigeonhole containse
at most one any number at least one
distinct colors
the same color
• #### Solution

Choosing balls with distinct colors corresponds to a mapping $$f$$, where $$f(i)$$ indicates the pigeonhole into which to place the $$i$$-th ball. If each pigeonhole may contain at most one ball, this must be an injective mapping.

We count surjective mappings using the inclusion-exclusion principle, i.e. by (more easily) counting the mappings which are not surjective. If $$A_j$$ indicates the set of mappings $$f$$ where the element $$j$$ is not in the image of $$f$$, we obtain $$\left|\bigcap\limits_{j\in I} A_j\right|=(n-|I|)!$$. The resulting equation is an application of the inclusion-exclusion principle to the intersections with the index set $$I$$ of size $$i$$.

If we are choosing balls of a single color and at most one ball will fit into each pigeonhole, this corresponds to a choice of a $$k$$-element subset of pigeonholes, where the pigeonholes in the chosen set will be the ones with balls.

If more balls can fit into a pigeonohole, this corresponds to the sum $$x_1+…+x_n=k$$, where $$x_i$$ denotes the number of balls in the $$i$$-th pigeonhole.

If each pigeonhole must contain at least one ball, we first separate $$n$$ balls, place one in each pigeonhole and distribute the remaining balls as in the preceding case.

distinct colors $$\frac{n!}{(n-k)!}$$ $$n^k$$ $$\sum\limits_{i=0}^{n-1} (-1)^i \binom{n}{i} (n-i)^k$$
the same color $$\binom{n}{k}$$ $$\binom{n+k-1}{k}$$ $$\binom{k-1}{n-1}$$