\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{multicol}
\usepackage{latexsym}
\usepackage{verbatim}
\usepackage[pdftex]{graphicx}
\usepackage{url}
\usepackage{wasysym}
\usepackage{mathrsfs}
\usepackage{hyperref}
\hypersetup{colorlinks=true}
\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6in}
\setlength{\topmargin}{-0.4in}
\setlength{\textheight}{8.5in}


\usepackage{tikz}
\newcommand*\circled[1]{\tikz[baseline=(char.base)]{
            \node[shape=circle,draw,inner sep=2pt] (char) {#1};}}
\input{preamble.tex}

\begin{document}

\homework{6: Catalan Numbers}{Due Friday, Week 3}

This problem set is slightly different.  Pick \textbf{two} of the \textbf{six} objects below, and show that they each satisfy the recurrence
\begin{align*}
C_0 = C_1 = 1, C_{n} = \sum_{k=0}^{n-1} C_kC_{(n-1)-k}.
\end{align*}

\begin{enumerate}
\item Take $2n$ points in the plane, and pair them up by drawing nonintersecting arcs that lie above these points.  Let $C_n$ denote the total number of such pairs: we draw all of the configurations for $n=3$ below.
\begin{center}
\includegraphics[width=4in]{catalan1.pdf}
\end{center}
Show that the $C_n$'s satisfy our claimed recurrence.
\item Take all of the sequences of integers $(a_1, a_2, \ldots a_n)$ such that
\begin{itemize}
\item $1 \leq a_1 \leq a_2 \leq \ldots a_n$.
\item $a_i \leq i$, for every $i$.
\end{itemize}
Let $C_n$ denote the total number of such sequences of length $n$: we give all of the length-$3$ sequences here.
\begin{align*}
(1,1,1), (1,1,2), (1,1,3), (1,2,2), (1,2,3).
\end{align*}
Show that the $C_n$'s satisfy our claimed recurrence.
\item  A \textbf{stairstep} of height $n$ is made by stacking a $1 \times 1$ block on top of a $1 \times 2$ block on top of a \ldots $1 \times n$ block, to give us one of the diagrams below.  A \textbf{tiling} of a stairstep by $n$ rectangles is a way to cover one of these stairsteps with $k \times l$ rectangles, so that every block is covered and no block is covered twice.  Let $C_n$ denote the total number of coverings of a stairstep of height $n$ with $n$ rectangles: we draw the fourteen tilings of stairsteps of height 4 below.
\begin{center}
\includegraphics[width=4in]{catalan2.pdf}
\end{center}
Show that the $C_n$'s satisfy our claimed recurrence.
\item A \textbf{valid coin-stacking} is any way to stack circles as drawn below, so that the bottom row consists of $n$ consecutive coins.  Let $C_n$ denote the total number of valid coin-stackings such that the bottom row consists of $n$ consecutive coins: we draw all of the configurations for $n=3$ below.
\begin{center}
\includegraphics[width=4in]{catalan3.pdf}
\end{center}
Show that the $C_n$'s satisfy our claimed recurrence.
\item A \textbf{multiset} is a set where we allow elements to be picked multiple times.  We call a multiset that is a subset of $\mathbb{Z}/(n+1)\mathbb{Z}$ \textbf{nullifying} if adding all of its elements together gives us zero (mod $n+1$.)  Let $C_n$ denote the total number of $n$-element nullifying multisets of elements in $\mathbb{Z}/(n+1)\mathbb{Z}$.  Here are all of these multisets counted by $C_3$:
\begin{align*}
\{0,0,0\}, \{0,1,3\}, \{0,2,2\}, \{1,1,2\}, \{2,3,3\}.
\end{align*}
\item Take all of the sequences of integers $(a_1, a_2, \ldots a_n)$ such that 
\begin{itemize}
\item $a_i \leq 1$ for every $i$.
\item Each of the partial sums $\sum_{n=1}^k a_i$ is positive, for each $1 \leq k \leq n$.
\end{itemize}
Let $C_n$ denote the total number of such sequences of length $n-1$: we give all of the sequences for $C_3$ here.
\begin{align*}
(0,0), (0,1), (1,-1), (1,0), (1,1).
\end{align*}
Show that the $C_n$'s satisfy our claimed recurrence.
\end{enumerate}







\end{document}