Directions: Solve the following problems. All written work must be your own. See the course syllabus for detailed rules.

[5.4] Let $C_{n}$ be the $n$ th Catalan number. Recall that $C_{n} = \frac{1}{n + 1} (\binom{2 n}{n})$ and $C_{n}$ satisfies the recurrence $C_{0} = 1$ and $C_{n} = \sum_{k = 1}^{n} C_{k - 1} C_{n - k}$ for $n \geq 1$ .
Let $A_{n}$ be the set of permutations $(x_{1}, \dots, x_{n})$ of $[n]$ that do not contain three entries $x_{i}, x_{k}, x_{j}$ such that $i < k < j$ and $x_{i} < x_{j} < x_{k}$ . Let $a_{n} = | A_{n} |$ . Our aim is to prove that the sequences $(a_{0}, a_{1}, \dots)$ and $(C_{0}, C_{1}, \dots)$ are the same sequence, meaning that $a_{n} = C_{n}$ .
1. Let $k$ and $n$ be integers such that $1 \leq k \leq n$ . Let $A_{n, k}$ be the set of permutations $(x_{1}, \dots, x_{n}) \in A_{n}$ such that $x_{k} = n$ . Prove that $| A_{n, k} | = a_{k - 1} a_{n - k}$ .
2. Let $n$ be a positive integer. Prove that $a_{n} = \sum_{k = 1}^{n} a_{k - 1} a_{n - k}$ .
3. Explain why this implies that $a_{n} = C_{n}$ for all $n$ .
[8.1] Use inclusion/exclusion to find a formula for the number of surjective functions $f$ from ${1, \dots, n}$ onto ${1, 2, 3, 4}$ .
[10.1.13] Prove that $d_{1}, \dots, d_{p}$ is graphic if and only if $p - 1 - d_{1}, \dots, p - 1 - d_{p}$ is graphic.
[10.2.1] Let $x$ and $y$ be vertices of a graph.
1. Suppose that there is a closed walk containing both $x$ and $y$ . Must there be a closed trail containing both $x$ and $y$ ?
2. Suppose that there is a closed trail containing both $x$ and $y$ . Must there be a cycle containing both $x$ and $y$ ?