\documentclass[numbers=enddot,12pt,final,onecolumn,notitlepage]{scrartcl}%
\usepackage{amsfonts}
\usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage}
\usepackage[all,cmtip]{xy}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{framed}
\usepackage{comment}
\usepackage{color}
\usepackage{hyperref}
\usepackage{ifthen}
\usepackage[sc]{mathpazo}
\usepackage[T1]{fontenc}
\usepackage{needspace}
\usepackage{tabls}
\usepackage{tikz}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Wednesday, December 09, 2020 16:37:22}
%TCIDATA{SuppressPackageManagement}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%BeginMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
%EndMSIPreambleData
\newcounter{exer}
\theoremstyle{definition}
\newtheorem{theo}{Theorem}[section]
\newenvironment{theorem}[1][]
{\begin{theo}[#1]\begin{leftbar}}
{\end{leftbar}\end{theo}}
\newtheorem{lem}[theo]{Lemma}
\newenvironment{lemma}[1][]
{\begin{lem}[#1]\begin{leftbar}}
{\end{leftbar}\end{lem}}
\newtheorem{prop}[theo]{Proposition}
\newenvironment{proposition}[1][]
{\begin{prop}[#1]\begin{leftbar}}
{\end{leftbar}\end{prop}}
\newtheorem{defi}[theo]{Definition}
\newenvironment{definition}[1][]
{\begin{defi}[#1]\begin{leftbar}}
{\end{leftbar}\end{defi}}
\newtheorem{remk}[theo]{Remark}
\newenvironment{remark}[1][]
{\begin{remk}[#1]\begin{leftbar}}
{\end{leftbar}\end{remk}}
\newtheorem{coro}[theo]{Corollary}
\newenvironment{corollary}[1][]
{\begin{coro}[#1]\begin{leftbar}}
{\end{leftbar}\end{coro}}
\newtheorem{conv}[theo]{Convention}
\newenvironment{condition}[1][]
{\begin{conv}[#1]\begin{leftbar}}
{\end{leftbar}\end{conv}}
\newtheorem{quest}[theo]{Question}
\newenvironment{algorithm}[1][]
{\begin{quest}[#1]\begin{leftbar}}
{\end{leftbar}\end{quest}}
\newtheorem{warn}[theo]{Warning}
\newenvironment{conclusion}[1][]
{\begin{warn}[#1]\begin{leftbar}}
{\end{leftbar}\end{warn}}
\newtheorem{conj}[theo]{Conjecture}
\newenvironment{conjecture}[1][]
{\begin{conj}[#1]\begin{leftbar}}
{\end{leftbar}\end{conj}}
\newtheorem{exam}[theo]{Example}
\newenvironment{example}[1][]
{\begin{exam}[#1]\begin{leftbar}}
{\end{leftbar}\end{exam}}
\newtheorem{exmp}[exer]{Exercise}
\newenvironment{exercise}[1][]
{\begin{exmp}[#1]\begin{leftbar}}
{\end{leftbar}\end{exmp}}
\newenvironment{statement}{\begin{quote}}{\end{quote}}
\newenvironment{fns}{\begin{footnotesize}}{\end{footnotesize}}
\iffalse
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\fi
\let\sumnonlimits\sum
\let\prodnonlimits\prod
\let\cupnonlimits\bigcup
\let\capnonlimits\bigcap
\renewcommand{\sum}{\sumnonlimits\limits}
\renewcommand{\prod}{\prodnonlimits\limits}
\renewcommand{\bigcup}{\cupnonlimits\limits}
\renewcommand{\bigcap}{\capnonlimits\limits}
\setlength\tablinesep{3pt}
\setlength\arraylinesep{3pt}
\setlength\extrarulesep{3pt}
\voffset=0cm
\hoffset=-0.7cm
\setlength\textheight{22.5cm}
\setlength\textwidth{15.5cm}
\newenvironment{verlong}{}{}
\newenvironment{vershort}{}{}
\newenvironment{noncompile}{}{}
\excludecomment{verlong}
\includecomment{vershort}
\excludecomment{noncompile}
\newcommand{\id}{\operatorname{id}}
\newcommand{\rev}{\operatorname{rev}}
\newcommand{\conncomp}{\operatorname{conncomp}}
\newcommand{\conn}{\operatorname{conn}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\powset}[2][]{\ifthenelse{\equal{#2}{}}{\mathcal{P}\left(#1\right)}{\mathcal{P}_{#1}\left(#2\right)}}
\newcommand{\set}[1]{\left\{ #1 \right\}}
\newcommand{\abs}[1]{\left| #1 \right|}
\newcommand{\tup}[1]{\left( #1 \right)}
\newcommand{\ive}[1]{\left[ #1 \right]}
\newcommand{\verts}[1]{\operatorname{V}\left( #1 \right)}
\newcommand{\edges}[1]{\operatorname{E}\left( #1 \right)}
\newcommand{\arcs}[1]{\operatorname{A}\left( #1 \right)}
\newcommand{\underbrack}[2]{\underbrace{#1}_{\substack{#2}}}
\newcommand{\are}{\ar@{-}}
\newcommand{\arebi}[1][]{\ar@{<-}@/_/[#1] \ar@/^/[#1]}
\newcommand\staircasepath[4]{
\fill[cyan!25]  (#1) rectangle +(#2,#3);
\fill[fill=lime]
(#1)
\foreach \dir in {#4}{
\ifnum\dir=1
-- ++(1,0)
\else
-- ++(0,1)
\fi
} |- (#1);
\draw[help lines] (#1) grid +(#2,#3);
\draw[dashed] (#1) -- +(#2,#2);
\coordinate (prev) at (#1);
\foreach \dir in {#4}{
\ifnum\dir=1
\coordinate (dep) at (1,0);
\else
\coordinate (dep) at (0,1);
\fi
\draw[line width=2pt,-stealth] (prev) -- ++(dep) coordinate (prev);
};
}
\newcommand\delannoypath[4]{
\fill[cyan!25]  (#1) rectangle +(#2,#3);
\fill[fill=lime]
(#1)
\foreach \dir in {#4}{
\ifnum\dir=1
-- ++(1,0)
\else
	  \ifnum\dir=0
-- ++(0,1)
	  \else
	  -- ++(1,1)
	  \fi
\fi
} |- (#1);
\draw[help lines] (#1) grid +(#2,#3);
\coordinate (prev) at (#1);
\foreach \dir in {#4}{
\ifnum\dir=1
\coordinate (dep) at (1,0);
\else
	  \ifnum\dir=0
\coordinate (dep) at (0,1);
	  \else
	  \coordinate (dep) at (1,1);
	  \fi
\fi
\draw[line width=2pt,-stealth] (prev) -- ++(dep) coordinate (prev);
};
}
\newcommand\dyckpath[3]{
\fill[fill=lime]
(#1)
\foreach \dir in {#3}{
\ifnum\dir=1
-- ++(1,-1)
\else
-- ++(1,1)
\fi
} |- (#1);
\draw[help lines] (#1) grid +(2*#2, #2);
\coordinate (prev) at (#1);
\foreach \dir in {#3}{
\ifnum\dir=1
\coordinate (dep) at (1,-1);
\else
\coordinate (dep) at (1,1);
\fi
\draw[line width=2pt,-stealth] (prev) -- ++(dep) coordinate (prev);
};
}
\ihead{Math 4707 Spring 2018 (Darij Grinberg): midterm 2}
\ohead{page \thepage}
\cfoot{}
\begin{document}

\begin{center}
\textbf{Math 4707 Spring 2018 (Darij Grinberg): midterm 2 with solutions
[preliminary version]}
\end{center}

%

%TCIMACRO{\TeXButton{tableofcontents}{\tableofcontents}}%
%BeginExpansion
\tableofcontents
%EndExpansion


\bigskip

Recall the following:

\begin{itemize}
\item If $n\in\mathbb{N}$, then $\left[  n\right]  $ denotes the $n$-element
set $\left\{  1,2,\ldots,n\right\}  $.

\item We use the Iverson bracket notation.
\end{itemize}

Also, here is a collection of identities that we shall use:

\begin{itemize}
\item We have
\begin{equation}
\dbinom{m}{n}=0 \label{eq.binom.0}%
\end{equation}
for every $m\in\mathbb{N}$ and $n\in\mathbb{N}$ satisfying $m<n$.

\item We have%
\begin{equation}
\dbinom{m}{n}=\dbinom{m-1}{n-1}+\dbinom{m-1}{n} \label{eq.binom.rec.m}%
\end{equation}
for any $m\in\mathbb{Z}$ and $n\in\mathbb{Z}$. (This is the recurrence
relation of the binomial coefficients.)

\item We have%
\begin{equation}
\dbinom{m}{n}=\dbinom{m}{m-n} \label{eq.binom.symm}%
\end{equation}
for any $m\in\mathbb{N}$ and $n\in\mathbb{N}$ satisfying $m\geq n$.

\item We have
\begin{equation}
\dbinom{m+n}{m}=\dbinom{m+n}{n} \label{eq.binom.symm2}%
\end{equation}
for any $m\in\mathbb{N}$ and $n\in\mathbb{N}$. (This follows by applying
(\ref{eq.binom.symm}) to $m+n$ and $m$ instead of $m$ and $n$.)

\item We have%
\begin{equation}
\dbinom{m}{n}=\dfrac{m!}{n!\left(  m-n\right)  !} \label{eq.binom.formula}%
\end{equation}
for any $m\in\mathbb{N}$ and $n\in\mathbb{N}$ satisfying $m\geq n$. (This is
\cite[Proposition 3.4]{detnotes}.)

\item We have%
\begin{equation}
\dbinom{m}{n}\neq0 \label{eq.binom.neq0}%
\end{equation}
for any $m\in\mathbb{N}$ and $n\in\mathbb{N}$ satisfying $m\geq n$. (This
follows immediately from (\ref{eq.binom.formula}), since $m!\neq0$.)

\item We have%
\begin{equation}
\dbinom{m}{n}=\dfrac{m}{n}\dbinom{m-1}{n-1} \label{eq.binom.absorp}%
\end{equation}
for any $m\in\mathbb{Q}$ and $n\in\left\{  1,2,3,\ldots\right\}  $. (This is
the \textit{absorption identity}, and is precisely \cite[Proposition
3.22]{detnotes}. Also, it is very easy to check directly.)

\item We have%
\begin{equation}
\dbinom{m}{n}=\dfrac{m-n+1}{n}\dbinom{m}{n-1} \label{eq.binom.absorp2}%
\end{equation}
for any $m\in\mathbb{Q}$ and $n\in\left\{  1,2,3,\ldots\right\}  $. (This is
easy to check\footnote{\textit{Proof of (\ref{eq.binom.absorp2}):} Let
$m\in\mathbb{Q}$ and $n\in\left\{  1,2,3,\ldots\right\}  $. Then, $n\neq0$
(since $n\in\left\{  1,2,3,\ldots\right\}  $), so that the fraction
$\dfrac{m-n+1}{n}$ is well-defined.
\par
We have $n\in\left\{  1,2,3,\ldots\right\}  $; in other words, $n$ is a
positive integer. Hence, $m\left(  m-1\right)  \cdots\left(  m-n+1\right)
=\left(  m\left(  m-1\right)  \cdots\left(  m-n+2\right)  \right)
\cdot\left(  m-n+1\right)  $ and $n!=n\cdot\left(  n-1\right)  !$.
\par
We have $n\in\left\{  1,2,3,\ldots\right\}  \subseteq\mathbb{N}$. Thus, the
definition of $\dbinom{m}{n}$ yields%
\begin{align}
\dbinom{m}{n}  &  =\dfrac{m\left(  m-1\right)  \cdots\left(  m-n+1\right)
}{n!}=\dfrac{\left(  m\left(  m-1\right)  \cdots\left(  m-n+2\right)  \right)
\cdot\left(  m-n+1\right)  }{n\cdot\left(  n-1\right)  !}\nonumber\\
&  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{since }m\left(  m-1\right)  \cdots\left(  m-n+1\right)  =\left(
m\left(  m-1\right)  \cdots\left(  m-n+2\right)  \right)  \cdot\left(
m-n+1\right) \\
\text{and }n!=n\cdot\left(  n-1\right)  !
\end{array}
\right) \nonumber\\
&  =\dfrac{m-n+1}{n}\cdot\dfrac{m\left(  m-1\right)  \cdots\left(
m-n+2\right)  }{\left(  n-1\right)  !}. \label{pf.eq.binom.absorp2.pf.1}%
\end{align}
\par
Moreover, $n-1\in\mathbb{N}$ (since $n\in\left\{  1,2,3,\ldots\right\}  $), so
that the definition of $\dbinom{m}{n-1}$ yields%
\begin{align*}
\dbinom{m}{n-1}  &  =\dfrac{m\left(  m-1\right)  \cdots\left(  m-\left(
n-1\right)  +1\right)  }{\left(  n-1\right)  !}=\dfrac{m\left(  m-1\right)
\cdots\left(  m-n+2\right)  }{\left(  n-1\right)  !}\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{since }m-\left(  n-1\right)
+1=m-n+2\right)  .
\end{align*}
Multiplying this equality by $\dfrac{m-n+1}{n}$, we obtain%
\[
\dfrac{m-n+1}{n}\dbinom{m}{n-1}=\dfrac{m-n+1}{n}\cdot\dfrac{m\left(
m-1\right)  \cdots\left(  m-n+2\right)  }{\left(  n-1\right)  !}.
\]
Comparing this with (\ref{pf.eq.binom.absorp2.pf.1}), we obtain $\dbinom{m}%
{n}=\dfrac{m-n+1}{n}\dbinom{m}{n-1}$. This proves (\ref{eq.binom.absorp2}).}.)

\item Every $n\in\mathbb{N}$ satisfies
\begin{equation}
\sum_{k=0}^{n}\dbinom{n}{k}=2^{n}. \label{eq.binom.1+1}%
\end{equation}
(This is Corollary 1.16b in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18s/4707-2018jan22.pdf}{the
classwork from 22 January 2018}, or \cite[Proposition 3.39 \textbf{(b)}%
]{detnotes}.)

\item Every $n\in\mathbb{N}$ satisfies%
\begin{equation}
\sum_{k=0}^{n}\left(  -1\right)  ^{k}\dbinom{n}{k}=\left[  n=0\right]  .
\label{eq.binom.1-1}%
\end{equation}
(This is Corollary 3.3 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18s/4707-2018feb14.pdf}{the
classwork from 14 February 2018}, or \cite[Proposition 3.39 \textbf{(c)}%
]{detnotes}.)

\item If $m\in\mathbb{N}$ and $n\in\mathbb{N}$, and if $S$ is an $m$-element
set, then
\begin{equation}
\dbinom{m}{n}\text{ is the number of all }n\text{-element subsets of
}S\text{.} \label{eq.binom.subsets}%
\end{equation}
(This is the combinatorial interpretation of the binomial coefficients.)
\end{itemize}

\subsection{Counting first-even tuples}

\begin{exercise}
\label{exe.count.first-even}Let $n$ and $d$ be two positive integers.

An $n$-tuple $\left(  x_{1},x_{2},\ldots,x_{n}\right)  \in\left[  d\right]
^{n}$ will be called \textit{first-even} if its first entry $x_{1}$ occurs in
it an even number of times (i.e., the number of $i\in\left[  n\right]  $
satisfying $x_{i}=x_{1}$ is even). (For example, the $3$-tuples $\left(
1,5,1\right)  $ and $\left(  2,2,3\right)  $ are first-even, while the
$3$-tuple $\left(  4,1,1\right)  $ is not.)

Prove that the number of first-even $n$-tuples in $\left[  d\right]  ^{n}$ is
$\dfrac{1}{2}d\left(  d^{n-1}-\left(  d-2\right)  ^{n-1}\right)  $.
\end{exercise}

Our solution for this exercise will rely on the following definition:

\begin{definition}
Let $n\in\mathbb{N}$ and $d\in\mathbb{N}$. Let $k\in\left[  d\right]  $. An
$n$-tuple $\left(  x_{1},x_{2},\ldots,x_{n}\right)  \in\left[  d\right]  ^{n}$
will be called $k$\textit{-even} if the number $k$ occurs in it an even number
of times (i.e., the number of $i\in\left[  n\right]  $ satisfying $x_{i}=k$ is
even). (For example, the $3$-tuple $\left(  1,4,4\right)  $ is $4$-even and
$3$-even but not $1$-even.)
\end{definition}

This definition generalizes the concept of \textquotedblleft$1$%
-even\textquotedblright\ defined in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18s/hw3s.pdf}{Homework set 3}.
Exercise 5 on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18s/hw3s.pdf}{Homework set 3}
claimed the following:

\begin{proposition}
\label{prop.count.first-even.1-even}Let $n\in\mathbb{N}$, and let $d$ be a
positive integer. Then, the number of $1$-even $n$-tuples in $\left[
d\right]  ^{n}$ is $\dfrac{1}{2}\left(  d^{n}+\left(  d-2\right)  ^{n}\right)
$.
\end{proposition}

The same argument proves the following:

\begin{proposition}
\label{prop.count.first-even.k-even}Let $n\in\mathbb{N}$, and let $d$ be a
positive integer. Let $k\in\left[  d\right]  $. Then, the number of $k$-even
$n$-tuples in $\left[  d\right]  ^{n}$ is $\dfrac{1}{2}\left(  d^{n}+\left(
d-2\right)  ^{n}\right)  $.
\end{proposition}

Indeed, Proposition \ref{prop.count.first-even.1-even} is the particular case
of Proposition \ref{prop.count.first-even.k-even} for $k=1$; but conversely,
Proposition \ref{prop.count.first-even.k-even} can be derived from Proposition
\ref{prop.count.first-even.1-even} by \textquotedblleft renaming $1$ as
$k$\textquotedblright.

\begin{fns}
To make this rigorous, you can argue as follows:

\begin{proof}
[Proof of Proposition \ref{prop.count.first-even.k-even} (sketched).]There is
clearly some permutation $\sigma\in S_{d}$ such that $\sigma\left(  1\right)
=k$. (For example, we can let $\sigma$ be the transposition swapping $1$ with
$k$ when $k\neq1$, and otherwise we can just set $\sigma=\operatorname*{id}$.)
Fix such a $\sigma$. Then, there is a bijection%
\begin{align*}
\left\{  1\text{-even }n\text{-tuples in }\left[  d\right]  ^{n}\right\}   &
\rightarrow\left\{  k\text{-even }n\text{-tuples in }\left[  d\right]
^{n}\right\}  ,\\
\left(  x_{1},x_{2},\ldots,x_{n}\right)   &  \mapsto\left(  \sigma\left(
x_{1}\right)  ,\sigma\left(  x_{2}\right)  ,\ldots,\sigma\left(  x_{n}\right)
\right)  .
\end{align*}
(This is well-defined, because the occurrences of the number $1$ in an
$n$-tuple $\left(  x_{1},x_{2},\ldots,x_{n}\right)  \in\left[  d\right]  ^{n}$
clearly correspond to the occurrences of the number $\sigma\left(  1\right)
=k$ in the $n$-tuple $\left(  \sigma\left(  x_{1}\right)  ,\sigma\left(
x_{2}\right)  ,\ldots,\sigma\left(  x_{n}\right)  \right)  $.) This bijection
shows that%
\begin{align*}
\left\vert \left\{  k\text{-even }n\text{-tuples in }\left[  d\right]
^{n}\right\}  \right\vert  &  =\left\vert \left\{  1\text{-even }%
n\text{-tuples in }\left[  d\right]  ^{n}\right\}  \right\vert \\
&  =\left(  \text{the number of }1\text{-even }n\text{-tuples in }\left[
d\right]  ^{n}\right) \\
&  =\dfrac{1}{2}\left(  d^{n}+\left(  d-2\right)  ^{n}\right)
\ \ \ \ \ \ \ \ \ \ \left(  \text{by Proposition
\ref{prop.count.first-even.1-even}}\right)  .
\end{align*}
In other words, the number of $k$-even $n$-tuples in $\left[  d\right]  ^{n}$
is $\dfrac{1}{2}\left(  d^{n}+\left(  d-2\right)  ^{n}\right)  $. This proves
Proposition \ref{prop.count.first-even.k-even}.
\end{proof}
\end{fns}

\begin{proof}
[Solution to Exercise \ref{exe.count.first-even} (sketched).]We first make the
following claim:

\begin{statement}
\textit{Observation 1:} Let $k\in\left[  d\right]  $. Then, the number of
$n$-tuples in $\left[  d\right]  ^{n-1}$ that are \textbf{not} $k$-even is
$\dfrac{1}{2}\left(  d^{n-1}-\left(  d-2\right)  ^{n-1}\right)  $.
\end{statement}

[\textit{Proof of Observation 1:} Proposition
\ref{prop.count.first-even.k-even} (applied to $n-1$ instead of $n$) shows
that the number of $k$-even $\left(  n-1\right)  $-tuples in $\left[
d\right]  ^{n-1}$ is $\dfrac{1}{2}\left(  d^{n-1}+\left(  d-2\right)
^{n-1}\right)  $. Hence, the number of $\left(  n-1\right)  $-tuples in
$\left[  d\right]  ^{n-1}$ that are \textbf{not} $k$-even is $d^{n-1}%
-\dfrac{1}{2}\left(  d^{n-1}+\left(  d-2\right)  ^{n-1}\right)  $ (since the
total number of $\left(  n-1\right)  $-tuples in $\left[  d\right]  ^{n-1}$ is
$d^{n-1}$). In view of $d^{n-1}-\dfrac{1}{2}\left(  d^{n-1}+\left(
d-2\right)  ^{n-1}\right)  =\dfrac{1}{2}\left(  d^{n-1}-\left(  d-2\right)
^{n-1}\right)  $, this rewrites as follows: The number of $\left(  n-1\right)
$-tuples in $\left[  d\right]  ^{n-1}$ that are \textbf{not} $k$-even is
$\dfrac{1}{2}\left(  d^{n-1}-\left(  d-2\right)  ^{n-1}\right)  $. This proves
Observation 1.]

We can construct each first-even $n$-tuple $\left(  x_{1},x_{2},\ldots
,x_{n}\right)  $ in $\left[  d\right]  ^{n}$ as follows:

\begin{itemize}
\item First, we choose the value of $x_{1}$. We denote this value by $k$.
There are $d$ choices at this step (since this value must belong to $\left[
d\right]  $).

\item Next, we choose the $\left(  n-1\right)  $-tuple $\left(  x_{2}%
,x_{3},\ldots,x_{n}\right)  $. Note that the entry $k=x_{1}$ must occur an
\textbf{odd} number of times in this $\left(  n-1\right)  $-tuple $\left(
x_{2},x_{3},\ldots,x_{n}\right)  $ (because we want the $n$-tuple $\left(
x_{1},x_{2},\ldots,x_{n}\right)  $ to be first-even, so that $x_{1}$ must
occur an \textbf{even} number of times in this $n$-tuple; but the $\left(
n-1\right)  $-tuple $\left(  x_{2},x_{3},\ldots,x_{n}\right)  $ is missing its
very first occurrence, and thus must contain it an \textbf{odd} number of
times). In other words, the $\left(  n-1\right)  $-tuple $\left(  x_{2}%
,x_{3},\ldots,x_{n-1}\right)  $ must \textbf{not} be $k$-even. Thus, there are
$\dfrac{1}{2}\left(  d^{n-1}-\left(  d-2\right)  ^{n-1}\right)  $ choices at
this step (since Observation 1 yields that the number of $\left(  n-1\right)
$-tuples in $\left[  d\right]  ^{n-1}$ that are \textbf{not} $k$-even is
$\dfrac{1}{2}\left(  d^{n-1}-\left(  d-2\right)  ^{n-1}\right)  $).
\end{itemize}

Hence, the total number of first-even $n$-tuples $\left(  x_{1},x_{2}%
,\ldots,x_{n}\right)  $ in $\left[  d\right]  ^{n}$ is
\[
d\cdot\dfrac{1}{2}\left(  d^{n-1}-\left(  d-2\right)  ^{n-1}\right)
=\dfrac{1}{2}d\left(  d^{n-1}-\left(  d-2\right)  ^{n-1}\right)  .
\]
This solves Exercise \ref{exe.count.first-even}.
\end{proof}

\subsection{Counting legal paths (generalization of Catalan numbers)}

Recall the notion of a \textit{lattice path}, defined in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18s/mt1s.pdf}{Midterm 1}. (Lattice
paths have up-steps and right-steps.)

We say that a point $\left(  x,y\right)  \in\mathbb{Z}^{2}$ is
\textit{off-limits} if $y>x$. (Thus, the off-limits points are the ones that
lie strictly above the $x=y$ diagonal in Cartesian coordinates.)

A lattice path $\left(  v_{0},v_{1},\ldots,v_{n}\right)  $ is said to be
\textit{legal} if none of the points $v_{0},v_{1},\ldots,v_{n}$ is off-limits.

For example, the lattice path drawn from $\left(  0,0\right)  $ to $\left(
4,5\right)  $ drawn in the picture%
\[%
%TCIMACRO{\TeXButton{an illegal path}{\begin{tikzpicture}
%\staircasepath{0,0}{5}{4}{1,0,1,1,0,0,0,1,1};
%\end{tikzpicture}
%}}%
%BeginExpansion
\begin{tikzpicture}
\staircasepath{0,0}{5}{4}{1,0,1,1,0,0,0,1,1};
\end{tikzpicture}
%EndExpansion
\]
\footnote{Formally speaking, this lattice path is the list \newline$\left(
\left(  0,0\right)  ,\left(  1,0\right)  ,\left(  1,1\right)  ,\left(
2,1\right)  ,\left(  3,1\right)  ,\left(  3,2\right)  ,\left(  3,3\right)
,\left(  3,4\right)  ,\left(  4,4\right)  ,\left(  5,4\right)  \right)  $.} is
not legal, since it contains the off-limits point $\left(  3,4\right)  $.
Meanwhile, the lattice path from $\left(  0,0\right)  $ to $\left(
4,4\right)  $ drawn in the picture%
\[%
%TCIMACRO{\TeXButton{an illegal path}{\begin{tikzpicture}
%\staircasepath{0,0}{4}{4}{1,1,0,1,0,0,1,0};
%\end{tikzpicture}}}%
%BeginExpansion
\begin{tikzpicture}
\staircasepath{0,0}{4}{4}{1,1,0,1,0,0,1,0};
\end{tikzpicture}%
%EndExpansion
\]
is legal.

For any $n\in\mathbb{Z}$ and $m\in\mathbb{Z}$, we let $L_{n,m}$ be the number
of all legal lattice paths from $\left(  0,0\right)  $ to $\left(  n,m\right)
$.

For each point $v=\left(  x,y\right)  \in\mathbb{Z}^{2}$, we let
$\mathbf{x}\left(  v\right)  $ denote the x-coordinate $x$ of $v$, and we let
$\mathbf{y}\left(  v\right)  $ denote the y-coordinate $y$ of $v$. For
example, $\mathbf{x}\left(  \left(  5,9\right)  \right)  =5$ and
$\mathbf{y}\left(  \left(  5,9\right)  \right)  =9$.

The following facts are easy:

\begin{lemma}
\label{lem.catalan.count-legal.trivi}Let $n\in\mathbb{Z}$ and $m\in\mathbb{Z}$.

\textbf{(a)} If $\left(  v_{0},v_{1},\ldots,v_{p}\right)  $ is a lattice path
from $\left(  0,0\right)  $ to $\left(  n,m\right)  $, then%
\begin{align*}
0  &  =\mathbf{x}\left(  v_{0}\right)  \leq\mathbf{x}\left(  v_{1}\right)
\leq\cdots\leq\mathbf{x}\left(  v_{p}\right)  =n\ \ \ \ \ \ \ \ \ \ \text{and}%
\\
0  &  =\mathbf{y}\left(  v_{0}\right)  \leq\mathbf{y}\left(  v_{1}\right)
\leq\cdots\leq\mathbf{y}\left(  v_{p}\right)  =m.
\end{align*}


\textbf{(b)} If $\left(  v_{0},v_{1},\ldots,v_{p}\right)  $ is a lattice path
from $\left(  0,0\right)  $ to $\left(  n,m\right)  $, then%
\[
\mathbf{x}\left(  v_{i}\right)  +\mathbf{y}\left(  v_{i}\right)
=i\ \ \ \ \ \ \ \ \ \ \text{for each }i\in\left\{  0,1,\ldots,p\right\}  .
\]


\textbf{(c)} If $\left(  v_{0},v_{1},\ldots,v_{p}\right)  $ is a lattice path
from $\left(  0,0\right)  $ to $\left(  n,m\right)  $, then $p=n+m$.

\textbf{(d)} The lattice path $\left(  \left(  0,0\right)  \right)  $
(consisting of the single point $\left(  0,0\right)  $) is the only lattice
path from $\left(  0,0\right)  $ to $\left(  0,0\right)  $.

\textbf{(e)} We have $L_{0,0}=1$.

\textbf{(f)} We have $L_{n,m}=0$ if at least one of the numbers $n$ and $m$ is negative.

\textbf{(g)} We have $L_{n,m}=0$ if $m>n$.
\end{lemma}

\begin{fns}
The following obnoxiously long argument just formalizes the obviousness:

\begin{proof}
[Proof of Lemma \ref{lem.catalan.count-legal.trivi}.]\textbf{(a)} Let $\left(
v_{0},v_{1},\ldots,v_{p}\right)  $ be a lattice path from $\left(  0,0\right)
$ to $\left(  n,m\right)  $. Thus, the definition of a lattice path shows that
$v_{0}=\left(  0,0\right)  $ and $v_{p}=\left(  n,m\right)  $. From
$v_{0}=\left(  0,0\right)  $, we obtain $\mathbf{x}\left(  v_{0}\right)  =0$
and $\mathbf{y}\left(  v_{0}\right)  =0$. From $v_{p}=\left(  n,m\right)  $,
we obtain $\mathbf{x}\left(  v_{p}\right)  =n$ and $\mathbf{y}\left(
v_{p}\right)  =m$.

Let $i\in\left[  p\right]  $. Then, the definition of a lattice path shows
that the difference vector $v_{i}-v_{i-1}$ is either $\left(  0,1\right)  $ or
$\left(  1,0\right)  $ (because $\left(  v_{0},v_{1},\ldots,v_{p}\right)  $ is
a lattice path). In other words, either $v_{i}-v_{i-1}=\left(  0,1\right)  $
or $v_{i}-v_{i-1}=\left(  1,0\right)  $. Thus, $\mathbf{x}\left(
v_{i-1}\right)  \leq\mathbf{x}\left(  v_{i}\right)  $%
\ \ \ \ \footnote{\textit{Proof.} We know that either $v_{i}-v_{i-1}=\left(
0,1\right)  $ or $v_{i}-v_{i-1}=\left(  1,0\right)  $. Hence, we are in one of
the following two cases:
\par
\textit{Case 1:} We have $v_{i}-v_{i-1}=\left(  0,1\right)  $.
\par
\textit{Case 2:} We have $v_{i}-v_{i-1}=\left(  1,0\right)  $.
\par
Let us first consider Case 1. In this case, we have $v_{i}-v_{i-1}=\left(
0,1\right)  $. Thus, $\mathbf{x}\left(  v_{i}-v_{i-1}\right)  =0$. But
subtraction of vectors in $\mathbb{Z}^{2}$ is done coordinatewise. Thus,
$\mathbf{x}\left(  v_{i}-v_{i-1}\right)  =\mathbf{x}\left(  v_{i}\right)
-\mathbf{x}\left(  v_{i-1}\right)  $. Hence, $\mathbf{x}\left(  v_{i}\right)
-\mathbf{x}\left(  v_{i-1}\right)  =\mathbf{x}\left(  v_{i}-v_{i-1}\right)
=0$, so that $\mathbf{x}\left(  v_{i}\right)  =\mathbf{x}\left(
v_{i-1}\right)  $. Therefore, $\mathbf{x}\left(  v_{i-1}\right)
=\mathbf{x}\left(  v_{i}\right)  \leq\mathbf{x}\left(  v_{i}\right)  $. Thus,
$\mathbf{x}\left(  v_{i-1}\right)  \leq\mathbf{x}\left(  v_{i}\right)  $ is
proven in Case 1.
\par
Let us next consider Case 2. In this case, we have $v_{i}-v_{i-1}=\left(
1,0\right)  $. Thus, $\mathbf{x}\left(  v_{i}-v_{i-1}\right)  =1$. But
subtraction of vectors in $\mathbb{Z}^{2}$ is done coordinatewise. Thus,
$\mathbf{x}\left(  v_{i}-v_{i-1}\right)  =\mathbf{x}\left(  v_{i}\right)
-\mathbf{x}\left(  v_{i-1}\right)  $. Hence, $\mathbf{x}\left(  v_{i}\right)
-\mathbf{x}\left(  v_{i-1}\right)  =\mathbf{x}\left(  v_{i}-v_{i-1}\right)
=1$, so that $\mathbf{x}\left(  v_{i}\right)  =\mathbf{x}\left(
v_{i-1}\right)  +1\geq\mathbf{x}\left(  v_{i-1}\right)  $. Therefore,
$\mathbf{x}\left(  v_{i-1}\right)  \leq\mathbf{x}\left(  v_{i}\right)  $.
Thus, $\mathbf{x}\left(  v_{i-1}\right)  \leq\mathbf{x}\left(  v_{i}\right)  $
is proven in Case 2.
\par
We have now proven $\mathbf{x}\left(  v_{i-1}\right)  \leq\mathbf{x}\left(
v_{i}\right)  $ in each of the two Cases 1 and 2. Hence, $\mathbf{x}\left(
v_{i-1}\right)  \leq\mathbf{x}\left(  v_{i}\right)  $ always holds. Qed.}.

Now, forget that we fixed $i$. We thus have proven that $\mathbf{x}\left(
v_{i-1}\right)  \leq\mathbf{x}\left(  v_{i}\right)  $ for each $i\in\left[
p\right]  $. In other words, $\mathbf{x}\left(  v_{0}\right)  \leq
\mathbf{x}\left(  v_{1}\right)  \leq\cdots\leq\mathbf{x}\left(  v_{p}\right)
$. Combining this with $\mathbf{x}\left(  v_{0}\right)  =0$ and $\mathbf{x}%
\left(  v_{p}\right)  =n$, we obtain%
\[
0=\mathbf{x}\left(  v_{0}\right)  \leq\mathbf{x}\left(  v_{1}\right)
\leq\cdots\leq\mathbf{x}\left(  v_{p}\right)  =n.
\]
Similarly,%
\[
0=\mathbf{y}\left(  v_{0}\right)  \leq\mathbf{y}\left(  v_{1}\right)
\leq\cdots\leq\mathbf{y}\left(  v_{p}\right)  =m.
\]
Thus, Lemma \ref{lem.catalan.count-legal.trivi} \textbf{(a)} is proven.

\textbf{(b)} Let $\left(  v_{0},v_{1},\ldots,v_{p}\right)  $ be a lattice path
from $\left(  0,0\right)  $ to $\left(  n,m\right)  $. Thus, the definition of
a lattice path shows that $v_{0}=\left(  0,0\right)  $ and $v_{p}=\left(
n,m\right)  $. From $v_{0}=\left(  0,0\right)  $, we obtain $\mathbf{x}\left(
v_{0}\right)  =0$ and $\mathbf{y}\left(  v_{0}\right)  =0$.

For each $i\in\left\{  0,1,\ldots,p\right\}  $, we define an integer $z_{i}$
by $z_{i}=\mathbf{x}\left(  v_{i}\right)  +\mathbf{y}\left(  v_{i}\right)  -i$.

Let $i\in\left[  p\right]  $. Then, the definition of a lattice path shows
that the difference vector $v_{i}-v_{i-1}$ is either $\left(  0,1\right)  $ or
$\left(  1,0\right)  $ (because $\left(  v_{0},v_{1},\ldots,v_{p}\right)  $ is
a lattice path). In other words, either $v_{i}-v_{i-1}=\left(  0,1\right)  $
or $v_{i}-v_{i-1}=\left(  1,0\right)  $. Thus, $z_{i}=z_{i-1}$%
\ \ \ \ \footnote{\textit{Proof.} The definition of $z_{i}$ yields
$z_{i}=\mathbf{x}\left(  v_{i}\right)  +\mathbf{y}\left(  v_{i}\right)  -i$.
But the definition of $z_{i-1}$ yields $z_{i-1}=\mathbf{x}\left(
v_{i-1}\right)  +\mathbf{y}\left(  v_{i-1}\right)  -\left(  i-1\right)  $.
\par
We know that either $v_{i}-v_{i-1}=\left(  0,1\right)  $ or $v_{i}%
-v_{i-1}=\left(  1,0\right)  $. Hence, we are in one of the following two
cases:
\par
\textit{Case 1:} We have $v_{i}-v_{i-1}=\left(  0,1\right)  $.
\par
\textit{Case 2:} We have $v_{i}-v_{i-1}=\left(  1,0\right)  $.
\par
Let us first consider Case 1. In this case, we have $v_{i}-v_{i-1}=\left(
0,1\right)  $. Thus, $\mathbf{x}\left(  v_{i}-v_{i-1}\right)  =0$ and
$\mathbf{y}\left(  v_{i}-v_{i-1}\right)  =1$. But subtraction of vectors in
$\mathbb{Z}^{2}$ is done coordinatewise. Thus, $\mathbf{x}\left(
v_{i}-v_{i-1}\right)  =\mathbf{x}\left(  v_{i}\right)  -\mathbf{x}\left(
v_{i-1}\right)  $. Hence, $\mathbf{x}\left(  v_{i}\right)  -\mathbf{x}\left(
v_{i-1}\right)  =\mathbf{x}\left(  v_{i}-v_{i-1}\right)  =0$. Hence,
$\mathbf{x}\left(  v_{i}\right)  =\mathbf{x}\left(  v_{i-1}\right)  $.
\par
Also, subtraction of vectors in $\mathbb{Z}^{2}$ is done coordinatewise. Thus,
$\mathbf{y}\left(  v_{i}-v_{i-1}\right)  =\mathbf{y}\left(  v_{i}\right)
-\mathbf{y}\left(  v_{i-1}\right)  $. Hence, $\mathbf{y}\left(  v_{i}\right)
-\mathbf{y}\left(  v_{i-1}\right)  =\mathbf{y}\left(  v_{i}-v_{i-1}\right)
=1$. Hence, $\mathbf{y}\left(  v_{i}\right)  =1+\mathbf{y}\left(
v_{i-1}\right)  $.
\par
Thus,%
\begin{align*}
z_{i}  &  =\underbrace{\mathbf{x}\left(  v_{i}\right)  }_{=\mathbf{x}\left(
v_{i-1}\right)  }+\underbrace{\mathbf{y}\left(  v_{i}\right)  }_{=1+\mathbf{y}%
\left(  v_{i-1}\right)  }-i=\mathbf{x}\left(  v_{i-1}\right)  +\left(
1+\mathbf{y}\left(  v_{i-1}\right)  \right)  -i\\
&  =\mathbf{x}\left(  v_{i-1}\right)  +\mathbf{y}\left(  v_{i-1}\right)
-i+1=\mathbf{x}\left(  v_{i-1}\right)  +\mathbf{y}\left(  v_{i-1}\right)
-\left(  i-1\right)  =z_{i-1}%
\end{align*}
(since $z_{i-1}=\mathbf{x}\left(  v_{i-1}\right)  +\mathbf{y}\left(
v_{i-1}\right)  -\left(  i-1\right)  $). Thus, $z_{i}=z_{i-1}$ is proven in
Case 1.
\par
Similarly, we can prove $z_{i}=z_{i-1}$ in Case 2.
\par
We have now proven $z_{i}=z_{i-1}$ in each of the two Cases 1 and 2. Hence,
$z_{i}=z_{i-1}$ always holds. Qed.}. In other words, $z_{i-1}=z_{i}$.

Now, forget that we fixed $i$. We thus have proven that $z_{i-1}=z_{i}$ for
each $i\in\left[  p\right]  $. In other words, $z_{0}=z_{1}=\cdots=z_{p}$.

Now, let $i\in\left\{  0,1,\ldots,p\right\}  $ be arbitrary. Then, from
$z_{0}=z_{1}=\cdots=z_{p}$, we obtain
\begin{align*}
z_{i}  &  =z_{0}=\underbrace{\mathbf{x}\left(  v_{0}\right)  }_{=0}%
+\underbrace{\mathbf{y}\left(  v_{0}\right)  }_{=0} - 0
\ \ \ \ \ \ \ \ \ \ \left(  \text{by the definition of }z_{0}\right) \\
&  =0.
\end{align*}
Hence, $0=z_{i}=\mathbf{x}\left(  v_{i}\right)  +\mathbf{y}\left(
v_{i}\right)  -i$ (by the definition of $z_{i}$). In other words,
$\mathbf{x}\left(  v_{i}\right)  +\mathbf{y}\left(  v_{i}\right)  =i$. This
proves Lemma \ref{lem.catalan.count-legal.trivi} \textbf{(b)}.

\textbf{(c)} Let $\left(  v_{0},v_{1},\ldots,v_{p}\right)  $ be a lattice path
from $\left(  0,0\right)  $ to $\left(  n,m\right)  $. Thus, the definition of
a lattice path shows that $v_{0}=\left(  0,0\right)  $ and $v_{p}=\left(
n,m\right)  $. From $v_{p}=\left(  n,m\right)  $, we obtain $\mathbf{x}\left(
v_{p}\right)  =n$ and $\mathbf{y}\left(  v_{p}\right)  =m$.

But Lemma \ref{lem.catalan.count-legal.trivi} \textbf{(b)} (applied to $i=p$)
yields $\mathbf{x}\left(  v_{p}\right)  +\mathbf{y}\left(  v_{p}\right)  =p$.
Hence, $p=\underbrace{\mathbf{x}\left(  v_{p}\right)  }_{=n}%
+\underbrace{\mathbf{y}\left(  v_{p}\right)  }_{=m}=n+m$. This proves Lemma
\ref{lem.catalan.count-legal.trivi} \textbf{(c)}.

\textbf{(d)} Clearly, the lattice path $\left(  \left(  0,0\right)  \right)  $
(containing just the single point $\left(  0,0\right)  $) is a lattice path
from $\left(  0,0\right)  $ to $\left(  0,0\right)  $.

Let $\left(  v_{0},v_{1},\ldots,v_{p}\right)  $ be a lattice path from
$\left(  0,0\right)  $ to $\left(  0,0\right)  $. Thus, the definition of a
lattice path shows that $v_{0}=\left(  0,0\right)  $ and $v_{p}=\left(
0,0\right)  $. But Lemma \ref{lem.catalan.count-legal.trivi} \textbf{(c)}
(applied to $0$ and $0$ instead of $n$ and $m$) yields $p=0+0=0$. Hence,
$\left(  v_{0},v_{1},\ldots,v_{p}\right)  =\left(  v_{0},v_{1},\ldots
,v_{0}\right)  =\left(  v_{0}\right)  =\left(  \left(  0,0\right)  \right)  $
(since $v_{0}=\left(  0,0\right)  $).

Now, forget that we fixed $\left(  v_{0},v_{1},\ldots,v_{p}\right)  $. We thus
have shown that if $\left(  v_{0},v_{1},\ldots,v_{p}\right)  $ is a lattice
path from $\left(  0,0\right)  $ to $\left(  0,0\right)  $, then $\left(
v_{0},v_{1},\ldots,v_{p}\right)  =\left(  \left(  0,0\right)  \right)  $. In
other words, every lattice path from $\left(  0,0\right)  $ to $\left(
0,0\right)  $ must be equal to $\left(  \left(  0,0\right)  \right)  $. Hence,
the path $\left(  \left(  0,0\right)  \right)  $ is the only lattice path from
$\left(  0,0\right)  $ to $\left(  0,0\right)  $ (because we already know that
$\left(  \left(  0,0\right)  \right)  $ is a lattice path from $\left(
0,0\right)  $ to $\left(  0,0\right)  $). This proves Lemma
\ref{lem.catalan.count-legal.trivi} \textbf{(d)}.

\textbf{(e)} We must prove that $L_{0,0}=1$. In other words, we must prove
that there is exactly one legal lattice path from $\left(  0,0\right)  $ to
$\left(  0,0\right)  $ (because $L_{0,0}$ was defined as the number of all
legal lattice paths from $\left(  0,0\right)  $ to $\left(  0,0\right)  $). So
let us prove this.

Clearly, the lattice path $\left(  \left(  0,0\right)  \right)  $ (containing
just the single point $\left(  0,0\right)  $) is a lattice path from $\left(
0,0\right)  $ to $\left(  0,0\right)  $, and is legal (since the point
$\left(  0,0\right)  $ is not off-limits). Hence, there exists at least one
legal lattice path from $\left(  0,0\right)  $ to $\left(  0,0\right)  $
(namely, this lattice path $\left(  \left(  0,0\right)  \right)  $).

But Lemma \ref{lem.catalan.count-legal.trivi} \textbf{(d)} yields that the
lattice path $\left(  \left(  0,0\right)  \right)  $ is the only lattice path
from $\left(  0,0\right)  $ to $\left(  0,0\right)  $. Hence, the lattice path
$\left(  \left(  0,0\right)  \right)  $ is the only \textbf{legal} lattice
path from $\left(  0,0\right)  $ to $\left(  0,0\right)  $ as well. Thus,
there is \textbf{exactly one} legal lattice path from $\left(  0,0\right)  $
to $\left(  0,0\right)  $ (namely, $\left(  \left(  0,0\right)  \right)  $).
In other words, $L_{0,0}=1$ (since $L_{0,0}$ is the number of all legal
lattice paths from $\left(  0,0\right)  $ to $\left(  0,0\right)  $). This
proves Lemma \ref{lem.catalan.count-legal.trivi} \textbf{(e)}.

\textbf{(f)} Assume that at least one of the numbers $n$ and $m$ is negative.
We must prove that $L_{n,m}=0$. In other words, we must prove that there are
no legal lattice paths from $\left(  0,0\right)  $ to $\left(  n,m\right)  $
(because $L_{n,m}$ was defined as the number of all legal lattice paths from
$\left(  0,0\right)  $ to $\left(  n,m\right)  $). So let us prove this.

Let $\left(  v_{0},v_{1},\ldots,v_{p}\right)  $ be a legal lattice path from
$\left(  0,0\right)  $ to $\left(  n,m\right)  $. Then, Lemma
\ref{lem.catalan.count-legal.trivi} \textbf{(a)} yields%
\begin{align*}
0  &  =\mathbf{x}\left(  v_{0}\right)  \leq\mathbf{x}\left(  v_{1}\right)
\leq\cdots\leq\mathbf{x}\left(  v_{p}\right)  =n\ \ \ \ \ \ \ \ \ \ \text{and}%
\\
0  &  =\mathbf{y}\left(  v_{0}\right)  \leq\mathbf{y}\left(  v_{1}\right)
\leq\cdots\leq\mathbf{y}\left(  v_{p}\right)  =m.
\end{align*}
Hence, $0\leq n$ and $0\leq m$. Thus, $n$ is nonnegative (since $0\leq n$) and
$m$ is nonnegative (since $0\leq m$). Hence, both $n$ and $m$ are nonnegative.
This contradicts the fact that at least one of $n$ and $m$ is negative.

Now, forget that we fixed $\left(  v_{0},v_{1},\ldots,v_{p}\right)  $. We thus
have obtained a contradiction for each legal lattice path $\left(  v_{0}%
,v_{1},\ldots,v_{p}\right)  $ from $\left(  0,0\right)  $ to $\left(
n,m\right)  $. Hence, there are no legal lattice paths from $\left(
0,0\right)  $ to $\left(  n,m\right)  $. In other words, $L_{n,m}=0$ (since
$L_{n,m}$ is the number of all legal lattice paths from $\left(  0,0\right)  $
to $\left(  n,m\right)  $). This proves Lemma
\ref{lem.catalan.count-legal.trivi} \textbf{(f)}.

\textbf{(g)} Assume that $m>n$. We must prove that $L_{n,m}=0$. In other
words, we must prove that there are no legal lattice paths from $\left(
0,0\right)  $ to $\left(  n,m\right)  $ (because $L_{n,m}$ was defined as the
number of all legal lattice paths from $\left(  0,0\right)  $ to $\left(
n,m\right)  $). So let us prove this.

Let $\left(  v_{0},v_{1},\ldots,v_{p}\right)  $ be a legal lattice path from
$\left(  0,0\right)  $ to $\left(  n,m\right)  $. Thus, the definition of a
lattice path shows that $v_{0}=\left(  0,0\right)  $ and $v_{p}=\left(
n,m\right)  $. Moreover, the definition of \textquotedblleft
legal\textquotedblright\ shows that none of the points $v_{0},v_{1}%
,\ldots,v_{p}$ is off-limits (since the lattice path $\left(  v_{0}%
,v_{1},\ldots,v_{p}\right)  $ is legal). Hence, in particular, the point
$v_{p}$ is not off-limits.

But $m>n$. Thus, the point $\left(  n,m\right)  $ is off-limits. In other
words, the point $v_{p}$ is off-limits (since $v_{p}=\left(  n,m\right)  $).
This contradicts the fact that the point $v_{p}$ is not off-limits.

Now, forget that we fixed $\left(  v_{0},v_{1},\ldots,v_{p}\right)  $. We thus
have obtained a contradiction for each legal lattice path $\left(  v_{0}%
,v_{1},\ldots,v_{p}\right)  $ from $\left(  0,0\right)  $ to $\left(
n,m\right)  $. Hence, there are no legal lattice paths from $\left(
0,0\right)  $ to $\left(  n,m\right)  $. In other words, $L_{n,m}=0$ (since
$L_{n,m}$ is the number of all legal lattice paths from $\left(  0,0\right)  $
to $\left(  n,m\right)  $). This proves Lemma
\ref{lem.catalan.count-legal.trivi} \textbf{(g)}.
\end{proof}
\end{fns}

\begin{remark}
If you know the notion of a directed graph (a.k.a. digraph), you will
immediately recognize the legal lattice paths as the paths in a certain
(infinite) directed graph, whose vertices are the pairs $\left(  x, y\right)
\in\mathbb{Z}^{2}$ satisfying $y \leq x$, and whose arcs are $\left(  x,
y\right)  \to\left(  x, y+1\right)  $ and $\left(  x, y\right)  \to\left(
x+1, y\right)  $.
\end{remark}

\begin{noncompile}
\begin{remark}
Clearly,
\[
L_{n,m}=0\ \ \ \ \ \ \ \ \ \ \text{if any of }n\text{ and }m\text{ is
negative}%
\]
(because a lattice path from $\left(  0,0\right)  $ to $\left(  n,m\right)  $
can only exist if both $n$ and $m$ are nonnegative\footnote{Why?
\par
Let $\left(  v_{0},v_{1},\ldots,v_{g}\right)  $ be a lattice path from
$\left(  0,0\right)  $ to $\left(  n,m\right)  $. We must show that both $n$
and $m$ are nonnegative.
\par
Recall that $\left(  v_{0},v_{1},\ldots,v_{g}\right)  $ is a lattice path from
$\left(  0,0\right)  $ to $\left(  n,m\right)  $. Hence, $v_{0}=\left(
0,0\right)  $ and $v_{g}=\left(  n,m\right)  $.
\par
Now, each $i\in\left\{  0,1,\ldots,g\right\}  $ satisfies $v_{i}\in
\mathbb{N}^{2}$. (This is proven by induction on $i$, where the induction base
uses $v_{0}=\left(  0,0\right)  \in\mathbb{N}^{2}$, and the induction step
observes that an up-step or a right-step starting from a point in
$\mathbb{N}^{2}$ necessarily leads to a point in $\mathbb{N}^{2}$.) Thus, in
particular, $v_{g}\in\mathbb{N}^{2}$, so that $\left(  n,m\right)  =v_{g}%
\in\mathbb{N}^{2}$. Hence, both $n$ and $m$ are nonnegative. Qed.}). Also,
\[
L_{n,m}=0\ \ \ \ \ \ \ \ \ \ \text{if }m>n
\]
(because if $m>n$, then the point $\left(  n,m\right)  $ is off-limits, and
thus a legal lattice path cannot end at $\left(  n,m\right)  $).
\end{remark}
\end{noncompile}

\begin{exercise}
\label{exe.catalan.count-legal}\textbf{(a)} Prove that $L_{n,m}=L_{n-1,m}%
+L_{n,m-1}$ for any $n\in\mathbb{Z}$ and $m\in\mathbb{Z}$ satisfying $n\geq m$
and $\left(  n,m\right)  \neq\left(  0,0\right)  $.

\textbf{(b)} Prove that%
\[
L_{n,m}=\dbinom{n+m}{m}-\dbinom{n+m}{m-1}%
\]
for all $n\in\mathbb{N}$ and $m\in\mathbb{N}$ satisfying $n\geq m-1$.

[The requirement $n\geq m-1$ as opposed to $n\geq m$ is not a typo; the
equality still holds for $n=m-1$, albeit for fairly simple reasons.]

\textbf{(c)} Prove that $L_{n,m}=\dfrac{n+1-m}{n+1}\dbinom{n+m}{m}$ for all
$n\in\mathbb{N}$ and $m\in\mathbb{N}$ satisfying $n\geq m-1$.

\textbf{(d)} Prove that $L_{n,n}=\dfrac{1}{n+1}\dbinom{2n}{n}$ for any
$n\in\mathbb{N}$.
\end{exercise}

\begin{remark}
Exercise \ref{exe.catalan.count-legal} \textbf{(c)} can be rewritten as
follows:%
\[
L_{n,m}=\dfrac{n+1-m}{n+1+m}\dbinom{n+1+m}{n+1}%
\]
for all $n\in\mathbb{N}$ and $m\in\mathbb{N}$ satisfying $n\geq m-1$.

This is a particular case of the so-called \textit{ballot theorem} (see, e.g.,
\cite{Renaul07}), obtained by setting $a=n+1$, $b=m$ and $k=1$. Indeed, a
legal lattice path from $\left(  0,0\right)  $ to $\left(  n,m\right)  $
corresponds to a way to count $n+1$ votes for candidate $A$ and $m$ votes for
candidate $B$ during an (anonymous) election in such a way that candidate $A$
leads (i.e., has more votes than candidate $B$) throughout the counting
process (at least after the first vote has been counted). (If you have such a
vote counting process, you can construct the corresponding lattice path as
follows: Ignore the first vote (which is necessarily a vote for $A$, since
otherwise $A$ would lose the lead right away). Every time a vote for $A$ is
counted, take a right-step; every time a vote for $B$ is counted, take an up-step.)

Exercise \ref{exe.catalan.count-legal} \textbf{(d)} is, of course, equivalent
to the well-known fact that the Catalan numbers $\dfrac{1}{n+1}\dbinom{2n}{n}$
count Dyck words and Dyck paths. Vic Reiner proved this in two different ways
(once using generating functions and once combinatorially) in one of the
classes he substituted.

We shall solve Exercise \ref{exe.catalan.count-legal} \textbf{(b)} by a (more
or less) straightforward induction on $n+m$. Exercise
\ref{exe.catalan.count-legal} \textbf{(d)} will follow from Exercise
\ref{exe.catalan.count-legal} \textbf{(b)} (via Exercise
\ref{exe.catalan.count-legal} \textbf{(c)}). However, it is rather difficult
to prove Exercise \ref{exe.catalan.count-legal} \textbf{(d)} directly by
induction. Thus, if one wants to prove Exercise \ref{exe.catalan.count-legal}
\textbf{(d)} by induction, one is more or less forced to generalize it to
Exercise \ref{exe.catalan.count-legal} \textbf{(b)}. This illustrates an
important phenomenon in mathematics: A more general statement is often easier
to prove than a less general one (particularly when the proof uses induction).
Thus, generalizing is a problem-solving skill.
\end{remark}

\begin{proof}
[Solution to Exercise \ref{exe.catalan.count-legal} (sketched).]In the
following, the word \textquotedblleft point\textquotedblright\ will always
mean a pair $\left(  x,y\right)  \in\mathbb{Z}^{2}$ (and will be regarded as a
point in the Euclidean plane $\mathbb{R}^{2}$). The word \textquotedblleft
path\textquotedblright\ will always mean a lattice path. Moreover, if $n$ and
$m$ are two integers, then \textquotedblleft path to $\left(  n,m\right)
$\textquotedblright\ shall always mean \textquotedblleft path from $\left(
0,0\right)  $ to $\left(  n,m\right)  $\textquotedblright. (So, paths start at
$\left(  0,0\right)  $ by default.)

For any $n\in\mathbb{Z}$ and $m\in\mathbb{Z}$, we have%
\begin{align}
L_{n,m}  &  =\left(  \text{the number of all legal lattice paths from }\left(
0,0\right)  \text{ to }\left(  n,m\right)  \right) \nonumber\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{by the definition of }L_{n,m}\right)
\nonumber\\
&  =\left(  \text{the number of all legal paths to }\left(  n,m\right)
\right)  \label{sol.catalan.count-legal.Lnm=}%
\end{align}
(because we abbreviate \textquotedblleft lattice paths from $\left(
0,0\right)  $ to $\left(  n,m\right)  $\textquotedblright\ as
\textquotedblleft paths to $\left(  n,m\right)  $\textquotedblright).

A \textit{step} in a path $\left(  v_{0},v_{1},\ldots,v_{n}\right)  $ means a
pair of the form $\left(  v_{i-1},v_{i}\right)  $ for some $i\in\left[
n\right]  $. More precisely, this pair $\left(  v_{i-1},v_{i}\right)  $ will
be called the $i$\textit{-th step} of the path.

We say that a path $\left(  v_{0},v_{1},\ldots,v_{n}\right)  $ \textit{passes}
through a point $w$ if $w\in\left\{  v_{0},v_{1},\ldots,v_{n}\right\}  $.

\textbf{(a)} Let $n\in\mathbb{Z}$ and $m\in\mathbb{Z}$ be such that $n\geq m$
and $\left(  n,m\right)  \neq\left(  0,0\right)  $. If the point $\left(
n,m\right)  $ was off-limits, then we would have $m>n$, which would contradict
$n\geq m$. Thus, the point $\left(  n,m\right)  $ is not off-limits.

The equality (\ref{sol.catalan.count-legal.Lnm=}) (applied to $m-1$ instead of
$m$) yields
\begin{equation}
L_{n,m-1}=\left(  \text{the number of all legal paths to }\left(
n,m-1\right)  \right)  . \label{sol.catalan.count-legal.a.Lnm-1=}%
\end{equation}


Any path to $\left(  n,m\right)  $ contains at least one step (since
otherwise, we would have $\left(  n,m\right)  =\left(  0,0\right)  $, which
would contradict $\left(  n,m\right)  \neq\left(  0,0\right)  $), and thus has
a \textbf{last} step. This last step must be either an up-step, or a
right-step. Hence,%
\begin{align}
&  \left(  \text{the number of all legal paths to }\left(  n,m\right)  \right)
\nonumber\\
&  =\left(  \text{the number of all legal paths to }\left(  n,m\right)  \text{
whose last step is an up-step}\right) \nonumber\\
&  \ \ \ \ \ \ \ \ \ \ +\left(  \text{the number of all legal paths to
}\left(  n,m\right)  \text{ whose last step is a right-step}\right)  .
\label{sol.catalan.count-legal.a.step1}%
\end{align}
Let us now compute the two numbers on the right hand side.

Any legal path $\mathbf{p}$ to $\left(  n,m\right)  $ whose last step is an
up-step must pass through $\left(  n,m-1\right)  $ (because this is the point
from which an up-step leads to $\left(  n,m\right)  $). Thus, this path
$\mathbf{p}$ consists of two parts: the first part is a path to $\left(
n,m-1\right)  $; the second part is a single up-step from $\left(
n,m-1\right)  $ to $\left(  n,m\right)  $. Let us denote the first part by
$L\left(  \mathbf{p}\right)  $; this first part $L\left(  \mathbf{p}\right)  $
is still legal (because any off-limits point on it would also be contained in
$\mathbf{p}$). Hence, we have defined a map%
\begin{align*}
L  &  :\left\{  \text{legal paths to }\left(  n,m\right)  \text{ whose last
step is an up-step}\right\} \\
&  \rightarrow\left\{  \text{legal paths to }\left(  n,m-1\right)  \right\}
\end{align*}
(which simply removes the last step from a path). This map $L$ is a bijection
(indeed, the inverse map simply adds an up-step at the end of a
path\footnote{Why is this inverse map well-defined?
\par
We must show that if $\mathbf{q}$ is a legal path to $\left(  n,m-1\right)  $,
then adding an up-step at the end of $\mathbf{q}$ results in a legal path to
$\left(  n,m\right)  $ whose last step is an up-step. It is clear that adding
an up-step at the end of $\mathbf{q}$ results in a path to $\left(
n,m\right)  $ whose last step is an up-step; let us denote this latter path by
$\mathbf{q}^{\prime}$. All we need to check is that this new path
$\mathbf{q}^{\prime}$ is legal.
\par
The path $\mathbf{q}$ is legal; in other words, none of the points on
$\mathbf{q}$ is off-limits. Also, the point $\left(  n,m\right)  $ is not
off-limits.
\par
Recall that the path $\mathbf{q}^{\prime}$ is obtained by adding an up-step at
the end of $\mathbf{q}$. Thus, the points on this path $\mathbf{q}^{\prime}$
are the points on $\mathbf{q}$ and the new point $\left(  n,m\right)  $ (which
is where the newly added up-step leads). Since neither the points on
$\mathbf{q}$ nor the new point $\left(  n,m\right)  $ are off-limits, we thus
conclude that none of the points on $\mathbf{q}^{\prime}$ is off-limits. In
other words, the path $\mathbf{q}^{\prime}$ is legal. This is exactly what we
wanted to show.}). Thus,
\begin{align*}
&  \left\vert \left\{  \text{legal paths to }\left(  n,m-1\right)  \right\}
\right\vert \\
&  =\left\vert \left\{  \text{legal paths to }\left(  n,m\right)  \text{ whose
last step is an up-step}\right\}  \right\vert \\
&  =\left(  \text{the number of all legal paths to }\left(  n,m\right)  \text{
whose last step is an up-step}\right)  .
\end{align*}
Comparing this with%
\begin{align*}
\left\vert \left\{  \text{legal paths to }\left(  n,m-1\right)  \right\}
\right\vert  &  =\left(  \text{the number of all legal paths to }\left(
n,m-1\right)  \right) \\
&  =L_{n,m-1}\ \ \ \ \ \ \ \ \ \ \left(  \text{by
(\ref{sol.catalan.count-legal.a.Lnm-1=})}\right)  ,
\end{align*}
we obtain%
\[
\left(  \text{the number of all legal paths to }\left(  n,m\right)  \text{
whose last step is an up-step}\right)  =L_{n,m-1}.
\]
Similarly,%
\[
\left(  \text{the number of all legal paths to }\left(  n,m\right)  \text{
whose last step is a right-step}\right)  =L_{n-1,m}.
\]
Hence, (\ref{sol.catalan.count-legal.a.step1}) becomes%
\begin{align*}
&  \left(  \text{the number of all paths to }\left(  n,m\right)  \right) \\
&  =\underbrace{\left(  \text{the number of all paths to }\left(  n,m\right)
\text{ whose last step is an up-step}\right)  }_{=L_{n,m-1}}\\
&  \ \ \ \ \ \ \ \ \ \ +\underbrace{\left(  \text{the number of all paths to
}\left(  n,m\right)  \text{ whose last step is a right-step}\right)
}_{=L_{n-1,m}}\\
&  =L_{n,m-1}+L_{n-1,m}=L_{n-1,m}+L_{n,m-1}.
\end{align*}
Hence, (\ref{sol.catalan.count-legal.Lnm=}) yields%
\[
L_{n,m}=\left(  \text{the number of all legal paths to }\left(  n,m\right)
\right)  =L_{n-1,m}+L_{n,m-1}.
\]
This solves Exercise \ref{exe.catalan.count-legal} \textbf{(a)}.

\textbf{(b)} We shall solve Exercise \ref{exe.catalan.count-legal}
\textbf{(b)} by strong induction on $n+m$:

\textit{Induction step:} Let $k\in\mathbb{N}$. Assume (as the induction
hypothesis) that Exercise \ref{exe.catalan.count-legal} \textbf{(b)} holds
whenever $n+m<k$. We must prove that Exercise \ref{exe.catalan.count-legal}
\textbf{(b)} holds when $n+m=k$.

We have assumed that Exercise \ref{exe.catalan.count-legal} \textbf{(b)} holds
whenever $n+m<k$. In other words, if $n\in\mathbb{N}$ and $m\in\mathbb{N}$
satisfy $n\geq m-1$ and $n+m<k$, then%
\begin{equation}
L_{n,m}=\dbinom{n+m}{m}-\dbinom{n+m}{m-1}.
\label{sol.catalan.count-legal.b.IH}%
\end{equation}


Now, let $n\in\mathbb{N}$ and $m\in\mathbb{N}$ be such that $n\geq m-1$ and
$n+m=k$. We are going to prove that%
\begin{equation}
L_{n,m}=\dbinom{n+m}{m}-\dbinom{n+m}{m-1}.
\label{sol.catalan.count-legal.b.IG}%
\end{equation}


Indeed, (\ref{sol.catalan.count-legal.b.IG}) is true when $n=m-1$%
\ \ \ \ \footnote{\textit{Proof.} Assume that $n=m-1$. Thus, $m>m-1=n$. Hence,
Lemma \ref{lem.catalan.count-legal.trivi} \textbf{(g)} shows that $L_{n,m}=0$.
But (\ref{eq.binom.symm2}) yields $\dbinom{m+n}{m}=\dbinom{m+n}{n}%
=\dbinom{n+m}{m-1}$ (since $m+n=n+m$ and $n=m-1$). Therefore, $\dbinom
{n+m}{m-1}=\dbinom{m+n}{m}=\dbinom{n+m}{m}$. In other words, $\dbinom{n+m}%
{m}-\dbinom{n+m}{m-1}=0$. Comparing this with $L_{n,m}=0$, we obtain
$L_{n,m}=\dbinom{n+m}{m}-\dbinom{n+m}{m-1}$. In other words,
(\ref{sol.catalan.count-legal.b.IG}) holds. Thus, we have proven that
(\ref{sol.catalan.count-legal.b.IG}) is true when $n=m-1$.}. Hence, for the
rest of this proof, we WLOG assume that we don't have $n=m-1$. In other words,
we have $n\neq m-1$.

We have $n>m-1$ (since we have $n\geq m-1$ but $n\neq m-1$). Since $n$ and
$m-1$ are integers, this shows that $n\geq\left(  m-1\right)  +1=m$.

Furthermore, (\ref{sol.catalan.count-legal.b.IG}) is true when $\left(
n,m\right)  =\left(  0,0\right)  $\ \ \ \ \footnote{\textit{Proof.} Assume
that $\left(  n,m\right)  =\left(  0,0\right)  $. Thus, $n=0$ and $m=0$.
Hence, $L_{n,m}=L_{0,0}=1$ (by Lemma \ref{lem.catalan.count-legal.trivi}
\textbf{(e)}). Comparing this with%
\begin{align*}
\dbinom{n+m}{m}-\dbinom{n+m}{m-1}  &  =\underbrace{\dbinom{0+0}{0}}%
_{=1}-\underbrace{\dbinom{0+0}{0-1}}_{=0}\ \ \ \ \ \ \ \ \ \ \left(
\text{since }n=0\text{ and }m=0\right) \\
&  =1,
\end{align*}
we obtain $L_{n,m}=\dbinom{n+m}{m}-\dbinom{n+m}{m-1}$. In other words,
(\ref{sol.catalan.count-legal.b.IG}) holds. Thus, we have proven that
(\ref{sol.catalan.count-legal.b.IG}) is true when $\left(  n,m\right)
=\left(  0,0\right)  $.}. Hence, for the rest of this proof, we WLOG assume
that we don't have $\left(  n,m\right)  =\left(  0,0\right)  $. In other
words, we have $\left(  n,m\right)  \neq\left(  0,0\right)  $. Hence, Exercise
\ref{exe.catalan.count-legal} \textbf{(a)} yields $L_{n,m}=L_{n-1,m}%
+L_{n,m-1}$.

Moreover, (\ref{sol.catalan.count-legal.b.IG}) is true when $m=0$%
\ \ \ \ \footnote{\textit{Proof.} Assume that $m=0$. If we had $n=0$, then we
would thus have $\left(  \underbrace{n}_{=0},\underbrace{m}_{=0}\right)
=\left(  0,0\right)  $, which would contradict $\left(  n,m\right)
\neq\left(  0,0\right)  $. Thus, we cannot have $n=0$. Hence, $n\neq0$, so
that $n>0$ (since $n\in\mathbb{N}$) and therefore $n-1\in\mathbb{N}$.
\par
The number $m-1$ is negative (since $\underbrace{m}_{=0}-1=-1<0$). Hence, at
least one of the integers $n$ and $m-1$ is negative. Thus, Lemma
\ref{lem.catalan.count-legal.trivi} \textbf{(f)} (applied to $m-1$ instead of
$m$) yields $L_{n,m-1}=0$.
\par
Also, $n-1\in\mathbb{N}$ and $m\in\mathbb{N}$ satisfy $\underbrace{\left(
n-1\right)  }_{<n}+m<n+m=k$ and $\underbrace{n}_{\geq0=m}-1\geq m-1$. Hence,
(\ref{sol.catalan.count-legal.b.IH}) (applied to $n-1$ instead of $n$) yields%
\begin{align*}
L_{n-1,m}  &  =\dbinom{\left(  n-1\right)  +m}{m}-\dbinom{\left(  n-1\right)
+m}{m-1}\\
&  =\underbrace{\dbinom{\left(  n-1\right)  +0}{0}}_{=1}-\underbrace{\dbinom
{\left(  n-1\right)  +0}{0-1}}_{=\dbinom{n-1}{-1}=0}%
\ \ \ \ \ \ \ \ \ \ \left(  \text{since }m=0\right) \\
&  =1.
\end{align*}
Now,%
\[
L_{n,m}=\underbrace{L_{n-1,m}}_{=1}+\underbrace{L_{n,m-1}}_{=0}=1.
\]
Comparing this with%
\begin{align*}
\dbinom{n+m}{m}-\dbinom{n+m}{m-1}  &  =\underbrace{\dbinom{n+0}{0}}%
_{=1}-\underbrace{\dbinom{n+0}{0-1}}_{=\dbinom{n}{-1}=0}%
\ \ \ \ \ \ \ \ \ \ \left(  \text{since }m=0\right) \\
&  =1,
\end{align*}
we obtain $L_{n,m}=\dbinom{n+m}{m}-\dbinom{n+m}{m-1}$. In other words,
(\ref{sol.catalan.count-legal.b.IG}) holds. Thus, we have proven that
(\ref{sol.catalan.count-legal.b.IG}) is true when $m=0$.}. Hence, for the rest
of this proof, we WLOG assume that we don't have $m=0$. In other words, we
have $m\neq0$. Since $m\in\mathbb{N}$, we thus obtain $m>0$, so that
$m-1\in\mathbb{N}$ (since $m\in\mathbb{N}$). From $n\geq m>0$, we also obtain
$n-1\in\mathbb{N}$ (since $n\in\mathbb{N}$).

The numbers $n-1\in\mathbb{N}$ and $m\in\mathbb{N}$ satisfy $\underbrace{n}%
_{\geq m}-1\geq m-1$ and $\underbrace{\left(  n-1\right)  }_{<n}+m<n+m=k$.
Hence, (\ref{sol.catalan.count-legal.b.IH}) (applied to $n-1$ instead of $n$)
yields%
\[
L_{n-1,m}=\dbinom{\left(  n-1\right)  +m}{m}-\dbinom{\left(  n-1\right)
+m}{m-1}=\dbinom{n+m-1}{m}-\dbinom{n+m-1}{m-1}%
\]
(since $\left(  n-1\right)  +m=n+m-1$).

On the other hand, the numbers $n\in\mathbb{N}$ and $m-1\in\mathbb{N}$ satisfy
$n\geq\left(  m-1\right)  -1$ (since $n\geq m-1\geq\left(  m-1\right)  -1$)
and $n+\underbrace{\left(  m-1\right)  }_{<m}<n+m=k$. Hence,
(\ref{sol.catalan.count-legal.b.IH}) (applied to $m-1$ instead of $m$) yields%
\[
L_{n,m-1}=\dbinom{n+\left(  m-1\right)  }{m-1}-\dbinom{n+\left(  m-1\right)
}{\left(  m-1\right)  -1}=\dbinom{n+m-1}{m-1}-\dbinom{n+m-1}{\left(
m-1\right)  -1}%
\]
(since $n+\left(  m-1\right)  =n+m-1$).

But%
\begin{align*}
L_{n,m}  &  =\underbrace{L_{n-1,m}}_{=\dbinom{n+m-1}{m}-\dbinom{n+m-1}{m-1}%
}+\underbrace{L_{n,m-1}}_{=\dbinom{n+m-1}{m-1}-\dbinom{n+m-1}{\left(
m-1\right)  -1}}\\
&  =\dbinom{n+m-1}{m}-\dbinom{n+m-1}{m-1}+\dbinom{n+m-1}{m-1}-\dbinom
{n+m-1}{\left(  m-1\right)  -1}.
\end{align*}
Comparing this with%
\begin{align*}
&  \underbrace{\dbinom{n+m}{m}}_{\substack{=\dbinom{n+m-1}{m-1}+\dbinom
{n+m-1}{m}\\\text{(by (\ref{eq.binom.rec.m}) (applied to }n+m\text{ and
}m\\\text{instead of }m\text{ and }n\text{))}}}-\underbrace{\dbinom{n+m}{m-1}%
}_{\substack{=\dbinom{n+m-1}{\left(  m-1\right)  -1}+\dbinom{n+m-1}%
{m-1}\\\text{(by (\ref{eq.binom.rec.m}) (applied to }n+m\text{ and
}m-1\\\text{instead of }m\text{ and }n\text{))}}}\\
&  =\dbinom{n+m-1}{m-1}+\dbinom{n+m-1}{m} - \left(  \dbinom{n+m-1}{\left(
m-1\right)  -1}+\dbinom{n+m-1}{m-1} \right) \\
&  =\dbinom{n+m-1}{m}-\dbinom{n+m-1}{m-1}+\dbinom{n+m-1}{m-1}-\dbinom
{n+m-1}{\left(  m-1\right)  -1},
\end{align*}
we obtain $L_{n,m}=\dbinom{n+m}{m}-\dbinom{n+m}{m-1}$. Thus,
(\ref{sol.catalan.count-legal.b.IG}) is proven.

Now, forget that we fixed $n$ and $m$. We thus have shown that if
$n\in\mathbb{N}$ and $m\in\mathbb{N}$ satisfy $n\geq m-1$ and $n+m=k$, then
(\ref{sol.catalan.count-legal.b.IG}) holds. In other words, Exercise
\ref{exe.catalan.count-legal} \textbf{(b)} holds when $n+m=k$. This completes
the induction step. Hence, Exercise \ref{exe.catalan.count-legal} \textbf{(b)}
is solved by induction.

\textbf{(c)} Let $n\in\mathbb{N}$ and $m\in\mathbb{N}$ be such that $n\geq
m-1$. Then, the fraction $\dfrac{m}{n+1}$ is well-defined (since $n+1\neq0$
(since $n\in\mathbb{N}$)).

Also, (\ref{eq.binom.absorp2}) (applied to $n+m$ and $m$ instead of $m$ and
$n$) yields%
\[
\dbinom{n+m}{m}=\dfrac{\left(  n+m\right)  -m+1}{m}\dbinom{n+m}{m-1}%
=\dfrac{n+1}{m}\dbinom{n+m}{m-1}%
\]
(since $\left(  n+m\right)  -m+1=n+1$). Multiplying this equality by
$\dfrac{m}{n+1}$, we obtain
\begin{equation}
\dfrac{m}{n+1}\dbinom{n+m}{m}=\dfrac{m}{n+1}\cdot\dfrac{n+1}{m}\dbinom
{n+m}{m-1}=\dbinom{n+m}{m-1}. \label{sol.catalan.count-legal.c.1}%
\end{equation}


But Exercise \ref{exe.catalan.count-legal} \textbf{(b)} yields%
\begin{align*}
L_{n,m}  &  =\dbinom{n+m}{m}-\underbrace{\dbinom{n+m}{m-1}}_{\substack{=\dfrac
{m}{n+1}\dbinom{n+m}{m}\\\text{(by (\ref{sol.catalan.count-legal.c.1}))}%
}}=\dbinom{n+m}{m}-\dfrac{m}{n+1}\dbinom{n+m}{m}\\
&  =\underbrace{\left(  1-\dfrac{m}{n+1}\right)  }_{=\dfrac{n+1-m}{n+1}%
}\dbinom{n+m}{m}=\dfrac{n+1-m}{n+1}\dbinom{n+m}{m}.
\end{align*}
This solves Exercise \ref{exe.catalan.count-legal} \textbf{(c)}.

\textbf{(d)} Let $n\in\mathbb{N}$. Then, $n\geq n-1$. Hence, Exercise
\ref{exe.catalan.count-legal} \textbf{(c)} (applied to $m=n$) yields
\[
L_{n,n}=\dfrac{n+1-n}{n+1}\dbinom{n+n}{n}=\dfrac{1}{n+1}\dbinom{2n}{n}%
\]
(since $n+1-n=1$ and $n+n=2n$). This solves Exercise
\ref{exe.catalan.count-legal} \textbf{(d)}.
\end{proof}

\subsection{Scary fractions}

\begin{exercise}
\label{exe.binom.scaryfrac}Let $k$, $a$ and $b$ be three positive integers
such that $k\leq a\leq b$. Prove that%
\[
\dfrac{k-1}{k}\sum_{n=a}^{b}\dfrac{1}{\dbinom{n}{k}}=\dfrac{1}{\dbinom
{a-1}{k-1}}-\dfrac{1}{\dbinom{b}{k-1}}.
\]

\end{exercise}

Exercise \ref{exe.binom.scaryfrac} may look scary, but it is a straightforward
exercise on induction (on $b$). To make our life a little bit easier, we shall
slightly relax the condition $a\leq b$ to $b\geq a-1$ (so that we can use the
case $b=a-1$ instead of $b=a$ as an induction base):

\begin{proposition}
\label{prop.binom.scaryfrac}Let $k$ be a positive integer. Let $a$ be a
positive integer such that $k\leq a$. Let $b\in\left\{  a-1,a,a+1,\ldots
\right\}  $. Then,%
\[
\dfrac{k-1}{k}\sum_{n=a}^{b}\dfrac{1}{\dbinom{n}{k}}=\dfrac{1}{\dbinom
{a-1}{k-1}}-\dfrac{1}{\dbinom{b}{k-1}}.
\]
(In particular, all fractions appearing in this equality are well-defined.)
\end{proposition}

\begin{proof}
[Proof of Proposition \ref{prop.binom.scaryfrac}.]All fractions appearing in
Proposition \ref{prop.binom.scaryfrac} are well-defined.

\begin{fns}
[\textit{Proof:} We have $k\neq0$ (since $k$ is a positive integer); thus, the
fraction $\dfrac{k-1}{k}$ is well-defined.

Also, $a-1\in\mathbb{N}$ (since $a$ is a positive integer) and $k-1\in
\mathbb{N}$ (since $k$ is a positive integer) and $a-1\geq k-1$ (since
$\underbrace{k}_{\leq a}-1\leq a-1$). Thus, (\ref{eq.binom.neq0}) (applied to
$a-1$ and $k-1$ instead of $m$ and $n$) yields $\dbinom{a-1}{k-1}\neq0$.
Hence, the fraction $\dfrac{1}{\dbinom{a-1}{k-1}}$ is well-defined.

Also, $b\in\left\{  a-1,a,a+1,\ldots\right\}  $, so that $b\geq a-1\geq
k-1\geq0$ (since $k-1\in\mathbb{N}$). Hence, $b\in\mathbb{N}$ (since $b\geq0$
and $b\in\left\{  a-1,a,a+1,\ldots\right\}  \subseteq\mathbb{Z}$) and
$k-1\in\mathbb{N}$ and $b\geq k-1$. Thus, (\ref{eq.binom.neq0}) (applied to
$b$ and $k-1$ instead of $m$ and $n$) yields $\dbinom{b}{k-1}\neq0$. Hence,
the fraction $\dfrac{1}{\dbinom{b}{k-1}}$ is well-defined.

Now, let $n\in\left\{  a,a+1,\ldots,b\right\}  $. Thus, $n\geq a>a-1\geq0$, so
that $n\in\mathbb{N}$ (since $n\in\left\{  a,a+1,\ldots,b\right\}
\subseteq\mathbb{Z}$). Also, $k\in\mathbb{N}$. Furthermore, $n\geq a\geq k$
(since $k\leq a$). Hence, (\ref{eq.binom.neq0}) (applied to $n$ and $k$
instead of $m$ and $n$) yields $\dbinom{n}{k}\neq0$. Hence, the fraction
$\dfrac{1}{\dbinom{n}{k}}$ is well-defined.

Now, forget that we fixed $n$. We thus have shown that the fraction $\dfrac
{1}{\dbinom{n}{k}}$ is well-defined for each $n\in\left\{  a,a+1,\ldots
,b\right\}  $. We now have proven that the fractions $\dfrac{k-1}{k}$,
$\dfrac{1}{\dbinom{a-1}{k-1}}$ and $\dfrac{1}{\dbinom{b}{k-1}}$ and also the
fractions $\dfrac{1}{\dbinom{n}{k}}$ for all $n\in\left\{  a,a+1,\ldots
,b\right\}  $ are well-defined. In other words, all fractions appearing in
Proposition \ref{prop.binom.scaryfrac} are well-defined.]
\end{fns}

Let us now prove Proposition \ref{prop.binom.scaryfrac} by induction on $b$:

\textit{Induction base:} Comparing%
\[
\dfrac{k-1}{k}\underbrace{\sum_{n=a}^{a-1}\dfrac{1}{\dbinom{n}{k}}}_{=\left(
\text{empty sum}\right)  =0}=\dfrac{k-1}{k}\cdot0=0
\]
with $\dfrac{1}{\dbinom{a-1}{k-1}}-\dfrac{1}{\dbinom{a-1}{k-1}}=0$, we
conclude that $\dfrac{k-1}{k}\sum_{n=a}^{a-1}\dfrac{1}{\dbinom{n}{k}}%
=\dfrac{1}{\dbinom{a-1}{k-1}}-\dfrac{1}{\dbinom{a-1}{k-1}}$. In other words,
Proposition \ref{prop.binom.scaryfrac} holds for $b=a-1$. This completes the
induction base.

\textit{Induction step:} Let $\beta\in\left\{  a,a+1,a+2,\ldots\right\}  $.
Assume that Proposition \ref{prop.binom.scaryfrac} holds for $b=\beta-1$. We
must prove that Proposition \ref{prop.binom.scaryfrac} holds for $b=\beta$.

We have assumed that Proposition \ref{prop.binom.scaryfrac} holds for
$b=\beta-1$. In other words, we have%
\begin{equation}
\dfrac{k-1}{k}\sum_{n=a}^{\beta-1}\dfrac{1}{\dbinom{n}{k}}=\dfrac{1}%
{\dbinom{a-1}{k-1}}-\dfrac{1}{\dbinom{\beta-1}{k-1}}.
\label{pf.prop.binom.scaryfrac.IH}%
\end{equation}
(In particular, all fractions appearing in this equality are well-defined.)

We have $k\in\left\{  1,2,3,\ldots\right\}  $ (since $k$ is a positive
integer). Hence, (\ref{eq.binom.absorp}) (applied to $m=\beta$ and $n=k$)
yields $\dbinom{\beta}{k}=\dfrac{\beta}{k}\dbinom{\beta-1}{k-1}$. Multiplying
this equality by $k$, we obtain%
\begin{equation}
k\dbinom{\beta}{k}=k\cdot\dfrac{\beta}{k}\dbinom{\beta-1}{k-1}=\beta
\dbinom{\beta-1}{k-1}. \label{pf.prop.binom.scaryfrac.4}%
\end{equation}
Now,%
\begin{align}
&  \dfrac{k-1}{k}\underbrace{\sum_{n=a}^{\beta}\dfrac{1}{\dbinom{n}{k}}%
}_{=\sum_{n=a}^{\beta-1}\dfrac{1}{\dbinom{n}{k}}+\dfrac{1}{\dbinom{\beta}{k}}%
}\nonumber\\
&  =\dfrac{k-1}{k}\left(  \sum_{n=a}^{\beta-1}\dfrac{1}{\dbinom{n}{k}}%
+\dfrac{1}{\dbinom{\beta}{k}}\right) \nonumber\\
&  =\underbrace{\dfrac{k-1}{k}\sum_{n=a}^{\beta-1}\dfrac{1}{\dbinom{n}{k}}%
}_{\substack{=\dfrac{1}{\dbinom{a-1}{k-1}}-\dfrac{1}{\dbinom{\beta-1}{k-1}%
}\\\text{(by (\ref{pf.prop.binom.scaryfrac.IH}))}}}+\underbrace{\dfrac{k-1}%
{k}\cdot\dfrac{1}{\dbinom{\beta}{k}}}_{\substack{=\dfrac{k-1}{k\dbinom{\beta
}{k}}=\dfrac{k-1}{\beta\dbinom{\beta-1}{k-1}}\\\text{(by
(\ref{pf.prop.binom.scaryfrac.4}))}}}\nonumber\\
&  =\dfrac{1}{\dbinom{a-1}{k-1}}-\dfrac{1}{\dbinom{\beta-1}{k-1}}+\dfrac
{k-1}{\beta\dbinom{\beta-1}{k-1}}=\dfrac{1}{\dbinom{a-1}{k-1}}%
-\underbrace{\left(  \dfrac{1}{\dbinom{\beta-1}{k-1}}-\dfrac{k-1}{\beta
\dbinom{\beta-1}{k-1}}\right)  }_{=\dfrac{\beta-\left(  k-1\right)  }%
{\beta\dbinom{\beta-1}{k-1}}=\dfrac{\beta-k+1}{\beta\dbinom{\beta-1}{k-1}}%
}\nonumber\\
&  =\dfrac{1}{\dbinom{a-1}{k-1}}-\dfrac{\beta-k+1}{\beta\dbinom{\beta-1}{k-1}%
}. \label{pf.prop.binom.scaryfrac.5}%
\end{align}


Also, (\ref{eq.binom.absorp2}) (applied to $m=\beta$ and $n=k$) yields
$\dbinom{\beta}{k}=\dfrac{\beta-k+1}{k}\dbinom{\beta}{k-1}$. Multiplying this
equality by $k$, we obtain%
\[
k\dbinom{\beta}{k}=k\cdot\dfrac{\beta-k+1}{k}\dbinom{\beta}{k-1}=\left(
\beta-k+1\right)  \dbinom{\beta}{k-1}.
\]
Comparing this with (\ref{pf.prop.binom.scaryfrac.4}), we obtain%
\[
\beta\dbinom{\beta-1}{k-1}=\left(  \beta-k+1\right)  \dbinom{\beta}{k-1}.
\]
Therefore,
\[
\dfrac{\beta-k+1}{\beta\dbinom{\beta-1}{k-1}}=\dfrac{\beta-k+1}{\left(
\beta-k+1\right)  \dbinom{\beta}{k-1}}=\dfrac{1}{\dbinom{\beta}{k-1}}.
\]
Hence, (\ref{pf.prop.binom.scaryfrac.5}) becomes%
\[
\dfrac{k-1}{k}\sum_{n=a}^{\beta}\dfrac{1}{\dbinom{n}{k}}=\dfrac{1}%
{\dbinom{a-1}{k-1}}-\underbrace{\dfrac{\beta-k+1}{\beta\dbinom{\beta-1}{k-1}}%
}_{=\dfrac{1}{\dbinom{\beta}{k-1}}}=\dfrac{1}{\dbinom{a-1}{k-1}}-\dfrac
{1}{\dbinom{\beta}{k-1}}%
\]
(and, in particular, all fractions appearing in this equality are
well-defined). In other words, Proposition \ref{prop.binom.scaryfrac} holds
for $b=\beta$. This completes the induction step. Thus, Proposition
\ref{prop.binom.scaryfrac} is proven by induction.
\end{proof}

\begin{proof}
[Solution to Exercise \ref{exe.binom.scaryfrac}.]From $b\geq a\geq a-1$, we
obtain $b\in\left\{  a-1,a,a+1,\ldots\right\}  $ (since $b$ is an integer).
Thus, Proposition \ref{prop.binom.scaryfrac} yields $\dfrac{k-1}{k}\sum
_{n=a}^{b}\dfrac{1}{\dbinom{n}{k}}=\dfrac{1}{\dbinom{a-1}{k-1}}-\dfrac
{1}{\dbinom{b}{k-1}}$. This solves Exercise \ref{exe.binom.scaryfrac}.
\end{proof}

\subsection{Derangements that are involutions}

\begin{definition}
Let $\sigma$ be a permutation of a set $X$.

\textbf{(a)} We say that $\sigma$ is a \textit{derangement} if and only if
each $x\in X$ satisfies $\sigma\left(  x\right)  \neq x$.

\textbf{(b)} We say that $\sigma$ is an \textit{involution} if and only if
$\sigma\circ\sigma=\operatorname*{id}$ (that is, each $x\in X$ satisfies
$\sigma\left(  \sigma\left(  x\right)  \right)  =x$).
\end{definition}

For example, the permutation $\alpha$ of the set $\left[  5\right]  $ that
sends $1,2,3,4,5$ to $3,5,1,4,2$ is an involution (it satisfies $\alpha\left(
\underbrace{\alpha\left(  1\right)  }_{=3}\right)  =\alpha\left(  3\right)
=1$ and $\alpha\left(  \underbrace{\alpha\left(  2\right)  }_{=5}\right)
=\alpha\left(  5\right)  =2$ and similarly $\alpha\left(  \alpha\left(
x\right)  \right)  =x$ for all other $x\in\left[  5\right]  $), but not a
derangement (since $\alpha\left(  4\right)  =4$).

On the other hand, the permutation $\beta$ of the set $\left[  6\right]  $
that sends $1,2,3,4,5,6$ to $3,4,2,1,6,5$ is a derangement (it satisfies
$\beta\left(  x\right)  \neq x$ for all $x\in\left[  6\right]  $), but not an
involution (since $\beta\left(  \beta\left(  1\right)  \right)  \neq1$).

\begin{exercise}
Let $n\in\mathbb{N}$. Prove the following:

\textbf{(a)} If $n$ is odd, then there exist no derangements of $\left[
n\right]  $ that are involutions.

\textbf{(b)} If $n$ is even, then the number of derangements of $\left[
n\right]  $ that are involutions is $\dfrac{n!}{2^{n/2}\left(  n/2\right)  !}$.

[\textbf{Hint:} What does the number $\dfrac{n!}{2^{n/2}\left(  n/2\right)
!}$ remind you of?]
\end{exercise}

\subsection{Hypergreen permutations}

\begin{exercise}
Let $n\in\mathbb{N}$ be such that $n\geq2$. We shall call a permutation
$\pi\in S_{n}$ \textit{hypergreen} if it satisfies both $\pi\left(  1\right)
<\pi\left(  2\right)  $ and $\pi^{-1}\left(  1\right)  <\pi^{-1}\left(
2\right)  $.

\textbf{(a)} Prove that any $\pi\in S_{n}$ satisfying $\pi\left(  1\right)
=1$ must be hypergreen.

\textbf{(b)} Prove that the number of hypergreen permutations $\pi\in S_{n}$
that \textbf{do not} satisfy $\pi\left(  1\right)  =1$ is $\dbinom{n-2}{2}%
^{2}\left(  n-4\right)  !$. (Here, $\dbinom{n-2}{2}^{2}\left(  n-4\right)  !$
is understood to be $0$ when $n<4$.)

[\textbf{Hint:} For \textbf{(b)}, argue first that if $\pi\in S_{n}$ is
hypergreen but does not satisfy $\pi\left(  1\right)  =1$, then the four
numbers $1,2,\pi\left(  1\right)  ,\pi\left(  2\right)  $ are distinct.]
\end{exercise}

\subsection{Counting the parts of all compositions}

Recall that if $n\in\mathbb{N}$, then a \textit{composition} of $n$ means a
finite list $\left(  a_{1},a_{2},\ldots,a_{k}\right)  $ of positive integers
such that $a_{1}+a_{2}+\cdots+a_{k}=n$.

For example, the compositions of $3$ are $\left(  3\right)  $, $\left(
2,1\right)  $, $\left(  1,2\right)  $ and $\left(  1,1,1\right)  $.

The \textit{length} of a composition $\left(  a_{1},a_{2},\ldots,a_{k}\right)
$ of $n$ is defined to be $k$.

\begin{exercise}
Let $n$ be a positive integer. Prove that the sum of the lengths of all
compositions of $n$ is $\left(  n+1\right)  2^{n-2}$.
\end{exercise}

See \cite[solution to Exercise 2.10.9]{19fco} for a solution to this exercise.

\begin{thebibliography}{99999999}                                                                                         %


\bibitem[19fco]{19fco}Darij Grinberg, \textit{Enumerative Combinatorics
(Drexel Fall 2019 Math 222 notes)}, 18 September 2020.\newline\url{http://www.cip.ifi.lmu.de/~grinberg/t/19fco/n/n.pdf}

\bibitem[Grinbe16]{detnotes}Darij Grinberg, \textit{Notes on the combinatorial
fundamentals of algebra}, 10 January 2019.\newline%
\url{http://www.cip.ifi.lmu.de/~grinberg/primes2015/sols.pdf} \newline The
numbering of theorems and formulas in this link might shift when the project
gets updated; for a \textquotedblleft frozen\textquotedblright\ version whose
numbering is guaranteed to match that in the citations above, see
\url{https://github.com/darijgr/detnotes/releases/tag/2019-01-10} .

\bibitem[Renaul07]{Renaul07}Marc Renault, \textit{Four Proofs of the Ballot
Theorem}, Mathematics Magazine, vol. 80, no. 5, 2007, pp. 345--352.\newline\url{http://webspace.ship.edu/msrenault/ballotproblem/Four Proofs of the Ballot Theorem.pdf}
\end{thebibliography}


\end{document}