\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=Sunday, March 31, 2019 19:30:19}
%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 1}
\ohead{page \thepage}
\cfoot{}
\begin{document}

\begin{center}
\textbf{Math 4707 Spring 2018 (Darij Grinberg): midterm 1 with solutions}
\end{center}

%

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


\bigskip

Let us recall that%
\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$. (This is
exactly \cite[Proposition 3.6]{detnotes}.)

We also recall the \textit{recurrence relation of the binomial coefficients}.
It says that%
\[
\dbinom{n}{k}=\dbinom{n-1}{k-1}+\dbinom{n-1}{k}%
\]
for all $n\in\mathbb{Q}$ and $k\in\mathbb{Z}$.

\subsection{More on the Sierpinski triangle in Pascal's triangle}

\begin{exercise}
\label{exe.binom.2k-1}Let $n\in\mathbb{N}$.

\textbf{(a)} Prove that the integer $\dbinom{2^{n}-1}{b}$ is odd for each
$b\in\left\{  0,1,\ldots,2^{n}-1\right\}  $.

\textbf{(b)} Prove that the integer $\dbinom{2^{n}}{b}$ is even for each
$b\in\left\{  1,2,\ldots,2^{n}-1\right\}  $.

[Here, the set $\left\{  0,1,\ldots,2^{n}-1\right\}  $ means the set of all
integers $k$ with $0\leq k\leq2^{n}-1$, and the set $\left\{  1,2,\ldots
,2^{n}-1\right\}  $ means the set of all integers $k$ with $1\leq k\leq
2^{n}-1$.]
\end{exercise}

I know of several solutions for Exercise \ref{exe.binom.2k-1}. The shortest
one (though seemingly somewhat unmotivated) relies on the following
binomial-coefficient identity:

\begin{proposition}
\label{prop.binom.pie-binid-0}Let $n\in\mathbb{N}$ and $m\in\mathbb{N}$. Then,%
\[
\sum_{r=0}^{m}\left(  -1\right)  ^{r}\dbinom{n}{r}=\left(  -1\right)
^{m}\dbinom{n-1}{m}.
\]

\end{proposition}

Proposition \ref{prop.binom.pie-binid-0} is the particular case of \cite[Lemma
3.47]{detnotes} obtained by setting $k=0$. But it also falls prey to a
straightforward induction, which should be routine by now:

\begin{fns}
\begin{proof}
[Proof of Proposition \ref{prop.binom.pie-binid-0}.]We shall prove Proposition
\ref{prop.binom.pie-binid-0} by induction on $m$:

\textit{Induction base:} We have $\sum_{r=0}^{0}\left(  -1\right)  ^{r}%
\dbinom{n}{r}=\underbrace{\left(  -1\right)  ^{0}}_{=1}\underbrace{\dbinom
{n}{0}}_{=1}=1$. Comparing this with $\underbrace{\left(  -1\right)  ^{0}%
}_{=1}\underbrace{\dbinom{n-1}{0}}_{=1}=1$, we obtain $\sum_{r=0}^{0}\left(
-1\right)  ^{r}\dbinom{n}{r}=\left(  -1\right)  ^{0}\dbinom{n-1}{0}$. In other
words, Proposition \ref{prop.binom.pie-binid-0} holds for $m=0$.

\textit{Induction step:} Let $\mu\in\mathbb{N}$. Assume that Proposition
\ref{prop.binom.pie-binid-0} holds for $m=\mu$. We must prove that Proposition
\ref{prop.binom.pie-binid-0} holds for $m=\mu+1$.

We have assumed that Proposition \ref{prop.binom.pie-binid-0} holds for
$m=\mu$. In other words, we have%
\[
\sum_{r=0}^{\mu}\left(  -1\right)  ^{r}\dbinom{n}{r}=\left(  -1\right)  ^{\mu
}\dbinom{n-1}{\mu}.
\]
Now,%
\begin{align*}
\sum_{r=0}^{\mu+1}\left(  -1\right)  ^{r}\dbinom{n}{r}  &  =\underbrace{\sum
_{r=0}^{\mu}\left(  -1\right)  ^{r}\dbinom{n}{r}}_{=\left(  -1\right)  ^{\mu
}\dbinom{n-1}{\mu}}+\left(  -1\right)  ^{\mu+1}\underbrace{\dbinom{n}{\mu+1}%
}_{\substack{=\dbinom{n-1}{\left(  \mu+1\right)  -1}+\dbinom{n-1}{\mu
+1}\\\text{(by the recurrence relation of the binomial coefficients)}}}\\
&  =\underbrace{\left(  -1\right)  ^{\mu}}_{=-\left(  -1\right)  ^{\mu+1}%
}\dbinom{n-1}{\mu}+\left(  -1\right)  ^{\mu+1}\left(  \underbrace{\dbinom
{n-1}{\left(  \mu+1\right)  -1}}_{=\dbinom{n-1}{\mu}}+\dbinom{n-1}{\mu
+1}\right) \\
&  =\left(  -\left(  -1\right)  ^{\mu+1}\right)  \dbinom{n-1}{\mu}+\left(
-1\right)  ^{\mu+1}\left(  \dbinom{n-1}{\mu}+\dbinom{n-1}{\mu+1}\right) \\
&  =-\left(  -1\right)  ^{\mu+1}\dbinom{n-1}{\mu}+\left(  -1\right)  ^{\mu
+1}\dbinom{n-1}{\mu}+\left(  -1\right)  ^{\mu+1}\dbinom{n-1}{\mu+1}\\
&  =\left(  -1\right)  ^{\mu+1}\dbinom{n-1}{\mu+1}.
\end{align*}
In other words, Proposition \ref{prop.binom.pie-binid-0} holds for $m=\mu+1$.
This completes the induction step. Thus, Proposition
\ref{prop.binom.pie-binid-0} is proven by induction.
\end{proof}
\end{fns}

Actually, Proposition \ref{prop.binom.pie-binid-0} holds for all
$n\in\mathbb{Q}$ (not just for $n\in\mathbb{N}$), and the same proof that we
gave above applies in this generality.

Our next is ingredient is Exercise 4 from
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18s/hw1s.pdf}{Math 4707 Homework
Set 1}, which we restate as a proposition:

\begin{proposition}
\label{prop.binom.pascal-sierpinski}Let $n\in\mathbb{N}$. Let $a$ and $b$ be
two elements of $\left\{  0,1,\ldots,2^{n}-1\right\}  $. Then,%
\begin{align}
\dbinom{2^{n}+a}{b}  &  \equiv\dbinom{a}{b}\operatorname{mod}%
2\ \ \ \ \ \ \ \ \ \ \text{and}\label{eq.prop.binom.pascal-sierpinski.1}\\
\dbinom{2^{n}+a}{2^{n}+b}  &  \equiv\dbinom{a}{b}\operatorname{mod}2.
\label{eq.prop.binom.pascal-sierpinski.2}%
\end{align}


[Here, \textquotedblleft$\left\{  0,1,\ldots,2^{n}-1\right\}  $%
\textquotedblright\ means the set of all integers $k$ satisfying $0\leq
k\leq2^{n}-1$.]
\end{proposition}

We recall also the following easy fact (which appeared as Lemma 0.12
\textbf{(a)} in the solutions to
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18s/hw1s.pdf}{Math 4707 Homework
Set 1}):

\begin{lemma}
\label{lem.0choosek.a}Let $b\in\mathbb{Z}$. Then, $\dbinom{0}{b}=\left[
b=0\right]  $. (Here, the Iverson bracket notation is being used.)
\end{lemma}

We can now easily deal with Exercise \ref{exe.binom.2k-1}:

\begin{proof}
[Solution to Exercise \ref{exe.binom.2k-1}.]\textbf{(b)} Let $b\in\left\{
1,2,\ldots,2^{n}-1\right\}  $. We have $0\in\left\{  0,1,\ldots,2^{n}%
-1\right\}  $ and $b\in\left\{  1,2,\ldots,2^{n}-1\right\}  \subseteq\left\{
0,1,\ldots,2^{n}-1\right\}  $. Hence, (\ref{eq.prop.binom.pascal-sierpinski.1}%
) (applied to $a=0$) yields $\dbinom{2^{n}+0}{b}\equiv\dbinom{0}%
{b}\operatorname{mod}2$.

Lemma \ref{lem.0choosek.a} yields $\dbinom{0}{b}=\left[  b=0\right]  $. But
$b\neq0$ (since $b\in\left\{  1,2,\ldots,2^{n}-1\right\}  $). Hence, $\left[
b=0\right]  =0$. Finally, $2^{n}=2^{n}+0$. Therefore,%
\[
\dbinom{2^{n}}{b}=\dbinom{2^{n}+0}{b}\equiv\dbinom{0}{b}=\left[  b=0\right]
=0\operatorname{mod}2.
\]
In other words, the integer $\dbinom{2^{n}}{b}$ is even. This solves Exercise
\ref{exe.binom.2k-1} \textbf{(b)}.

\textbf{(a)} Let $b\in\left\{  0,1,\ldots,2^{n}-1\right\}  $. Thus,
$b\leq2^{n}-1$. Now,
\begin{equation}
\dbinom{2^{n}}{r}\equiv0\operatorname{mod}2\ \ \ \ \ \ \ \ \ \ \text{for each
}r\in\left\{  1,2,\ldots,b\right\}  . \label{sol.binom.2k-1.a.1}%
\end{equation}


[\textit{Proof of (\ref{sol.binom.2k-1.a.1}):} Let $r\in\left\{
1,2,\ldots,b\right\}  $. Thus, $r\in\left\{  1,2,\ldots,b\right\}
\subseteq\left\{  1,2,\ldots,2^{n}-1\right\}  $ (since $b\leq2^{n}-1$). Hence,
Exercise \ref{exe.binom.2k-1} \textbf{(b)} (applied to $r$ instead of $b$)
yields that the integer $\dbinom{2^{n}}{r}$ is even. In other words,
$\dbinom{2^{n}}{r}\equiv0\operatorname{mod}2$. This proves
(\ref{sol.binom.2k-1.a.1}).]

The integer $\left(  -1\right)  ^{b}$ is odd (because it is either $1$ or
$-1$). In other words, $\left(  -1\right)  ^{b}\equiv1\operatorname{mod}2$.

Proposition \ref{prop.binom.pie-binid-0} (applied to $2^{n}$ and $b$ instead
of $n$ and $m$) yields%
\[
\sum_{r=0}^{b}\left(  -1\right)  ^{r}\dbinom{2^{n}}{r}=\underbrace{\left(
-1\right)  ^{b}}_{\equiv1\operatorname{mod}2}\dbinom{2^{n}-1}{b}\equiv
\dbinom{2^{n}-1}{b}\operatorname{mod}2.
\]
Hence,
\begin{align*}
\dbinom{2^{n}-1}{b}  &  \equiv\sum_{r=0}^{b}\left(  -1\right)  ^{r}%
\dbinom{2^{n}}{r}=\underbrace{\left(  -1\right)  ^{0}}_{=1}\underbrace{\dbinom
{2^{n}}{0}}_{=1}+\sum_{r=1}^{b}\left(  -1\right)  ^{r}\underbrace{\dbinom
{2^{n}}{r}}_{\substack{\equiv0\operatorname{mod}2\\\text{(by
(\ref{sol.binom.2k-1.a.1}))}}}\\
&  \equiv1+\underbrace{\sum_{r=1}^{b}\left(  -1\right)  ^{r}0}_{=0}%
=1\operatorname{mod}2.
\end{align*}
In other words, the integer $\dbinom{2^{n}-1}{b}$ is odd. This solves Exercise
\ref{exe.binom.2k-1} \textbf{(a)}.
\end{proof}

\begin{fns}
\begin{remark}
The above solution of Exercise \ref{exe.binom.2k-1} \textbf{(a)} appears to
come out of left field; how did I come up with Proposition
\ref{prop.binom.pie-binid-0}, and how did I think of applying it to $2^{n}$
and $b$ instead of $n$ and $m$ ?

Here is the motivation: Having solved part \textbf{(b)}, I wanted to deduce
part \textbf{(a)} from it. This necessitates finding a formula for the entries
in the $\left(  2^{n}-1\right)  $-st row of Pascal's triangle in terms of
entries in the $2^{n}$-th row. To get such a formula, I try to reorganize the
recurrence relation of the binomial coefficients as%
\begin{equation}
\dbinom{2^{n}-1}{b}=\dbinom{2^{n}}{b}-\dbinom{2^{n}-1}{b-1}.
\label{rmk.binom.2k-1.motiv.1}%
\end{equation}
But now, I have a $\dbinom{2^{n}-1}{b-1}$ on the right hand side, which is
another entry on the $\left(  2^{n}-1\right)  $-st row. I rewrite this
$\dbinom{2^{n}-1}{b-1}$ again using the recurrence relation of the binomial
coefficients, obtaining $\dbinom{2^{n}-1}{b-1}=\dbinom{2^{n}}{b-1}%
-\dbinom{2^{n}-1}{b-2}$. Substituting into (\ref{rmk.binom.2k-1.motiv.1}), I
obtain%
\begin{align*}
\dbinom{2^{n}-1}{b}  &  =\dbinom{2^{n}}{b}-\left(  \dbinom{2^{n}}{b-1}%
-\dbinom{2^{n}-1}{b-2}\right) \\
&  =\dbinom{2^{n}}{b}-\dbinom{2^{n}}{b-1}+\dbinom{2^{n}-1}{b-2}.
\end{align*}
Now, I have a $\dbinom{2^{n}-1}{b-2}$ on the right hand side, which I rewrite
using the recurrence relation in the same way... and so on. I obtain the
following chain of equalities:%
\begin{align*}
\dbinom{2^{n}-1}{b}  &  =\dbinom{2^{n}}{b}-\dbinom{2^{n}-1}{b-1}\\
&  =\dbinom{2^{n}}{b}-\dbinom{2^{n}}{b-1}+\dbinom{2^{n}-1}{b-2}\\
&  =\dbinom{2^{n}}{b}-\dbinom{2^{n}}{b-1}+\dbinom{2^{n}}{b-2}-\dbinom{2^{n}%
-1}{b-3}\\
&  =\cdots.
\end{align*}
I end this chain once the binomial coefficient with the $2^{n}-1$ on top is
$\dbinom{2^{n}-1}{-1}$. The result is%
\begin{align*}
\dbinom{2^{n}-1}{b}  &  =\dbinom{2^{n}}{b}-\dbinom{2^{n}}{b-1}+\dbinom{2^{n}%
}{b-2}\pm\cdots+\left(  -1\right)  ^{b}\dbinom{2^{n}}{0}+\left(  -1\right)
^{b+1}\underbrace{\dbinom{2^{n}-1}{-1}}_{=0}\\
&  =\dbinom{2^{n}}{b}-\dbinom{2^{n}}{b-1}+\dbinom{2^{n}}{b-2}\pm\cdots+\left(
-1\right)  ^{b}\dbinom{2^{n}}{0}.
\end{align*}
This is a binomial identity that doesn't rely on $2^{n}$ being a power of $2$,
so I generalize it to%
\[
\dbinom{n-1}{b}=\dbinom{n}{b}-\dbinom{n}{b-1}+\dbinom{n}{b-2}\pm\cdots+\left(
-1\right)  ^{b}\dbinom{n}{0}%
\]
for all $n\in\mathbb{N}$. This is just a restatement of Proposition
\ref{prop.binom.pie-binid-0}.
\end{remark}
\end{fns}

\subsection{Counting by symmetry}

Recall that if $n \in\mathbb{N}$, then $\left[  n \right]  $ denotes the
$n$-element set $\left\{  1, 2, \ldots, n \right\}  $. If $n \in\mathbb{N}$,
then $S_{n}$ shall mean the set of all permutations of the set $\left[  n
\right]  $. The number of these permutations is $\left|  S_{n} \right|  = n!$.
(We shall prove this in class soon.) Note that $S_{n}$ is called the
\textit{$n$-th symmetric group}.

\begin{proposition}
\label{prop.perm.si34} Let $n\geq4$ be an integer. Then, the number of all
permutations $\sigma\in S_{n}$ satisfying $\sigma\left(  3\right)
>\sigma\left(  4\right)  $ is $n!/2$.
\end{proposition}

\begin{proof}
[Proof of Proposition \ref{prop.perm.si34}.]I say that a permutation
$\sigma\in S_{n}$ is

\begin{itemize}
\item \textit{green} if it satisfies $\sigma\left(  3\right)  >\sigma\left(
4\right)  $;

\item \textit{red} if it satisfies $\sigma\left(  3\right)  <\sigma\left(
4\right)  $.
\end{itemize}

Every permutation $\sigma\in S_{n}$ is either green or red (indeed, every
permutation $\sigma\in S_{n}$ is injective, and thus satisfies $\sigma\left(
3\right)  \neq\sigma\left(  4\right)  $, so that it must satisfy either
$\sigma\left(  3\right)  >\sigma\left(  4\right)  $ or $\sigma\left(
3\right)  <\sigma\left(  4\right)  $), but no permutation $\sigma\in S_{n}$
can be both green and red at the same time (since $\sigma\left(  3\right)
>\sigma\left(  4\right)  $ would contradict $\sigma\left(  3\right)
<\sigma\left(  4\right)  $). Hence, the set $S_{n}$ is the union of its two
disjoint subsets $\left\{  \text{green permutations }\sigma\in S_{n}\right\}
$ and $\left\{  \text{red permutations }\sigma\in S_{n}\right\}  $. Thus,%
\begin{equation}
\left\vert S_{n}\right\vert =\left\vert \left\{  \text{green permutations
}\sigma\in S_{n}\right\}  \right\vert +\left\vert \left\{  \text{red
permutations }\sigma\in S_{n}\right\}  \right\vert .
\label{pf.prop.perm.si34.sum}%
\end{equation}


On the other hand, I claim that \textquotedblleft the colors are
equidistributed\textquotedblright, i.e., the number of green permutations
$\sigma\in S_{n}$ equals the number of red permutations $\sigma\in S_{n}$.

To prove this, I will construct a bijection from $\left\{  \text{green
permutations }\sigma\in S_{n}\right\}  $ to $\left\{  \text{red permutations
}\sigma\in S_{n}\right\}  $.

Indeed, let $s_{3}$ be the permutation of $\left[  n\right]  $ that swaps the
numbers $3$ and $4$ while leaving all other numbers unchanged. That is,
$s_{3}$ is given by%
\[
s_{3}\left(  i\right)  =%
\begin{cases}
4, & \text{if }i=3;\\
3, & \text{if }i=4;\\
i, & \text{if }i\notin\left\{  3,4\right\}
\end{cases}
\ \ \ \ \ \ \ \ \ \ \text{for all }i\in\left[  n\right]  .
\]
(In one-line notation, $s_{3}$ is represented as $\left(  1,2,4,3,5,6,\ldots
,n\right)  $, where only the two numbers $3$ and $4$ are out of order.)

Notice that $s_{3}\circ s_{3}=\operatorname*{id}$. (Visually speaking, this is
clear: If we swap $3$ and $4$, and then swap $3$ and $4$ again, then all
numbers return to their old places.)

If $\alpha$ and $\beta$ are two permutations of $\left[  n\right]  $, then
their composition $\alpha\circ\beta$ is a permutation of $\left[  n\right]  $
as well\footnote{because permutations of $\left[  n\right]  $ are just
bijective maps $\left[  n\right]  \rightarrow\left[  n\right]  $, but the
composition of two bijective maps is again bijective}. Hence, for every
permutation $\sigma\in S_{n}$, the map $\sigma\circ s_{3}$ is also a
permutation of $\left[  n\right]  $.

We now claim that
\begin{equation}
\text{if }\sigma\in S_{n}\text{ is green, then }\sigma\circ s_{3}\in
S_{n}\text{ is red.} \label{pf.prop.perm.si34.g2r}%
\end{equation}


[\textit{Proof of (\ref{pf.prop.perm.si34.g2r}):} Assume that $\sigma\in
S_{n}$ is green. Thus, $\sigma\left(  3\right)  >\sigma\left(  4\right)  $ (by
the definition of \textquotedblleft green\textquotedblright).

We know $\sigma\circ s_{3}$ is a permutation of $\left[  n\right]  $. In other
words, $\sigma\circ s_{3}\in S_{n}$. We must prove that $\sigma\circ s_{3}$ is
red. In other words, we must prove that $\left(  \sigma\circ s_{3}\right)
\left(  3\right)  <\left(  \sigma\circ s_{3}\right)  \left(  4\right)  $
(because this is what it means for $\sigma\circ s_{3}$ to be red).

But the definition of $s_{3}$ shows that $s_{3}\left(  3\right)  =4$ and
$s_{3}\left(  4\right)  =3$. Thus, $\left(  \sigma\circ s_{3}\right)  \left(
3\right)  =\sigma\left(  \underbrace{s_{3}\left(  3\right)  }_{=4}\right)
=\sigma\left(  4\right)  $ and $\left(  \sigma\circ s_{3}\right)  \left(
4\right)  =\sigma\left(  \underbrace{s_{3}\left(  4\right)  }_{=3}\right)
=\sigma\left(  3\right)  $. Hence, $\left(  \sigma\circ s_{3}\right)  \left(
4\right)  =\sigma\left(  3\right)  >\sigma\left(  4\right)  =\left(
\sigma\circ s_{3}\right)  \left(  3\right)  $. In other words, $\left(
\sigma\circ s_{3}\right)  \left(  3\right)  <\left(  \sigma\circ s_{3}\right)
\left(  4\right)  $. But this is exactly what we wanted to prove. Thus,
(\ref{pf.prop.perm.si34.g2r}) is proven.]

An analogous argument shows that%
\begin{equation}
\text{if }\sigma\in S_{n}\text{ is red, then }\sigma\circ s_{3}\in S_{n}\text{
is green.} \label{pf.prop.perm.si34.r2g}%
\end{equation}


Now, let $\alpha$ be the map%
\begin{align*}
\left\{  \text{green permutations }\sigma\in S_{n}\right\}   &  \rightarrow
\left\{  \text{red permutations }\sigma\in S_{n}\right\}  ,\\
\sigma &  \mapsto\sigma\circ s_{3}%
\end{align*}
(this is well-defined because of (\ref{pf.prop.perm.si34.g2r})). Let $\beta$
be the map%
\begin{align*}
\left\{  \text{red permutations }\sigma\in S_{n}\right\}   &  \rightarrow
\left\{  \text{green permutations }\sigma\in S_{n}\right\}  ,\\
\sigma &  \mapsto\sigma\circ s_{3}%
\end{align*}
(this is well-defined because of (\ref{pf.prop.perm.si34.r2g})). We have
$\alpha\circ\beta=\operatorname*{id}$ (since every red permutation $\sigma\in
S_{n}$ satisfies%
\begin{align*}
\left(  \alpha\circ\beta\right)  \left(  \sigma\right)   &  =\alpha\left(
\underbrace{\beta\left(  \sigma\right)  }_{\substack{=\sigma\circ
s_{3}\\\text{(by the definition of }\beta\text{)}}}\right)  =\alpha\left(
\sigma\circ s_{3}\right) \\
&  =\left(  \sigma\circ s_{3}\right)  \circ s_{3}\ \ \ \ \ \ \ \ \ \ \left(
\text{by the definition of }\alpha\right) \\
&  =\sigma\circ\underbrace{\left(  s_{3}\circ s_{3}\right)  }%
_{=\operatorname*{id}}=\sigma=\operatorname*{id}\left(  \sigma\right)
\end{align*}
) and $\beta\circ\alpha=\operatorname*{id}$ (by an analogous computation).
Thus, the two maps $\alpha$ and $\beta$ are mutually inverse. Hence, $\alpha$
is a bijection. Thus, we have found a bijection from $\left\{  \text{green
permutations }\sigma\in S_{n}\right\}  $ to $\left\{  \text{red permutations
}\sigma\in S_{n}\right\}  $ (namely, $\alpha$). Therefore,%
\begin{equation}
\left\vert \left\{  \text{green permutations }\sigma\in S_{n}\right\}
\right\vert =\left\vert \left\{  \text{red permutations }\sigma\in
S_{n}\right\}  \right\vert . \label{pf.prop.perm.si34.equal}%
\end{equation}


Now, (\ref{pf.prop.perm.si34.sum}) becomes%
\begin{align*}
\left\vert S_{n}\right\vert  &  =\left\vert \left\{  \text{green permutations
}\sigma\in S_{n}\right\}  \right\vert +\underbrace{\left\vert \left\{
\text{red permutations }\sigma\in S_{n}\right\}  \right\vert }%
_{\substack{=\left\vert \left\{  \text{green permutations }\sigma\in
S_{n}\right\}  \right\vert \\\text{(by (\ref{pf.prop.perm.si34.equal}))}}}\\
&  =\left\vert \left\{  \text{green permutations }\sigma\in S_{n}\right\}
\right\vert +\left\vert \left\{  \text{green permutations }\sigma\in
S_{n}\right\}  \right\vert \\
&  =2\cdot\left\vert \left\{  \text{green permutations }\sigma\in
S_{n}\right\}  \right\vert .
\end{align*}
Hence,%
\[
\left\vert \left\{  \text{green permutations }\sigma\in S_{n}\right\}
\right\vert =\dfrac{1}{2}\underbrace{\left\vert S_{n}\right\vert }%
_{=n!}=\dfrac{1}{2}n!=n!/2.
\]
In other words, the number of all green permutations $\sigma\in S_{n}$ is
$n!/2$. In other words, the number of all permutations $\sigma\in S_{n}$
satisfying $\sigma\left(  3\right)  >\sigma\left(  4\right)  $ is $n!/2$
(because these permutations are precisely the green permutations $\sigma\in
S_{n}$). This proves Proposition \ref{prop.perm.si34}.
\end{proof}

Our above proof was an example of a \textquotedblleft counting by
symmetry\textquotedblright: We did not count the green permutations directly;
instead, we showed that they are in bijection with the remaining (i.e., red)
permutations $\sigma\in S_{n}$ (that is, we matched up each green permutation
with a red one), from which we concluded that they make up exactly half of the
set $S_{n}$; and this told us that there are $\dfrac{1}{2}\left\vert
S_{n}\right\vert =n!/2$ of them.

\begin{exercise}
\label{exe.perm.count-mulj-order}Let $n\geq4$ be an integer. Prove the following:

\textbf{(a)} The number of all permutations $\sigma\in S_{n}$ satisfying
$\sigma\left(  1\right)  >\sigma\left(  2\right)  $ and $\sigma\left(
3\right)  >\sigma\left(  4\right)  $ is $n!/4$.

\textbf{(b)} The number of all permutations $\sigma\in S_{n}$ satisfying
$\sigma\left(  1\right)  >\sigma\left(  2\right)  >\sigma\left(  3\right)  $
is $n!/6$.

[\textbf{Hint:} You'll need more than $2$ colors...]
\end{exercise}

\begin{proof}
[Solution to Exercise \ref{exe.perm.count-mulj-order} (sketched).]I will be
more laconic than in the proof of Proposition \ref{prop.perm.si34} above,
because much of the arguments below simply repeats arguments made in the
latter proof.

The main tool for this solution will be the $n-1$ \textit{simple
transpositions} $s_{1},s_{2},\ldots,s_{n-1}$. These are defined as follows:
Given $k\in\left[  n-1\right]  $, we let $s_{k}$ be the permutation of
$\left[  n\right]  $ that swaps the numbers $k$ and $k+1$ while leaving all
other numbers unchanged.\footnote{That is, $s_{k}$ is given by%
\[
s_{k}\left(  i\right)  =%
\begin{cases}
k+1, & \text{if }i=k;\\
k, & \text{if }i=k+1;\\
i, & \text{if }i\notin\left\{  k,k+1\right\}
\end{cases}
\ \ \ \ \ \ \ \ \ \ \text{for all }i\in\left[  n\right]  .
\]
(In one-line notation, $s_{k}$ is represented as $\left(  1,2,\ldots
,k-1,k+1,k,k+2,k+3,\ldots,n\right)  $, where only the two numbers $k$ and
$k+1$ are out of order.)} Of course, for $k=3$, this $s_{k}$ is precisely the
permutation $s_{3}$ that was used in the proof of Proposition
\ref{prop.perm.si34}. These permutations $s_{1},s_{2},\ldots,s_{n-1}$ are
known as the \textit{simple transpositions} in $S_{n}$, and they are in a
sense the \textquotedblleft building blocks\textquotedblright\ of all
permutations (see Remark \ref{rmk.perm.count-mulj-order.skbraid} \textbf{(c)} below).

For each $k\in\left[  n-1\right]  $, we have $s_{k}\circ s_{k}%
=\operatorname*{id}$. (This generalizes the $s_{3}\circ s_{3}%
=\operatorname*{id}$ from the proof of Proposition \ref{prop.perm.si34}. Of
course, the proof is just as trivial.)

Let us now come to the actual solution.

\textbf{(a)} I say that a permutation $\sigma\in S_{n}$ is

\begin{itemize}
\item \textit{green-green} if it satisfies $\sigma\left(  1\right)
>\sigma\left(  2\right)  $ and $\sigma\left(  3\right)  >\sigma\left(
4\right)  $;

\item \textit{green-red} if it satisfies $\sigma\left(  1\right)
>\sigma\left(  2\right)  $ and $\sigma\left(  3\right)  <\sigma\left(
4\right)  $;

\item \textit{red-green} if it satisfies $\sigma\left(  1\right)
<\sigma\left(  2\right)  $ and $\sigma\left(  3\right)  >\sigma\left(
4\right)  $;

\item \textit{red-red} if it satisfies $\sigma\left(  1\right)  <\sigma\left(
2\right)  $ and $\sigma\left(  3\right)  <\sigma\left(  4\right)  $.
\end{itemize}

Every permutation $\sigma\in S_{n}$ is either green-green or green-red or
red-green or red-red, but no permutation $\sigma\in S_{n}$ can have two (or
more) of these properties simultaneously. Thus,%
\begin{align}
&  \left\vert S_{n}\right\vert \nonumber\\
&  =\left\vert \left\{  \text{green-green permutations }\sigma\in
S_{n}\right\}  \right\vert \nonumber\\
&  \ \ \ \ \ \ \ \ \ \ +\left\vert \left\{  \text{green-red permutations
}\sigma\in S_{n}\right\}  \right\vert \nonumber\\
&  \ \ \ \ \ \ \ \ \ \ +\left\vert \left\{  \text{red-green permutations
}\sigma\in S_{n}\right\}  \right\vert \nonumber\\
&  \ \ \ \ \ \ \ \ \ \ +\left\vert \left\{  \text{red-red permutations }%
\sigma\in S_{n}\right\}  \right\vert . \label{sol.perm.count-mulj-order.a.1}%
\end{align}


Next, I claim that the four \textquotedblleft colors\textquotedblright\ (by
which I mean the properties \textquotedblleft green-green\textquotedblright,
\textquotedblleft green-red\textquotedblright, \textquotedblleft
red-green\textquotedblright\ and \textquotedblleft red-red\textquotedblright)
are equidistributed, i.e., the number of permutations of one color equals the
number of permutations of any other.

It is easy to see that if $\sigma\in S_{n}$ is green-green, then $\sigma\circ
s_{3}\in S_{n}$ is green-red\footnote{The proof of this is analogous to the
proof of (\ref{pf.prop.perm.si34.g2r}) above, except that we now also need to
check that $\left(  \sigma\circ s_{3}\right)  \left(  1\right)  >\left(
\sigma\circ s_{3}\right)  \left(  2\right)  $ (but this is obvious: we have
$\left(  \sigma\circ s_{3}\right)  \left(  1\right)  =\sigma\left(
\underbrace{s_{3}\left(  1\right)  }_{=1}\right)  =\sigma\left(  1\right)  $
and similarly $\left(  \sigma\circ s_{3}\right)  \left(  2\right)
=\sigma\left(  2\right)  $).}. This lets us define a map%
\begin{align*}
\left\{  \text{green-green permutations }\sigma\in S_{n}\right\}   &
\rightarrow\left\{  \text{green-red permutations }\sigma\in S_{n}\right\}  ,\\
\sigma &  \mapsto\sigma\circ s_{3}.
\end{align*}
Likewise, we can define a map%
\begin{align*}
\left\{  \text{green-red permutations }\sigma\in S_{n}\right\}   &
\rightarrow\left\{  \text{green-green permutations }\sigma\in S_{n}\right\}
,\\
\sigma &  \mapsto\sigma\circ s_{3}.
\end{align*}
These two maps are mutually inverse\footnote{This can be proven in the same
way as we showed that $\alpha$ and $\beta$ are mutually inverse in the proof
of Proposition \ref{prop.perm.si34} above.}. Thus, we have found a bijection
from $\left\{  \text{green-green permutations }\sigma\in S_{n}\right\}  $ to
$\left\{  \text{green-red permutations }\sigma\in S_{n}\right\}  $. Hence,%
\begin{align}
&  \left\vert \left\{  \text{green-green permutations }\sigma\in
S_{n}\right\}  \right\vert \nonumber\\
&  =\left\vert \left\{  \text{green-red permutations }\sigma\in S_{n}\right\}
\right\vert . \label{sol.perm.count-mulj-order.a.3a}%
\end{align}


Similarly,%
\begin{align}
&  \left\vert \left\{  \text{red-green permutations }\sigma\in S_{n}\right\}
\right\vert \nonumber\\
&  =\left\vert \left\{  \text{red-red permutations }\sigma\in S_{n}\right\}
\right\vert . \label{sol.perm.count-mulj-order.a.3b}%
\end{align}


But we also have%
\begin{align}
&  \left\vert \left\{  \text{green-green permutations }\sigma\in
S_{n}\right\}  \right\vert \nonumber\\
&  =\left\vert \left\{  \text{red-green permutations }\sigma\in S_{n}\right\}
\right\vert . \label{sol.perm.count-mulj-order.a.3c}%
\end{align}
(The proof of this is analogous to the proof of
(\ref{sol.perm.count-mulj-order.a.3a}), but we now need to use $s_{1}$ instead
of $s_{3}$. Thus, the mutually inverse bijections between $\left\{
\text{green-green permutations }\sigma\in S_{n}\right\}  $ and $\left\{
\text{red-green permutations }\sigma\in S_{n}\right\}  $ no longer send a
permutation $\sigma$ to $\sigma\circ s_{3}$, but instead send a permutation
$\sigma$ to $\sigma\circ s_{1}$.)

Combining the three equalities (\ref{sol.perm.count-mulj-order.a.3a}),
(\ref{sol.perm.count-mulj-order.a.3b}) and
(\ref{sol.perm.count-mulj-order.a.3c}), we see that the four numbers%
\begin{align*}
&  \left\vert \left\{  \text{green-green permutations }\sigma\in
S_{n}\right\}  \right\vert ,\ \ \ \ \ \ \ \ \ \ \left\vert \left\{
\text{green-red permutations }\sigma\in S_{n}\right\}  \right\vert ,\\
&  \left\vert \left\{  \text{red-green permutations }\sigma\in S_{n}\right\}
\right\vert ,\ \ \ \ \ \ \ \ \ \ \left\vert \left\{  \text{red-red
permutations }\sigma\in S_{n}\right\}  \right\vert
\end{align*}
are all the same. Hence, all four addends on the right hand side of
(\ref{sol.perm.count-mulj-order.a.1}) equal $\left\vert \left\{
\text{green-green permutations }\sigma\in S_{n}\right\}  \right\vert $. Thus,
(\ref{sol.perm.count-mulj-order.a.1}) simplifies to%
\[
\left\vert S_{n}\right\vert =4\cdot\left\vert \left\{  \text{green-green
permutations }\sigma\in S_{n}\right\}  \right\vert .
\]
Hence,%
\[
\left\vert \left\{  \text{green-green permutations }\sigma\in S_{n}\right\}
\right\vert =\dfrac{1}{4}\underbrace{\left\vert S_{n}\right\vert }%
_{=n!}=\dfrac{1}{4}n!=n!/4.
\]
In other words, the number of all green-green permutations $\sigma\in S_{n}$
is $n!/4$. In other words, the number of all permutations $\sigma\in S_{n}$
satisfying $\sigma\left(  1\right)  >\sigma\left(  2\right)  $ and
$\sigma\left(  3\right)  >\sigma\left(  4\right)  $ is $n!/4$ (because these
permutations are precisely the green-green permutations $\sigma\in S_{n}$).
This solves Exercise \ref{exe.perm.count-mulj-order} \textbf{(a)}.

\textbf{(b)} I say that a permutation $\sigma\in S_{n}$ is

\begin{itemize}
\item \textit{color-123} if it satisfies $\sigma\left(  1\right)
>\sigma\left(  2\right)  >\sigma\left(  3\right)  $;

\item \textit{color-132} if it satisfies $\sigma\left(  1\right)
>\sigma\left(  3\right)  >\sigma\left(  2\right)  $;

\item \textit{color-213} if it satisfies $\sigma\left(  2\right)
>\sigma\left(  1\right)  >\sigma\left(  3\right)  $;

\item \textit{color-231} if it satisfies $\sigma\left(  2\right)
>\sigma\left(  3\right)  >\sigma\left(  1\right)  $;

\item \textit{color-312} if it satisfies $\sigma\left(  3\right)
>\sigma\left(  1\right)  >\sigma\left(  2\right)  $;

\item \textit{color-321} if it satisfies $\sigma\left(  3\right)
>\sigma\left(  2\right)  >\sigma\left(  1\right)  $.
\end{itemize}

(By now we have dropped all pretense that our adjectives are real colors.)

Each permutation $\sigma\in S_{n}$ has exactly one of the six properties
\textquotedblleft color-123\textquotedblright, \textquotedblleft
color-132\textquotedblright, \textquotedblleft color-213\textquotedblright,
\textquotedblleft color-231\textquotedblright, \textquotedblleft
color-312\textquotedblright\ and \textquotedblleft color-321\textquotedblright%
\ (because these properties classify permutations $\sigma\in S_{n}$ according
to the relative order between their first three values $\sigma\left(
1\right)  ,\sigma\left(  2\right)  ,\sigma\left(  3\right)  $). Hence,%
\begin{align}
\left\vert S_{n}\right\vert  &  =\left\vert \left\{  \text{color-123
permutations }\sigma\in S_{n}\right\}  \right\vert +\left\vert \left\{
\text{color-132 permutations }\sigma\in S_{n}\right\}  \right\vert \nonumber\\
&  \ \ \ \ \ \ \ \ \ \ +\left\vert \left\{  \text{color-213 permutations
}\sigma\in S_{n}\right\}  \right\vert +\left\vert \left\{  \text{color-231
permutations }\sigma\in S_{n}\right\}  \right\vert \nonumber\\
&  \ \ \ \ \ \ \ \ \ \ +\left\vert \left\{  \text{color-312 permutations
}\sigma\in S_{n}\right\}  \right\vert +\left\vert \left\{  \text{color-321
permutations }\sigma\in S_{n}\right\}  \right\vert .
\label{sol.perm.count-mulj-order.b.1}%
\end{align}


We shall now, as before, prove that these six properties (\textquotedblleft
colors\textquotedblright) are \textquotedblleft
equidistributed\textquotedblright. The arguments we use will again be similar
to those used in the proof of Proposition \ref{prop.perm.si34}, so we restrict
ourselves to a sketch:

\begin{itemize}
\item It is easy to see that if $\sigma\in S_{n}$ is color-123, then
$\sigma\circ s_{1}\in S_{n}$ is color-213. This lets us define a map%
\begin{align*}
\left\{  \text{color-123 permutations }\sigma\in S_{n}\right\}   &
\rightarrow\left\{  \text{color-213 permutations }\sigma\in S_{n}\right\}  ,\\
\sigma &  \mapsto\sigma\circ s_{1}.
\end{align*}
Likewise, we can define a map%
\begin{align*}
\left\{  \text{color-213 permutations }\sigma\in S_{n}\right\}   &
\rightarrow\left\{  \text{color-123 permutations }\sigma\in S_{n}\right\}  ,\\
\sigma &  \mapsto\sigma\circ s_{1}.
\end{align*}
These two maps are mutually inverse. Thus, we have found a bijection from
$\left\{  \text{color-123 permutations }\sigma\in S_{n}\right\}  $ to
$\left\{  \text{color-213 permutations }\sigma\in S_{n}\right\}  $. Hence,%
\begin{align}
&  \left\vert \left\{  \text{color-123 permutations }\sigma\in S_{n}\right\}
\right\vert \nonumber\\
&  =\left\vert \left\{  \text{color-213 permutations }\sigma\in S_{n}\right\}
\right\vert . \label{sol.perm.count-mulj-order.b.2a}%
\end{align}


\item Similarly,%
\begin{align}
&  \left\vert \left\{  \text{color-132 permutations }\sigma\in S_{n}\right\}
\right\vert \nonumber\\
&  =\left\vert \left\{  \text{color-231 permutations }\sigma\in S_{n}\right\}
\right\vert \label{sol.perm.count-mulj-order.b.2b}%
\end{align}
and%
\begin{align}
&  \left\vert \left\{  \text{color-312 permutations }\sigma\in S_{n}\right\}
\right\vert \nonumber\\
&  =\left\vert \left\{  \text{color-321 permutations }\sigma\in S_{n}\right\}
\right\vert . \label{sol.perm.count-mulj-order.b.2c}%
\end{align}


\item A similar argument using $s_{2}$ instead of $s_{1}$ shows that%
\begin{align}
&  \left\vert \left\{  \text{color-213 permutations }\sigma\in S_{n}\right\}
\right\vert \nonumber\\
&  =\left\vert \left\{  \text{color-312 permutations }\sigma\in S_{n}\right\}
\right\vert \label{sol.perm.count-mulj-order.b.3a}%
\end{align}
and%
\begin{align}
&  \left\vert \left\{  \text{color-321 permutations }\sigma\in S_{n}\right\}
\right\vert \nonumber\\
&  =\left\vert \left\{  \text{color-231 permutations }\sigma\in S_{n}\right\}
\right\vert . \label{sol.perm.count-mulj-order.b.3b}%
\end{align}

\end{itemize}

Combining the five equalities (\ref{sol.perm.count-mulj-order.b.2a}),
(\ref{sol.perm.count-mulj-order.b.2b}), (\ref{sol.perm.count-mulj-order.b.2c}%
), (\ref{sol.perm.count-mulj-order.b.3a}) and
(\ref{sol.perm.count-mulj-order.b.3b}), we conclude that the six numbers%
\begin{align*}
&  \left\vert \left\{  \text{color-123 permutations }\sigma\in S_{n}\right\}
\right\vert ,\ \ \ \ \ \ \ \ \ \ \left\vert \left\{  \text{color-132
permutations }\sigma\in S_{n}\right\}  \right\vert \\
&  \left\vert \left\{  \text{color-213 permutations }\sigma\in S_{n}\right\}
\right\vert ,\ \ \ \ \ \ \ \ \ \ \left\vert \left\{  \text{color-231
permutations }\sigma\in S_{n}\right\}  \right\vert \\
&  \left\vert \left\{  \text{color-312 permutations }\sigma\in S_{n}\right\}
\right\vert ,\ \ \ \ \ \ \ \ \ \ \left\vert \left\{  \text{color-321
permutations }\sigma\in S_{n}\right\}  \right\vert
\end{align*}
are all the same. Hence, all six addends on the right hand side of
(\ref{sol.perm.count-mulj-order.b.1}) equal $\left\vert \left\{
\text{color-123 permutations }\sigma\in S_{n}\right\}  \right\vert $. Thus,
(\ref{sol.perm.count-mulj-order.b.1}) simplifies to%
\[
\left\vert S_{n}\right\vert =6\cdot\left\vert \left\{  \text{color-123
permutations }\sigma\in S_{n}\right\}  \right\vert .
\]
Hence,%
\[
\left\vert \left\{  \text{color-123 permutations }\sigma\in S_{n}\right\}
\right\vert =\dfrac{1}{6}\underbrace{\left\vert S_{n}\right\vert }%
_{=n!}=\dfrac{1}{6}n!=n!/6.
\]
In other words, the number of all color-123 permutations $\sigma\in S_{n}$ is
$n!/6$. In other words, the number of all permutations $\sigma\in S_{n}$
satisfying $\sigma\left(  1\right)  >\sigma\left(  2\right)  >\sigma\left(
3\right)  $ is $n!/6$ (because these permutations are precisely the color-123
permutations $\sigma\in S_{n}$). This solves Exercise
\ref{exe.perm.count-mulj-order} \textbf{(b)}.
\end{proof}

\begin{remark}
\label{rmk.perm.count-mulj-order.skbraid}Let $n\in\mathbb{N}$. The simple
transpositions $s_{1},s_{2},\ldots,s_{n-1}$ introduced in the above solution
of Exercise \ref{exe.perm.count-mulj-order} are rather significant. Here are
three more of their properties:

\textbf{(a)} If $k\in\left[  n-1\right]  $ and $l\in\left[  n-1\right]  $
satisfy $\left\vert k-l\right\vert >1$, then $s_{k}\circ s_{l}=s_{l}\circ
s_{k}$. (This is often called a \textquotedblleft locality
principle\textquotedblright; essentially, it says that swapping $k$ and $k+1$
doesn't interact with swapping $l$ and $l+1$ when $\left\vert k-l\right\vert
>1$.)

\textbf{(b)} For each $k\in\left[  n-2\right]  $, we have $s_{k}\circ
s_{k+1}\circ s_{k}=s_{k+1}\circ s_{k}\circ s_{k+1}$. (This is called the
\textquotedblleft braid relation\textquotedblright, and is easily verified by
hand; in fact, both $s_{k}\circ s_{k+1}\circ s_{k}$ and $s_{k+1}\circ
s_{k}\circ s_{k+1}$ turn out to be the permutation of $\left[  n\right]  $
that swaps $k$ with $k+2$ while leaving all other numbers unchanged.)

\textbf{(c)} Each permutation in $S_{n}$ can be written as a composition of
some of the $s_{1},s_{2},\ldots,s_{n-1}$. (Note that the composition may be
empty -- in which case it is understood to mean the trivial permutation
$\operatorname*{id}$ -- and that any of the $s_{1},s_{2},\ldots,s_{n-1}$ can
appear many times in the composition.)

For an example, the permutation of $\left[  5\right]  $ that sends $1,2,3,4,5$
to $5,3,1,2,4$ can be written as $s_{4}\circ s_{3}\circ s_{2}\circ s_{1}\circ
s_{3}\circ s_{2}$.

(We will prove this later this semester.)
\end{remark}

\begin{remark}
\label{rmk.perm.count-mulj-order.genb}Exercise \ref{exe.perm.count-mulj-order}
\textbf{(b)} can be generalized: If $n\in\mathbb{N}$ and $k\in\left\{
0,1,\ldots,n\right\}  $, then the number of all permutations $\sigma\in S_{n}$
satisfying $\sigma\left(  1\right)  >\sigma\left(  2\right)  >\cdots
>\sigma\left(  k\right)  $ is $n!/k!$. This can be proven in the same way as
we solved Exercise \ref{exe.perm.count-mulj-order} \textbf{(b)}, except that
we now need to be more systematic about the colors (there are $k!$ colors now)
and justify their equidistribution abstractly -- which is more difficult.

There is a simpler proof, though. [\textbf{Hint:} In order to construct a
permutation $\sigma\in S_{n}$ satisfying $\sigma\left(  1\right)
>\sigma\left(  2\right)  >\cdots>\sigma\left(  k\right)  $, you can first
choose the set $\left\{  \sigma\left(  1\right)  ,\sigma\left(  2\right)
,\ldots,\sigma\left(  k\right)  \right\}  $ (this should be a $k$-element
subset of $\left[  n\right]  $, so there are $\dbinom{n}{k}$ choices for it),
which automatically determines the values $\sigma\left(  1\right)
,\sigma\left(  2\right)  ,\ldots,\sigma\left(  k\right)  $ (namely, they must
be the $k$ elements of this set in decreasing order); then choose the
remaining $n-k$ values $\sigma\left(  k+1\right)  ,\sigma\left(  k+2\right)
,\ldots,\sigma\left(  n\right)  $ (these are just $n-k$ distinct values chosen
from an $\left(  n-k\right)  $-element set, so there are $\left(  n-k\right)
!$ choices for them). Thus, the total number of options is $\dbinom{n}%
{k}\left(  n-k\right)  !=n!/k!$.]
\end{remark}

\subsection{More on Fibonacci numbers}

Recall that the
\textit{\href{https://en.wikipedia.org/wiki/Fibonacci_number}{Fibonacci
sequence}} is the sequence $\left(  f_{0},f_{1},f_{2},\ldots\right)  $ of
integers which is defined recursively by $f_{0}=0$, $f_{1}=1$, and
\begin{equation}
f_{n}=f_{n-1}+f_{n-2}\ \ \ \ \ \ \ \ \ \ \text{for all }n\geq2.
\label{eq.fib.rec}%
\end{equation}


\begin{exercise}
\label{exe.fib.more-ids}Prove the following:

\textbf{(a)} We have $7f_{n}=f_{n-4}+f_{n+4}$ for each $n\geq4$.

\textbf{(b)} We have $f_{1}+f_{2}+\cdots+f_{n}=f_{n+2}-1$ for each
$n\in\mathbb{N}$.

\textbf{(c)} We have $f_{1}+f_{3}+f_{5}+\cdots+f_{2n-1}=f_{2n}$ for each
$n\in\mathbb{N}$.

\textbf{(d)} We have $f_{2}+f_{4}+f_{6}+\cdots+f_{2n}=f_{2n+1}-1$ for each
$n\in\mathbb{N}$.

\textbf{(e)} We have $f_{m+n+1}=f_{m+1}f_{n+1}+f_{m}f_{n}$ for all
$m\in\mathbb{N}$ and $n\in\mathbb{N}$.

\textbf{(f)} For every $m\in\mathbb{N}$, we have
\[
f_{2m+2}=\sum_{\substack{\left(  a,b\right)  \in\mathbb{N}^{2};\\a+b\leq
m}}\dbinom{m-a}{b}\dbinom{m-b}{a}.
\]


[\textbf{Hint:} All parts can be proven bijectively; part \textbf{(f)} is
actually easiest to prove bijectively! (On the other hand, proving part
\textbf{(a)} bijectively is a challenge; there are much easier ways.) As a
reminder: Any exercises from previous problem sets can be used without proof.]
\end{exercise}

\begin{proof}
[Solution to Exercise \ref{exe.fib.more-ids} (sketched).]We shall use the
symbol \textquotedblleft$\overset{\text{(\ref{eq.fib.rec})}}{=}$%
\textquotedblright\ for \textquotedblleft equals, because of the recurrence
equation (\ref{eq.fib.rec})\textquotedblright. For example, $f_{5}%
\overset{\text{(\ref{eq.fib.rec})}}{=}f_{4}+f_{3}$ and $f_{3}+f_{2}%
\overset{\text{(\ref{eq.fib.rec})}}{=}f_{4}$ and $f_{k+5}%
\overset{\text{(\ref{eq.fib.rec})}}{=}f_{k+4}+f_{k+3}$ for every
$k\in\mathbb{N}$.

\textbf{(a)} Let $n\geq4$. Then,%
\begin{align*}
f_{n-4}+\underbrace{f_{n+4}}_{\overset{\text{(\ref{eq.fib.rec})}}{=}%
f_{n+3}+f_{n+2}}  &  =f_{n-4}+\underbrace{f_{n+3}}%
_{\overset{\text{(\ref{eq.fib.rec})}}{=}f_{n+2}+f_{n+1}}+\underbrace{f_{n+2}%
}_{\overset{\text{(\ref{eq.fib.rec})}}{=}f_{n+1}+f_{n}}\\
&  =f_{n-4}+f_{n+2}+f_{n+1}+f_{n+1}+f_{n}=f_{n-4}+\underbrace{f_{n+2}%
}_{\overset{\text{(\ref{eq.fib.rec})}}{=}f_{n+1}+f_{n}}+2f_{n+1}+f_{n}\\
&  =f_{n-4}+f_{n+1}+f_{n}+2f_{n+1}+f_{n}=f_{n-4}+2f_{n}+3\underbrace{f_{n+1}%
}_{\overset{\text{(\ref{eq.fib.rec})}}{=}f_{n}+f_{n-1}}\\
&  =f_{n-4}+2f_{n}+3\left(  f_{n}+f_{n-1}\right)  =f_{n-4}+5f_{n}%
+3\underbrace{f_{n-1}}_{\overset{\text{(\ref{eq.fib.rec})}}{=}f_{n-2}+f_{n-3}%
}\\
&  =f_{n-4}+5f_{n}+3\left(  f_{n-2}+f_{n-3}\right)  =\underbrace{f_{n-4}%
+f_{n-3}}_{\overset{\text{(\ref{eq.fib.rec})}}{=}f_{n-2}}+5f_{n}%
+3f_{n-2}+2f_{n-3}\\
&  =f_{n-2}+5f_{n}+3f_{n-2}+2f_{n-3}=5f_{n}+2f_{n-2}+2\underbrace{\left(
f_{n-2}+f_{n-3}\right)  }_{\overset{\text{(\ref{eq.fib.rec})}}{=}f_{n-1}}\\
&  =5f_{n}+2f_{n-2}+2f_{n-1}=5f_{n}+2\underbrace{\left(  f_{n-1}%
+f_{n-2}\right)  }_{\overset{\text{(\ref{eq.fib.rec})}}{=}f_{n}}\\
&  =5f_{n}+2f_{n}=7f_{n}.
\end{align*}
This solves Exercise \ref{exe.fib.more-ids} \textbf{(a)}.

\textbf{(b)} We shall solve Exercise \ref{exe.fib.more-ids} \textbf{(b)} by
induction on $n$:

\textit{Induction base:} Comparing $f_{1}+f_{2}+\cdots+f_{0}=\left(
\text{empty sum}\right)  =0$ with $f_{0+2}-1=\underbrace{f_{2}}_{=1}-1=1-1=0$,
we obtain $f_{1}+f_{2}+\cdots+f_{0}=f_{0+2}-1$. In other words, Exercise
\ref{exe.fib.more-ids} \textbf{(b)} holds for $n=0$. This completes the
induction base.

\textit{Induction step:} Let $k\in\mathbb{N}$. Assume that Exercise
\ref{exe.fib.more-ids} \textbf{(b)} holds for $n=k$. We must prove that
Exercise \ref{exe.fib.more-ids} \textbf{(b)} holds for $n=k+1$.

We have $f_{1}+f_{2}+\cdots+f_{k}=f_{k+2}-1$ (since Exercise
\ref{exe.fib.more-ids} \textbf{(b)} holds for $n=k$). Now,%
\begin{align*}
f_{1}+f_{2}+\cdots+f_{k+1}  &  =\underbrace{\left(  f_{1}+f_{2}+\cdots
+f_{k}\right)  }_{=f_{k+2}-1}+f_{k+1}=f_{k+2}-1+f_{k+1}=\underbrace{f_{k+2}%
+f_{k+1}}_{\overset{\text{(\ref{eq.fib.rec})}}{=}f_{k+3}=f_{\left(
k+1\right)  +2}}-1\\
&  =f_{\left(  k+1\right)  +2}-1.
\end{align*}
In other words, Exercise \ref{exe.fib.more-ids} \textbf{(b)} holds for
$n=k+1$. This completes the induction step. Thus, Exercise
\ref{exe.fib.more-ids} \textbf{(b)} is solved.

\textbf{(c)} We shall solve Exercise \ref{exe.fib.more-ids} \textbf{(c)} by
induction on $n$:

\textit{Induction base:} Comparing $f_{1}+f_{3}+f_{5}+\cdots+f_{2\cdot
0-1}=\left(  \text{empty sum}\right)  =0$ with $f_{2\cdot0}=f_{0}=0$, we
obtain $f_{1}+f_{3}+f_{5}+\cdots+f_{2\cdot0-1}=f_{2\cdot0}$. In other words,
Exercise \ref{exe.fib.more-ids} \textbf{(c)} holds for $n=0$. This completes
the induction base.

\textit{Induction step:} Let $k\in\mathbb{N}$. Assume that Exercise
\ref{exe.fib.more-ids} \textbf{(c)} holds for $n=k$. We must prove that
Exercise \ref{exe.fib.more-ids} \textbf{(c)} holds for $n=k+1$.

We have $f_{1}+f_{3}+f_{5}+\cdots+f_{2k-1}=f_{2k}$ (since Exercise
\ref{exe.fib.more-ids} \textbf{(c)} holds for $n=k$). Now,
\begin{align*}
f_{1}+f_{3}+f_{5}+\cdots+f_{2\left(  k+1\right)  -1}  &  =\underbrace{\left(
f_{1}+f_{3}+f_{5}+\cdots+f_{2k-1}\right)  }_{=f_{2k}}+\underbrace{f_{2\left(
k+1\right)  -1}}_{=f_{2k+1}}=f_{2k}+f_{2k+1}\\
&  =f_{2k+1}+f_{2k}\overset{\text{(\ref{eq.fib.rec})}}{=}f_{2k+2}=f_{2\left(
k+1\right)  }.
\end{align*}
In other words, Exercise \ref{exe.fib.more-ids} \textbf{(c)} holds for
$n=k+1$. This completes the induction step. Thus, Exercise
\ref{exe.fib.more-ids} \textbf{(c)} is solved.

\textbf{(d)} We shall solve Exercise \ref{exe.fib.more-ids} \textbf{(d)} by
induction on $n$:

\textit{Induction base:} Comparing $f_{2}+f_{4}+f_{6}+\cdots+f_{2\cdot
0}=\left(  \text{empty sum}\right)  =0$ with $f_{2\cdot0+1}%
-1=\underbrace{f_{1}}_{=1}-1=1-1=0$, we obtain $f_{2}+f_{4}+f_{6}%
+\cdots+f_{2\cdot0}=f_{2\cdot0+1}-1$. In other words, Exercise
\ref{exe.fib.more-ids} \textbf{(d)} holds for $n=0$. This completes the
induction base.

\textit{Induction step:} Let $k\in\mathbb{N}$. Assume that Exercise
\ref{exe.fib.more-ids} \textbf{(d)} holds for $n=k$. We must prove that
Exercise \ref{exe.fib.more-ids} \textbf{(d)} holds for $n=k+1$.

We have $f_{2}+f_{4}+f_{6}+\cdots+f_{2k}=f_{2k+1}-1$ (since Exercise
\ref{exe.fib.more-ids} \textbf{(d)} holds for $n=k$). Now,
\begin{align*}
f_{2}+f_{4}+f_{6}+\cdots+f_{2\left(  k+1\right)  }  &  =\underbrace{\left(
f_{2}+f_{4}+f_{6}+\cdots+f_{2k}\right)  }_{=f_{2k+1}-1}%
+\underbrace{f_{2\left(  k+1\right)  }}_{=f_{2k+2}}=f_{2k+1}-1+f_{2k+2}\\
&  =\underbrace{f_{2k+2}+f_{2k+1}}_{\overset{\text{(\ref{eq.fib.rec})}%
}{=}f_{2k+3}=f_{2\left(  k+1\right)  +1}}-1=f_{2\left(  k+1\right)  +1}-1.
\end{align*}
In other words, Exercise \ref{exe.fib.more-ids} \textbf{(d)} holds for
$n=k+1$. This completes the induction step. Thus, Exercise
\ref{exe.fib.more-ids} \textbf{(d)} is solved.

\textbf{(e)} We shall solve Exercise \ref{exe.fib.more-ids} \textbf{(e)} by
induction on $n$:

\textit{Induction base:} For all $m\in\mathbb{N}$, we have $f_{m+0+1}%
=f_{m+1}f_{0+1}+f_{m}f_{0}$\ \ \ \ \footnote{\textit{Proof.} Let
$m\in\mathbb{N}$. Then, $f_{m+0+1}=f_{m+1}$. Comparing this with
$f_{m+1}\underbrace{f_{0+1}}_{=f_{1}=1}+f_{m}\underbrace{f_{0}}_{=0}%
=f_{m+1}1+f_{m}0=f_{m+1}$, we obtain $f_{m+0+1}=f_{m+1}f_{0+1}+f_{m}f_{0}$,
qed.}. In other words, Exercise \ref{exe.fib.more-ids} \textbf{(e)} holds for
$n=0$. This completes the induction base.

\textit{Induction step:} Let $k\in\mathbb{N}$. Assume that Exercise
\ref{exe.fib.more-ids} \textbf{(e)} holds for $n=k$. We must prove that
Exercise \ref{exe.fib.more-ids} \textbf{(e)} holds for $n=k+1$.

We have assumed that Exercise \ref{exe.fib.more-ids} \textbf{(e)} holds for
$n=k$. In other words, we have%
\begin{equation}
f_{m+k+1}=f_{m+1}f_{k+1}+f_{m}f_{k}\ \ \ \ \ \ \ \ \ \ \text{for all }%
m\in\mathbb{N}. \label{sol.fib.more-ids.e.IH}%
\end{equation}


Now, let $m\in\mathbb{N}$. Then, we can apply (\ref{sol.fib.more-ids.e.IH}) to
$m+1$ instead of $m$. Thus, we obtain%
\begin{align*}
f_{\left(  m+1\right)  +k+1}  &  =\underbrace{f_{\left(  m+1\right)  +1}%
}_{=f_{m+2}\overset{\text{(\ref{eq.fib.rec})}}{=}f_{m+1}+f_{m}}f_{k+1}%
+f_{m+1}f_{k}\\
&  =\left(  f_{m+1}+f_{m}\right)  f_{k+1}+f_{m+1}f_{k}=f_{m+1}f_{k+1}%
+f_{m}f_{k+1}+f_{m+1}f_{k}\\
&  =f_{m+1}\underbrace{\left(  f_{k+1}+f_{k}\right)  }%
_{\overset{\text{(\ref{eq.fib.rec})}}{=}f_{k+2}=f_{\left(  k+1\right)  +1}%
}+f_{m}f_{k+1}=f_{m+1}f_{\left(  k+1\right)  +1}+f_{m}f_{k+1}.
\end{align*}


Now, forget that we fixed $m$. We thus have shown that $f_{\left(  m+1\right)
+k+1}=f_{m+1}f_{\left(  k+1\right)  +1}+f_{m}f_{k+1}$ for all $m\in\mathbb{N}%
$. In other words, Exercise \ref{exe.fib.more-ids} \textbf{(e)} holds for
$n=k+1$. This completes the induction step. Thus, Exercise
\ref{exe.fib.more-ids} \textbf{(e)} is solved.

\textbf{(f)} Recall the definition of a \textit{lacunar} subset of
$\mathbb{Z}$. (We defined this in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18s/hw2s.pdf}{Math 4707 Homework
set 2}.)

For any $n\in\mathbb{N}$, we have%
\begin{equation}
\left(  \text{the number of all lacunar subsets of }\left[  n\right]  \right)
=f_{n+2}. \label{sol.fib.more-ids.f.lacnum}%
\end{equation}
(For a proof of (\ref{sol.fib.more-ids.f.lacnum}), see
\href{http://www.cip.ifi.lmu.de/~grinberg/t/17f/hw1s.pdf}{Exercise 4
\textbf{(c)} on Fall 2017 Math 4707 Homework set 1}, in which the number of
all lacunar subsets of $\left[  n\right]  $ was denoted by $g\left(  n\right)
$.)

For any $n\in\mathbb{N}$, $a\in\mathbb{Z}$ and $b\in\mathbb{Z}$, we let
$N\left(  n,a,b\right)  $ denote the number of all lacunar subsets of $\left[
n\right]  $ that contain exactly $a$ even and exactly $b$ odd elements. Then,
Exercise 3 \textbf{(a)} from
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18s/hw2s.pdf}{Math 4707 Homework
set 2} states that%
\begin{equation}
N\left(  2m,a,b\right)  =\left[  a\leq m\right]  \left[  b\leq m\right]
\dbinom{m-a}{b}\dbinom{m-b}{a} \label{sol.fib.more-ids.f.lacNa}%
\end{equation}
for all $m\in\mathbb{N}$, $a\in\mathbb{N}$ and $b\in\mathbb{N}$.

Now, let $m\in\mathbb{N}$. If $a$ and $b$ are two elements of $\left\{
0,1,\ldots,m\right\}  $ satisfying $a+b>m$, then%
\begin{equation}
\dbinom{m-a}{b}=0. \label{sol.fib.more-ids.f.m-acb=0}%
\end{equation}


\begin{fns}
[\textit{Proof of (\ref{sol.fib.more-ids.f.m-acb=0}):} Let $a$ and $b$ be two
elements of $\left\{  0,1,\ldots,m\right\}  $ satisfying $a+b>m$. From
$a+b>m$, we obtain $b>m-a$, so that $m-a<b$. Also, $a\leq m$ (since
$a\in\left\{  0,1,\ldots,m\right\}  $) and thus $m-a\geq0$, so that
$m-a\in\mathbb{N}$. Hence, (\ref{eq.binom.0}) (applied to $m-a$ and $b$
instead of $m$ and $n$) shows that $\dbinom{m-a}{b}=0$. This proves
(\ref{sol.fib.more-ids.f.m-acb=0}).]
\end{fns}

Any subset of $\left[  2m\right]  $ has at most $m$ even elements (because the
whole set $\left[  2m\right]  $ has only $m$ even elements) and at most $m$
odd elements (similarly). Thus, we can classify the lacunar subsets of
$\left[  2m\right]  $ according to their number of even elements (which is an
integer in $\left\{  0,1,\ldots,m\right\}  $) and their number of odd elements
(which is an integer in $\left\{  0,1,\ldots,m\right\}  $). Hence,%
\begin{align*}
&  \left(  \text{the number of all lacunar subsets of }\left[  2m\right]
\right) \\
&  =\sum_{a\in\left\{  0,1,\ldots,m\right\}  }\sum_{b\in\left\{
0,1,\ldots,m\right\}  }\underbrace{\left(
\begin{array}
[c]{c}%
\text{the number of all lacunar subsets of }\left[  2m\right]  \text{ that
contain}\\
\text{exactly }a\text{ even and exactly }b\text{ odd elements}%
\end{array}
\right)  }_{\substack{=N\left(  2m,a,b\right)  \\\text{(by the definition of
}N\left(  2m,a,b\right)  \text{)}}}\\
&  =\sum_{a\in\left\{  0,1,\ldots,m\right\}  }\sum_{b\in\left\{
0,1,\ldots,m\right\}  }\underbrace{N\left(  2m,a,b\right)  }%
_{\substack{=\left[  a\leq m\right]  \left[  b\leq m\right]  \dbinom{m-a}%
{b}\dbinom{m-b}{a}\\\text{(by (\ref{sol.fib.more-ids.f.lacNa}))}}}\\
&  =\sum_{a\in\left\{  0,1,\ldots,m\right\}  }\sum_{b\in\left\{
0,1,\ldots,m\right\}  }\underbrace{\left[  a\leq m\right]  }%
_{\substack{=1\\\text{(since }a\in\left\{  0,1,\ldots,m\right\}  \text{)}%
}}\underbrace{\left[  b\leq m\right]  }_{\substack{=1\\\text{(since }%
b\in\left\{  0,1,\ldots,m\right\}  \text{)}}}\dbinom{m-a}{b}\dbinom{m-b}{a}\\
&  =\underbrace{\sum_{a\in\left\{  0,1,\ldots,m\right\}  }\sum_{b\in\left\{
0,1,\ldots,m\right\}  }}_{=\sum_{\left(  a,b\right)  \in\left\{
0,1,\ldots,m\right\}  ^{2}}}\dbinom{m-a}{b}\dbinom{m-b}{a}=\sum_{\left(
a,b\right)  \in\left\{  0,1,\ldots,m\right\}  ^{2}}\dbinom{m-a}{b}\dbinom
{m-b}{a}\\
&  =\underbrace{\sum_{\substack{\left(  a,b\right)  \in\left\{  0,1,\ldots
,m\right\}  ^{2};\\a+b\leq m}}}_{\substack{=\sum_{\substack{\left(
a,b\right)  \in\mathbb{N}^{2};\\a+b\leq m}}\\\text{(since any two
nonnegative}\\\text{integers }a\text{ and }b\\\text{satisfying }a+b\leq
m\text{ must}\\\text{satisfy }\left(  a,b\right)  \in\left\{  0,1,\ldots
,m\right\}  ^{2}\text{)}}}\dbinom{m-a}{b}\dbinom{m-b}{a}+\sum
_{\substack{\left(  a,b\right)  \in\left\{  0,1,\ldots,m\right\}
^{2};\\a+b>m}}\underbrace{\dbinom{m-a}{b}}_{\substack{=0\\\text{(by
(\ref{sol.fib.more-ids.f.m-acb=0}))}}}\dbinom{m-b}{a}\\
&  =\sum_{\substack{\left(  a,b\right)  \in\mathbb{N}^{2};\\a+b\leq m}%
}\dbinom{m-a}{b}\dbinom{m-b}{a}+\underbrace{\sum_{\substack{\left(
a,b\right)  \in\left\{  0,1,\ldots,m\right\}  ^{2};\\a+b>m}}0\dbinom{m-b}{a}%
}_{=0}=\sum_{\substack{\left(  a,b\right)  \in\mathbb{N}^{2};\\a+b\leq
m}}\dbinom{m-a}{b}\dbinom{m-b}{a}.
\end{align*}
Comparing this with%
\begin{align*}
&  \left(  \text{the number of all lacunar subsets of }\left[  2m\right]
\right) \\
&  =f_{2m+2}\ \ \ \ \ \ \ \ \ \ \left(  \text{by
(\ref{sol.fib.more-ids.f.lacnum}), applied to }n=2m\right)  ,
\end{align*}
we obtain $f_{2m+2}=\sum_{\substack{\left(  a,b\right)  \in\mathbb{N}%
^{2};\\a+b\leq m}}\dbinom{m-a}{b}\dbinom{m-b}{a}$. This solves Exercise
\ref{exe.fib.more-ids} \textbf{(f)}.
\end{proof}

\begin{remark}
Exercise \ref{exe.fib.more-ids} \textbf{(a)} is one of the so-called
\textit{Zeckendorf family identities}. Here are the first seven of them:%
\begin{align*}
1f_{n}  &  =f_{n}\text{ for all }n\geq0;\\
2f_{n}  &  =f_{n-2}+f_{n+1}\text{ for all }n\geq2;\\
3f_{n}  &  =f_{n-2}+f_{n+2}\text{ for all }n\geq2;\\
4f_{n}  &  =f_{n-2}+f_{n}+f_{n+2}\text{ for all }n\geq2;\\
5f_{n}  &  =f_{n-4}+f_{n-1}+f_{n+3}\text{ for all }n\geq4;\\
6f_{n}  &  =f_{n-4}+f_{n+1}+f_{n+3}\text{ for all }n\geq4;\\
7f_{n}  &  =f_{n-4}+f_{n+4}\text{ for all }n\geq4.
\end{align*}
See \cite{gri-zeck} for more about them (particularly, about how to construct
them all).

Of course, parts \textbf{(a)}, \textbf{(b)}, \textbf{(c)}, \textbf{(d)},
\textbf{(e)} of Exercise \ref{exe.fib.more-ids} can also be proven using
Binet's formula (and the formula for the sum of a geometric series); the
computations aren't particularly fun but can be done.

Alternative solutions abound. For example, part \textbf{(d)} can be easily
derived from parts \textbf{(b)} and \textbf{(c)}.

Exercise \ref{exe.fib.more-ids} \textbf{(e)} also is a particular case of
\cite[Theorem 2.26 \textbf{(a)}]{detnotes} (obtained by setting $a=1$ and
$b=1$, so that the sequence $\left(  x_{0},x_{1},x_{2},\ldots\right)  $
defined in \cite[Theorem 2.26 \textbf{(a)}]{detnotes} becomes precisely the
Fibonacci sequence $\left(  f_{0},f_{1},f_{2},\ldots\right)  $).

Perhaps more interesting is the question of solving Exercise
\ref{exe.fib.more-ids} bijectively (when $f_{n}$ is understood, e.g., as the
number of all lacunar subsets of $\left[  n-2\right]  $, or as the number of
domino tilings of a $2\times\left(  n-1\right)  $-rectangle). This, too, can
be done. A bijective proof for part \textbf{(a)} can, in principle, be
obtained from the bijective proof of (\ref{eq.fib.rec}) (but the bijection
will involve myriad cases). More generally, each of the Zeckendorf family
identities can be proven bijectively; see \cite[\S 3.7]{WooZei} for details.

For a bijective proof of part \textbf{(b)}, see \cite[Identity 1]{BenQui03} or
\cite[Identity 1]{BenQui-fib}. (Notice that the notations in \cite[Identity
1]{BenQui03} or \cite[Identity 1]{BenQui-fib} are different from ours; their
$f_{n}$ is our $f_{n+1}$.)

For a bijective proof of part \textbf{(c)}, see \cite[Identity 2]{BenQui03}. A
similar argument can be used to prove part \textbf{(d)}.

For a bijective proof of part \textbf{(e)}, see \cite[Identity 3]{BenQui03} or
\cite[Identity 2]{BenQui-fib}.

For a bijective proof of part \textbf{(f)} (different from the one we have
given), see \cite[Identity 5]{BenQui-fib} (but beware that Benjamin and Quinn
are cavalier about the summation bounds: their double sum $\sum_{i\geq0}%
\sum_{j\geq0}$ should be $\sum_{i\in\left\{  0,1,\ldots,n\right\}  }\sum
_{j\in\left\{  0,1,\ldots,n\right\}  }$).
\end{remark}

\subsection{More lattice path counting}

Recall that the set $\mathbb{Z}^{2}$ is called the \textit{integer lattice},
and its elements $\left(  a,b\right)  \in\mathbb{Z}^{2}$ are called
\textit{points}. We regard these points as points on the Cartesian plane.

A \textit{lattice path} is a path on the integer lattice that uses only two
kinds of steps:

\begin{itemize}
\item up-steps ($U$), which have the form $\left(  x,y\right)  \mapsto\left(
x,y+1\right)  $;

\item right-steps ($R$), which have the form $\left(  x,y\right)
\mapsto\left(  x+1,y\right)  $.
\end{itemize}

Thus, strictly speaking, a \textit{lattice path} is a sequence $\left(
v_{0},v_{1},\ldots,v_{n}\right)  $ of points $v_{i}\in\mathbb{Z}^{2}$ such
that for each $i\in\left[  n\right]  $, the difference vector $v_{i}-v_{i-1}$
is either $\left(  0,1\right)  $ or $\left(  1,0\right)  $.

If $\left(  a,b\right)  \in\mathbb{Z}^{2}$ and $\left(  c,d\right)
\in\mathbb{Z}^{2}$ are two points on the integer lattice, then a
\textit{lattice path from }$\left(  a,b\right)  $\textit{ to }$\left(
c,d\right)  $ is a lattice path $\left(  v_{0},v_{1},\ldots,v_{n}\right)  $
satisfying $v_{0}=\left(  a,b\right)  $ and $v_{n}=\left(  c,d\right)  $.

\begin{exercise}
\label{exe.count.lp3}\textbf{(a)} Given six integers $a_{1},b_{1},c_{1}%
,a_{2},b_{2},c_{2}$ satisfying $0\leq a_{1}\leq b_{1}\leq c_{1}$ and $0\leq
a_{2}\leq b_{2}\leq c_{2}$. How many lattice paths from $\left(  0,0\right)  $
to $\left(  c_{1},c_{2}\right)  $ pass through none of the points $\left(
a_{1},a_{2}\right)  $ nor $\left(  b_{1},b_{2}\right)  $ ?

\textbf{(b)} Given six integers $a,b,c,A,B,C$ satisfying $0\leq a\leq b\leq c$
and $0\leq A\leq B\leq C$. How many $c$-element subsets $S$ of $\left[
C\right]  $ satisfy $\left\vert S\cap\left[  A\right]  \right\vert \neq a$ and
$\left\vert S\cap\left[  B\right]  \right\vert \neq b$ ?
\end{exercise}

\begin{proof}
[Solution to Exercise \ref{exe.count.lp3} (sketched).]\textbf{(b)} Observe
that $A\leq B\leq C$ and thus $\left[  A\right]  \subseteq\left[  B\right]
\subseteq\left[  C\right]  $.

We define the following three sets:%
\begin{align*}
U  &  =\left\{  c\text{-element subsets }S\text{ of }\left[  C\right]
\right\}  ;\\
X  &  =\left\{  c\text{-element subsets }S\text{ of }\left[  C\right]  \text{
satisfying }\left\vert S\cap\left[  A\right]  \right\vert =a\right\}  ;\\
Y  &  =\left\{  c\text{-element subsets }S\text{ of }\left[  C\right]  \text{
satisfying }\left\vert S\cap\left[  B\right]  \right\vert =b\right\}  .
\end{align*}
Then,
\begin{align*}
&  U\setminus\left(  X\cup Y\right) \\
&  =\left\{  c\text{-element subsets }S\text{ of }\left[  C\right]  \text{
satisfying neither }\left\vert S\cap\left[  A\right]  \right\vert =a\text{ nor
}\left\vert S\cap\left[  B\right]  \right\vert =b\right\} \\
&  =\left\{  c\text{-element subsets }S\text{ of }\left[  C\right]  \text{
satisfying }\left\vert S\cap\left[  A\right]  \right\vert \neq a\text{ and
}\left\vert S\cap\left[  B\right]  \right\vert \neq b\right\}  .
\end{align*}
Hence, $\left\vert U\setminus\left(  X\cup Y\right)  \right\vert $ is the
number of all $c$-element subsets $S$ of $\left[  C\right]  $ satisfying
$\left\vert S\cap\left[  A\right]  \right\vert \neq a$ and $\left\vert
S\cap\left[  B\right]  \right\vert \neq b$. This is the number that we need to compute.

But $X\cup Y$ is clearly a subset of $U$. Thus,%
\begin{align}
\left\vert U\setminus\left(  X\cup Y\right)  \right\vert  &  =\left\vert
U\right\vert -\underbrace{\left\vert X\cup Y\right\vert }_{=\left\vert
X\right\vert +\left\vert Y\right\vert -\left\vert X\cap Y\right\vert
}=\left\vert U\right\vert -\left(  \left\vert X\right\vert +\left\vert
Y\right\vert -\left\vert X\cap Y\right\vert \right) \nonumber\\
&  =\left\vert U\right\vert -\left\vert X\right\vert -\left\vert Y\right\vert
+\left\vert X\cap Y\right\vert . \label{sol.count.lp3.b.3}%
\end{align}
Hence, we need to compute $\left\vert U\right\vert $, $\left\vert X\right\vert
$, $\left\vert Y\right\vert $ and $\left\vert X\cap Y\right\vert $.

Computing $\left\vert U\right\vert $ is easy: The definition of $U$ yields%
\begin{align}
\left\vert U\right\vert  &  =\left\vert \left\{  c\text{-element subsets
}S\text{ of }\left[  C\right]  \right\}  \right\vert \nonumber\\
&  =\left(  \text{the number of all }c\text{-element subsets }S\text{ of
}\left[  C\right]  \right) \nonumber\\
&  =\dbinom{C}{c} \label{sol.count.lp3.b.U}%
\end{align}
(by the combinatorial interpretation of binomial coefficients).

Let us next compute $\left\vert X\right\vert $. Recall that%
\[
X=\left\{  c\text{-element subsets }S\text{ of }\left[  C\right]  \text{
satisfying }\left\vert S\cap\left[  A\right]  \right\vert =a\right\}  .
\]
Thus, $\left\vert X\right\vert $ is the number of all $c$-element subsets $S$
of $\left[  C\right]  $ satisfying $\left\vert S\cap\left[  A\right]
\right\vert =a$. Such a subset must always contain exactly $a$ elements from
$\left[  A\right]  $ (because it must satisfy $\left\vert S\cap\left[
A\right]  \right\vert =a$) and exactly $c-a$ elements from $\left[  C\right]
\setminus\left[  A\right]  $ (because it must have $c$ elements in total).
Thus, we can construct such a subset as follows:

\begin{itemize}
\item First, we decide which $a$ elements of $\left[  A\right]  $ shall belong
to $S$. This can be done in $\dbinom{A}{a}$ many ways (since we are just
choosing an $a$-element subset of $\left[  A\right]  $).

\item Next, we decide which $c-a$ elements of $\left[  C\right]
\setminus\left[  A\right]  $ shall belong to $S.$ This can be done in
$\dbinom{C-A}{c-a}$ many ways (since $\left\vert \left[  C\right]
\setminus\left[  A\right]  \right\vert =C-A$).
\end{itemize}

Thus, altogether, the number of options is $\dbinom{A}{a}\dbinom{C-A}{c-a}$.
We thus have proven that%
\begin{equation}
\left\vert X\right\vert =\dbinom{A}{a}\dbinom{C-A}{c-a}.
\label{sol.count.lp3.b.X}%
\end{equation}
Similarly,%
\begin{equation}
\left\vert Y\right\vert =\dbinom{B}{b}\dbinom{C-B}{c-b}.
\label{sol.count.lp3.b.Y}%
\end{equation}


It remains to compute $\left\vert X\cap Y\right\vert $. The definitions of $X$
and $Y$ yield%
\[
X\cap Y=\left\{  c\text{-element subsets }S\text{ of }\left[  C\right]  \text{
satisfying both }\left\vert S\cap\left[  A\right]  \right\vert =a\text{ and
}\left\vert S\cap\left[  B\right]  \right\vert =b\right\}  .
\]
Thus, $\left\vert X\cap Y\right\vert $ is the number of all $c$-element
subsets $S$ of $\left[  C\right]  $ satisfying both $\left\vert S\cap\left[
A\right]  \right\vert =a$ and $\left\vert S\cap\left[  B\right]  \right\vert
=b$. Such a subset must always contain exactly $a$ elements from $\left[
A\right]  $ (because it must satisfy $\left\vert S\cap\left[  A\right]
\right\vert =a$), exactly $b-a$ elements from $\left[  B\right]
\setminus\left[  A\right]  $ (because it must satisfy $\left\vert S\cap\left[
B\right]  \right\vert =b$ and $\left\vert S\cap\left[  A\right]  \right\vert
=a$, so that
\begin{align*}
\left\vert \underbrace{S\cap\left(  \left[  B\right]  \setminus\left[
A\right]  \right)  }_{=\left(  S\cap\left[  B\right]  \right)  \setminus
\left(  S\cap\left[  A\right]  \right)  }\right\vert  &  =\left\vert \left(
S\cap\left[  B\right]  \right)  \setminus\left(  S\cap\left[  A\right]
\right)  \right\vert \\
&  =\underbrace{\left\vert S\cap\left[  B\right]  \right\vert }_{=b}%
-\underbrace{\left\vert S\cap\left[  A\right]  \right\vert }_{=a}%
\ \ \ \ \ \ \ \ \ \ \left(  \text{since }S\cap\underbrace{\left[  A\right]
}_{\subseteq\left[  B\right]  }\subseteq S\cap\left[  B\right]  \right) \\
&  =b-a
\end{align*}
), and exactly $c-b$ elements from $\left[  C\right]  \setminus\left[
B\right]  $ (because it must have $c$ elements in total, but $\left\vert
S\cap\left[  B\right]  \right\vert =b$). Thus, we can construct such a subset
as follows:

\begin{itemize}
\item First, we decide which $a$ elements of $\left[  A\right]  $ shall belong
to $S$. This can be done in $\dbinom{A}{a}$ many ways (since we are just
choosing an $a$-element subset of $\left[  A\right]  $).

\item Next, we decide which $b-a$ elements of $\left[  B\right]
\setminus\left[  A\right]  $ shall belong to $S.$ This can be done in
$\dbinom{B-A}{b-a}$ many ways (since $\left\vert \left[  B\right]
\setminus\left[  A\right]  \right\vert =B-A$).

\item Next, we decide which $c-b$ elements of $\left[  C\right]
\setminus\left[  B\right]  $ shall belong to $S.$ This can be done in
$\dbinom{C-B}{c-b}$ many ways (since $\left\vert \left[  C\right]
\setminus\left[  B\right]  \right\vert =C-B$).
\end{itemize}

Thus, altogether, the number of options is $\dbinom{A}{a}\dbinom{B-A}%
{b-a}\dbinom{C-B}{c-b}$. We thus have proven that%
\begin{equation}
\left\vert X\cap Y\right\vert =\dbinom{A}{a}\dbinom{B-A}{b-a}\dbinom{C-B}%
{c-b}. \label{sol.count.lp3.b.XnY}%
\end{equation}


Now, (\ref{sol.count.lp3.b.3}) becomes%
\begin{align*}
&  \left\vert U\setminus\left(  X\cup Y\right)  \right\vert \\
&  =\underbrace{\left\vert U\right\vert }_{\substack{=\dbinom{C}{c}\\\text{(by
(\ref{sol.count.lp3.b.U}))}}}-\underbrace{\left\vert X\right\vert
}_{\substack{=\dbinom{A}{a}\dbinom{C-A}{c-a}\\\text{(by
(\ref{sol.count.lp3.b.X}))}}}-\underbrace{\left\vert Y\right\vert
}_{\substack{=\dbinom{B}{b}\dbinom{C-B}{c-b}\\\text{(by
(\ref{sol.count.lp3.b.Y}))}}}+\underbrace{\left\vert X\cap Y\right\vert
}_{\substack{=\dbinom{A}{a}\dbinom{B-A}{b-a}\dbinom{C-B}{c-b}\\\text{(by
(\ref{sol.count.lp3.b.XnY}))}}}\\
&  =\dbinom{C}{c}-\dbinom{A}{a}\dbinom{C-A}{c-a}-\dbinom{B}{b}\dbinom
{C-B}{c-b}+\dbinom{A}{a}\dbinom{B-A}{b-a}\dbinom{C-B}{c-b}.
\end{align*}
So this is the number of all $c$-element subsets $S$ of $\left[  C\right]  $
satisfy $\left\vert S\cap\left[  A\right]  \right\vert \neq a$ and $\left\vert
S\cap\left[  B\right]  \right\vert \neq b$.

(As far as I know, this answer cannot be simplified any further.)

\textbf{(a)} If $\mathbf{v}=\left(  v_{0},v_{1},\ldots,v_{n}\right)  $ is a
lattice path, then the \textit{up-set} of $\mathbf{v}$ shall mean the set of
all $i\in\left[  n\right]  $ such that the difference vector $v_{i}-v_{i-1}$
equals $\left(  0,1\right)  $ (in other words, such that the step from
$v_{i-1}$ to $v_{i}$ is an up-step). Roughly speaking, the up-set of a lattice
path $\mathbf{v}$ tells us which steps of the path $\mathbf{v}$ are up-steps.
For example, the up-set of the lattice path $\begin{tikzpicture}
\delannoypath{0,0}{5}{3}{1,1,0,1,1,0,0,1};
\end{tikzpicture}$ is $\left\{  3,6,7\right\}  $, since the up-steps of this
path are its $3$-rd, $6$-th and $7$-th steps.

If $\mathbf{v}=\left(  v_{0},v_{1},\ldots,v_{n}\right)  $ is a lattice path
from $\left(  0,0\right)  $ to $\left(  c_{1},c_{2}\right)  $, then we
necessarily have $n=c_{1}+c_{2}$ (indeed, we need precisely $c_{1}+c_{2}$
steps to get from $\left(  0,0\right)  $ to $\left(  c_{1},c_{2}\right)  $,
because each step increases the sum of the coordinates of the point by exactly
$1$), and therefore the up-set of $\mathbf{v}$ is a subset of $\left[
n\right]  =\left[  c_{1}+c_{2}\right]  $. Moreover, this up-set is a $c_{2}%
$-element set (indeed, its size is the number of all up-steps of $\mathbf{v}$,
but this number must be $c_{1}$ because $\mathbf{v}$ goes from a point with
y-coordinate $0$ to a point with y-coordinate $c_{2}$), and thus is a $c_{2}%
$-element subset of $\left[  c_{1}+c_{2}\right]  $.

Let $\mathcal{L}$ be the set of all lattice paths from $\left(  0,0\right)  $
to $\left(  c_{1},c_{2}\right)  $. Thus, what we have just showed is the
following: For any $\mathbf{v}\in\mathcal{L}$, the up-set of $\mathbf{v}$ is a
$c_{2}$-element subset of $\left[  c_{1}+c_{2}\right]  $. Thus, we can define
a map%
\begin{align*}
\operatorname*{Ups}:\mathcal{L}  &  \rightarrow\left\{  c_{2}\text{-element
subsets of }\left[  c_{1}+c_{2}\right]  \right\}  ,\\
\mathbf{v}  &  \mapsto\left(  \text{the up-set of }\mathbf{v}\right)  .
\end{align*}
It is easy to see that this map $\operatorname*{Ups}$ is injective (since any
lattice path $\mathbf{v}$ from $\left(  0,0\right)  $ to $\left(  c_{1}%
,c_{2}\right)  $ is uniquely determined by its up-set) and surjective (because
for any $c_{2}$-element subset $S$ of $\left[  c_{1}+c_{2}\right]  $, we can
easily construct a lattice path from $\left(  0,0\right)  $ to $\left(
c_{1},c_{2}\right)  $ whose up-set is $S$). Thus, $\operatorname*{Ups}$ is a bijection.

Moreover, it is easy to check the following two facts:

\begin{itemize}
\item A lattice path $\mathbf{v}\in\mathcal{L}$ passes through the point
$\left(  a_{1},a_{2}\right)  $ if and only if its up-set $\operatorname*{Ups}%
\mathbf{v}$ satisfies $\left\vert \left(  \operatorname*{Ups}\mathbf{v}%
\right)  \cap\left[  a_{1}+a_{2}\right]  \right\vert =a_{2}$. (Indeed, for the
path $\mathbf{v}$ to pass through $\left(  a_{1},a_{2}\right)  $, it must
spend precisely $a_{2}$ of its first $a_{1}+a_{2}$ steps moving upwards; i.e.,
its up-set $\operatorname*{Ups}\mathbf{v}$ should contain exactly $a_{2}$
elements of $\left[  a_{1}+a_{2}\right]  $, but this is equivalent to saying
that $\left\vert \left(  \operatorname*{Ups}\mathbf{v}\right)  \cap\left[
a_{1}+a_{2}\right]  \right\vert =a_{2}$.)

\item A lattice path $\mathbf{v}\in\mathcal{L}$ passes through the point
$\left(  b_{1},b_{2}\right)  $ if and only if its up-set $\operatorname*{Ups}%
\mathbf{v}$ satisfies $\left\vert \left(  \operatorname*{Ups}\mathbf{v}%
\right)  \cap\left[  b_{1}+b_{2}\right]  \right\vert =b_{2}$. (The reason for
this is analogous.)
\end{itemize}

Hence, a lattice path $\mathbf{v}\in\mathcal{L}$ passes through none of the
points $\left(  a_{1},a_{2}\right)  $ and $\left(  b_{1},b_{2}\right)  $ if
and only if it satisfies neither $\left\vert \left(  \operatorname*{Ups}%
\mathbf{v}\right)  \cap\left[  a_{1}+a_{2}\right]  \right\vert =a_{2}$ nor
$\left\vert \left(  \operatorname*{Ups}\mathbf{v}\right)  \cap\left[
b_{1}+b_{2}\right]  \right\vert =b_{2}$. Thus,%
\begin{align}
&  \left(
\begin{array}
[c]{c}%
\text{the number of lattice paths }\mathbf{v}\in\mathcal{L}\text{ passing
through}\\
\text{none of the points }\left(  a_{1},a_{2}\right)  \text{ and }\left(
b_{1},b_{2}\right)
\end{array}
\right) \nonumber\\
&  =\left(
\begin{array}
[c]{c}%
\text{the number of lattice paths }\mathbf{v}\in\mathcal{L}\text{
satisfying}\\
\text{neither }\left\vert \left(  \operatorname*{Ups}\mathbf{v}\right)
\cap\left[  a_{1}+a_{2}\right]  \right\vert =a_{2}\text{ nor }\left\vert
\left(  \operatorname*{Ups}\mathbf{v}\right)  \cap\left[  b_{1}+b_{2}\right]
\right\vert =b_{2}%
\end{array}
\right) \nonumber\\
&  =\left(
\begin{array}
[c]{c}%
\text{the number of }S\in\left\{  c_{2}\text{-element subsets of }\left[
c_{1}+c_{2}\right]  \right\}  \text{ satisfying}\\
\text{neither }\left\vert S\cap\left[  a_{1}+a_{2}\right]  \right\vert
=a_{2}\text{ nor }\left\vert S\cap\left[  b_{1}+b_{2}\right]  \right\vert
=b_{2}%
\end{array}
\right) \nonumber\\
&  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{here, we have substituted }S\text{ for }\operatorname*{Ups}%
\mathbf{v}\text{, since}\\
\operatorname*{Ups}:\mathcal{L}\rightarrow\left\{  c_{2}\text{-element subsets
of }\left[  c_{1}+c_{2}\right]  \right\}  \text{ is a bijection}%
\end{array}
\right) \nonumber\\
&  =\left(
\begin{array}
[c]{c}%
\text{the number of }c_{2}\text{-element subsets }S\text{ of }\left[
c_{1}+c_{2}\right]  \text{ satisfying}\\
\text{neither }\left\vert S\cap\left[  a_{1}+a_{2}\right]  \right\vert
=a_{2}\text{ nor }\left\vert S\cap\left[  b_{1}+b_{2}\right]  \right\vert
=b_{2}%
\end{array}
\right) \nonumber\\
&  =\left(
\begin{array}
[c]{c}%
\text{the number of }c_{2}\text{-element subsets }S\text{ of }\left[
c_{1}+c_{2}\right]  \text{ satisfying}\\
\left\vert S\cap\left[  a_{1}+a_{2}\right]  \right\vert \neq a_{2}\text{ and
}\left\vert S\cap\left[  b_{1}+b_{2}\right]  \right\vert \neq b_{2}%
\end{array}
\right)  . \label{sol.count.lp3.a.8}%
\end{align}
Now, define six integers $a,b,c,A,B,C$ by $a=a_{2}$, $b=b_{2}$, $c=c_{2}$,
$A=a_{1}+a_{2}$, $B=b_{1}+b_{2}$ and $C=c_{1}+c_{2}$. Clearly, $0\leq a\leq
b\leq c$ (since $0\leq a_{2}\leq b_{2}\leq c_{2}$) and $0\leq A\leq B\leq C$
(since $0\leq a_{1}\leq b_{1}\leq c_{1}$ and $0\leq a_{2}\leq b_{2}\leq c_{2}%
$). Thus, our answer to Exercise \ref{exe.count.lp3} \textbf{(b)} yields%
\begin{align*}
&  \left(
\begin{array}
[c]{c}%
\text{the number of }c\text{-element subsets }S\text{ of }\left[  C\right]
\text{ satisfying}\\
\left\vert S\cap\left[  A\right]  \right\vert \neq a\text{ and }\left\vert
S\cap\left[  B\right]  \right\vert \neq b
\end{array}
\right) \\
&  =\dbinom{C}{c}-\dbinom{A}{a}\dbinom{C-A}{c-a}-\dbinom{B}{b}\dbinom
{C-B}{c-b}+\dbinom{A}{a}\dbinom{B-A}{b-a}\dbinom{C-B}{c-b}.
\end{align*}
In view of $a=a_{2}$, $b=b_{2}$, $c=c_{2}$, $A=a_{1}+a_{2}$, $B=b_{1}+b_{2}$
and $C=c_{1}+c_{2}$, this rewrites as%
\begin{align}
&  \left(
\begin{array}
[c]{c}%
\text{the number of }c_{2}\text{-element subsets }S\text{ of }\left[
c_{1}+c_{2}\right]  \text{ satisfying}\\
\left\vert S\cap\left[  a_{1}+a_{2}\right]  \right\vert \neq a_{2}\text{ and
}\left\vert S\cap\left[  b_{1}+b_{2}\right]  \right\vert \neq b_{2}%
\end{array}
\right) \nonumber\\
&  =\dbinom{c_{1}+c_{2}}{c_{2}}-\dbinom{a_{1}+a_{2}}{a_{2}}\dbinom{\left(
c_{1}+c_{2}\right)  -\left(  a_{1}+a_{2}\right)  }{c_{2}-a_{2}}-\dbinom
{b_{1}+b_{2}}{b_{2}}\dbinom{\left(  c_{1}+c_{2}\right)  -\left(  b_{1}%
+b_{2}\right)  }{c_{2}-b_{2}}\nonumber\\
&  \ \ \ \ \ \ \ \ \ \ +\dbinom{a_{1}+a_{2}}{a_{2}}\dbinom{\left(  b_{1}%
+b_{2}\right)  -\left(  a_{1}+a_{2}\right)  }{b_{2}-a_{2}}\dbinom{\left(
c_{1}+c_{2}\right)  -\left(  b_{1}+b_{2}\right)  }{c_{2}-b_{2}}.
\label{sol.count.lp3.a.12}%
\end{align}


Recall that the lattice paths from $\left(  0,0\right)  $ to $\left(
c_{1},c_{2}\right)  $ are precisely the lattice paths $\mathbf{v}%
\in\mathcal{L}$ (because of how we defined $\mathcal{L}$). Hence,%
\begin{align*}
&  \left(
\begin{array}
[c]{c}%
\text{the number of lattice paths from }\left(  0,0\right)  \text{ to }\left(
c_{1},c_{2}\right)  \text{ passing}\\
\text{through none of the points }\left(  a_{1},a_{2}\right)  \text{ and
}\left(  b_{1},b_{2}\right)
\end{array}
\right) \\
&  =\left(
\begin{array}
[c]{c}%
\text{the number of lattice paths }\mathbf{v}\in\mathcal{L}\text{ passing
through}\\
\text{none of the points }\left(  a_{1},a_{2}\right)  \text{ and }\left(
b_{1},b_{2}\right)
\end{array}
\right) \\
&  =\left(
\begin{array}
[c]{c}%
\text{the number of }c_{2}\text{-element subsets }S\text{ of }\left[
c_{1}+c_{2}\right]  \text{ satisfying}\\
\left\vert S\cap\left[  a_{1}+a_{2}\right]  \right\vert \neq a_{2}\text{ and
}\left\vert S\cap\left[  b_{1}+b_{2}\right]  \right\vert \neq b_{2}%
\end{array}
\right) \\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{by (\ref{sol.count.lp3.a.8})}\right) \\
&  =\dbinom{c_{1}+c_{2}}{c_{2}}-\dbinom{a_{1}+a_{2}}{a_{2}}\dbinom{\left(
c_{1}+c_{2}\right)  -\left(  a_{1}+a_{2}\right)  }{c_{2}-a_{2}}-\dbinom
{b_{1}+b_{2}}{b_{2}}\dbinom{\left(  c_{1}+c_{2}\right)  -\left(  b_{1}%
+b_{2}\right)  }{c_{2}-b_{2}}\\
&  \ \ \ \ \ \ \ \ \ \ +\dbinom{a_{1}+a_{2}}{a_{2}}\dbinom{\left(  b_{1}%
+b_{2}\right)  -\left(  a_{1}+a_{2}\right)  }{b_{2}-a_{2}}\dbinom{\left(
c_{1}+c_{2}\right)  -\left(  b_{1}+b_{2}\right)  }{c_{2}-b_{2}}\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{by (\ref{sol.count.lp3.a.12})}\right)  .
\end{align*}

\end{proof}

\subsection{Zig-zag binary strings}

If $n\in\mathbb{N}$, then a \textit{binary }$n$\textit{-string} shall mean an
$n$-tuple of elements of $\left\{  0,1\right\}  $. (For example, $\left(
0,1,1,0,1\right)  $ is a binary $5$-string.)

We say that a binary $n$-string $\left(  a_{1},a_{2},\ldots,a_{n}\right)  $ is
\textit{zig-zag} if it satisfies $a_{1}\leq a_{2}\geq a_{3}\leq a_{4}%
\geq\cdots$ (in other words, $a_{i}\leq a_{i+1}$ for every odd $i\in\left[
n-1\right]  $, and $a_{i}\geq a_{i+1}$ for every even $i\in\left[  n-1\right]
$).

For example, $\left(  0,1,1,1,0,0,0,1\right)  $ is a zig-zag binary
$8$-string, but $\left(  0,1,0,0,1\right)  $ is not.

\begin{exercise}
\label{exe.count.binary-zig}Find a simple expression (no summation signs, only
known functions and sequences) for the number of zig-zag binary $n$-strings
for all $n\in\mathbb{N}$.
\end{exercise}

\begin{proof}
[Solution to Exercise \ref{exe.count.binary-zig} (sketched).]For each
$n\in\mathbb{N}$, let $z_{n}$ be the number of zig-zag binary $n$-strings. We
must then find a simple expression for $z_{n}$.

We claim that%
\begin{equation}
z_{n}=f_{n+2}\ \ \ \ \ \ \ \ \ \ \text{for each }n\in\mathbb{N}\text{.}
\label{sol.count.binary-zig.goal1}%
\end{equation}


In order to prove this, we will first show that
\begin{equation}
z_{n}=z_{n-1}+z_{n-2}\ \ \ \ \ \ \ \ \ \ \text{for each }n>1.
\label{sol.count.binary-zig.goal2}%
\end{equation}


But before we do this, let us find the first few values of $z_{n}$. The only
binary $0$-string is the empty $0$-tuple $\left(  {}\right)  $, and it is
zig-zag. Thus, there exists exactly $1$ zig-zag binary $0$-string; in other
words, $z_{0}=1$. Likewise, $z_{1}=2$, because there are exactly $2$ zig-zag
binary $1$-strings (namely, $\left(  0\right)  $ and $\left(  1\right)  $).
There are $3$ zig-zag binary $2$-strings (namely, $\left(  0,0\right)  $,
$\left(  0,1\right)  $ and $\left(  1,1\right)  $); hence, $z_{2}=3$.

Now, we introduce a \textquotedblleft mirror\textquotedblright\ version of
zig-zag strings: We shall say that a binary $n$-string $\left(  a_{1}%
,a_{2},\ldots,a_{n}\right)  $ is \textit{zag-zig} if it satisfies $a_{1}\geq
a_{2}\leq a_{3}\geq a_{4}\leq\cdots$ (in other words, $a_{i}\geq a_{i+1}$ for
every odd $i\in\left[  n-1\right]  $, and $a_{i}\leq a_{i+1}$ for every even
$i\in\left[  n-1\right]  $). Clearly, for each $n\in\mathbb{N}$, we have%
\begin{align}
&  \left(  \text{the number of zag-zig binary }n\text{-strings}\right)
\nonumber\\
&  =\left(  \text{the number of zig-zag binary }n\text{-strings}\right)  .
\label{sol.count.binary-zig.1}%
\end{align}
(Indeed, there is a bijection $\left\{  \text{zag-zig binary }n\text{-strings}%
\right\}  \rightarrow\left\{  \text{zig-zag binary }n\text{-strings}\right\}
$, which sends every zag-zig binary $n$-string $\left(  a_{1},a_{2}%
,\ldots,a_{n}\right)  $ to the zig-zag binary string $\left(  1-a_{1}%
,1-a_{2},\ldots,1-a_{n}\right)  $.)

Let us now prove (\ref{sol.count.binary-zig.goal2}):

[\textit{Proof of (\ref{sol.count.binary-zig.goal2}):} Let $n>1$ be an
integer. There are two kinds of zig-zag binary $n$-strings: those that start
with a $0$, and those that start with a $1$. Let us count them separately.

A zig-zag binary $n$-string that starts with a $0$ must have the form $\left(
0,a_{2},a_{3},\ldots,a_{n}\right)  $, where $0\leq a_{2}\geq a_{3}\leq
a_{4}\geq a_{5}\leq\cdots$. The inequality $0\leq a_{2}$ is automatically
satisfied, and thus can be omitted; hence, the requirement \textquotedblleft%
$0\leq a_{2}\geq a_{3}\leq a_{4}\geq a_{5}\leq\cdots$\textquotedblright%
\ becomes \textquotedblleft$a_{2}\geq a_{3}\leq a_{4}\geq a_{5}\leq\cdots
$\textquotedblright. In other words, this requirement says that the binary
$\left(  n-1\right)  $-string $\left(  a_{2},a_{3},\ldots,a_{n}\right)  $ is
zag-zig. Hence, the map%
\begin{align*}
\left\{  \text{zig-zag binary }n\text{-strings starting with a }0\right\}   &
\rightarrow\left\{  \text{zag-zig binary }\left(  n-1\right)  \text{-strings}%
\right\}  ,\\
\left(  a_{1},a_{2},\ldots,a_{n}\right)   &  \mapsto\left(  a_{2},a_{3}%
,\ldots,a_{n}\right)
\end{align*}
is well-defined. This map is furthermore a bijection (as can be easily seen:
the inverse map sends each $\left(  a_{2},a_{3},\ldots,a_{n}\right)  $ to
$\left(  0,a_{2},a_{3},\ldots,a_{n}\right)  $). Thus,%
\begin{align}
&  \left\vert \left\{  \text{zig-zag binary }n\text{-strings starting with a
}0\right\}  \right\vert \nonumber\\
&  =\left\vert \left\{  \text{zag-zig binary }\left(  n-1\right)
\text{-strings}\right\}  \right\vert \nonumber\\
&  =\left(  \text{the number of zag-zig binary }\left(  n-1\right)
\text{-strings}\right) \nonumber\\
&  =\left(  \text{the number of zig-zag binary }\left(  n-1\right)
\text{-strings}\right) \nonumber\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{by (\ref{sol.count.binary-zig.1})
(applied to }n-1\text{ instead of }n\text{)}\right) \nonumber\\
&  =z_{n-1} \label{sol.count.binary-zig.1.pf.1}%
\end{align}
(since $z_{n-1}$ is defined as the number of zig-zag binary $\left(
n-1\right)  $-strings).

On the other hand, a zig-zag binary $n$-string that starts with a $1$ must
have the form $\left(  1,a_{2},a_{3},\ldots,a_{n}\right)  $, where $1\leq
a_{2}\geq a_{3}\leq a_{4}\geq a_{5}\leq\cdots$. The inequality $1\leq a_{2}$
is equivalent to $a_{2}=1$ (because $a_{2}\in\left\{  0,1\right\}  $), and
thus a zig-zag binary $n$-string that starts with a $1$ must have the form
$\left(  1,1,a_{3},a_{4},\ldots,a_{n}\right)  $, where $1\leq1\geq a_{3}\leq
a_{4}\geq a_{5}\leq\cdots$. The inequalities $1\leq1\geq a_{3}$ are
automatically satisfied (since $a_{3}\in\left\{  0,1\right\}  $), and thus can
be omitted; hence, the requirement \textquotedblleft$1\leq1\geq a_{3}\leq
a_{4}\geq a_{5}\leq\cdots$\textquotedblright\ becomes \textquotedblleft%
$a_{3}\leq a_{4}\geq a_{5}\leq a_{6}\geq\cdots$\textquotedblright. In other
words, this requirement says that the binary $\left(  n-2\right)  $-string
$\left(  a_{3},a_{4},\ldots,a_{n}\right)  $ is zig-zag. Hence, the map%
\begin{align*}
\left\{  \text{zig-zag binary }n\text{-strings starting with a }1\right\}   &
\rightarrow\left\{  \text{zig-zag binary }\left(  n-2\right)  \text{-strings}%
\right\}  ,\\
\left(  a_{1},a_{2},\ldots,a_{n}\right)   &  \mapsto\left(  a_{3},a_{4}%
,\ldots,a_{n}\right)
\end{align*}
is well-defined. This map is furthermore a bijection (as can be easily seen:
the inverse map sends each $\left(  a_{3},a_{4},\ldots,a_{n}\right)  $ to
$\left(  1,1,a_{3},a_{4},\ldots,a_{n}\right)  $). Thus,%
\begin{align}
&  \left\vert \left\{  \text{zig-zag binary }n\text{-strings starting with a
}1\right\}  \right\vert \nonumber\\
&  =\left\vert \left\{  \text{zig-zag binary }\left(  n-2\right)
\text{-strings}\right\}  \right\vert \nonumber\\
&  =\left(  \text{the number of zig-zag binary }\left(  n-2\right)
\text{-strings}\right) \nonumber\\
&  =z_{n-2} \label{sol.count.binary-zig.1.pf.2}%
\end{align}
(since $z_{n-2}$ is defined as the number of zig-zag binary $\left(
n-2\right)  $-strings).

Now, each zig-zag binary $n$-string either starts with a $0$ or starts with a
$1$ (since its first entry is in $\left\{  0,1\right\}  $). Hence,%
\begin{align*}
&  \left(  \text{the number of zig-zag binary }n\text{-strings}\right)  \\
&  =\underbrace{\left(  \text{the number of zig-zag binary }n\text{-strings
starting with a }0\right)  }_{\substack{=\left\vert \left\{  \text{zig-zag
binary }n\text{-strings starting with a }0\right\}  \right\vert \\=z_{n-1}%
\\\text{(by (\ref{sol.count.binary-zig.1.pf.1}))}}}\\
&  \ \ \ \ \ \ \ \ \ \ +\underbrace{\left(  \text{the number of zig-zag binary
}n\text{-strings starting with a }1\right)  }_{\substack{=\left\vert \left\{
\text{zig-zag binary }n\text{-strings starting with a }1\right\}  \right\vert
\\=z_{n-2}\\\text{(by (\ref{sol.count.binary-zig.1.pf.2}))}}}\\
&  =z_{n-1}+z_{n-2}.
\end{align*}
Now, recall that $z_{n}$ is defined as the number of zig-zag binary
$n$-strings. Thus,%
\[
z_{n}=\left(  \text{the number of zig-zag binary }n\text{-strings}\right)
=z_{n-1}+z_{n-2}.
\]
This proves (\ref{sol.count.binary-zig.goal2}).]

Now, it is straightforward to prove (\ref{sol.count.binary-zig.goal1}) by
strong induction on $n$. The induction step relies on the recurrence equation
(\ref{sol.count.binary-zig.goal2}) (which is exactly the same as the
recurrence equation for the Fibonacci sequence) and on the starting values
$z_{0}=1$ and $z_{1}=2$. We leave the details to the reader. Thus, Exercise
\ref{exe.count.binary-zig} is solved.
\end{proof}

\begin{remark}
Exercise \ref{exe.count.binary-zig} is \cite[Exercise 1.35 \textbf{(e)}%
]{Stanley-EC1}; see the same source for other combinatorial properties of
Fibonacci numbers.

There is also a bijective proof of (\ref{sol.count.binary-zig.goal1}), relying
on (\ref{sol.fib.more-ids.f.lacnum}). The key step is to show that the map%
\begin{align*}
\left\{  \text{zig-zag binary }n\text{-strings}\right\}   &  \rightarrow
\left\{  \text{lacunar subsets of }\left[  n\right]  \right\}  ,\\
\left(  a_{1},a_{2},\ldots,a_{n}\right)   &  \mapsto\left\{  i\in\left[
n\right]  \ \mid\ a_{i}\equiv i\operatorname{mod}2\right\}
\end{align*}
is a bijection. The inverse map sends a lacunar subset $S$ of $\left[
n\right]  $ to the $n$-tuple $\left(  a_{1},a_{2},\ldots,a_{n}\right)  $,
where $a_{i}$ is the remainder of $i+\left[  i\notin S\right]  $ upon division
by $2$. Can you check that these maps are well-defined and mutually inverse?
\end{remark}

\subsection{A binomial identity}

\begin{exercise}
\label{exe.binid.kurlis}Let $n\in\mathbb{N}$. Prove that%
\[
\sum_{k=0}^{n}\dfrac{\left(  -1\right)  ^{k}}{\dbinom{n}{k}}=2\cdot\dfrac
{n+1}{n+2}\left[  n\text{ is even}\right]  .
\]
(Again, we are using the Iverson bracket notation, so $\left[  n\text{ is
even}\right]  $ is $1$ if $n$ is even and $0$ otherwise.)

[\textbf{Hint:} Show that $\dfrac{1}{\dbinom{n}{k}}=\left(  \dfrac{1}%
{\dbinom{n+1}{k}}+\dfrac{1}{\dbinom{n+1}{k+1}}\right)  \dfrac{n+1}{n+2}$ for
each $k\in\left\{  0,1,\ldots,n\right\}  $.]
\end{exercise}

\begin{remark}
The left hand side in Exercise \ref{exe.binid.kurlis} is the alternating sum
of the reciprocals of all (nonzero) binomial coefficients in the $n$-th row of
Pascal's triangle. What about the regular (non-alternating) sum? It appears
that the simplest known formula merely rewrites it as a different (somewhat
simpler) sum:%
\[
\sum_{k=0}^{n}\dfrac{1}{\dbinom{n}{k}}=\dfrac{n+1}{2^{n+1}}\sum_{k=1}%
^{n+1}\dfrac{2^{k}}{k}.
\]
See, e.g., \url{https://math.stackexchange.com/a/481686/} for a proof of this
formula (and also of the fact that the sum on the left tends to $2$ as
$n\rightarrow\infty$). (This formula is also proven in \cite[solution to
Exercise 3.20 \textbf{(b)}]{detnotes}.)
\end{remark}

Let us give a sketch of a solution to Exercise \ref{exe.binid.kurlis}. (The
solution in all its details can be found in \cite[solution to Exercise 3.20
\textbf{(a)}]{detnotes}; but I believe almost all of it is routine for you at
this point.)

Following the hint, we begin by proving the following lemma:

\begin{lemma}
\label{lem.sol.binid.kurlis.rec}Let $n\in\mathbb{N}$. Let $k\in\left\{
0,1,\ldots,n\right\}  $. Then,%
\begin{equation}
\dfrac{1}{\dbinom{n}{k}}=\left(  \dfrac{1}{\dbinom{n+1}{k}}+\dfrac{1}%
{\dbinom{n+1}{k+1}}\right)  \dfrac{n+1}{n+2}.
\label{eq.lem.sol.binid.kurlis.rec.eq}%
\end{equation}
(In particular, all the fractions in this equality are well-defined.)
\end{lemma}

\begin{fns}
\begin{proof}
[Proof of Lemma \ref{lem.sol.binid.kurlis.rec} (sketched).]Because of
$k\in\left\{  0,1,\ldots,n\right\}  $, we have
\begin{equation}
\dbinom{n}{k}=\dfrac{n!}{k!\left(  n-k\right)  !}.
\label{pf.lem.sol.binid.kurlis.rec.1}%
\end{equation}
In particular, $\dbinom{n}{k}\neq0$, so that the fraction $\dfrac{1}%
{\dbinom{n}{k}}$ in (\ref{eq.lem.sol.binid.kurlis.rec.eq}) is well-defined.
But $k\in\left\{  0,1,\ldots,n\right\}  $ also entails that both $k$ and $k+1$
belong to $\left\{  0,1,\ldots,n+1\right\}  $. Therefore,
\begin{equation}
\dbinom{n+1}{k}=\dfrac{\left(  n+1\right)  !}{k!\left(  \left(  n+1\right)
-k\right)  !}=\dfrac{\left(  n+1\right)  !}{k!\left(  n-k+1\right)  !}
\label{pf.lem.sol.binid.kurlis.rec.2}%
\end{equation}
and%
\begin{equation}
\dbinom{n+1}{k+1}=\dfrac{\left(  n+1\right)  !}{\left(  k+1\right)  !\left(
\left(  n+1\right)  -\left(  k+1\right)  \right)  !}=\dfrac{\left(
n+1\right)  !}{\left(  k+1\right)  !\left(  n-k\right)  !}.
\label{pf.lem.sol.binid.kurlis.rec.3}%
\end{equation}
These two numbers are nonzero; thus, the fractions $\dfrac{1}{\dbinom{n+1}{k}%
}$ and $\dfrac{1}{\dbinom{n+1}{k+1}}$ in (\ref{eq.lem.sol.binid.kurlis.rec.eq}%
) are also well-defined. (Of course, so is the fraction $\dfrac{n+1}{n+2}$,
since $n+2\geq2>0$.)

It remains to verify the equality (\ref{eq.lem.sol.binid.kurlis.rec.eq})
itself. But this is easy: The equalities (\ref{pf.lem.sol.binid.kurlis.rec.1}%
), (\ref{pf.lem.sol.binid.kurlis.rec.2}) and
(\ref{pf.lem.sol.binid.kurlis.rec.3}) allow us to rewrite
(\ref{eq.lem.sol.binid.kurlis.rec.eq}) as%
\[
\dfrac{1}{\left(  \dfrac{n!}{k!\left(  n-k\right)  !}\right)  }=\left(
\dfrac{1}{\left(  \dfrac{\left(  n+1\right)  !}{k!\left(  n-k+1\right)
!}\right)  }+\dfrac{1}{\left(  \dfrac{\left(  n+1\right)  !}{\left(
k+1\right)  !\left(  n-k\right)  !}\right)  }\right)  \dfrac{n+1}{n+2}.
\]
In view of $\left(  n+1\right)  !=\left(  n+1\right)  \cdot n!$, $\left(
n-k+1\right)  !=\left(  n-k+1\right)  \cdot\left(  n-k\right)  !$ and $\left(
k+1\right)  !=\left(  k+1\right)  \cdot k!$, this can be further rewritten as%
\[
\dfrac{1}{\left(  \dfrac{n!}{k!\left(  n-k\right)  !}\right)  }=\left(
\dfrac{1}{\left(  \dfrac{\left(  n+1\right)  \cdot n!}{k!\left(  n-k+1\right)
\cdot\left(  n-k\right)  !}\right)  }+\dfrac{1}{\left(  \dfrac{\left(
n+1\right)  \cdot n!}{\left(  k+1\right)  \cdot k!\left(  n-k\right)
!}\right)  }\right)  \dfrac{n+1}{n+2}.
\]
If we multiply both sides of this equality by $\dfrac{n!}{k!\left(
n-k\right)  !}$, we obtain%
\[
1=\left(  \dfrac{1}{\left(  \dfrac{n+1}{n-k+1}\right)  }+\dfrac{1}{\left(
\dfrac{n+1}{k+1}\right)  }\right)  \dfrac{n+1}{n+2}.
\]
But this follows from straightforward computations. Thus, Lemma
\ref{lem.sol.binid.kurlis.rec} is proven.
\end{proof}
\end{fns}

\begin{proof}
[Solution to Exercise \ref{exe.binid.kurlis}.]Let $\lambda=\dfrac{n+1}{n+2}$.
Every $k\in\left\{  0,1,\ldots,n\right\}  $ satisfies%
\begin{align*}
\dfrac{\left(  -1\right)  ^{k}}{\dbinom{n}{k}}  &  =\left(  -1\right)
^{k}\underbrace{\dfrac{1}{\dbinom{n}{k}}}_{\substack{=\left(  \dfrac
{1}{\dbinom{n+1}{k}}+\dfrac{1}{\dbinom{n+1}{k+1}}\right)  \dfrac{n+1}%
{n+2}\\\text{(by (\ref{eq.lem.sol.binid.kurlis.rec.eq}))}}}\\
&  =\left(  -1\right)  ^{k}\left(  \dfrac{1}{\dbinom{n+1}{k}}+\dfrac
{1}{\dbinom{n+1}{k+1}}\right)  \underbrace{\dfrac{n+1}{n+2}}_{=\lambda
}=\left(  -1\right)  ^{k}\left(  \dfrac{1}{\dbinom{n+1}{k}}+\dfrac{1}%
{\dbinom{n+1}{k+1}}\right)  \lambda\\
&  =\dfrac{\left(  -1\right)  ^{k}}{\dbinom{n+1}{k}}\lambda+\underbrace{\dfrac
{\left(  -1\right)  ^{k}}{\dbinom{n+1}{k+1}}}_{\substack{=\dfrac{-\left(
-1\right)  ^{k+1}}{\dbinom{n+1}{k+1}}\\\text{(since }\left(  -1\right)
^{k}=-\left(  -1\right)  ^{k+1}\text{)}}}\lambda\\
&  =\dfrac{\left(  -1\right)  ^{k}}{\dbinom{n+1}{k}}\lambda+\dfrac{-\left(
-1\right)  ^{k+1}}{\dbinom{n+1}{k+1}}\lambda=\dfrac{\left(  -1\right)  ^{k}%
}{\dbinom{n+1}{k}}\lambda-\dfrac{\left(  -1\right)  ^{k+1}}{\dbinom{n+1}{k+1}%
}\lambda.
\end{align*}
Adding up this equality for all $k\in\left\{  0,1,\ldots,n\right\}  $, we
obtain%
\begin{align*}
\sum_{k=0}^{n}\dfrac{\left(  -1\right)  ^{k}}{\dbinom{n}{k}}  &  =\sum
_{k=0}^{n}\left(  \dfrac{\left(  -1\right)  ^{k}}{\dbinom{n+1}{k}}%
\lambda-\dfrac{\left(  -1\right)  ^{k+1}}{\dbinom{n+1}{k+1}}\lambda\right)
=\dfrac{\left(  -1\right)  ^{0}}{\dbinom{n+1}{0}}\lambda-\dfrac{\left(
-1\right)  ^{n+1}}{\dbinom{n+1}{n+1}}\lambda\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{by the telescope principle}\right) \\
&  =\dfrac{1}{1}\lambda-\dfrac{\left(  -1\right)  ^{n+1}}{1}\lambda\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{since }\left(  -1\right)  ^{0}=1\text{
and }\dbinom{n+1}{0}=1\text{ and }\dbinom{n+1}{n+1}=1\right) \\
&  =\lambda-\underbrace{\left(  -1\right)  ^{n+1}}_{=-\left(  -1\right)  ^{n}%
}\lambda=\lambda+\left(  -1\right)  ^{n}\lambda=\underbrace{\left(  1+\left(
-1\right)  ^{n}\right)  }_{\substack{=2\left[  n\text{ is even}\right]
\\\text{(because }1+\left(  -1\right)  ^{n}\\\text{equals }2\text{ when
}n\text{ is even,}\\\text{and equals }0\text{ when }n\text{ is odd)}}%
}\lambda\\
&  =2\left[  n\text{ is even}\right]  \underbrace{\lambda}_{=\dfrac{n+1}{n+2}%
}=2\cdot\dfrac{n+1}{n+2}\left[  n\text{ is even}\right]  .
\end{align*}
This solves Exercise \ref{exe.binid.kurlis}.
\end{proof}

\subsection{Splitting integers into binomial coefficients}

\begin{exercise}
\label{exe.binsys.1}Let $j$ be a positive integer. A $j$\textit{-trail} shall
mean a $j$-tuple $\left(  n_{1},n_{2},\ldots,n_{j}\right)  $ of nonnegative
integers satisfying $n_{1}<n_{2}<\cdots<n_{j}$.

Let $n\in\mathbb{N}$. Prove that there exists a unique $j$-trail $\left(
n_{1},n_{2},\ldots,n_{j}\right)  $ satisfying%
\[
n=\sum_{k=1}^{j}\dbinom{n_{k}}{k}.
\]

\end{exercise}

\begin{example}
For $j=3$, Exercise \ref{exe.binsys.1} says the following: For each
$n\in\mathbb{N}$, there exists a unique $3$-trail $\left(  n_{1},n_{2}%
,n_{3}\right)  $ satisfying%
\[
n=\dbinom{n_{1}}{1}+\dbinom{n_{2}}{2}+\dbinom{n_{3}}{3}.
\]


For example, for $n=0$, this $3$-trail is $\left(  0,1,2\right)  $; for $n=1$,
this $3$-trail is $\left(  0,1,3\right)  $; for $n=5$, this $3$-trail is
$\left(  0,2,4\right)  $ (since $5=\dbinom{0}{1}+\dbinom{2}{2}+\dbinom{4}{3}$).
\end{example}

Exercise \ref{exe.binsys.1} is
\href{https://en.wikipedia.org/wiki/Macaulay_representation_of_an_integer}{a
result of Macaulay}, and appears in various texts on commutative algebra
(e.g., \cite[Lemma A.5.1]{SwaHun06}).

The following solution essentially follows \cite[proof of Lemma A.5.1]%
{SwaHun06}. We begin with proving lemmas:

\begin{lemma}
\label{lem.binsys.1.hockey}Every $n\in\mathbb{N}$ and $q\in\mathbb{Q}$ satisfy%
\[
\sum_{r=0}^{n}\dbinom{r+q}{r}=\dbinom{n+q+1}{n}.
\]

\end{lemma}

Lemma \ref{lem.binsys.1.hockey} is one of the forms of the hockey-stick
identity. It is easily proven by induction on $n$ (see \cite[Exercise 3.3
\textbf{(a)}]{detnotes} for the details).

From now on, we shall be tacitly using the following fact: If $m\in\mathbb{N}$
and $n\in\mathbb{Z}$, then%
\begin{equation}
\dbinom{m}{n}\geq0. \label{eq.binom.nonneg}%
\end{equation}
(This follows, e.g., from the fact that $\dbinom{m}{n}$ is the number of all
$n$-element subsets of $\left[  m\right]  $.)

\begin{lemma}
\label{lem.binsys.1.monoton}Let $k\in\mathbb{N}$.

\textbf{(a)} If $k$ is positive, then $\dbinom{k-1}{k}<\dbinom{k}{k}%
<\dbinom{k+1}{k}<\dbinom{k+2}{k}<\cdots$.

\textbf{(b)} We have $\dbinom{0}{k}\leq\dbinom{1}{k}\leq\dbinom{2}{k}%
\leq\cdots$.

\textbf{(c)} Let $a\in\mathbb{N}$ and $b\in\mathbb{N}$ be such that
$\dbinom{a}{k}>\dbinom{b}{k}$. Then, $a>b$.
\end{lemma}

\begin{fns}
\begin{proof}
[Proof of Lemma \ref{lem.binsys.1.monoton} (sketched).]\textbf{(a)} Assume
that $k$ is positive. We must prove that $\dbinom{k-1}{k}<\dbinom{k}%
{k}<\dbinom{k+1}{k}<\dbinom{k+2}{k}<\cdots$. In other words, we must show that
$\dbinom{a}{k}<\dbinom{a+1}{k}$ for each $a\in\left\{  k-1,k,k+1,\ldots
\right\}  $.

So let $a\in\left\{  k-1,k,k+1,\ldots\right\}  $. Then, $k-1\in\mathbb{N}$
(since $k$ is a positive integer), so that $k-1\geq0$. Also, $a\in\left\{
k-1,k,k+1,\ldots\right\}  $, so that $a\geq k-1$ and therefore $k-1\in\left\{
0,1,\ldots,a\right\}  $ (since $k-1\geq0$). Hence, $\dbinom{a}{k-1}=\dfrac
{a!}{\left(  k-1\right)  !\left(  a-\left(  k-1\right)  \right)  !}>0$. Now,
the recurrence relation of the binomial coefficients yields
\[
\dbinom{a+1}{k}=\underbrace{\dbinom{a}{k-1}}_{>0}+\dbinom{a}{k}>\dbinom{a}%
{k}.
\]
In other words, $\dbinom{a}{k}<\dbinom{a+1}{k}$. This is precisely what we
wanted to prove. Thus, Lemma \ref{lem.binsys.1.monoton} \textbf{(a)} is proven.

\textbf{(b)} We must show that $\dbinom{0}{k}\leq\dbinom{1}{k}\leq\dbinom
{2}{k}\leq\cdots$. In other words, we must show that $\dbinom{a}{k}\leq
\dbinom{a+1}{k}$ for each $a\in\mathbb{N}$.

So let $a\in\mathbb{N}$. We must show that $\dbinom{a}{k}\leq\dbinom{a+1}{k}$.

This is obvious when $k=0$ (because in this case, both $\dbinom{a}{k}$ and
$\dbinom{a+1}{k}$ equal $1$). Hence, we WLOG assume that $k\neq0$. Thus,
$k\geq1$ (since $k\in\mathbb{N}$), so that $k-1\in\mathbb{N}$. Also,
$a\in\mathbb{N}$. Hence, $\dbinom{a}{k-1}\geq0$ (by (\ref{eq.binom.nonneg})).
Now, the recurrence relation of the binomial coefficients yields
\[
\dbinom{a+1}{k}=\underbrace{\dbinom{a}{k-1}}_{\geq0}+\dbinom{a}{k}\geq
\dbinom{a}{k}.
\]
In other words, $\dbinom{a}{k}\leq\dbinom{a+1}{k}$. This is precisely what we
wanted to prove. Thus, Lemma \ref{lem.binsys.1.monoton} \textbf{(b)} is proven.

\textbf{(c)} Assume the contrary. Thus, $a\leq b$.

Lemma \ref{lem.binsys.1.monoton} \textbf{(b)} yields $\dbinom{0}{k}\leq
\dbinom{1}{k}\leq\dbinom{2}{k}\leq\cdots$. In other words, for any
$u\in\mathbb{N}$ and $v\in\mathbb{N}$ satisfying $u\leq v$, we have
$\dbinom{u}{k}\leq\dbinom{v}{k}$. Applying this to $u=a$ and $v=b$, we obtain
$\dbinom{a}{k}\leq\dbinom{b}{k}$ (since $a\leq b$). But this contradicts
$\dbinom{a}{k}>\dbinom{b}{k}$. This contradiction shows that our assumption
was wrong. Thus, Lemma \ref{lem.binsys.1.monoton} \textbf{(c)} is proven.
\end{proof}
\end{fns}

\begin{lemma}
\label{lem.binsys.1.hockey-ineq}Let $g$ be a positive integer. Let
$n_{1},n_{2},\ldots,n_{g}$ be nonnegative integers satisfying $n_{1}%
<n_{2}<\cdots<n_{g}$. Then:

\textbf{(a)} We have $n_{i}\leq n_{g}-g+i$ for each $i\in\left[  g\right]  $.

\textbf{(b)} We have%
\[
\dbinom{n_{g}}{g-1}>\sum_{k=1}^{g-1}\dbinom{n_{k}}{k}.
\]


\textbf{(c)} Let $m_{g}$ be an integer such that $n_{g}<m_{g}$. Then,%
\[
\dbinom{m_{g}}{g}>\sum_{k=1}^{g}\dbinom{n_{k}}{k}.
\]

\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.binsys.1.hockey-ineq} (sketched).]\textbf{(a)} We
have $n_{i}-i\leq n_{i+1}-\left(  i+1\right)  $ for each $i\in\left[
g-1\right]  $\ \ \ \ \footnote{\textit{Proof.} Let $i\in\left[  g-1\right]  $.
Thus, $n_{i}<n_{i+1}$ (since $n_{1}<n_{2}<\cdots<n_{g}$), so that $n_{i}\leq
n_{i+1}-1$ (since $n_{i}$ and $n_{i+1}$ are integers). Subtracting $i$ from
both sides of this inequality, we obtain $n_{i}-i\leq n_{i+1}-1-i=n_{i+1}%
-\left(  i+1\right)  $. Qed.}. In other words,%
\begin{equation}
n_{1}-1\leq n_{2}-2\leq\cdots\leq n_{g}-g.
\label{pf.lem.binsys.1.hockey-ineq.a.1}%
\end{equation}


Now, let $i\in\left[  g\right]  $. Thus, $1\leq i\leq g$, so that $g\geq1$ and
thus $1\in\left[  g\right]  $. Also, $i\leq g$; therefore,
(\ref{pf.lem.binsys.1.hockey-ineq.a.1}) yields $n_{i}-i\leq n_{g}-g$. Hence,
$n_{i}\leq n_{g}-g+i$. This proves Lemma \ref{lem.binsys.1.hockey-ineq}
\textbf{(a)}.

\textbf{(b)} Let $k\in\left[  g-1\right]  $. Thus, Lemma
\ref{lem.binsys.1.hockey-ineq} \textbf{(a)} (applied to $i=k$) yields
$n_{k}\leq n_{g}-g+k$. Thus, $n_{g}-g+k\geq n_{k}\geq0$ (since $n_{k}$ is
nonnegative), so that $n_{g}-g+k\in\mathbb{N}$. Also, $n_{k}\in\mathbb{N}$
(since $n_{k}$ is a nonnegative integer). But Lemma \ref{lem.binsys.1.monoton}
\textbf{(b)} yields $\dbinom{0}{k}\leq\dbinom{1}{k}\leq\dbinom{2}{k}\leq
\cdots$. Hence, $\dbinom{u}{k}\leq\dbinom{v}{k}$ for any $u\in\mathbb{N}$ and
$v\in\mathbb{N}$ satisfying $u\leq v$. Applying this to $u=n_{k}$ and
$v=n_{g}-g+k$, we obtain $\dbinom{n_{k}}{k}\leq\dbinom{n_{g}-g+k}{k}$ (since
$n_{k}\leq n_{g}-g+k$). In other words,%
\begin{equation}
\dbinom{n_{g}-g+k}{k}\geq\dbinom{n_{k}}{k}.
\label{pf.lem.binsys.1.hockey-ineq.b.1}%
\end{equation}


Now, forget that we fixed $k$. We thus have proven the inequality
(\ref{pf.lem.binsys.1.hockey-ineq.b.1}) for each $k\in\left[  g-1\right]  $.

But $g-1\in\mathbb{N}$ (since $g$ is a positive integer). Hence, Lemma
\ref{lem.binsys.1.hockey} (applied to $g-1$ and $n_{g}-g$ instead of $n$ and
$q$) yields%
\[
\sum_{r=0}^{g-1}\dbinom{r+n_{g}-g}{r}=\dbinom{\left(  n_{g}-g\right)  +\left(
g-1\right)  +1}{g-1}=\dbinom{n_{g}}{g-1}%
\]
(since $\left(  n_{g}-g\right)  +\left(  g-1\right)  +1=n_{g}$). Thus,%
\begin{align*}
\dbinom{n_{g}}{g-1}  &  =\sum_{r=0}^{g-1}\dbinom{r+n_{g}-g}{r}=\sum
_{k=0}^{g-1}\dbinom{k+n_{g}-g}{k}\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{here, we have renamed the summation index
}r\text{ as }k\right) \\
&  =\underbrace{\dbinom{0+n_{g}-g}{0}}_{=1}+\sum_{k=1}^{g-1}%
\underbrace{\dbinom{k+n_{g}-g}{k}}_{\substack{=\dbinom{n_{g}-g+k}{k}%
\geq\dbinom{n_{k}}{k}\\\text{(by (\ref{pf.lem.binsys.1.hockey-ineq.b.1}))}%
}}\geq1+\sum_{k=1}^{g-1}\dbinom{n_{k}}{k}>\sum_{k=1}^{g-1}\dbinom{n_{k}}{k}.
\end{align*}
This proves Lemma \ref{lem.binsys.1.hockey-ineq} \textbf{(b)}.

\textbf{(c)} We have $n_{g}<m_{g}$, so that $n_{g}\leq m_{g}-1$ (since $n_{g}$
and $m_{g}$ are integers). Thus, $n_{g}+1\leq m_{g}$.

Lemma \ref{lem.binsys.1.monoton} \textbf{(b)} (applied to $k=g$) yields
$\dbinom{0}{g}\leq\dbinom{1}{g}\leq\dbinom{2}{g}\leq\cdots$. Hence,
$\dbinom{u}{g}\leq\dbinom{v}{g}$ for any $u\in\mathbb{N}$ and $v\in\mathbb{N}$
satisfying $u\leq v$. Applying this to $u=n_{g}+1$ and $v=m_{g}$, we obtain
$\dbinom{n_{g}+1}{g}\leq\dbinom{m_{g}}{g}$ (since $n_{g}+1\leq m_{g}$). Hence,%
\begin{align*}
\dbinom{m_{g}}{g}  &  \geq\dbinom{n_{g}+1}{g}=\underbrace{\dbinom{n_{g}}{g-1}%
}_{\substack{>\sum_{k=1}^{g-1}\dbinom{n_{k}}{k}\\\text{(by Lemma
\ref{lem.binsys.1.hockey-ineq} \textbf{(b)})}}}+\dbinom{n_{g}}{g}\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{by the recurrence relation of the
binomial coefficients}\right) \\
&  >\sum_{k=1}^{g-1}\dbinom{n_{k}}{k}+\dbinom{n_{g}}{g}=\sum_{k=1}^{g}%
\dbinom{n_{k}}{k}.
\end{align*}
This proves Lemma \ref{lem.binsys.1.hockey-ineq} \textbf{(c)}.
\end{proof}

We are now close to the uniqueness part of Exercise \ref{exe.binsys.1}:

\begin{lemma}
\label{lem.binsys.1.uni}Let $j$ be a positive integer. Let $n\in\mathbb{N}$.
Then, there exists \textbf{at most one} $j$-trail $\left(  n_{1},n_{2}%
,\ldots,n_{j}\right)  $ satisfying%
\begin{equation}
n=\sum_{k=1}^{j}\dbinom{n_{k}}{k}. \label{eq.lem.binsys.1.uni.eq}%
\end{equation}

\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.binsys.1.uni} (sketched).]We need to show that any
two $j$-trails $\left(  n_{1},n_{2},\ldots,n_{j}\right)  $ satisfying
(\ref{eq.lem.binsys.1.uni.eq}) are equal.

So let $\left(  a_{1},a_{2},\ldots,a_{j}\right)  $ and $\left(  b_{1}%
,b_{2},\ldots,b_{j}\right)  $ be two such $j$-trails. We must then prove that
$\left(  a_{1},a_{2},\ldots,a_{j}\right)  $ and $\left(  b_{1},b_{2}%
,\ldots,b_{j}\right)  $ are equal.

Assume the contrary. Thus, $\left(  a_{1},a_{2},\ldots,a_{j}\right)
\neq\left(  b_{1},b_{2},\ldots,b_{j}\right)  $. Hence, there exists some
$k\in\left[  j\right]  $ satisfying $a_{k}\neq b_{k}$. Let $g$ be the
\textbf{largest} such $k$. Thus, $g$ is an element of $\left[  j\right]  $
satisfying $a_{g}\neq b_{g}$, but
\begin{equation}
\text{every }k\in\left[  j\right]  \text{ that is larger than }g\text{ must
satisfy }a_{k}=b_{k}. \label{pf.lem.binsys.1.uni.1}%
\end{equation}


We can rewrite (\ref{pf.lem.binsys.1.uni.1}) as follows: Every $k\in\left\{
g+1,g+2,\ldots,j\right\}  $ must satisfy $a_{k}=b_{k}$. Thus,%
\begin{equation}
\text{every }k\in\left\{  g+1,g+2,\ldots,j\right\}  \text{ must satisfy
}\dbinom{a_{k}}{k}=\dbinom{b_{k}}{k}. \label{pf.lem.binsys.1.uni.1b}%
\end{equation}


We know that $\left(  a_{1},a_{2},\ldots,a_{j}\right)  $ is a $j$-trail. In
other words, $\left(  a_{1},a_{2},\ldots,a_{j}\right)  $ is a $j$-tuple of
nonnegative integers satisfying $a_{1}<a_{2}<\cdots<a_{j}$ (because this is
how a $j$-trail was defined). Similarly, $\left(  b_{1},b_{2},\ldots
,b_{j}\right)  $ is a $j$-tuple of nonnegative integers satisfying
$b_{1}<b_{2}<\cdots<b_{j}$.

Also, $\left(  a_{1},a_{2},\ldots,a_{j}\right)  $ is a $j$-trail $\left(
n_{1},n_{2},\ldots,n_{j}\right)  $ satisfying (\ref{eq.lem.binsys.1.uni.eq}).
In other words, $\left(  a_{1},a_{2},\ldots,a_{j}\right)  $ is a $j$-trail and
satisfies%
\begin{equation}
n=\sum_{k=1}^{j}\dbinom{a_{k}}{k}. \label{pf.lem.binsys.1.uni.2a}%
\end{equation}
Similarly, $\left(  b_{1},b_{2},\ldots,b_{j}\right)  $ is a $j$-trail and
satisfies%
\begin{equation}
n=\sum_{k=1}^{j}\dbinom{b_{k}}{k}. \label{pf.lem.binsys.1.uni.2b}%
\end{equation}


We can WLOG assume that $a_{g}\leq b_{g}$ (since otherwise, we can simply
switch the roles of $\left(  a_{1},a_{2},\ldots,a_{j}\right)  $ and $\left(
b_{1},b_{2},\ldots,b_{j}\right)  $). Thus, $a_{g}<b_{g}$ (since $a_{g}\neq
b_{g}$). Now, $a_{1},a_{2},\ldots,a_{g}$ are nonnegative integers satisfying
$a_{1}<a_{2}<\cdots<a_{g}$ (since $a_{1}<a_{2}<\cdots<a_{j}$). Hence, Lemma
\ref{lem.binsys.1.hockey-ineq} \textbf{(c)} (applied to $a_{i}$ and $b_{g}$
instead of $n_{i}$ and $m_{g}$) yields%
\begin{equation}
\dbinom{b_{g}}{g}>\sum_{k=1}^{g}\dbinom{a_{k}}{k}.
\label{pf.lem.binsys.1.uni.4}%
\end{equation}


Now, (\ref{pf.lem.binsys.1.uni.2a}) yields%
\begin{align}
n  &  =\sum_{k=1}^{j}\dbinom{a_{k}}{k}=\sum_{k=1}^{g}\dbinom{a_{k}}{k}%
+\sum_{k=g+1}^{j}\underbrace{\dbinom{a_{k}}{k}}_{\substack{=\dbinom{b_{k}}%
{k}\\\text{(by (\ref{pf.lem.binsys.1.uni.1b}))}}}\nonumber\\
&  =\sum_{k=1}^{g}\dbinom{a_{k}}{k}+\sum_{k=g+1}^{j}\dbinom{b_{k}}{k}.
\label{pf.lem.binsys.1.uni.5}%
\end{align}


On the other hand, (\ref{pf.lem.binsys.1.uni.2b}) yields%
\begin{align*}
n  &  =\sum_{k=1}^{j}\dbinom{b_{k}}{k}=\sum_{k=1}^{g-1}\underbrace{\dbinom
{b_{k}}{k}}_{\substack{\geq0\\\text{(since }b_{k}\text{ and }k\text{
are}\\\text{nonnegative integers)}}}+\sum_{k=g}^{j}\dbinom{b_{k}}{k}%
\geq\underbrace{\sum_{k=1}^{g-1}0}_{=0}+\sum_{k=g}^{j}\dbinom{b_{k}}{k}\\
&  =\sum_{k=g}^{j}\dbinom{b_{k}}{k}=\underbrace{\dbinom{b_{g}}{g}%
}_{\substack{>\sum_{k=1}^{g}\dbinom{a_{k}}{k}\\\text{(by
(\ref{pf.lem.binsys.1.uni.4}))}}}+\sum_{k=g+1}^{j}\dbinom{b_{k}}{k}\\
&  >\sum_{k=1}^{g}\dbinom{a_{k}}{k}+\sum_{k=g+1}^{j}\dbinom{b_{k}}%
{k}=n\ \ \ \ \ \ \ \ \ \ \left(  \text{by (\ref{pf.lem.binsys.1.uni.5}%
)}\right)  .
\end{align*}
This is clearly absurd. Thus, we have found a contradiction. This shows that
our assumption was wrong. Hence, $\left(  a_{1},a_{2},\ldots,a_{j}\right)  $
and $\left(  b_{1},b_{2},\ldots,b_{j}\right)  $ are equal. This proves Lemma
\ref{lem.binsys.1.uni}.
\end{proof}

Next, we need another simple lemma:

\begin{lemma}
\label{lem.binsys.1.outgrow}Let $k$ be a positive integer. Let $n\in
\mathbb{N}$. Then, there exists an $h\in\left\{  k-1,k,k+1,\ldots\right\}  $
such that $\dbinom{h}{k}\leq n<\dbinom{h+1}{k}$.
\end{lemma}

Notice that the $h$ in Lemma \ref{lem.binsys.1.outgrow} is also unique; but we
will not need this.

\begin{proof}
[Proof of Lemma \ref{lem.binsys.1.outgrow} (sketched).]The gist of the proof
is the following: The sequence
\[
\left(  \dbinom{k-1}{k},\dbinom{k}{k},\dbinom{k+1}{k},\dbinom{k+2}{k}%
,\ldots\right)
\]
of nonnegative integers begins with $\dbinom{k-1}{k}=0$, and is strictly
increasing (by Lemma \ref{lem.binsys.1.monoton} \textbf{(a)}); therefore, it
eventually \textquotedblleft outgrows\textquotedblright\ the number $n$. In
other words, $\dbinom{g}{k}>n$ for large enough $g$. Now, if we pick the
smallest such $g$, then $g-1$ will be an $h\in\left\{  k-1,k,k+1,\ldots
\right\}  $ such that $\dbinom{h}{k}\leq n<\dbinom{h+1}{k}$; this proves Lemma
\ref{lem.binsys.1.outgrow}.

\begin{fns}
For the sake of completeness, let me show a more formalized version of this argument.

We have $k-1\in\mathbb{N}$ (since $k$ is a positive integer) and $k-1<k$.
Thus, (\ref{eq.binom.0}) (applied to $k-1$ and $k$ instead of $m$ and $n$)
yields $\dbinom{k-1}{k}=0$.

Lemma \ref{lem.binsys.1.monoton} \textbf{(a)} yields that%
\[
\dbinom{k-1}{k}<\dbinom{k}{k}<\dbinom{k+1}{k}<\dbinom{k+2}{k}<\cdots.
\]
Hence, the elements $\dbinom{k-1}{k},\dbinom{k}{k},\dbinom{k+1}{k}%
,\dbinom{k+2}{k},\ldots$ are distinct. Thus, in particular, the elements
$\dbinom{k-1}{k},\dbinom{k}{k},\dbinom{k+1}{k},\ldots,\dbinom{k+n}{k}$ are
distinct. In other words, the elements $\dbinom{g}{k}$ for $g\in\left\{
k-1,k,k+1,\ldots,k+n\right\}  $ are distinct. Hence,%
\begin{align}
&  \left\vert \left\{  \dbinom{g}{k}\ \mid\ g\in\left\{  k-1,k,k+1,\ldots
,k+n\right\}  \right\}  \right\vert \nonumber\\
&  =\left\vert \left\{  k-1,k,k+1,\ldots,k+n\right\}  \right\vert =n+2>n+1.
\label{pf.lem.binsys.1.outgrow.1}%
\end{align}


Thus, there exists some $g\in\left\{  k-1,k,k+1,\ldots,k+n\right\}  $ such
that $\dbinom{g}{k}\notin\left\{  0,1,\ldots,n\right\}  $%
\ \ \ \ \footnote{\textit{Proof.} Assume the contrary. Thus, there exists no
such $g$. In other words, each $g\in\left\{  k-1,k,k+1,\ldots,k+n\right\}  $
satisfies $\dbinom{g}{k}\in\left\{  0,1,\ldots,n\right\}  $. In other words,
\[
\left\{  \dbinom{g}{k}\ \mid\ g\in\left\{  k-1,k,k+1,\ldots,k+n\right\}
\right\}  \subseteq\left\{  0,1,\ldots,n\right\}  .
\]
Hence,%
\[
\left\vert \left\{  \dbinom{g}{k}\ \mid\ g\in\left\{  k-1,k,k+1,\ldots
,k+n\right\}  \right\}  \right\vert \leq\left\vert \left\{  0,1,\ldots
,n\right\}  \right\vert =n+1.
\]
But this contradicts (\ref{pf.lem.binsys.1.outgrow.1}). This contradiction
shows that our assumption was wrong, qed.}. Let $p$ be the \textbf{smallest}
such $g$. Thus, $p$ is an element of $\left\{  k-1,k,k+1,\ldots,k+n\right\}  $
such that $\dbinom{p}{k}\notin\left\{  0,1,\ldots,n\right\}  $, but each
$g\in\left\{  k-1,k,k+1,\ldots,k+n\right\}  $ that is smaller than $p$ must
satisfy%
\begin{equation}
\dbinom{g}{k}\in\left\{  0,1,\ldots,n\right\}  .
\label{pf.lem.binsys.1.outgrow.3}%
\end{equation}


If we had $p=k-1$, then we would have $\dbinom{p}{k}=\dbinom{k-1}{k}%
=0\in\left\{  0,1,\ldots,n\right\}  $ (since $n\in\mathbb{N}$), which would
contradict $\dbinom{p}{k}\notin\left\{  0,1,\ldots,n\right\}  $. Hence, we
cannot have $p=k-1$. Thus, $p\neq k-1$. Combining this with $p\in\left\{
k-1,k,k+1,\ldots,k+n\right\}  $, we obtain%
\[
p\in\left\{  k-1,k,k+1,\ldots,k+n\right\}  \setminus\left\{  k-1\right\}
=\left\{  k,k+1,\ldots,k+n\right\}  ,
\]
so that $p-1\in\left\{  k-1,k,k+1,\ldots,k+n-1\right\}  \subseteq\left\{
k-1,k,k+1,\ldots,k+n\right\}  $. Since $p-1$ is smaller than $p$, we can thus
apply (\ref{pf.lem.binsys.1.outgrow.3}) to $g=p-1$. As a result, we obtain
$\dbinom{p-1}{k}\in\left\{  0,1,\ldots,n\right\}  $. Hence, $\dbinom{p-1}%
{k}\leq n$.

Also, $p\in\left\{  k-1,k,k+1,\ldots,k+n\right\}  \subseteq\mathbb{N}$ (since
$k-1\in\mathbb{N}$). Hence, $p$ is a nonnegative integer. Now, $\dbinom{p}%
{k}\in\mathbb{N}$ (since both $p$ and $k$ are nonnegative
integers).\ Combining this with $\dbinom{p}{k}\notin\left\{  0,1,\ldots
,n\right\}  $, we obtain $\dbinom{p}{k}\in\mathbb{N}\setminus\left\{
0,1,\ldots,n\right\}  =\left\{  n+1,n+2,n+3,\ldots\right\}  $, so that
$\dbinom{p}{k}\geq n+1>n$. Thus, $n<\dbinom{p}{k}=\dbinom{\left(  p-1\right)
+1}{k}$ (since $p=\left(  p-1\right)  +1$).

Altogether, we now know that $p-1\in\left\{  k-1,k,k+1,\ldots,k+n-1\right\}
\subseteq\left\{  k-1,k,k+1,\ldots\right\}  $ and $\dbinom{p-1}{k}\leq
n<\dbinom{\left(  p-1\right)  +1}{k}$. Hence, there exists an $h\in\left\{
k-1,k,k+1,\ldots\right\}  $ such that $\dbinom{h}{k}\leq n<\dbinom{h+1}{k}$
(namely, $h=p-1$). This proves Lemma \ref{lem.binsys.1.outgrow}.
\end{fns}
\end{proof}

We can now show the existence part of Exercise \ref{exe.binsys.1}:

\begin{lemma}
\label{lem.binsys.1.exi}Let $j$ be a positive integer. Let $n\in\mathbb{N}$.
Then, there exists \textbf{at least one} $j$-trail $\left(  n_{1},n_{2}%
,\ldots,n_{j}\right)  $ satisfying%
\begin{equation}
n=\sum_{k=1}^{j}\dbinom{n_{k}}{k}. \label{eq.lem.binsys.1.exi.eq}%
\end{equation}

\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.binsys.1.exi} (sketched).]We shall prove Lemma
\ref{lem.binsys.1.exi} by induction on $j$:

\textit{Induction base:} For each $n\in\mathbb{N}$, there exists at least one
$1$-trail $\left(  n_{1},n_{2},\ldots,n_{1}\right)  $ satisfying $n=\sum
_{k=1}^{1}\dbinom{n_{k}}{k}$ (namely, the $1$-trail $\left(  n\right)
$).\ \ \ \ \footnote{Indeed, a $1$-trail $\left(  n_{1},n_{2},\ldots
,n_{1}\right)  $ is the same as a $1$-tuple $\left(  n_{1}\right)  $
consisting of a single nonnegative integer $n_{1}$; and this $1$-trail
satisfies $n=\sum_{k=1}^{1}\dbinom{n_{k}}{k}$ if and only if we have $n=n_{1}$
(because $\sum_{k=1}^{1}\dbinom{n_{k}}{k}=\dbinom{n_{1}}{1}=n_{1}$).} In other
words, Lemma \ref{lem.binsys.1.exi} holds for $j=1$. This completes the
induction base.

\textit{Induction step:} Let $i$ be a positive integer. Assume that Lemma
\ref{lem.binsys.1.exi} holds for $j=i$. We must prove that Lemma
\ref{lem.binsys.1.exi} holds for $j=i+1$.

Let $n\in\mathbb{N}$. We are going to show that there is at least one $\left(
i+1\right)  $-trail $\left(  n_{1},n_{2},\ldots,n_{i+1}\right)  $ satisfying
$n=\sum_{k=1}^{i+1}\dbinom{n_{k}}{k}$.

Lemma \ref{lem.binsys.1.outgrow} (applied to $k=i+1$) shows that there exists
an \newline$h\in\left\{  \left(  i+1\right)  -1,i+1,\left(  i+1\right)
+1,\ldots\right\}  $ such that $\dbinom{h}{i+1}\leq n<\dbinom{h+1}{i+1}$.
Consider this $h$.

We have%
\[
h\in\left\{  \left(  i+1\right)  -1,i+1,\left(  i+1\right)  +1,\ldots\right\}
=\left\{  i,i+1,i+2,\ldots\right\}  ,
\]
so that $h\in\mathbb{N}$ and $h\geq i$.

From $\dbinom{h}{i+1}\leq n$, we conclude that $n-\dbinom{h}{i+1}\geq0$, so
that $n-\dbinom{h}{i+1}\in\mathbb{N}$. Thus, we can define an $m\in\mathbb{N}$
by $m=n-\dbinom{h}{i+1}$.

Now, recall that we assumed that Lemma \ref{lem.binsys.1.exi} holds for $j=i$.
Hence, we can apply Lemma \ref{lem.binsys.1.exi} to $i$ and $m$ instead of $j$
and $n$. We thus conclude that there exists \textbf{at least one} $i$-trail
$\left(  n_{1},n_{2},\ldots,n_{i}\right)  $ satisfying%
\begin{equation}
m=\sum_{k=1}^{i}\dbinom{n_{k}}{k}. \label{pf.lem.binsys.1.exi.4}%
\end{equation}
Consider this $i$-trail $\left(  n_{1},n_{2},\ldots,n_{i}\right)  $.

We know that $\left(  n_{1},n_{2},\ldots,n_{i}\right)  $ is an $i$-trail. In
other words, $\left(  n_{1},n_{2},\ldots,n_{i}\right)  $ is an $i$-tuple of
nonnegative integers satisfying $n_{1}<n_{2}<\cdots<n_{i}$ (because this is
how an $i$-trail was defined).

We have $m=n-\dbinom{h}{i+1}$, so that
\[
m+\dbinom{h}{i+1}=n<\dbinom{h+1}{i+1}=\dbinom{h}{i}+\dbinom{h}{i+1}%
\]
(by the recurrence relation of the binomial coefficients). Subtracting
$\dbinom{h}{i+1}$ from this inequality, we obtain $m<\dbinom{h}{i}$. Hence,%
\[
\dbinom{h}{i}>m=\sum_{k=1}^{i}\dbinom{n_{k}}{k}=\sum_{k=1}^{i-1}%
\underbrace{\dbinom{n_{k}}{k}}_{\substack{\geq0\\\text{(since }n_{k}\text{ and
}k\\\text{are nonnegative)}}}+\dbinom{n_{i}}{i}\geq\underbrace{\sum
_{k=1}^{i-1}0}_{=0}+\dbinom{n_{i}}{i}=\dbinom{n_{i}}{i}.
\]
Hence, Lemma \ref{lem.binsys.1.monoton} \textbf{(c)} (applied to $i$, $h$ and
$n_{i}$ instead of $k$, $a$ and $b$) yields $h>n_{i}$. In other words,
$n_{i}<h$.

Now, let us extend the $i$-tuple $\left(  n_{1},n_{2},\ldots,n_{i}\right)  $
to an $\left(  i+1\right)  $-tuple $\left(  n_{1},n_{2},\ldots,n_{i+1}\right)
$ by setting $n_{i+1}=h$. Thus, $n_{i}<h=n_{i+1}$. Combining $n_{1}%
<n_{2}<\cdots<n_{i}$ with $n_{i}<n_{i+1}$, we obtain $n_{1}<n_{2}%
<\cdots<n_{i+1}$. Also, $n_{i+1}=h\in\mathbb{N}$, so that $n_{i+1}$ is a
nonnegative integer.

Also, $n_{1},n_{2},\ldots,n_{i+1}$ are nonnegative integers (since
$n_{1},n_{2},\ldots,n_{i}$ are nonnegative integers, and since $n_{i+1}$ is a
nonnegative integer). Thus, $\left(  n_{1},n_{2},\ldots,n_{i+1}\right)  $ is
an $\left(  i+1\right)  $-tuple of nonnegative integers satisfying
$n_{1}<n_{2}<\cdots<n_{i+1}$. In other words, $\left(  n_{1},n_{2}%
,\ldots,n_{i+1}\right)  $ is an $\left(  i+1\right)  $-trail (by the
definition of an $\left(  i+1\right)  $-trail). Moreover, we have
\[
\sum_{k=1}^{i+1}\dbinom{n_{k}}{k}=\underbrace{\sum_{k=1}^{i}\dbinom{n_{k}}{k}%
}_{\substack{=m\\\text{(by (\ref{pf.lem.binsys.1.exi.4}))}}%
}+\underbrace{\dbinom{n_{i+1}}{i+1}}_{\substack{=\dbinom{h}{i+1}\\\text{(since
}n_{i+1}=h\text{)}}}=m+\dbinom{h}{i+1}=n.
\]
In other words, $n=\sum_{k=1}^{i+1}\dbinom{n_{k}}{k}$.

Thus, we have constructed an $\left(  i+1\right)  $-trail $\left(  n_{1}%
,n_{2},\ldots,n_{i+1}\right)  $ satisfying $n=\sum_{k=1}^{i+1}\dbinom{n_{k}%
}{k}$. Hence, there exists \textbf{at least one} such $\left(  i+1\right)  $-trail.

Now, forget that we fixed $n$. We thus have shown that for each $n\in
\mathbb{N}$, there exists \textbf{at least one} $\left(  i+1\right)  $-trail
$\left(  n_{1},n_{2},\ldots,n_{i+1}\right)  $ satisfying $n=\sum_{k=1}%
^{i+1}\dbinom{n_{k}}{k}$. In other words, Lemma \ref{lem.binsys.1.exi} holds
for $j=i+1$. This completes the induction step. Thus, Lemma
\ref{lem.binsys.1.exi} is proven by induction.
\end{proof}

\begin{proof}
[Solution to Exercise \ref{exe.binsys.1} (sketched).]Lemma
\ref{lem.binsys.1.exi} shows that there exists \textbf{at least one} $j$-trail
$\left(  n_{1},n_{2},\ldots,n_{j}\right)  $ satisfying%
\[
n=\sum_{k=1}^{j}\dbinom{n_{k}}{k}.
\]
Moreover, this $j$-trail is unique, according to Lemma \ref{lem.binsys.1.uni}.
Hence, Exercise \ref{exe.binsys.1} is solved.
\end{proof}

\begin{thebibliography}{9999999999999}                                                                                    %


\bibitem[BenQui03]{BenQui03}Arthur T. Benjamin and Jennifer J. Quinn,
\textit{Proofs that Really Count: The Art of Combinatorial Proof}, The
Mathematical Association of America, 2003.

\bibitem[BenQui04]{BenQui-fib}%
\href{https://www.math.hmc.edu/~benjamin/papers/bama.pdf}{Arthur T. Benjamin
and Jennifer J. Quinn, \textit{Proofs that Really Count: The Magic of
Fibonacci Numbers and More}, Mathematical Adventures for Students and
Amateurs, (David F. Hayes and Tatiana Shubin, editors), Spectrum Series of
MAA, pp. 83--98, 2004.}

\bibitem[Galvin17]{Galvin}David Galvin, \textit{Basic discrete mathematics},
13 December 2017.\newline\url{http://www.cip.ifi.lmu.de/~grinberg/t/17f/60610lectures2017-Galvin.pdf}

\bibitem[Grinbe10]{gri-zeck}Darij Grinberg, \textit{Zeckendorf family
identities generalized}, version 24 February 2018.\newline%
\url{http://www.cip.ifi.lmu.de/~grinberg/zeckendorfBRIEF.pdf}\newline(Detailed
version: \url{http://www.cip.ifi.lmu.de/~grinberg/zeckendorfLONG.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[Fall2017-HW1s]{fall2017-hw1s}Darij Grinberg, \textit{Math 4707 \&
Math 4990 Fall 2017 (Darij Grinberg): homework set 1 with solutions.}\newline\url{http://www.cip.ifi.lmu.de/~grinberg/t/17f/hw1s.pdf}

\bibitem[Stan11]{Stanley-EC1}Richard Stanley, \textit{Enumerative
Combinatorics, volume 1}, Second edition, version of 15 July 2011. Available
at \url{http://math.mit.edu/~rstan/ec/} .

\bibitem[SwaHun06]{SwaHun06}Irena Swanson and Craig Huneke, \textit{Integral
Closure of Ideals, Rings, and Modules}, London Mathematical Society Lecture
Note Series \#336, Cambridge University Press, Cambridge, 2006.\newline\url{http://people.reed.edu/~iswanson/book/SwansonHuneke.pdf}

\bibitem[WooZei09]{WooZei}Philip Matchett Wood, Doron Zeilberger, \textit{A
translation method for finding combinatorial bijections}, Annals of
Combinatorics \textbf{13} (2009), pp. 383--402. \newline\url{http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/trans-method.html}
\end{thebibliography}


\end{document}