Skip to main content\( \newcommand{\identity}{\mathrm{id}}
\newcommand{\notdivide}{{\not{\mid}}}
\newcommand{\notsubset}{\not\subset}
\newcommand{\lcm}{\operatorname{lcm}}
\newcommand{\gf}{\operatorname{GF}}
\newcommand{\inn}{\operatorname{Inn}}
\newcommand{\aut}{\operatorname{Aut}}
\newcommand{\Hom}{\operatorname{Hom}}
\newcommand{\cis}{\operatorname{cis}}
\newcommand{\chr}{\operatorname{char}}
\newcommand{\Null}{\operatorname{Null}}
\def\Z{\mathbb Z}
\def\R{\mathbb R}
\def\Q{\mathbb Q}
\def\N{\mathbb N}
\def\C{\mathbb C}
\def\W{\mathbb W}
\def\ba{{\mathbf{a}}}
\def\bb{\mathbf{b}}
\def\bh{{\mathbf{h}}}
\def\bu{{\mathbf{u}}}
\def\bv{{\mathbf{v}}}
\def\bw{{\mathbf{w}}}
\def\bx{{\mathbf{x}}}
\def\by{\mathbf{y}}
\def\bone{{\mathbf{1}}}
\def\bzero{\mathbf{0}}
\def\var{{\mbox{var}}}
\def\P{{\mathbb{P}}}
\def\E{{\mathbb{E}}}
\def\cA{{\mathcal{A}}}
\def\cB{{\mathcal{B}}}
\def\cC{{\mathcal{C}}}
\def\cP{\mathcal P}
\def\cN{\mathcal N}
\def\cE{\mathcal E}
\def\cO{\mathcal O}
\def\cF{\mathcal F}
\def\cX{\mathcal X}
\def\nimsum{\, \oplus \,}
\def\mex{{\mathrm{mex}}}
\newcommand{\pile}[1]{\bullet{#1}}
\def\g{g}
\def\kin{k^{\mathrm{in}}}
\def\kout{k^{\mathrm{out}}}
\newcommand{\indeg}[1]{k^{\mathrm{in}}_{#1}}
\newcommand{\outdeg}[1]{k^{\mathrm{out}}_{#1}}
\tikzset{->-/.style={decoration={
markings,
mark=at position .5 with {\arrow{latex}}},postaction={decorate}}}
\newcommand{\nimbleboard}[1]{
\begin{scope}[shift={(.25, .4)}]
\draw (0,-.3) -- (#1,-.3) -- (#1+.45, .7) -- (#1+.45, 1);
\draw (0,0) -- (#1,0);
\draw (.45,1) -- (#1+.45,1);
\foreach \i in {0, ..., #1} {
\draw (\i, -.3) -- (\i, 0) -- (\i+.45,1);
}
\foreach \i in {1, ..., #1} {
\node[style={font=\sffamily\scriptsize}] at (\i - .5, -.15) {\i};
}
\end{scope}
}
\newcommand{\coin}[1]{
\begin{scope}[shift={#1}]
\draw[color=white, fill=white] (-.4, 0) -- (-.4, -.1) -- (.4,-.1) -- (.4,0) -- cycle;
\draw[thick, fill=white] (0,0) ellipse (0.4 and 0.10);
\draw[thick, fill=white] (.4,-.1) arc (0:-180:0.4 and 0.10);
\draw[thick] (0.4,0) -- (0.4, -.1);
\draw[thick] (-0.4,0) -- (-0.4, -.1);
\end{scope}
}
\newcommand{\bean}[2]{
\begin{scope}[shift={#1}, rotate={#2}]
\draw [very thick, fill=gray!50] plot [smooth cycle] coordinates {(-.2,0) (-.175, .07) (-.1,.1) (0,.075) (.1,.1) (.175, .07) (.2,0) (.15, -.07) (0,-.1) (-.15, -.07)};
\end{scope}
}
\newcommand{\heap}[2]{
\begin{scope}[shift={#1}]
\draw[very thick] (0,0) circle ({#2});
\end{scope}
}
\newcommand{\lt}{<}
\newcommand{\gt}{>}
\newcommand{\amp}{&}
\)
Chapter 17 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}}}\) |
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):
Then write down the formula for the size of the set of functions.
\(\mathcal{A} = \{ \) all possible functions from \([r]\) to \([s] \}\text{.}\)
\(\mathcal{B} = \{ \) all injective functions from \([r]\) to \([s] \}\text{.}\)
\(\mathcal{C} = \{ \) all surjective functions from \([r]\) to \([s] \}\text{.}\)
\(\mathcal{D} = \{ \) all bijective functions from \([r]\) to \([s] \}\text{.}\)
3.
You want to give away 20 identical baseballs to 10 baseball fans. How many ways can this be done when \(\ldots\)
There are no restrictions on how you give them away.
Every fan must get at least one baseball.
Every fan must get exactly two baseballs.
4.
You want to give away 20 distinct baseball caps (from different teams) to 10 fans. How many ways can this be done when \(\ldots\)
There are no restrictions on how you give them away.
Every fan must get at least one baseball cap.
Every fan must get exactly two baseball caps.