1. Define a set $S$ of character strings over the alphabet $\{a,b\}$ by the following rules: $a$ is in $S$ and $ab$ is in $S$. If the string $x$ is in $S$ and $y$ is in $S$, then $axb$ is in $S$ and $xy$ is in $S$. Nothing else is in $S$. Prove that every string in $S$ has at least as many $a$'s as $b$'s.

2. Every day, starting on day 0, one vampire arrives in Seattle from Transylvania and, starting on the day after its arrival, bites one Seattlite every day. People bitten become vampires themselves and live forever. New vampires also bite one person each day starting the next day after they were bitten. Let $V_n$ be the number of vampires in Seattle on day $n$. So, for example, $V_0 = 1$, $V_1 = 3$ (one that arrived from Transylvania on day 0, one that he bit on day 1, and another one that arrived from Transylvania on day 1), $V_2 = 7$ and so on.
   1. Write a recurrence relation for $V_n$ that is valid for any $n \ge 2$.

   2. Prove by induction on $n$ that $V_n \le 3^{n}$.

3. Permutations:
   1. How many permutations of the letters {a,b,c,d,e,f,g,h} are there?

   2. How many permutations of {a,b,c,d,e,f,g,h} are there that don't contain the letters ``bad'' (appearing consecutively)?

   3. How many permutations of {a,b,c,d,e,f,g,h} are there that don't contain either the letters ``bad'' appearing consecutively or the letters ``fech'' appearing consecutively?

   4. How many words of length 10 can be constructed using the letters {a,b,c,d,e,f,g,h} that contain exactly 3 a's? (They don't have to have any English meaning.)

4. A standard deck of 52 cards is shuffled completely (i.e., any of the permutations is equally likely.) What is the probability that no two spades are adjacent in the shuffled deck?

5. Consider an undirected graph on $n$ vertices generated as follows. For each pair of vertices, an edge between those vertices is included in the graph with probability $p$, and not included with probability $1-p$. What is the expected number of edges in the graph?

6. Suppose a biased coin with probability 3/4 of coming up heads is tossed independently 100 times.
   1. What is the conditional probability that the first 50 tosses are heads given that the total number of heads is 50?
   2. What is the expected number of heads?
   3. Suppose that you are paid $50 if the number of heads in the first two tosses is even and $100 if the number of heads in these first two tosses is odd. What is your expected return?

7. On the next set of questions, fill in the $\ldots$.
   1. The number of subsets of an $n$ element set is $\ldots$

   2. The number of ways of choosing an unordered subset of size $k$ out of a set of size $r$ is $\ldots$

   3. The coefficient of $x^{10}$ in the polynomial $(5x+1)^{100}$ is $\ldots$

   4. The number of different binary relations from a set $A$ of size $n$ to a set $B$ of size $m$ is $\ldots$

   5. The number of different reflexive binary relations on a set $A$ of size $n$ is $\ldots$

   6. The number of different undirected graphs (no self loops and no parallel edges) on $n$ vertices is $\ldots$

8. The final exam of a discrete math course consists of 50 true/false questions, each worth two points, and 25 multiple-choice questions, each worth four points. The probability that Linda answers a true/false question correctly is 0.9, and the probability that she answers a multiple-choice question correctly is 0.8. What is her expected score on the final?

9. A 3-person jury has two rational members, each of whom independently has a probability p of making the correct decision, and a third member who just flips a coin for each decision. The majority decision rules. A one-person jury has probability p of making the correct decision. Which jury has a better probability of making the correct decision? Justify your answer.

10. A pitcher's record is 21 wins and 4 losses. Prove that he must have enjoyed a winning streak of 5 games.