Collection of Maths Problems

Placing balls

Task number: 3449

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

• Answer

  Balls have	Each pigeonhole containse
  	at most one	any number	at least one
  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}\)