Name:      

Directions: Show all work. No credit for answers without work. Except when otherwise directed, you may leave answers in terms of binomial/multinomial coefficients, factorials, and sums with a small number of terms.

1. [4 parts, 6 points each] Let $U={\{1,2,3,4,5\}}^7$, the set of all lists of length $7$ with each entry in $\{1,2,3,4,5\}$.

   1. Compute $|U|$.
   2. Find the number of lists in $U$ that do not have consecutive even integers and do not have consecutive odd integers.
   3. How many lists in $U$ contain two consecutive entries that are equal?
   4. If a list in $U$ is chosen at random, what is the probability that the first two entries sum to $8$?

2. [6 points] How many ways are there to form subsets of size $3$ from a set of size $n$? Express your answer as a polynomial in $n$ with simplified coefficients.
3. [6 points] How many permutations of $\{1,\dots ,9\}$ have the even numbers appearing in order? For example $(5,3,2,4,7,6,1,9,8)$ counts but $(5,3,6,4,7,2,1,9,8)$ does not.

4. A fair coin is flipped 8 times.

   1. [4 points] Give the sample space $\mathrm{\Omega }$. Then compute $|\mathrm{\Omega }|$.
   2. [6 points] What is the probability that there are equally many heads and tails?
   3. [6 points] What is the probability that there is at least one head in the first four flips and at least one head in the last four flips?

5. [2 parts, 6 points each] A standard deck of cards has one card for each of the suit/rank pairs. The suits are spades, hearts, diamonds, and clubs; the ranks are ace, $2$ through $10$, jack, queen, and king. Four hands with 13 cards each are dealt from a freshly shuffled deck to players $A$, $B$, $C$, and $D$.

   1. What is the probability that player $A$ gets all the spades?
   2. What is the probability that players $A$ and $B$ together get all the spades and players $C$ and $D$ get none?
6. [6 points] How many non-negative integer solutions are there to $x_1+x_2+\cdots +x_6=83$ such that $x_1\le 25$?

7. [6 points] How many ways can we distribute 15 identical red balls and 4 identical green balls into 3 labeled boxes? (Putting all 15 red balls in box 1 and 2 green balls each in boxes 2 and 3 is different prom putting all 15 red balls in box 3 and putting 2 green balls in boxes 1 and 2.)

8. [10 points] Give a combinatorial proof that $\left(\genfrac{}{}{0.0pt}{}{n}{k}\right)=\left(\genfrac{}{}{0.0pt}{}{n-2}{k-2}\right)+2\left(\genfrac{}{}{0.0pt}{}{n-2}{k-1}\right)+\left(\genfrac{}{}{0.0pt}{}{n-2}{k}\right)$.

9. [2 parts, 6 points each] Let $A$ be the set of all lists in ${\{1,2,3,4,5\}}^n$ where every even entry appears before every odd entry, and let $B$ be the set of all lists in ${\{a,b,c\}}^{n+1}$ that contain at least one $c$. For example, if $n=4$, then $(4,2,3,3)\in A$ and $(a,c,b,c,c)\in B$.

   1. Describe a bijection $f:A\to B$. For $n=4$, explicitly compute $f(4,2,3,3)$ and find the element in $A$ that $f$ maps to $(a,c,b,c,c)$.
   2. Use the bijection to find a simple formula for $|A|$.