Chapter 22 Balls in Boxes Part 2
Exercises Practice Problems
1.
Last class, we filled in the following table:
\(n\) distinct boxes, \(k\) balls, boxes CAN be empty
| balls identical | balls distinct | conditions? | |
| no repetition | \(\displaystyle{{ n \choose k}}\) | \((n)_k\) | \(k \leq n\) |
| with repetition | \(\displaystyle{{n+k-1 \choose k}}\) | \(n^k\) | none |
We consider another variation on this problem: now the boxes cannot be empty. Try to fill in the following table. You will be able to determine 3 out of 4 of the answers. We will talk about the last one as a group.
\(n\) distinct boxes, \(k\) balls, boxes CANNOT be empty
| balls identical | balls distinct | conditions? | |
| no repetition | \(\phantom{\displaystyle{{a+b+c \choose d}}}\) | \(\phantom{\displaystyle{{a+b+c \choose d}}}\) | \(\phantom{\displaystyle{{a+b+c \choose d}}}\) |
| with repetition | \(\phantom{\displaystyle{{a+b+c \choose d}}}\) | \(\phantom{\displaystyle{{a+b+c \choose d}}}\) | \(\phantom{\displaystyle{{a+b+c \choose d}}}\) |
| balls identical | balls distinct | conditions? | |
| no repetition | \(\displaystyle{\phantom{{ a \choose b}}}\) \(1\) \(\displaystyle{\phantom{{ a \choose b}}}\) | \(n!=k!\) | \(n=k\) |
| with repetition | \(\displaystyle{{ k -1 \choose n-1}}\) | \(n! S(k,n)\) | \(k \geq n\) |
The formula \(n! S(k,n)\) uses the number \(S(k,n)\) which is called the Stirling Number of the Second Kind. It turns out that we've asked a very hard problem!
We do have the tools at our disposal to give and understand the formula for \(S(k,n)\text{.}\) However, the argument is a little more abstract than I usually like to cover in MATH 279. So you can just write down "\(n! S(k,n)\)" as the answer to this question (when it comes up) without knowing the particular formula for \(S(k,n)\text{.}\)
Some more details: the number \(S(k,n)\) counts the number of ways to put \(n\) distinct balls into \(k\) identical boxes where boxes cannot be empty and repetition is allowed. Can you explain why we must multiply by \(n!\) in order to get the number of ways to use \(\) instead?
2.
In this problem, you will count sets of functions from \([r]\) to \([s]\text{.}\) You will map each one to a balls-in-boxes problem. Decide each of the following questions (and write down your answers):
Are the balls distinct?
Are the boxes distinct?
Can boxes be empty?
Is repetition allowed?
What is the constraint on \(r\) and \(s\text{?}\)
Then write down the formula for the size of the set of functions.
\(\mathcal{A} = \{ \) all possible functions from \([r]\) to \([s] \}\text{.}\) Solution.
\begin{equation*} | \mathcal{A}| = s^r \end{equation*}\(\mathcal{B} = \{ \) all injective functions from \([r]\) to \([s] \}\text{.}\) Solution.
\begin{equation*} | \mathcal{B}| = (s)_r \end{equation*}\(\mathcal{C} = \{ \) all surjective functions from \([r]\) to \([s] \}\text{.}\) Solution.
\begin{equation*} | \mathcal{C}| = r! S(s,r) \end{equation*}\(\mathcal{D} = \{ \) all bijective functions from \([r]\) to \([s] \}\text{.}\) Solution.
\begin{equation*} | \mathcal{D}| = s!=r! \end{equation*}