\bigskip
\textit{\textbf{Note:} This homework consists of two parts. The first part (questions 1-6) will be graded and will determine your score for this homework. The second part (questions 7-8) will be graded if you submit them, but will not affect your homework score in any way. You are strongly advised to attempt all the questions in the first part. You should attempt the problems in the second part only if you are interested and have time to spare.}
\rule{6in}{2px}
\begin{center}
For each problem, justify all your answers unless otherwise specified.
\end{center}
\section*{Part 1: Required Problems}
\bigskip
\Question{Captain Combinatorial}
Please provide combinatorial proofs for the following identities.
\begin{Parts}
\Part $\binom{n}{i} = \binom{n}{n-i}$.
\nosolspace{2cm}
\Part $\sum_{i=1}^n i\binom{n}{i} = n2^{n-1}$.
\nosolspace{2cm}
\Part $\sum_{i=1}^n i\binom{n}{i}^2 = n\binom{2n-1}{n-1}$. (Hint: Part (a)
might be useful.)
\nosolspace{2cm}
\Part $\sum_{i=0}^n {n\choose i}\sum_{j=0}^{n-i}{n-i \choose j}=3^n$.
(Hint: consider the number of ways of splitting $n$ elements into 3 groups.)
\end{Parts}
\Question{On to Counting}
Let us consider two finite sets $A$ and $B$ of cardinalities $|A| = n$ and $|B|
= m$, respectively, and ask ourselves how many functions $f: A \to B$ there are that are
surjective.
\begin{Parts}
\Part Define $F$ to be the set of all functions $f: A\to B$ (not necessarily
surjective). What is the cardinality of $F$?
\Part For a fixed $b\in B$, define the set $F_b = \{ f\in F ~:~ f^{-1}\left(
\{b\}\right) = \varnothing \}$. What is the cardinality of $F_b$? How many
functions in $F_b$ are surjective? If $f$ is not surjective, is it
necessarily contained in $F_{b'}$ for some $b'\in B$?
\Part Use your results from the previous parts to compute the the number of functions
from $A$ to $B$ that are surjective.
\end{Parts}
\Question{Flippin' Coins}
Suppose we have an unbiased coin, with outcomes $H$ and $T$, with probability of heads
$\Pr[H] = 1/2$ and probability of tails also $\Pr[T] = 1/2$. Suppose we perform an
experiment in which we toss the coin 3 times. An outcome of this experiment is
$(X_1, X_2, X_3)$, where $X_i \in \{H,T\}$.
\begin{Parts}
\Part What is the \textit{sample space} for our experiment?
\Part Which of the following are examples of \textit{events}? Select all that apply.
\begin{itemize}
\item $\{(H,H,T), (H,H), (T)\}$
\item $\{(T, H, H), (H, T, H), (H, H, T), (H, H, H)\}$
\item $\{(T, T,T)\}$
\item $\{(T, T, T), (H, H, H)\}$
\item $\{(T, H, T), (H, H, T)\}$
\end{itemize}
\Part What is the complement of the event $\{(H,H,H),(H,H,T),(H,T,H),(H,T,T),(T,T,T)\}$?
\Part Let $A$ be the event that our outcome has 0 heads. Let $B$ be the event that our outcome has exactly 2 heads. What is $A \cup B$?
\Part What is the probability of the outcome $(H, H, T)$?
\Part What is the probability of the event that our outcome has exactly two heads?
\end{Parts}
\Question{Probability Warm-Up}
\begin{enumerate}[(a)]
\item Suppose that we have a bucket of 30 red balls and 70 blue balls. If we pick 20 balls out of the bucket, what is the probability of getting exactly $k$ red balls (assuming $0 \leq k \leq 20$) if the sampling is done with replacement?
\nosolspace{2cm}
\item Same as part (a), but the sampling is without replacement.
\nosolspace{2cm}
\item If we roll a regular, 6-sided die 5 times. What is the probability that at least one value is observed more than once?
\nosolspace{2cm}
\end{enumerate}
\Question{Monty Halls}
For each of the following modified Monty Hall scenarios, decide whether the
contestant should switch doors or not. Unless otherwise specified, Monty, as in the
original Monty Hall show, reveals a goat behind one door after the contestant has made
their first choice.
\begin{Parts}
\Part There are $n>2$ doors with $1$ car and $n-1$ goats.
\Part There are $n>2$ doors with $1$ car and $n-1$ goats, but Monty reveals
$n-2$ doors with goats behind them.
\Part There are $n>2$ doors with $k2$, and sample twice with replacement from
$\{0, \dots, p-1\}$, then multiply these two numbers with each other in
$(\bmod{p})$ space.
$E_1 = \text{The resulting product is }0$, $E_2 = \text{The product is }(p-1)/2$.
\Part Sample a random graph on $n$ vertices by including every possible
edge with probability $1/2$. $E_1 = \text{The graph is complete}$, $E_2 =
\text{vertex }v_1\text{ has degree }d$.
\Part Create a random stable marriage instance by having each person's
preference list be a random permutation of the opposite gender. Finally,
create a random pairing by matching men and women up randomly.
$E_1 = \text{The resulting pairing is the female-optimal stable
pairing}$, $E_2 = \text{All men have distinct favorite women}$.
% \Part Generate a random propositional statement $P$ by first
% sampling with replacement twice from $\{\mathrm{T}, \mathrm{F}\}$ (here
% $\mathrm{T}$ is the proposition that is always true, and $\mathrm{F}$
% is the proposition that is always false), then connecting the two samples
% with either $\vee$ or $\wedge$ with equal probability, and finally negate
% the resulting proposition with probability $1/2$. $E_1 = P \text{ is a
% tautology}$, $E_2 = P \text{ is a contradiction}$.
\end{Parts}
\bigskip
\textit{\textbf{Note:} This concludes the first part of the homework. The problems below are optional, will not affect your score, and should be attempted only if you have time to spare.}
\rule{6in}{2px}
\bigskip
\section*{Part 2: Optional Problems}
\bigskip
\Question{Fermat's Wristband}
Let $p$ be a prime number and let $k$ be a positive integer.
We have beads of
$k$ different colors, where any two beads of the same color are indistinguishable.
\begin{Parts}
\Part
We place $p$ beads onto a string.
How many different ways are there construct such a sequence of $p$ beads with up to $k$ different colors?
\Part
How many sequences of $p$ beads on the string are there that use at least two colors?
\Part
Now we tie the two ends of the string together, forming a
wristband.
Two wristbands are equivalent if the sequence of colors on one
can be obtained by rotating the beads on the other.
(For instance, if we have $k=3$ colors, red (R), green (G), and
blue (B), then the length $p = 5$ necklaces RGGBG, GGBGR, GBGRG, BGRGG, and GRGGB are all
equivalent, because these are all rotated versions of each other.)
How many non-equivalent wristbands are there now?
Again, the $p$
beads must not all have the same color.
(Your answer should be a simple function of $k$ and $p$.)
[\textit{Hint}: Think about the fact that rotating all the beads on the wristband to another
position produces an identical wristband.]
\Part Use your answer to part (c) to prove Fermat's little theorem.
\newpage
\end{Parts}
\Question{Peaceful rooks}
A friend of yours, Eithen Quinn, is fascinated by the following problem: placing $m$ rooks on an $n\times n$ chessboard,
so that they are in peaceful harmony (i.e. no two threaten each other). Each rook is a chess piece, and two rooks
threaten each other if and only if they are in the same row or column. You remind your friend that this is so simple that a baby
can accomplish the task. You forget however that babies cannot understand instructions, so when you give the $m$ rooks to
your baby niece, she simply puts them on random places on the chessboard. She however, never puts two rooks at the same
place on the board.
\begin{Parts}
\Part Assuming your niece picks the places uniformly at random, what is the
chance that she places the $(i+1)^{\text{st}}$ rook such that it doesn't
threaten any of the first $i$ rooks, given that the first $i$ rooks don't
threaten each other?
\Part What is the chance that your niece actually accomplishes the task and does not prove
you wrong?
\Part If you were using checker pieces as a replacement for rooks (so that they can be stacked on top of each other),
then what would be the probability that your niece's placements result in peace? Assume that two pieces stacked on top of each other threaten
each other.
\Part Explain the relationship between your answer to the previous part and the birthday paradox. In particular if we
assume that $23$ people have a 50\% chance of having a repeated birthday (in a 365-day calendar), what is
the probability that your niece places $23$ stackable pieces in a peaceful position on a $365\times 365$ board?
\end{Parts}