\documentclass[11pt]{article}
\usepackage{jeffe,handout,multicol,tikz,kgm}
\usepackage{graphicx}

\newcommand{\kgmcomment}[1]{}
\renewcommand{\gcd}{\mathrm{gcd}}

\begin{document}
\headers{Math378}{Homework 13}{Due Mon. Apr 27, 2026}

%\makeatletter
%\def\@oddfoot{\hfill \tikz \node[draw] {over} ; }
%\makeatother

%\newcommand{\seq}[1]{\left\langle #1\right\rangle}

\newcommand{\RR}{\mathbb{R}}
\newcommand{\ZZ}{\mathbb{Z}}

\makeatletter
\def\@oddfoot{}
\makeatother

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

\begin{enumerate}

\item {} [5.4] Let $C_n$ be the $n$th Catalan number.  Recall that $C_n = \frac{1}{n+1}\binom{2n}{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\ge 1$.  

Let $A_n$ be the set of permutations $(x_1,\ldots,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,\ldots)$ and $(C_0,C_1,\ldots)$ are the same sequence, meaning that $a_n = C_n$.
\begin{enumerate}
	\item Let $k$ and $n$ be integers such that $1\le k\le n$.  Let $A_{n,k}$ be the set of permutations $(x_1,\ldots,x_n)\in A_n$ such that $x_k = n$.  Prove that $|A_{n,k}| = a_{k-1}a_{n-k}$.
	\item Let $n$ be a positive integer.  Prove that $a_n = \sum_{k=1}^n a_{k-1}a_{n-k}$.
	\item Explain why this implies that $a_n = C_n$ for all $n$.
\end{enumerate}

\item {} {} [8.1] Use inclusion/exclusion to find a formula for the number of surjective functions $f$ from $\{1,\ldots,n\}$ onto $\{1,2,3,4\}$.

\item {} [10.1.13] Prove that $d_1,\ldots,d_p$ is graphic if and only if $p-1-d_1,\ldots,p-1-d_p$ is graphic.

\item {} [10.2.1] Let $x$ and $y$ be vertices of a graph.  
\begin{enumerate}
	\item Suppose that there is a closed walk containing both $x$ and $y$.  Must there be a closed trail containing both $x$ and $y$?
	\item Suppose that there is a closed trail containing both $x$ and $y$.  Must there be a cycle containing both $x$ and $y$?
\end{enumerate}


\end{enumerate}
\end{document}