Proving a formula for distributing $n$ objects into $r$ non-empty boxes / formula for number of onto functions

Question

Distribution of $n$ distinct objects into $r$ different boxes if empty boxes are not allowed or in each box at least one object is put is:

$$r^n - \dbinom{r}{1}(r-1)^n+ \dbinom{r}{2}(r-2)^n- \dbinom{r}{3}(r-3)^n + \cdots + (-1)^{r-1}\dbinom{r}{r-1}·1$$

It is a really daunting formula. I do not know how to prove it. It is given that this formula can be proved using principle of inclusions and exclusion and using set theory, but how?

Edit: This formula is also used to find the number of onto functions from a $A$ with $|A|=n$ to $B$ with $|B|=r$.

I would like to see the proof using elementary combinatorics and principle of inclusion and exclusion.

Answer 1

$\def\peq{\mathrel{\phantom{=}}{}}$For each $1 \leqslant k \leqslant r$, denote by $A_k$ the set of scenarios in which the $k$-th box is empty. The quantity to be found is$$ |\overline{A_1} \cap \cdots \cap \overline{A_r}| = |S| - |A_1 \cup \cdots \cup A_r|, $$ where $S$ is the set of all scenarios.

Now, by inclusion and exclusion principle,\begin{align*} |A_1 \cup \cdots \cup A_r| &= \sum_{1 \leqslant k \leqslant r} |A_k| - \sum_{k_1 < k_2} |A_{k_1} \cap A_{k_2}| + \cdots + (-1)^{j - 1} \sum_{k_1 < \cdots < k_j} |A_{k_1} \cap \cdots \cap A_{k_j}|\\ &\peq + \cdots + (-1)^{r - 1} |A_1 \cap \cdots \cap A_r|. \tag{1} \end{align*} Because for any $k_1 < \cdots < k_j$, the set $A_{k_1} \cap \cdots \cap A_{k_j}$ contains exactly all the scenarios in which the $k_1$-th, …, $k_j$-th boxes are empty, then$$ |A_{k_1} \cap \cdots \cap A_{k_j}| = (r - j)^n. $$ Also, there are $\displaystyle\binom{r}{j}$ ways to select $j$ boxes from these $r$ boxes, thus\begin{align*} (1) &= \sum_{1 \leqslant k \leqslant r} (r - 1)^n - \sum_{k_1 < k_2} (r - 2)^n + \cdots + (-1)^{j - 1} \sum_{k_1 < \cdots < k_j} (r - j)^n + \cdots + (-1)^{r - 1} · 0^n\\ &= (r - 1)^n \sum_{1 \leqslant k \leqslant r} 1 - (r - 2)^n \sum_{k_1 < k_2} 1 + \cdots + (-1)^{j - 1} (r - j)^n \sum_{k_1 < \cdots < k_j} 1 + \cdots + (-1)^{r - 1} · 0^n\\ &= (r - 1)^n \binom{r}{1} - (r - 2)^n \binom{r}{2} + \cdots + (-1)^{j - 1} (r - j)^n \binom{r}{j} + \cdots + (-1)^{r - 1} · 0^n, \end{align*} and\begin{align*} &\peq |\overline{A_1} \cap \cdots \cap \overline{A_r}| = |S| - |A_1 \cup \cdots \cup A_r|\\ &= r^n - \left( (r - 1)^n \binom{r}{1} - (r - 2)^n \binom{r}{2} + \cdots + (-1)^{j - 1} (r - j)^n \binom{r}{j} + \cdots + (-1)^{r - 1} · 0^n \right)\\ &= r^n - (r - 1)^n \binom{r}{1} + (r - 2)^n \binom{r}{2} + \cdots + (-1)^j (r - j)^n \binom{r}{j} + \cdots + (-1)^r · 0^n\\ &= r^n - (r - 1)^n \binom{r}{1} + (r - 2)^n \binom{r}{2} + \cdots + (-1)^j (r - j)^n \binom{r}{j} + \cdots + (-1)^{r - 1} · 1^n. \end{align*}

Answer 2

See the formula for the Stirling number of the second kind, which you can find here . ..

Addendum : there is a slight difference... Namely, the $r $ boxes are distinguishable. .. so multiply by $r! $...

Answer 3

Most of this was taken from Surjections, again.

First, note that your question can be reformulated as counting the number of surjective mappings from an $n$-element set to an $r$-element set.

We'll use the complement form of the Principle of Inclusion-Exclusion. If $S$ is some larger "universal" set and $A_1, \dots , A_x$ a collection of subsets of $S$, $$\left| \phantom{=} S- \bigcup^{x}_{i=1}A_i \phantom{=}\right|=\sum_{I \subset \{1, 2, 3, ..., x\}}(-1)^{|I|}\left|\phantom{=}\bigcap_{i\in I}A_i\phantom{=}\right|.$$

$\phantom{=}$

Let $x=r$, $S$ be the set of all mappings $\{1, 2, ..., n\} \rightarrow \{1,2, ..., r\}$, and $A_i$ be the set of mappings $f$ where $i$ is not in the image $f( \{1, 2, ..., n\} )$ (i.e. the mappings that do not "hit" i).

This makes $$\bigcup^{r}_{i=1}A_i$$ the set of all mappings that miss at least one element of $\{1,2, ..., r\}$. This is the set of all non-surjective mappings, so $$ S- \bigcup^{r}_{i=1}A_i $$ is the set of surjective mappings that we are interested in.

Now, by inclusion-exclusion, the number of surjective maps is

$$\left| \phantom{=} S- \bigcup^{r}_{i=1}A_i \phantom{=}\right|=\sum_{I \subset \{1, 2, 3, ..., r\}}(-1)^{|I|}\left|\phantom{=}\bigcap_{i\in I}A_i\phantom{=}\right|.$$ Fix some $I$. The set $\bigcap_{i\in I}A_i$ is the set of functions that miss all the elements of $I$.

There is a bijection from the set of functions $\{1, 2, ..., n\} \rightarrow \{1,2, ..., r\}$ that miss the elements of $I$ to the set of all functions $\{1, 2, ..., n\} \rightarrow \{1,2, ..., r\}\setminus I$, so the size of the former set is the size of the latter. We know the size of the latter (and hence, the former) set because the number of all functions from an $n$-element set to an $r-|I|$ element set is $(r-|I|)^n$.

Forgetting that we've fixed I, we now know that we have $\left|\bigcap_{i\in I}A_i\right|=(r-|I|)^n$ for any such $I$. So, substituting this in, we have \begin{align} \left| \phantom{=} S- \bigcup^{r}_{i=1}A_i \phantom{=}\right|&=\sum_{I \subset \{1, 2, 3, ..., r\}}(-1)^{|I|}\left|\phantom{=}\bigcap_{i\in I}A_i\phantom{=}\right|\\ &=\sum_{I \subset \{1, 2, 3, ..., r\}}(-1)^{|I|}(r-|I|)^n. \end{align}

Now we observe that the argument of our sum depends only on $|I|$, and not the elements in $I$. So let's divide up our sum by the size $|I|$ and see if we can get an expression that sums only over sizes $|I|$ instead of over the sets $I$.

\begin{align}\left| \phantom{=} S- \bigcup^{r}_{i=1}A_i \phantom{=}\right|&=\sum_{I \subset \{1, 2, 3, ..., r\}}(-1)^{|I|}(r-|I|)^n\\ &=\sum_{j=0}^r\sum_{\substack{I \subset \{1, 2, 3, ..., r\};\\|I|=j}}(-1)^{|I|}(r-|I|)^n\\ &=\sum_{j=0}^r\sum_{\substack{I \subset \{1, 2, 3, ..., r\};\\|I|=j}}(-1)^{j}(r-j)^n\\ &=\sum_{j=0}^r (-1)^{j}(r-j)^n \sum_{\substack{I \subset \{1, 2, 3, ..., r\};\\|I|=j}} 1. \end{align} We now notice that $\sum_{\substack{I \subset \{1, 2, 3, ..., r\};\\|I|=j}} 1$ just counts the number of $j$-element subsets of $\{1, 2, 3, ..., r\}$, and there are $\binom{r}{j}$ of these. So we now have \begin{align}\left| \phantom{=} S- \bigcup^{r}_{i=1}A_i \phantom{=}\right| &=\sum_{j=0}^r (-1)^{j}(r-j)^n \sum_{\substack{I \subset \{1, 2, 3, ..., r\};\\|I|=j}} 1\\ &=\sum_{j=0}^r (-1)^{j}(r-j)^n \binom{r}{j}\\ &=\sum_{j=0}^r (-1)^{j}\binom{r}{j}(r-j)^n. \end{align}