\Question{Counting, Counting, and More Counting}
The only way to learn counting is to practice, practice, practice, so
here is your chance to do so.
For this problem, you do not need to show work that justifies your answers.
We encourage you to leave your answer as an expression (rather than
trying to evaluate it to get a specific number).
\begin{Parts}
\Part How many 10-bit strings are there that contain exactly 4 ones?
\Part How many ways are there to arrange $n$ 1s and $k$ 0s into a sequence?
\Part A bridge hand is obtained by selecting 13 cards from a standard
52-card deck. The order of the cards in a bridge hand is
irrelevant. \\
How many different 13-card bridge hands are there?
How many different 13-card bridge hands are there that contain
no aces? How many different 13-card bridge hands are there that contain
all four aces? How many different 13-card bridge hands are there that contain
exactly 6 spades?
\Part How many 99-bit strings are there that contain more ones than
zeros?
\Part An anagram of FLORIDA is any re-ordering of the letters of FLORIDA, i.e., any
string made up of the letters F, L, O, R, I, D, and A, in any order.
The anagram does not have to be an English word. \\
How many different anagrams of FLORIDA are there? How many different anagrams
of ALASKA are there? How many different anagrams of ALABAMA are there?
How many different anagrams of MONTANA are there?
\Part If we have a standard 52-card deck, how many ways are there to
order these 52 cards?
\Part Two identical decks of 52 cards are mixed together, yielding a
stack of 104 cards.
How many different ways are there to order this stack of 104 cards?
\Part We have 9 balls, numbered 1 through 9, and 27 bins.
How many different ways are there to distribute these 9 balls among
the 27 bins? Assume the bins are distinguishable (e.g., numbered 1
through 27).
\Part We throw 9 identical balls into 7 bins.
How many different ways are there to distribute these 9 balls among
the 7 bins such that no bin is empty? Assume the bins are
distinguishable (e.g., numbered 1 through 7).
\Part How many different ways are there to throw 9 identical balls
into 27 bins? Assume the bins are distinguishable (e.g., numbered 1
through 27).
\Part There are exactly 20 students currently enrolled in a class.
How many different ways are there to pair up the 20 students, so
that each student is paired with one other student?
% \Part Let (1, 1) be the bottom-left corner and (8, 8) be the upper-right
% corner of a chessboard. If you are allowed to move one square at a time and
% can only move up or right, what is the number of ways to go from the bottom-left corner to
% the upper-right corner?
% \Part What is the number of ways to go from the bottom-left corner to
% the upper-right corner of the chesssboard, if you must pass through the square
% (6, 2), where $(i, j)$ represents the square in the $i$th row from the
% bottom and the $j$th column from the left? (Again, you are only allowed to move up or right.)
\Part How many solutions does $x_0 + x_1 + \cdots + x_k = n$ have, if each $x$ must be a non-negative integer?
\Part How many solutions does $x_0 + x_1 = n$ have, if each $x$ must be a \emph{strictly positive} integer?
\Part How many solutions does $x_0 + x_1 + \cdots + x_k = n$ have, if each $x$ must be a \emph{strictly positive} integer?
\end{Parts}
\Question{Counting on Graphs}
\begin{Parts}
\Part How many distinct undirected graphs are there with $n$ labeled vertices? Assume that there can be at most one edge between any two vertices, and there are no edges from a vertex to itself.
\Part How many distinct cycles are there in a complete graph with $n$ vertices? Assume that cycles cannot have duplicated edges. Two cycles are considered the same if they are equivalent up to reflection and rotating vertices.
\Part How many ways are there to color a bracelet with $n$ beads using $n$ colors, such that each bead has a different color? Note: two colorings are considered the same if one of them can be obtained by rotating the other.
\Part How many ways are there to color the faces of a cube using exactly $6$ colors, such that each face has a different color? Note: two colorings are considered the same if one of them can be obtained by rotating the other.
\end{Parts}
\Question{Fibonacci Fashion}
You have $n$ accessories in your wardrobe, and you'd like to plan which ones to wear each day for the next $t$ days. As a student of the Elegant Etiquette Charm School, you know it isn't fashionable to wear the same accessories multiple days in a row. (Note that the same goes for clothing items in general).
Therefore, you'd like to plan which accessories to wear each day represented by subsets $S_1,S_2,\ldots,S_t$, where $S_1 \subseteq \{1,2,\ldots,n\}$ and for $2\leq i \leq t$, $S_i \subseteq\{1,2,\ldots,n\}$ and $S_i$ is disjoint from $S_{i-1}$.
\begin{Parts}
\Part For $t\geq 1$, prove that there are $F_{t+2}$ binary strings of length $t$ with no consecutive zeros (assume the Fibonacci sequence starts with $F_0=0$ and $F_1=1$).
\Part Use a combinatorial proof to prove the following identity, which, for $t\geq 1$ and $n\geq 0$, gives the number of ways you can create subsets of your $n$ accessories for the next $t$ days such that no accessory is worn two days in a row:
\[\sum_{x_1 \geq 0} \sum_{x_2\geq 0}\cdots \sum_{x_t \geq 0} {n \choose x_1}{n-x_1 \choose x_2}{n-x_2 \choose x_3}\cdots {n-x_{t-1}\choose x_t}= (F_{t+2})^n.\]
(You may assume that $\binom{a}{b} = 0$ whenever $a < b$.)
\end{Parts}
\Question{Sample Space and Events}
Consider the sample space $\Omega$ of all outcomes from flipping a coin $3$ times.
\begin{Parts}
\Part List all the outcomes in $\Omega$. How many are there?
\Part Let $A$ be the event that the first flip is a heads. List all the outcomes
in $A$. How many are there?
\Part Let $B$ be the event that the third flip is a heads. List all the outcomes
in $B$. How many are there?
\Part Let $C$ be the event that the first and third flip are heads. List all
outcomes in $C$. How many are there?
\Part Let $D$ be the event that the first or the third flip is heads. List all
outcomes in $D$. How many are there?
\Part Are the events $A$ and $B$ disjoint? Express $C$ in terms of $A$ and
$B$. Express $D$ in terms of $A$ and $B$.
\Part Suppose now the coin is flipped $n \ge 3$ times instead of $3$
flips. Compute $|\Omega|, |A|,|B|,|C|,|D|$.
\Part
Your gambling buddy found a website online where he could buy trick coins that
are heads or tails on both sides. He puts three coins into a bag: one coin that
is heads on both sides, one coin that is tails on both sides, and one that is
heads on one side and tails on the other side. You shake the bag, draw out a
coin at random, put it on the table without looking at it, then look at the side
that is showing. Suppose you notice that the side that is showing is heads.
What is the probability that the other side is heads? Show your work. [\textit{Hint}:
The answer is NOT $1/2$.]
\end{Parts}
\Question{Calculate These... or Else}
\begin{Parts}
\Part
A straight is defined as a 5 card hand such that the card values can be arranged in consecutive ascending order, i.e.\ $\{8,9,10,J,Q\}$ is a straight. Values do not loop around, so $\{Q, K, A, 2, 3\}$ is not a straight. However, an ace counts as both a low card and a high card, so both $\{A, 2, 3, 4, 5\}$ and $\{10, J, Q, K, A\}$ are considered straights. When drawing a 5 card hand, what is the probability of drawing a straight from a standard 52-card deck?
\Part
What is the probability of drawing a straight or a flush? (A flush is five cards of the same suit.)
\Part
When drawing a 5 card hand, what is the probability of drawing at least one card from each suit?
\Part
Two squares are chosen at random on $8\times 8$ chessboard. What is the probability that they share a side?
\Part
8 rooks are placed randomly on an $8\times 8$ chessboard. What is the probability none of them are attacking each other? (Two rooks attack each other if they are in the same row, or in the same column).
%\Part A bag has two quarters and a penny. If someone removes a coin, the Coin-Replenisher will come and drop in 1 of the coin that was just removed with $3/4$ probability and with $1/4$ probability drop in 1 of the opposite coin. Someone removes one of the coins at random. The Coin-Replenisher drops in a penny. You randomly take a coin from the bag. What is the probability you take a quarter?
\end{Parts}
\Question{ Throwing Balls into a Depth-Limited Bin}
Say you want to throw $n$ balls into $n$ bins with depth $k-1$ (they can fit $k-1$ balls, after that the bins overflow). Suppose that $n$ is a large number and $k=0.1n$. You throw the balls randomly into the bins, but you would like it if they don't overflow. You feel that you might expect not too many balls to land in each bin, but you're not sure, so you decide to investigate the probability of a bin overflowing.
\begin{Parts}
\Part Focus on the first bin. Get an upper bound the number of ways that you can throw the balls into the bins such that this bin overflows. Try giving an argument about the following strategy: select $k$ balls to put in the first bin, and then throw the remaining balls randomly. You should assume that the balls are distinguishable.
\nosolspace{1cm}
\Part Calculate an upper bound on the probability that the first bin will overflow.
\nosolspace{1cm}
\Part Upper bound the probability that some bin will overflow. [\textit{Hint}: Use the union bound.]
\nosolspace{1cm}
\Part How does the above probability scale as $n$ gets really large? [\textit{Hint}: Use the union bound.]
\nosolspace{1cm}
\end{Parts}