\documentclass[paper=a4, fontsize=12pt]{scrartcl}%
\usepackage[T1]{fontenc}
\usepackage[english]{babel}
\usepackage{amsmath,amsfonts,amsthm,amssymb}
\usepackage{mathrsfs}
\usepackage{sectsty}
\usepackage{hyperref}
\usepackage{graphicx}
\usepackage{framed}
\usepackage{ifthen}
\usepackage{lastpage}
\usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage}
\usepackage[height=10in,a4paper,hmargin={1in,0.8in}]{geometry}
\usepackage[usenames,dvipsnames]{xcolor}
\usepackage{tikz}
\usepackage{verbatim}
\usepackage{tabls}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}%
\setcounter{MaxMatrixCols}{30}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Sunday, November 24, 2019 23:50:43}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%BeginMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
%EndMSIPreambleData
\allsectionsfont{\centering \normalfont\scshape}
\setlength\parindent{20pt}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\Z}[1]{\mathbb{Z}/#1\mathbb{Z}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\lcm}{\operatorname{lcm}}
\newcommand{\rev}{\operatorname{rev}}
\newcommand{\Fix}{\operatorname{Fix}}
\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{\lf}[2]{#1^{\underline{#2}}}
\newcommand{\underbrack}[2]{\underbrace{#1}_{\substack{#2}}}
\newcommand{\horrule}[1]{\rule{\linewidth}{#1}}
\newcommand{\nnn}{\nonumber\\}
\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}
\newtheoremstyle{plainsl}
{8pt plus 2pt minus 4pt}
{8pt plus 2pt minus 4pt}
{\slshape}
{0pt}
{\bfseries}
{.}
{5pt plus 1pt minus 1pt}
{}
\theoremstyle{plainsl}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{exercise}[theorem]{Exercise}
\newtheorem{examples}[theorem]{Examples}
\newtheorem{algorithm}[theorem]{Algorithm}
\newtheorem{question}[theorem]{Question}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newenvironment{statement}{\begin{quote}}{\end{quote}}
\newenvironment{fineprint}{\begin{small}}{\end{small}}
\newcommand{\myname}{Darij Grinberg}
\newcommand{\mymail}{darij.grinberg@drexel.edu}
\newcommand{\psetnumber}{2}
\iffalse
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\newenvironment{question}[1][Question]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\newenvironment{teachingnote}[1][Teaching note]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\fi
\ihead{Solutions to midterm \#\psetnumber}
\ohead{page \thepage\ of \pageref{LastPage}}
\ifoot{\myname}
\ofoot{\mymail}
\begin{document}

\title{ \normalfont {\normalsize \textsc{Drexel University, Department of
Mathematics} }\\[25pt] \rule{\linewidth}{0.5pt} \\[0.4cm] {\huge Math 222: Enumerative Combinatorics, }\\Fall 2019: Midterm 2\\\rule{\linewidth}{2pt} \\[0.5cm] }
\author{Darij Grinberg}
\maketitle

%----------------------------------------------------------------------------------------
%	EXERCISE 1
%----------------------------------------------------------------------------------------
\rule{\linewidth}{0.3pt} \\[0.4cm]

\section{Exercise 1}

\subsection{Problem}

Let $u \in\mathbb{R}$ and $n \in\mathbb{N}$. Prove that
\begin{equation}
\sum_{i=0}^{n} \dbinom{2i-u}{i} \dbinom{2 \left(  n-i \right)  + u}{n-i} =
4^{n} . \label{eq.exe.vander-1/2.gen-u.claim}%
\end{equation}


\subsection{Remark}

For $u=0$, this simplifies to
\begin{equation}
\sum_{i=0}^{n}\dbinom{2i}{i}\dbinom{2\left(  n-i\right)  }{n-i}=4^{n},
\label{eq.exe.vander-1/2.gen-u.u=0}%
\end{equation}
a famous identity which is probably easiest to prove by applying the
Chu--Vandermonde identity to $x=-1/2$ and $y=-1/2$ (see \cite[solution to
Exercise 3 \textbf{(b)}]{18f-hw3s} or \cite[solution to Exercise 3.23
\textbf{(a)}]{detnotes} for details). But to my knowledge, the more general
equality \eqref{eq.exe.vander-1/2.gen-u.claim} resists this clever trick.
Instead, proceed as follows: Rewrite $\dbinom{2i-u}{i}$ using upper negation,
and rewrite $\dbinom{2\left(  n-i\right)  +u}{n-i}$ as $\sum_{k=0}%
^{n-i}\dbinom{2n+1}{k}\dbinom{u-1-2i}{n-i-k}$ using Chu--Vandermonde. Then use
trinomial revision to turn $\dbinom{u-i-1}{i}\dbinom{u-1-2i}{n-i-k}$ into
$\dbinom{u-i-1}{n-k}\dbinom{n-k}{i}$. Does the result remind you of anything?

\subsection{Solution}

The exercise is the main result of the preprint \cite{DuaOli13} by Duarte and
de Oliveira; the following solution is taken (essentially unchanged) from this preprint.

Forget that we fixed $u$ and $n$. Let us state a few lemmas first. We begin
with the trinomial revision formula (\cite[Proposition 1.3.35]{notes}):

\begin{proposition}
[Trinomial revision formula]\label{prop.binom.trin-rev}Let $n,a,b\in
\mathbb{R}$. Then,%
\[
\dbinom{n}{a}\dbinom{a}{b}=\dbinom{n}{b}\dbinom{n-b}{a-b}.
\]

\end{proposition}

The next fact is a basic property of binomial coefficients (\cite[Proposition
1.3.6]{notes}):

\begin{proposition}
\label{prop.binom.0}Let $n\in\mathbb{N}$ and $k\in\mathbb{R}$ be such that
$k>n$. Then, $\dbinom{n}{k}=0$.
\end{proposition}

Next, we recall the Vandermonde convolution formula (\cite[Theorem
2.6.1]{notes}):

\begin{theorem}
[The Vandermonde convolution, or the Chu--Vandermonde identity]%
\label{thm.binom.vanderRR}Let $n\in\mathbb{N}$ and $x,y\in\mathbb{R}$. Then,%
\begin{align}
\dbinom{x+y}{n}  &  =\sum_{k=0}^{n}\dbinom{x}{k}\dbinom{y}{n-k}%
\label{eq.thm.binom.vanderRR.k=0-n}\\
&  =\sum_{k}\dbinom{x}{k}\dbinom{y}{n-k}. \label{eq.thm.binom.vanderRR.all-k}%
\end{align}
Here, the summation sign \textquotedblleft$\sum\limits_{k}$\textquotedblright%
\ on the right hand side of (\ref{eq.thm.binom.vanderRR.all-k}) means a sum
over all $k\in\mathbb{Z}$. (We are thus implicitly claiming that this sum over
all $k\in\mathbb{Z}$ is well-defined, i.e., that it has only finitely many
nonzero addends.)
\end{theorem}

We will also need the upper negation formula (\cite[Proposition 1.3.7]{notes}):

\begin{proposition}
[Upper negation formula]\label{prop.binom.upneg}Let $n\in\mathbb{R}$ and
$k\in\mathbb{Z}$. Then,%
\[
\dbinom{-n}{k}=\left(  -1\right)  ^{k}\dbinom{n+k-1}{k}.
\]

\end{proposition}

Furthermore, we shall need the result of \cite[Exercise 1]{19f-mt1s}:

\begin{proposition}
\label{prop.exe.binom.half-sum-of-k-row} Let $n\in\mathbb{N}$. Then,
\[
\sum_{k=0}^{n}\dbinom{2n+1}{k}=4^{n}.
\]

\end{proposition}

Finally, we shall use the result of \cite[Exercise 6]{19f-hw3s}:

\begin{proposition}
\label{prop.exe.binom.dividiff-x-iCq} Let $p\in\mathbb{N}$ and $q\in
\mathbb{N}$. Then,%
\[
\sum_{i=0}^{p}\left(  -1\right)  ^{i}\dbinom{p}{i}\dbinom{x-i}{q}=\dbinom
{x-p}{q-p}\qquad\text{for all $x\in\mathbb{R}$.}%
\]

\end{proposition}

More precisely, we will use the following consequence of this proposition:

\begin{corollary}
\label{cor.exe.binom.dividiff-x-iCq.1} Let $p\in\mathbb{N}$. Then,%
\[
\sum_{i=0}^{p}\left(  -1\right)  ^{i}\dbinom{p}{i}\dbinom{x-i}{p}%
=1\qquad\text{for all $x\in\mathbb{R}$.}%
\]

\end{corollary}

\begin{proof}
[Proof of Corollary \ref{cor.exe.binom.dividiff-x-iCq.1}.]Proposition
\ref{prop.exe.binom.dividiff-x-iCq} (applied to $q=p$) yields%
\begin{align*}
\sum_{i=0}^{p}\left(  -1\right)  ^{i}\dbinom{p}{i}\dbinom{x-i}{p}  &
=\dbinom{x-p}{p-p}=\dbinom{x-p}{0}\qquad\left(  \text{since }p-p=0\right) \\
&  =1\qquad\left(  \text{since }\dbinom{n}{0}=1\text{ for each }n\in
\mathbb{R}\right)  .
\end{align*}
This proves Corollary \ref{cor.exe.binom.dividiff-x-iCq.1}.
\end{proof}

Note that Corollary \ref{cor.exe.binom.dividiff-x-iCq.1} is precisely
\cite[(2)]{DuaOli13}. It is also a particular case of \cite[Exercise
5]{18f-hw3s} (applied to $j=p$, $s=1$ and $r=x$). (This suggests that
\cite[Exercise 5]{18f-hw3s} and Proposition
\ref{prop.exe.binom.dividiff-x-iCq} might have a common generalization; but I
have so far been unable to find one.)

\bigskip

Now, let us solve the exercise. Let $u\in\mathbb{R}$ and $n\in\mathbb{N}$. Let
$i\in\left\{  0,1,\ldots,n\right\}  $. Proposition \ref{prop.binom.upneg}
(applied to $u-2i$ and $i$ instead of $n$ and $k$) yields%
\[
\dbinom{-\left(  u-2i\right)  }{i}=\left(  -1\right)  ^{i}\dbinom{\left(
u-2i\right)  +i-1}{i}=\left(  -1\right)  ^{i}\dbinom{u-i-1}{i}%
\]
(since $\left(  u-2i\right)  +i-1=u-i-1$). In view of $-\left(  u-2i\right)
=2i-u$, this rewrites as%
\begin{equation}
\dbinom{2i-u}{i}=\left(  -1\right)  ^{i}\dbinom{u-i-1}{i}.
\label{sol.vander-1/2.gen-u.1}%
\end{equation}


Furthermore, $i\in\left\{  0,1,\ldots,n\right\}  $, so that $n-i\in\left\{
0,1,\ldots,n\right\}  \subseteq\mathbb{N}$. Hence,
(\ref{eq.thm.binom.vanderRR.k=0-n}) (applied to $2n+1$, $u-1-2i$ and $n-i$
instead of $x$, $y$ and $n$) yields%
\[
\dbinom{\left(  2n+1\right)  +\left(  u-1-2i\right)  }{n-i}=\sum_{k=0}%
^{n-i}\dbinom{2n+1}{k}\dbinom{u-1-2i}{n-i-k}.
\]
In view of $\left(  2n+1\right)  +\left(  u-1-2i\right)  =2\left(  n-i\right)
+u$, this rewrites as%
\begin{equation}
\dbinom{2\left(  n-i\right)  +u}{n-i}=\sum_{k=0}^{n-i}\dbinom{2n+1}{k}%
\dbinom{u-1-2i}{n-i-k}. \label{sol.vander-1/2.gen-u.2}%
\end{equation}


We want to replace the upper bound $n-i$ of this sum by $n$. To do so, we make
sure that this does not change the sum: In fact, recall that $n-i\in\left\{
0,1,\ldots,n\right\}  $. Hence, we can split the sum $\sum_{k=0}^{n}%
\dbinom{2n+1}{k}\dbinom{u-1-2i}{n-i-k}$ at $k=n-i$. We thus obtain%
\begin{align*}
&  \sum_{k=0}^{n}\dbinom{2n+1}{k}\dbinom{u-1-2i}{n-i-k}\\
&  =\sum_{k=0}^{n-i}\dbinom{2n+1}{k}\dbinom{u-1-2i}{n-i-k}+\sum_{k=n-i+1}%
^{n}\dbinom{2n+1}{k}\underbrace{\dbinom{u-1-2i}{n-i-k}}%
_{\substack{=0\\\text{(by the definition of binomial coefficients,}%
\\\text{since }n-i-k\notin\mathbb{N}\text{ (because }k\geq
n-i+1>n-i\\\text{and thus }n-i-k<0\text{ and thus }n-i-k\notin\mathbb{N}%
\text{))}}}\\
&  =\sum_{k=0}^{n-i}\dbinom{2n+1}{k}\dbinom{u-1-2i}{n-i-k}+\underbrace{\sum
_{k=n-i+1}^{n}\dbinom{2n+1}{k}0}_{=0}\\
&  =\sum_{k=0}^{n-i}\dbinom{2n+1}{k}\dbinom{u-1-2i}{n-i-k}.
\end{align*}
Comparing this with \eqref{sol.vander-1/2.gen-u.2}, we obtain%
\begin{equation}
\dbinom{2\left(  n-i\right)  +u}{n-i}=\sum_{k=0}^{n}\dbinom{2n+1}{k}%
\dbinom{u-1-2i}{n-i-k}. \label{sol.vander-1/2.gen-u.2b}%
\end{equation}


Furthermore, for each $k\in\mathbb{Z}$, we have%
\begin{align}
\dbinom{u-i-1}{n-k}\dbinom{n-k}{i}  &  =\dbinom{u-i-1}{i}\dbinom{\left(
u-i-1\right)  -i}{\left(  n-k\right)  -i}\nonumber\\
&  \qquad\qquad\left(
\begin{array}
[c]{c}%
\text{by Proposition \ref{prop.binom.trin-rev} (applied to }u-1-k\text{,
}n-k\text{ and }i\\
\text{instead of }n\text{, }a\text{ and }b\text{)}%
\end{array}
\right) \nonumber\\
&  =\dbinom{u-i-1}{i}\dbinom{u-1-2i}{n-i-k} \label{sol.vander-1/2.gen-u.3}%
\end{align}
(since $\left(  u-i-1\right)  -i=u-1-2i$ and $\left(  n-k\right)  -i=n-i-k$).

Now,
\begin{align}
&  \dbinom{2i-u}{i}\underbrace{\dbinom{2\left(  n-i\right)  +u}{n-i}%
}_{\substack{=\sum_{k=0}^{n}\dbinom{2n+1}{k}\dbinom{u-1-2i}{n-i-k}\\\text{(by
\eqref{sol.vander-1/2.gen-u.2b})}}}\nonumber\\
&  =\dbinom{2i-u}{i}\sum_{k=0}^{n}\dbinom{2n+1}{k}\dbinom{u-1-2i}%
{n-i-k}\nonumber\\
&  =\sum_{k=0}^{n}\underbrace{\dbinom{2i-u}{i}}_{\substack{=\left(  -1\right)
^{i}\dbinom{u-i-1}{i}\\\text{(by \eqref{sol.vander-1/2.gen-u.1})}}%
}\dbinom{2n+1}{k}\dbinom{u-1-2i}{n-i-k}\nonumber\\
&  =\sum_{k=0}^{n}\left(  -1\right)  ^{i}\underbrace{\dbinom{u-i-1}{i}%
\dbinom{2n+1}{k}}_{=\dbinom{2n+1}{k}\dbinom{u-i-1}{i}}\dbinom{u-1-2i}%
{n-i-k}\nonumber\\
&  =\sum_{k=0}^{n}\underbrace{\left(  -1\right)  ^{i}\dbinom{2n+1}{k}%
}_{=\dbinom{2n+1}{k}\left(  -1\right)  ^{i}}\ \ \underbrace{\dbinom{u-i-1}%
{i}\dbinom{u-1-2i}{n-i-k}}_{\substack{=\dbinom{u-i-1}{n-k}\dbinom{n-k}%
{i}\\\text{(by \eqref{sol.vander-1/2.gen-u.3})}}}\nonumber\\
&  =\sum_{k=0}^{n}\dbinom{2n+1}{k}\left(  -1\right)  ^{i}\dbinom{u-i-1}%
{n-k}\dbinom{n-k}{i}. \label{sol.vander-1/2.gen-u.5}%
\end{align}


Now, forget that we fixed $i$. We thus have proved
\eqref{sol.vander-1/2.gen-u.5} for each $i\in\left\{  0,1,\ldots,n\right\}  $.

Now,%
\begin{align}
&  \sum_{i=0}^{n}\underbrace{\dbinom{2i-u}{i}\dbinom{2\left(  n-i\right)
+u}{n-i}}_{\substack{=\sum_{k=0}^{n}\dbinom{2n+1}{k}\left(  -1\right)
^{i}\dbinom{u-i-1}{n-k}\dbinom{n-k}{i}.\\\text{(by
\eqref{sol.vander-1/2.gen-u.5})}}}\nonumber\\
&  =\underbrace{\sum_{i=0}^{n}\sum_{k=0}^{n}}_{=\sum_{k=0}^{n}\sum_{i=0}^{n}%
}\dbinom{2n+1}{k}\left(  -1\right)  ^{i}\dbinom{u-i-1}{n-k}\dbinom{n-k}%
{i}\nonumber\\
&  =\sum_{k=0}^{n}\underbrace{\sum_{i=0}^{n}\dbinom{2n+1}{k}\left(  -1\right)
^{i}\dbinom{u-i-1}{n-k}\dbinom{n-k}{i}}_{=\dbinom{2n+1}{k}\sum_{i=0}%
^{n}\left(  -1\right)  ^{i}\dbinom{u-i-1}{n-k}\dbinom{n-k}{i}}\nonumber\\
&  =\sum_{k=0}^{n}\dbinom{2n+1}{k}\sum_{i=0}^{n}\left(  -1\right)  ^{i}%
\dbinom{u-i-1}{n-k}\dbinom{n-k}{i}. \label{sol.vander-1/2.gen-u.8}%
\end{align}


Now, fix $k\in\left\{  0,1,\ldots,n\right\}  $. Then, $n-k\in\left\{
0,1,\ldots,n\right\}  \subseteq\mathbb{N}$. Now, we can split the sum
$\sum_{i=0}^{n}\left(  -1\right)  ^{i}\dbinom{u-i-1}{n-k}\dbinom{n-k}{i}$ at
$i=n-k$ (since $n-k\in\left\{  0,1,\ldots,n\right\}  $). We thus obtain
\begin{align}
&  \sum_{i=0}^{n}\left(  -1\right)  ^{i}\dbinom{u-i-1}{n-k}\dbinom{n-k}%
{i}\nonumber\\
&  =\sum_{i=0}^{n-k}\left(  -1\right)  ^{i}\underbrace{\dbinom{u-i-1}%
{n-k}\dbinom{n-k}{i}}_{\substack{=\dbinom{n-k}{i}\dbinom{u-i-1}{n-k}%
\\=\dbinom{n-k}{i}\dbinom{\left(  u-1\right)  -i}{n-k}\\\text{(since
}u-i-1=\left(  u-1\right)  -i\text{)}}}+\sum_{i=n-k+1}^{n}\left(  -1\right)
^{i}\dbinom{u-i-1}{n-k}\underbrace{\dbinom{n-k}{i}}_{\substack{=0\\\text{(by
Proposition \ref{prop.binom.0},}\\\text{applied to }n-k\text{ and
}i\\\text{instead of }n\text{ and }k\\\text{(since }i\geq n-k+1>n-k\text{))}%
}}\nonumber\\
&  =\sum_{i=0}^{n-k}\left(  -1\right)  ^{i}\dbinom{n-k}{i}\dbinom{\left(
u-1\right)  -i}{n-k}+\underbrace{\sum_{i=n-k+1}^{n}\left(  -1\right)
^{i}\dbinom{u-i-1}{n-k}0}_{=0}\nonumber\\
&  =\sum_{i=0}^{n-k}\left(  -1\right)  ^{i}\dbinom{n-k}{i}\dbinom{\left(
u-1\right)  -i}{n-k}=1 \label{sol.vander-1/2.gen-u.7}%
\end{align}
(by Corollary \ref{cor.exe.binom.dividiff-x-iCq.1}, applied to $p=n-k$ and
$x=u-1$).

Forget that we fixed $k$. We thus have proved \eqref{sol.vander-1/2.gen-u.7}
for each $k\in\left\{  0,1,\ldots,n\right\}  $. Hence,
\eqref{sol.vander-1/2.gen-u.8} becomes%
\begin{align*}
&  \sum_{i=0}^{n}\dbinom{2i-u}{i}\dbinom{2\left(  n-i\right)  +u}{n-i}\\
&  =\sum_{k=0}^{n}\dbinom{2n+1}{k}\underbrace{\sum_{i=0}^{n}\left(  -1\right)
^{i}\dbinom{u-i-1}{n-k}\dbinom{n-k}{i}}_{\substack{=1\\\text{(by
\eqref{sol.vander-1/2.gen-u.7})}}}=\sum_{k=0}^{n}\dbinom{2n+1}{k}=4^{n}%
\end{align*}
(by Proposition \ref{prop.exe.binom.half-sum-of-k-row}). This solves the exercise.

%----------------------------------------------------------------------------------------
%	EXERCISE 2
%----------------------------------------------------------------------------------------
\rule{\linewidth}{0.3pt} \\[0.4cm]

\section{Exercise 2}

\subsection{Problem}

Let $S$ be a finite set. Let $X$ and $Y$ be two \textbf{distinct} subsets of
$S$. Prove that
\[
\sum_{I\subseteq S}\left(  -1\right)  ^{\left\vert X\cap I\right\vert
+\left\vert Y\cap I\right\vert }=0.
\]


\subsection{Remark}

This exercise is Proposition 3 from my math.stackexchange post%
\[
\text{\url{https://math.stackexchange.com/a/1361250/}\ \ .}%
\]


Note that if we set $X=\varnothing$ and $Y=S$, then the claim of the exercise
readily simplifies to%
\[
\sum_{I\subseteq S}\left(  -1\right)  ^{\left\vert I\right\vert }%
=0\qquad\text{if }S\neq\varnothing.
\]
This is precisely \cite[Proposition 2.9.10]{notes} (except for the trivial
case when $S=\varnothing$). Thus, the exercise generalizes \cite[Proposition
2.9.10]{notes}.

\subsection{Solution}

We notice that the subsets $X$ and $Y$ play symmetric roles in the exercise;
i.e., if we swap $X$ with $Y$, then the claim of the exercise does not change
(since $\left\vert Y\cap I\right\vert +\left\vert X\cap I\right\vert
=\left\vert X\cap I\right\vert +\left\vert Y\cap I\right\vert $).

If both statements $X\subseteq Y$ and $Y\subseteq X$ were true, then we would
have $X=Y$, which would contradict the assumption that $X$ and $Y$ are
distinct. Thus, the statements $X\subseteq Y$ and $Y\subseteq X$ cannot both
be true. Hence, at least one of them is false. We WLOG assume that the first
one is false (because if the second one is false, then we can simply swap $X$
with $Y$\ \ \ \ \footnote{because if we swap $X$ with $Y$, then the claim of
the exercise does not change}, and arrive in a situation where the first one
is false). In other words, the statement $X\subseteq Y$ is false. In other
words, we have $X\not \subseteq Y$. In other words, there exists some $g\in X$
such that $g\notin Y$. Consider this $g$. Clearly, $g\in X\subseteq S$.

The rest of this solution proceeds very similarly to \cite[Second proof of
Proposition 2.9.10]{notes}.

Each subset $I$ of $S$ must satisfy either $g\in I$ or $g\notin I$ (but not
both at the same time). Hence, we can split the sum $\sum_{I\subseteq
S}\left(  -1\right)  ^{\left\vert X\cap I\right\vert +\left\vert Y\cap
I\right\vert }$ as follows:%
\begin{equation}
\sum_{I\subseteq S}\left(  -1\right)  ^{\left\vert X\cap I\right\vert
+\left\vert Y\cap I\right\vert }=\sum_{\substack{I\subseteq S;\\g\in
I}}\left(  -1\right)  ^{\left\vert X\cap I\right\vert +\left\vert Y\cap
I\right\vert }+\sum_{\substack{I\subseteq S;\\g\notin I}}\left(  -1\right)
^{\left\vert X\cap I\right\vert +\left\vert Y\cap I\right\vert }.
\label{sol.DIE.destructXY.1}%
\end{equation}


Each subset $J$ of $S$ satisfies $J\cup\left\{  g\right\}  \subseteq S$
(because $g\in S$) and $g\in J\cup\left\{  g\right\}  $ (obviously). Thus, the
map\footnote{The notation \textquotedblleft$\left\{  I\subseteq S\ \mid
\ g\notin I\right\}  $\textquotedblright\ means \textquotedblleft the set of
all subsets $I$ of $S$ satisfying $g\notin I$\textquotedblright. Similarly,
the notation \textquotedblleft$\left\{  I\subseteq S\ \mid\ g\in I\right\}
$\textquotedblright\ means \textquotedblleft the set of all subsets $I$ of $S$
satisfying $g\in I$\textquotedblright.}%
\begin{align*}
\left\{  I\subseteq S\ \mid\ g\notin I\right\}   &  \rightarrow\left\{
I\subseteq S\ \mid\ g\in I\right\}  ,\\
J  &  \mapsto J\cup\left\{  g\right\}
\end{align*}
is well-defined. The map%
\begin{align*}
\left\{  I\subseteq S\ \mid\ g\in I\right\}   &  \rightarrow\left\{
I\subseteq S\ \mid\ g\notin I\right\}  ,\\
K  &  \mapsto K\setminus\left\{  g\right\}
\end{align*}
is also well-defined. These two maps are mutually inverse\footnote{because of
the following two (easily proven) facts:
\par
\begin{itemize}
\item Every subset $J$ of $S$ satisfying $g\notin J$ must satisfy $\left(
J\cup\left\{  g\right\}  \right)  \setminus\left\{  g\right\}  =J$.
\par
\item Every subset $K$ of $S$ satisfying $g\in K$ must satisfy $\left(
K\setminus\left\{  g\right\}  \right)  \cup\left\{  g\right\}  =K$.
\end{itemize}
}, and thus are bijections. Hence, in particular, the map%
\begin{align*}
\left\{  I\subseteq S\ \mid\ g\notin I\right\}   &  \rightarrow\left\{
I\subseteq S\ \mid\ g\in I\right\}  ,\\
J  &  \mapsto J\cup\left\{  g\right\}
\end{align*}
is a bijection. Thus, we can substitute $J\cup\left\{  g\right\}  $ for $I$ in
the sum $\sum_{\substack{I\subseteq S;\\g\in I}}\left(  -1\right)
^{\left\vert X\cap I\right\vert +\left\vert Y\cap I\right\vert }$. We thus
obtain%
\begin{equation}
\sum_{\substack{I\subseteq S;\\g\in I}}\left(  -1\right)  ^{\left\vert X\cap
I\right\vert +\left\vert Y\cap I\right\vert }=\sum_{\substack{J\subseteq
S;\\g\notin J}}\left(  -1\right)  ^{\left\vert X\cap\left(  J\cup\left\{
g\right\}  \right)  \right\vert +\left\vert Y\cap\left(  J\cup\left\{
g\right\}  \right)  \right\vert }. \label{sol.DIE.destructXY.2}%
\end{equation}


In order to simplify the addends on the right hand side, we will use the
following observation:

\begin{statement}
\textit{Observation 1:} Let $J$ be a subset of $S$ such that $g\notin J$.
Then,%
\[
\left(  -1\right)  ^{\left\vert X\cap\left(  J\cup\left\{  g\right\}  \right)
\right\vert +\left\vert Y\cap\left(  J\cup\left\{  g\right\}  \right)
\right\vert }=-\left(  -1\right)  ^{\left\vert X\cap J\right\vert +\left\vert
Y\cap J\right\vert }.
\]

\end{statement}

[\textit{Proof of Observation 1:} It is well-known (and straightforward to
prove) that every three sets $A$, $B$ and $C$ satisfy%
\begin{equation}
A\cap\left(  B\cup C\right)  =\left(  A\cap B\right)  \cup\left(  A\cap
C\right)  . \label{sol.DIE.destructXY.distr}%
\end{equation}
(Indeed, this is known as the one of the two distributivity laws for unions
and intersections\footnote{The other distributivity law says that
\[
A\cup\left(  B\cap C\right)  =\left(  A\cup B\right)  \cap\left(  A\cup
C\right)  .
\]
}.)

Now, $g\in X$, thus $\left\{  g\right\}  \subseteq X$ and therefore
$X\cap\left\{  g\right\}  =\left\{  g\right\}  $. We have $g\notin J$ and thus
$g\notin X\cap J$ (because otherwise, we would have $g\in X\cap J\subseteq J$,
which would contradict $g\notin J$). Applying (\ref{sol.DIE.destructXY.distr})
to $A=X$, $B=J$ and $C=\left\{  g\right\}  $, we obtain%
\[
X\cap\left(  J\cup\left\{  g\right\}  \right)  =\left(  X\cap J\right)
\cup\underbrace{\left(  X\cap\left\{  g\right\}  \right)  }_{=\left\{
g\right\}  }=\left(  X\cap J\right)  \cup\left\{  g\right\}  .
\]
Hence,%
\begin{equation}
\left\vert X\cap\left(  J\cup\left\{  g\right\}  \right)  \right\vert
=\left\vert \left(  X\cap J\right)  \cup\left\{  g\right\}  \right\vert
=\left\vert X\cap J\right\vert +1 \label{sol.DIE.destructXY.o1.pf.1}%
\end{equation}
(since $g\notin X\cap J$). On the other hand, the sets $Y$ and $\left\{
g\right\}  $ are disjoint (since $g\notin Y$), and therefore $Y\cap\left\{
g\right\}  =\varnothing$. Applying (\ref{sol.DIE.destructXY.distr}) to $A=Y$,
$B=J$ and $C=\left\{  g\right\}  $, we obtain%
\[
Y\cap\left(  J\cup\left\{  g\right\}  \right)  =\left(  Y\cap J\right)
\cup\underbrace{\left(  Y\cap\left\{  g\right\}  \right)  }_{=\varnothing
}=\left(  Y\cap J\right)  \cup\varnothing=Y\cap J.
\]
Hence,%
\[
\left\vert Y\cap\left(  J\cup\left\{  g\right\}  \right)  \right\vert
=\left\vert Y\cap J\right\vert .
\]
Adding this equality to \eqref{sol.DIE.destructXY.o1.pf.1}, we obtain%
\[
\left\vert X\cap\left(  J\cup\left\{  g\right\}  \right)  \right\vert
+\left\vert Y\cap\left(  J\cup\left\{  g\right\}  \right)  \right\vert
=\left(  \left\vert X\cap J\right\vert +1\right)  +\left\vert Y\cap
J\right\vert =\left(  \left\vert X\cap J\right\vert +\left\vert Y\cap
J\right\vert \right)  +1.
\]
Hence,%
\[
\left(  -1\right)  ^{\left\vert X\cap\left(  J\cup\left\{  g\right\}  \right)
\right\vert +\left\vert Y\cap\left(  J\cup\left\{  g\right\}  \right)
\right\vert }=\left(  -1\right)  ^{\left(  \left\vert X\cap J\right\vert
+\left\vert Y\cap J\right\vert \right)  +1}=-\left(  -1\right)  ^{\left\vert
X\cap J\right\vert +\left\vert Y\cap J\right\vert }.
\]
This proves Observation 1.]

Now, \eqref{sol.DIE.destructXY.2} becomes%

\begin{align}
\sum_{\substack{I\subseteq S;\\g\in I}}\left(  -1\right)  ^{\left\vert X\cap
I\right\vert +\left\vert Y\cap I\right\vert }  &  =\sum_{\substack{J\subseteq
S;\\g\notin J}}\underbrace{\left(  -1\right)  ^{\left\vert X\cap\left(
J\cup\left\{  g\right\}  \right)  \right\vert +\left\vert Y\cap\left(
J\cup\left\{  g\right\}  \right)  \right\vert }}_{\substack{=-\left(
-1\right)  ^{\left\vert X\cap J\right\vert +\left\vert Y\cap J\right\vert
}\\\text{(by Observation 1)}}}\nonumber\\
&  =\sum_{\substack{J\subseteq S;\\g\notin J}}\left(  -\left(  -1\right)
^{\left\vert X\cap J\right\vert +\left\vert Y\cap J\right\vert }\right)
=-\sum_{\substack{J\subseteq S;\\g\notin J}}\left(  -1\right)  ^{\left\vert
X\cap J\right\vert +\left\vert Y\cap J\right\vert }\nonumber\\
&  =-\sum_{\substack{I\subseteq S;\\g\notin I}}\left(  -1\right)  ^{\left\vert
X\cap I\right\vert +\left\vert Y\cap I\right\vert }
\label{sol.DIE.destructXY.3}%
\end{align}
(here, we have renamed the summation index $J$ as $I$).

Now, \eqref{sol.DIE.destructXY.1} becomes%
\begin{align*}
\sum_{I\subseteq S}\left(  -1\right)  ^{\left\vert X\cap I\right\vert
+\left\vert Y\cap I\right\vert }  &  =\underbrace{\sum_{\substack{I\subseteq
S;\\g\in I}}\left(  -1\right)  ^{\left\vert X\cap I\right\vert +\left\vert
Y\cap I\right\vert }}_{\substack{=-\sum_{\substack{I\subseteq S;\\g\notin
I}}\left(  -1\right)  ^{\left\vert X\cap I\right\vert +\left\vert Y\cap
I\right\vert }\\\text{(by \eqref{sol.DIE.destructXY.3})}}}+\sum
_{\substack{I\subseteq S;\\g\notin I}}\left(  -1\right)  ^{\left\vert X\cap
I\right\vert +\left\vert Y\cap I\right\vert }\\
&  =-\sum_{\substack{I\subseteq S;\\g\notin I}}\left(  -1\right)  ^{\left\vert
X\cap I\right\vert +\left\vert Y\cap I\right\vert }+\sum_{\substack{I\subseteq
S;\\g\notin I}}\left(  -1\right)  ^{\left\vert X\cap I\right\vert +\left\vert
Y\cap I\right\vert }=0.
\end{align*}
This solves the exercise.

%----------------------------------------------------------------------------------------
%	EXERCISE 3
%----------------------------------------------------------------------------------------
\rule{\linewidth}{0.3pt} \\[0.4cm]

\section{Exercise 3}

\subsection{Problem}

A map $f : A \to B$ between two sets $A$ and $B$ will be called a
\textit{$2$-surjection} if each $b \in B$ satisfies $\left(  \text{\# of $a
\in A$ satisfying $f \left(  a \right)  = b$} \right)  \geq2$. (That is, if
each element of $B$ is taken as a value by $f$ at least twice.)

Let $m, n \in\mathbb{N}$. Find a formula (similar to \cite[Theorem
2.4.17]{notes}) for the \# of $2$-surjections from $\left[  m \right]  $ to
$\left[  n \right]  $.

\subsection{Solution sketch}

We shall use the notations $n^{\underline{k}}$ for lower factorials (as
defined in \cite[Definition 2.4.2]{notes}) and the notation
$\operatorname*{sur}\left(  m,n\right)  $ for numbers of surjections (as
defined in \cite[Definition 2.4.9]{notes}).

Now, we claim that
\begin{align}
&  \left(  \text{\# of }2\text{-surjections from }\left[  m\right]  \text{ to
}\left[  n\right]  \right) \nonumber\\
&  =\sum_{k=0}^{n}\left(  -1\right)  ^{k}\dbinom{n}{k}m^{\underline{k}%
}\operatorname*{sur}\left(  m-k,n-k\right) \label{sol.pie.2-surjs.goal1}\\
&  =\sum_{k=0}^{n}\left(  -1\right)  ^{k}k!\dbinom{n}{k}\dbinom{m}%
{k}\operatorname*{sur}\left(  m-k,n-k\right) \label{sol.pie.2-surjs.goal2}\\
&  =\sum_{k=0}^{n}\left(  -1\right)  ^{k}\dbinom{m}{k}n^{\underline{k}%
}\operatorname*{sur}\left(  m-k,n-k\right)  . \label{sol.pie.2-surjs.goal3}%
\end{align}
(Several other expressions are possible -- e.g., we can replace the upper
bound $n$ of the summation by $m$ or $\min\left\{  m,n\right\}  $ or $\infty$,
because all addends beyond $k=\min\left\{  m,n\right\}  $ are easily seen to
be $0$.)

In order to prove these formulas, we will need the following theorem
(\cite[Theorem 2.9.8]{notes}):

\begin{theorem}
[Principle of Inclusion and Exclusion (complement form, simplified)]%
\label{thm.pie.bU}Let $n\in\mathbb{N}$. Let $U$ be a finite set. Let
$A_{1},A_{2},\ldots,A_{n}$ be $n$ subsets of $U$. Then,%
\begin{align*}
&  \left\vert U\setminus\left(  A_{1}\cup A_{2}\cup\cdots\cup A_{n}\right)
\right\vert \\
&  =\sum_{I\subseteq\left[  n\right]  }\left(  -1\right)  ^{\left\vert
I\right\vert }\left\vert \left\{  s\in U\ \mid\ s\in A_{i}\text{ for all }i\in
I\right\}  \right\vert .
\end{align*}

\end{theorem}

Let
\[
U=\left\{  \text{surjections }f:\left[  m\right]  \rightarrow\left[  n\right]
\right\}  .
\]


If $f:\left[  m\right]  \rightarrow\left[  n\right]  $ is any map, and
$i\in\left[  n\right]  $ is an element, then we say that $f$ \textit{takes
}$i$ \textit{only once} if $\left(  \text{\# of $a\in \left[m\right]$
satisfying $f\left(
a\right)  =i$}\right)  =1$. The following observation is quite obvious:

\begin{statement}
\textit{Observation 1:} A $2$-surjection from $\left[  m\right]  $ to $\left[
n\right]  $ is the same thing as a surjection $f:\left[  m\right]
\rightarrow\left[  n\right]  $ for which there exists no $i\in\left[
n\right]  $ such that $f$ takes $i$ only once.
\end{statement}

For each $i\in\left[  n\right]  $, we let%
\[
A_{i}=\left\{  \text{surjections }f:\left[  m\right]  \rightarrow\left[
n\right]  \ \mid\ f\text{ takes }i\text{ only once}\right\}  .
\]
Hence, $A_{1},A_{2},\ldots,A_{n}$ are $n$ subsets of $U$. Furthermore, their
definition yields%
\begin{align*}
&  U\setminus\left(  A_{1}\cup A_{2}\cup\cdots\cup A_{n}\right) \\
&  =\left\{  \text{surjections }f:\left[  m\right]  \rightarrow\left[
n\right]  \ \mid\ \text{there exists no }i\in\left[  n\right]  \text{ such
that }f\text{ takes }i\text{ only once}\right\} \\
&  =\left\{  2\text{-surjections from }\left[  m\right]  \text{ to }\left[
n\right]  \right\}
\end{align*}
(by Observation 1). Hence,%
\begin{align}
&  \left\vert U\setminus\left(  A_{1}\cup A_{2}\cup\cdots\cup A_{n}\right)
\right\vert \nonumber\\
&  =\left\vert \left\{  2\text{-surjections from }\left[  m\right]  \text{ to
}\left[  n\right]  \right\}  \right\vert \nonumber\\
&  =\left(  \text{\# of }2\text{-surjections from }\left[  m\right]  \text{ to
}\left[  n\right]  \right)  . \label{sol.pie.2-surs.Uwo}%
\end{align}


Now, we claim:

\begin{statement}
\textit{Observation 2:} Let $I$ be a subset of $\left[  n\right]  $. Let
$k=\left\vert I\right\vert $. Then,%
\[
\left\vert \left\{  s\in U\ \mid\ s\in A_{i}\text{ for all }i\in I\right\}
\right\vert =m^{\underline{k}}\cdot\operatorname*{sur}\left(  m-k,n-k\right)
.
\]

\end{statement}

[\textit{Proof of Observation 2:} Let $i_{1},i_{2},\ldots,i_{k}$ be the $k$
elements of $I$ (listed without repetition). Thus, $i_{1},i_{2},\ldots,i_{k}$
are distinct and satisfy $I=\left\{  i_{1},i_{2},\ldots,i_{k}\right\}  $.

The definition of the sets $A_{i}$ easily yields%
\begin{align*}
&  \left\{  s\in U\ \mid\ s\in A_{i}\text{ for all }i\in I\right\} \\
&  =\left\{  \text{surjections }s:\left[  m\right]  \rightarrow\left[
n\right]  \ \mid\ \text{for each }i\in I  \text{, the map
}s\text{ takes }i\text{ only once}\right\} \\
&  =\left\{  \text{surjections }f:\left[  m\right]  \rightarrow\left[
n\right]  \ \mid\ \text{for each }i\in I  \text{, the map
}f\text{ takes }i\text{ only once}\right\} \\
&  =\left\{  \text{surjections }f:\left[  m\right]  \rightarrow\left[
n\right]  \ \mid\ \text{the map }f\text{ takes each of }i_{1},i_{2}%
,\ldots,i_{k}\text{ only once}\right\}
\end{align*}
(since $I=\left\{  i_{1},i_{2},\ldots,i_{k}\right\}  $). Thus, the elements of
$\left\{  s\in U\ \mid\ s\in A_{i}\text{ for all }i\in I\right\}  $ are the
surjections $f:\left[  m\right]  \rightarrow\left[  n\right]  $ that take each
of $i_{1},i_{2},\ldots,i_{k}$ only once (but may also take other elements of
$\left[  n\right]  $ only once). Thus, each $f\in\left\{  s\in U\ \mid\ s\in
A_{i}\text{ for all }i\in I\right\}  $ can be constructed by the following method:

\begin{itemize}
\item Choose the unique element $a_{1}\in\left[  m\right]  $ that satisfies
$f\left(  a_{1}\right)  =i_{1}$.\ \ \ \ \footnote{Such an $a_{1}$ is indeed
unique, since $f$ has to take $i_{1}$ only once.} There are $m$ choices here
(since $\left[  m\right]  $ has $m$ elements).

\item Choose the unique element $a_{2}\in\left[  m\right]  $ that satisfies
$f\left(  a_{2}\right)  =i_{2}$.\ \ \ \ \footnote{Such an $a_{2}$ is indeed
unique, since $f$ has to take $i_{2}$ only once.} There are $m-1$ choices here
(since $\left[  m\right]  $ has $m$ elements, but $a_{1}$ has already been
used up\footnote{Obviously, $a_{2}$ cannot be $a_{1}$, since $f\left(
a_{2}\right)  =i_{2}\neq i_{1}=f\left(  a_{1}\right)  $.}).

\item Choose the unique element $a_{3}\in\left[  m\right]  $ that satisfies
$f\left(  a_{3}\right)  =i_{3}$. There are $m-2$ choices here (since $\left[
m\right]  $ has $m$ elements, but the two distinct elements $a_{1}$ and
$a_{2}$ have already been used up).

\item Choose the unique element $a_{4}\in\left[  m\right]  $ that satisfies
$f\left(  a_{4}\right)  =i_{4}$. There are $m-3$ choices here (since $\left[
m\right]  $ has $m$ elements, but the three distinct elements $a_{1}$, $a_{2}$
and $a_{3}$ have already been used up).

\item And so on, until we have chosen $k$ distinct elements $a_{1}%
,a_{2},\ldots,a_{k}$ of $\left[  m\right]  $ that satisfy%
\[
f\left(  a_{p}\right)  =i_{p}\qquad\text{for each }p\in\left[  k\right]  .
\]


\item Now, choose the values of $f$ on the remaining $m-k$ elements of
$\left[  m\right]  $ (that is, on the elements of $\left[  m\right]
\setminus\left\{  a_{1},a_{2},\ldots,a_{k}\right\}  $). These values must
belong to the $\left(  n-k\right)  $-element set $\left[  n\right]  \setminus
I$, and furthermore they must completely cover this latter set (since $f$
should be surjective). Thus, we are really choosing a surjective map from the
$\left(  m-k\right)  $-element set $\left[  m\right]  \setminus\left\{
a_{1},a_{2},\ldots,a_{k}\right\}  $ to the $\left(  n-k\right)  $-element set
$\left[  n\right]  \setminus I$. There are $\operatorname*{sur}\left(
m-k,n-k\right)  $ choices for this (because of \cite[Proposition
2.4.11]{notes}).
\end{itemize}

Thus, the dependent product rule shows that the total \# of \newline%
$f\in\left\{  s\in U\ \mid\ s\in A_{i}\text{ for all }i\in I\right\}  $ is
\[
\underbrace{m\left(  m-1\right)  \left(  m-2\right)  \cdots\left(
m-k+1\right)  }_{=m^{\underline{k}}}\cdot\operatorname*{sur}\left(
m-k,n-k\right)  =m^{\underline{k}}\cdot\operatorname*{sur}\left(
m-k,n-k\right)  .
\]


In other words, $\left\vert \left\{  s\in U\ \mid\ s\in A_{i}\text{ for all
}i\in I\right\}  \right\vert =m^{\underline{k}}\cdot\operatorname*{sur}\left(
m-k,n-k\right)  $. This proves Observation 2.]

Now, \eqref{sol.pie.2-surs.Uwo} yields%
\begin{align*}
&  \left(  \text{\# of }2\text{-surjections from }\left[  m\right]  \text{ to
}\left[  n\right]  \right) \\
&  =\left\vert U\setminus\left(  A_{1}\cup A_{2}\cup\cdots\cup A_{n}\right)
\right\vert \\
&  =\sum_{I\subseteq\left[  n\right]  }\left(  -1\right)  ^{\left\vert
I\right\vert }\left\vert \left\{  s\in U\ \mid\ s\in A_{i}\text{ for all }i\in
I\right\}  \right\vert \qquad\left(  \text{by Theorem \ref{thm.pie.bU}}\right)
\\
&  =\sum_{k=0}^{n}\sum_{\substack{I\subseteq\left[  n\right]  ;\\\left\vert
I\right\vert =k}}\underbrace{\left(  -1\right)  ^{\left\vert I\right\vert }%
}_{\substack{=\left(  -1\right)  ^{k}\\\text{(since }\left\vert I\right\vert
=k\text{)}}}\ \ \underbrace{\left\vert \left\{  s\in U\ \mid\ s\in A_{i}\text{
for all }i\in I\right\}  \right\vert }_{\substack{=m^{\underline{k}}%
\cdot\operatorname*{sur}\left(  m-k,n-k\right)  \\\text{(by Observation 2)}%
}}\\
&  \qquad\qquad\left(
\begin{array}
[c]{c}%
\text{here, we have split the sum according to the value of }\left\vert
I\right\vert \text{,}\\
\text{since every subset }I\text{ of }\left[  n\right]  \text{ satisfies
}\left\vert I\right\vert \in\left\{  0,1,\ldots,n\right\}
\end{array}
\right) \\
&  =\sum_{k=0}^{n}\underbrace{\sum_{\substack{I\subseteq\left[  n\right]
;\\\left\vert I\right\vert =k}}\left(  -1\right)  ^{k}m^{\underline{k}}%
\cdot\operatorname*{sur}\left(  m-k,n-k\right)  }_{=\left(  \text{\# of
subsets }I\text{ of }\left[  n\right]  \text{ such that }\left\vert
I\right\vert =k\right)  \cdot\left(  -1\right)  ^{k}m^{\underline{k}}%
\cdot\operatorname*{sur}\left(  m-k,n-k\right)  }\\
&  =\sum_{k=0}^{n}\underbrace{\left(  \text{\# of subsets }I\text{ of }\left[
n\right]  \text{ such that }\left\vert I\right\vert =k\right)  }%
_{\substack{=\left(  \text{\# of }k\text{-element subsets of }\left[
n\right]  \right)  \\=\dbinom{n}{k}\\\text{(by Theorem \ref{thm.binom.comb})}%
}}\cdot\left(  -1\right)  ^{k}m^{\underline{k}}\cdot\operatorname*{sur}\left(
m-k,n-k\right) \\
&  =\sum_{k=0}^{n}\dbinom{n}{k}\cdot\left(  -1\right)  ^{k}m^{\underline{k}%
}\cdot\operatorname*{sur}\left(  m-k,n-k\right) \\
&  =\sum_{k=0}^{n}\left(  -1\right)  ^{k}\dbinom{n}{k}m^{\underline{k}%
}\operatorname*{sur}\left(  m-k,n-k\right)  .
\end{align*}
This proves \eqref{sol.pie.2-surjs.goal1}.

Next, we notice that $m^{\underline{k}}=k!\cdot\dbinom{m}{k}$ for each
$k\in\mathbb{N}$ (by \cite[Proposition 2.4.3 \textbf{(c)}]{notes}). Thus, the
right hand sides of \eqref{sol.pie.2-surjs.goal1} and
\eqref{sol.pie.2-surjs.goal2} are equal. Hence, \eqref{sol.pie.2-surjs.goal2}
follows from \eqref{sol.pie.2-surjs.goal1}.

Next, we notice that $n^{\underline{k}}=k!\cdot\dbinom{n}{k}$ for each
$k\in\mathbb{N}$ (by \cite[Proposition 2.4.3 \textbf{(c)}]{notes}). Thus, the
right hand sides of \eqref{sol.pie.2-surjs.goal3} and
\eqref{sol.pie.2-surjs.goal2} are equal. Hence, \eqref{sol.pie.2-surjs.goal3}
follows from \eqref{sol.pie.2-surjs.goal2}.

Thus, all our claims are proved.

\subsection{Remark}

This problem is easily seen to be equivalent to counting the set partitions of
$\left[  m\right]  $ into $n$ (nonempty) subsets with at least two elements
each (see, e.g., \cite[\S 16, \textquotedblleft Partitions of a set into
blocks with at least two elements each\textquotedblright]{Galvin}). Indeed, if
$f:\left[  m\right]  \rightarrow\left[  n\right]  $ is a $2$-surjection, then
we can set $M_{i}=\left\{  a\in\left[  m\right]  \ \mid\ f\left(  a\right)
=i\right\}  $ for each $i\in\left[  n\right]  $, and then $\left\{
M_{1},M_{2},\ldots,M_{n}\right\}  $ is a set partition of $\left[  m\right]  $
into $n$ subsets with at least two elements each. This is not quite a
bijection, but each set partition of the latter kind is obtained from exactly
$n!$ many different $2$-surjections $f$. Hence,%
\begin{align*}
&  \left(  \text{\# of }2\text{-surjections from }\left[  m\right]  \text{ to
}\left[  n\right]  \right) \\
&  =n!\cdot\left(  \text{\# of set partitions of }\left[  m\right]  \text{
into }n\text{ subsets with at least two elements each}\right)  .
\end{align*}


This kind of set partitions are known as \textit{rhyme schemes} (with no
unrhymed lines). See \href{https://en.wikipedia.org/wiki/Rhyme_scheme}{the
Wikipedia article for \textquotedblleft rhyme schemes\textquotedblright}
(which gives references for the \# of such set partitions where $n$ is not fixed).

%----------------------------------------------------------------------------------------
%	EXERCISE 4
%----------------------------------------------------------------------------------------
\rule{\linewidth}{0.3pt} \\[0.4cm]

\section{Exercise 4}

\subsection{Problem}

Let $n \in\mathbb{N}$ and $k \in\mathbb{N}$ be such that $n \geq k$.

Let $S_{n}$ denote the set of all permutations of $\left[  n \right]  $. For
each permutation $w \in S_{n}$, let $\operatorname{Fix} w$ denote the set of
all fixed points of $w$ (that is, the set $\left\{  i \in\left[  n \right]
\ \mid\ w \left(  i \right)  = i \right\}  $).

Prove that
\[
\sum_{w \in S_{n}} \dbinom{\left|  \operatorname{Fix} w \right|  }{k} =
\left(  n-k \right)  ! \dbinom{n}{k} = \dfrac{n!}{k!} .
\]


\subsection{Remark}

The $k=1$ case of this is saying that $\sum_{w \in S_{n}} \left|
\operatorname{Fix} w \right|  = n!$ (or, equivalently: a permutation of
$\left[  n \right]  $ has exactly $1$ fixed point on average). This was proved
in \cite[\S 0.2, Exercise 2]{17f-hw7s}. That argument may be helpful.

\subsection{Solution}

Forget that we fixed $n$ and $k$.

We shall use the following theorem (\cite[Theorem 1.3.12]{notes}):

\begin{theorem}
[Combinatorial interpretation of the binomial coefficients]%
\label{thm.binom.comb}Let $n\in\mathbb{N}$ and $k\in\mathbb{R}$. Let $S$ be an
$n$-element set. Then,%
\[
\dbinom{n}{k}=\left(  \text{\# of }k\text{-element subsets of }S\right)  .
\]

\end{theorem}

We will also use the following theorem (\cite[Theorem 1.3.9]{notes}):

\begin{theorem}
[Factorial formula for the binomial coefficients]\label{thm.binom.fac}Let
$n\in\mathbb{N}$ and $k\in\mathbb{N}$ be such that $k\leq n$. Then,%
\[
\dbinom{n}{k}=\dfrac{n!}{k!\cdot\left(  n-k\right)  !}.
\]

\end{theorem}

Now, let $n\in\mathbb{N}$. Recall the definition of $S_{n}$ given in the exercise.

If $X$ is any set, then we let $S_{X}$ denote the set of all permutations of
$X$. Thus, both $S_{n}$ and $S_{\left[  n\right]  }$ stand for the set of all
permutations of $\left[  n\right]  $. Hence, $S_{n}=S_{\left[  n\right]  }$.

We shall use the following fact (\cite[Corollary 2.9.16]{notes}):

\begin{corollary}
\label{cor.count.dera.subfix-size}Let $n\in\mathbb{N}$. Let $X$ be an
$n$-element set. Let $I$ be a subset of $X$. Then,
\[
\left\vert \left\{  \sigma\in S_{X}\ \mid\ \sigma\left(  i\right)  =i\text{
for each }i\in I\right\}  \right\vert =\left(  n-\left\vert I\right\vert
\right)  !.
\]

\end{corollary}

We observe the following simple fact:

\begin{statement}
\textit{Observation 1:} Let $w\in S_{n}$ be a permutation. Let $I$ be a subset
of $\left[  n\right]  $. Then, we have the logical equivalence%
\[
\left(  I\subseteq\operatorname*{Fix}w\right)  \ \Longleftrightarrow\ \left(
w\left(  i\right)  =i\text{ for each }i\in I\right)  .
\]

\end{statement}

[\textit{Proof of Observation 1:} For each $i\in I$, we have the following
chain of equivalences:%
\begin{align}
&  \ \left(  i\in\operatorname*{Fix}w\right) \nonumber\\
&  \Longleftrightarrow\ \left(  i\text{ is a fixed point of }w\right)
\qquad\left(  \text{since }\operatorname*{Fix}w\text{ is the set of all fixed
points of }w\right) \nonumber\\
&  \Longleftrightarrow\ \left(  i\in\left[  n\right]  \text{ and }w\left(
i\right)  =i\right)  \qquad\left(  \text{by the definition of
\textquotedblleft fixed point\textquotedblright}\right) \nonumber\\
&  \Longleftrightarrow\ \left(  w\left(  i\right)  =i\right)
\label{sol.perm.sumFixCk.o1.pf.1}%
\end{align}
(since $i\in\left[  n\right]  $ holds automatically (because $i\in
I\subseteq\left[  n\right]  $)). Now, we have the following chain of
equivalences:%
\begin{align*}
\left(  I\subseteq\operatorname*{Fix}w\right)  \  &  \Longleftrightarrow
\ \left(  \text{each }i\in I\text{ satisfies }i\in\operatorname*{Fix}w\right)
\\
&  \Longleftrightarrow\ \left(  \text{each }i\in I\text{ satisfies }w\left(
i\right)  =i\right) \\
&  \qquad\qquad\left(  \text{because of the equivalence
\eqref{sol.perm.sumFixCk.o1.pf.1} that holds for each }i\in I\right) \\
&  \Longleftrightarrow\ \left(  w\left(  i\right)  =i\text{ for each }i\in
I\right)  .
\end{align*}
This proves Observation 1.]

Now, let $k\in\mathbb{N}$ be such that $n\geq k$. Then, Theorem
\ref{thm.binom.comb} (applied to $S=\left[  n\right]  $) yields%
\begin{equation}
\dbinom{n}{k}=\left(  \text{\# of }k\text{-element subsets of }\left[
n\right]  \right)  . \label{sol.perm.sumFixCk.nCk}%
\end{equation}


Let $w\in S_{n}$. Then, $\operatorname*{Fix}w\subseteq\left[  n\right]  $.
Hence, every subset of $\operatorname*{Fix}w$ is also a subset of $\left[
n\right]  $. In other words, every subset $I$ of $\operatorname*{Fix}w$
automatically satisfies $I\subseteq\left[  n\right]  $. Therefore, in
particular, the $k$-element subsets $I$ of $\operatorname*{Fix}w$ such that
$I\subseteq\left[  n\right]  $ are simply the $k$-element subsets $I$ of
$\operatorname*{Fix}w$.

But each $k$-element subset $I$ of $\left[  n\right]  $ satisfies either
$I\subseteq\operatorname*{Fix}w$ or not $I\subseteq\operatorname*{Fix}w$ (but
not both). Thus,\footnote{We shall be using the Iverson bracket notation.}%
\begin{align*}
\sum_{\substack{I\text{ is a }k\text{-element}\\\text{subset of }\left[
n\right]  }}\left[  I\subseteq\operatorname*{Fix}w\right]   &  =\sum
_{\substack{I\text{ is a }k\text{-element}\\\text{subset of }\left[  n\right]
;\\I\subseteq\operatorname*{Fix}w}}\underbrace{\left[  I\subseteq
\operatorname*{Fix}w\right]  }_{\substack{=1\\\text{(since }I\subseteq
\operatorname*{Fix}w\text{)}}}+\sum_{\substack{I\text{ is a }k\text{-element}%
\\\text{subset of }\left[  n\right]  ;\\\text{not }I\subseteq
\operatorname*{Fix}w}}\underbrace{\left[  I\subseteq\operatorname*{Fix}%
w\right]  }_{\substack{=0\\\text{(since we don't have }I\subseteq
\operatorname*{Fix}w\text{)}}}\\
&  =\sum_{\substack{I\text{ is a }k\text{-element}\\\text{subset of }\left[
n\right]  ;\\I\subseteq\operatorname*{Fix}w}}1+\underbrace{\sum
_{\substack{I\text{ is a }k\text{-element}\\\text{subset of }\left[  n\right]
;\\\text{not }I\subseteq\operatorname*{Fix}w}}0}_{=0}=\sum_{\substack{I\text{
is a }k\text{-element}\\\text{subset of }\left[  n\right]  ;\\I\subseteq
\operatorname*{Fix}w}}1\\
&  =\left(  \text{\# of }k\text{-element subsets }I\text{ of }\left[
n\right]  \text{ such that }I\subseteq\operatorname*{Fix}w\right)  \cdot1\\
&  =\left(  \text{\# of }k\text{-element subsets }I\text{ of }\left[
n\right]  \text{ such that }I\subseteq\operatorname*{Fix}w\right) \\
&  =\left(  \text{\# of }k\text{-element sets }I\text{ such that }%
I\subseteq\left[  n\right]  \text{ and }I\subseteq\operatorname*{Fix}w\right)
\\
&  =\left(  \text{\# of }k\text{-element subsets }I\text{ of }%
\operatorname*{Fix}w\text{ such that }I\subseteq\left[  n\right]  \right) \\
&  =\left(  \text{\# of }k\text{-element subsets }I\text{ of }%
\operatorname*{Fix}w\right)
\end{align*}
(since the $k$-element subsets $I$ of $\operatorname*{Fix}w$ such that
$I\subseteq\left[  n\right]  $ are simply the $k$-element subsets $I$ of
$\operatorname*{Fix}w$).

But Theorem \ref{thm.binom.comb} (applied to $\left\vert \operatorname*{Fix}%
w\right\vert $ and $\operatorname*{Fix}w$ instead of $n$ and $S$) yields%
\begin{align*}
\dbinom{\left\vert \operatorname{Fix}w\right\vert }{k}  &  =\left(  \text{\#
of }k\text{-element subsets of }\operatorname*{Fix}w\right) \\
&  =\left(  \text{\# of }k\text{-element subsets }I\text{ of }%
\operatorname*{Fix}w\right)  .
\end{align*}
Comparing these two equalities, we obtain%
\begin{equation}
\dbinom{\left\vert \operatorname{Fix}w\right\vert }{k}=\sum_{\substack{I\text{
is a }k\text{-element}\\\text{subset of }\left[  n\right]  }}\left[
I\subseteq\operatorname*{Fix}w\right]  . \label{sol.perm.sumFixCk.FixwCk=}%
\end{equation}


Now, forget that we fixed $w$. We thus have proved
\eqref{sol.perm.sumFixCk.FixwCk=} for each $w\in S_{n}$. Now,
\begin{align}
\sum_{w\in S_{n}}\underbrace{\dbinom{\left\vert \operatorname{Fix}w\right\vert
}{k}}_{\substack{=\sum_{\substack{I\text{ is a }k\text{-element}\\\text{subset
of }\left[  n\right]  }}\left[  I\subseteq\operatorname*{Fix}w\right]
\\\text{(by \eqref{sol.perm.sumFixCk.FixwCk=})}}}  &  =\underbrace{\sum_{w\in
S_{n}}\ \ \sum_{\substack{I\text{ is a }k\text{-element}\\\text{subset of
}\left[  n\right]  }}}_{=\sum_{\substack{I\text{ is a }k\text{-element}%
\\\text{subset of }\left[  n\right]  }}\ \ \sum_{w\in S_{n}}}\left[
I\subseteq\operatorname*{Fix}w\right] \nonumber\\
&  =\sum_{\substack{I\text{ is a }k\text{-element}\\\text{subset of }\left[
n\right]  }}\ \ \sum_{w\in S_{n}}\left[  I\subseteq\operatorname*{Fix}%
w\right]  . \label{sol.perm.sumFixCk.4}%
\end{align}


Now, let $I$ be a $k$-element subset of $\left[  n\right]  $. Thus,
$\left\vert I\right\vert =k$ (since $I$ is a $k$-element set). Also,%
\begin{align}
&  \sum_{w\in S_{n}}\left[  I\subseteq\operatorname*{Fix}w\right] \nonumber\\
&  =\sum_{\substack{w\in S_{n};\\I\subseteq\operatorname*{Fix}w}%
}\ \ \underbrace{\left[  I\subseteq\operatorname*{Fix}w\right]  }%
_{\substack{=1\\\text{(since }I\subseteq\operatorname*{Fix}w\text{)}}%
}+\sum_{\substack{w\in S_{n};\\\text{not }I\subseteq\operatorname*{Fix}%
w}}\ \ \underbrace{\left[  I\subseteq\operatorname*{Fix}w\right]
}_{\substack{=0\\\text{(since we don't have }I\subseteq\operatorname*{Fix}%
w\text{)}}}\nonumber\\
&  \qquad\qquad\left(  \text{since each }w\in S_{n}\text{ satisfies either
}I\subseteq\operatorname*{Fix}w\text{ or not }I\subseteq\operatorname*{Fix}%
w\text{ (but not both)}\right) \nonumber\\
&  =\sum_{\substack{w\in S_{n};\\I\subseteq\operatorname*{Fix}w}%
}1+\underbrace{\sum_{\substack{w\in S_{n};\\\text{not }I\subseteq
\operatorname*{Fix}w}}0}_{=0}=\sum_{\substack{w\in S_{n};\\I\subseteq
\operatorname*{Fix}w}}1. \label{sol.perm.sumFixCk.5}%
\end{align}
But Observation 1 shows that for each $w\in S_{n}$, we have the equivalence
$\left(  I\subseteq\operatorname*{Fix}w\right)  \ \Longleftrightarrow\ \left(
w\left(  i\right)  =i\text{ for each }i\in I\right)  $. Hence, the summation
sign \textquotedblleft$\sum_{\substack{w\in S_{n};\\I\subseteq
\operatorname*{Fix}w}}$\textquotedblright\ on the right hand side of
(\ref{sol.perm.sumFixCk.5}) can be replaced by \textquotedblleft%
$\sum_{\substack{w\in S_{n};\\w\left(  i\right)  =i\text{ for each }i\in I}%
}$\textquotedblright. Hence, (\ref{sol.perm.sumFixCk.5}) rewrites as%
\begin{align}
\sum_{w\in S_{n}}\left[  I\subseteq\operatorname*{Fix}w\right]   &
=\sum_{\substack{w\in S_{n};\\w\left(  i\right)  =i\text{ for each }i\in
I}}1=\sum_{\substack{\sigma\in S_{n};\\\sigma\left(  i\right)  =i\text{ for
each }i\in I}}1\nonumber\\
&  \qquad\qquad\left(  \text{here, we have renamed the summation index
}w\text{ as }\sigma\right) \nonumber\\
&  =\left(  \text{\# of }\sigma\in S_{n}\text{ satisfying }\left(
\sigma\left(  i\right)  =i\text{ for each }i\in I\right)  \right)
\cdot1\nonumber\\
&  =\left(  \text{\# of }\sigma\in S_{n}\text{ satisfying }\left(
\sigma\left(  i\right)  =i\text{ for each }i\in I\right)  \right) \nonumber\\
&  =\left\vert \left\{  \sigma\in S_{n}\ \mid\ \sigma\left(  i\right)
=i\text{ for each }i\in I\right\}  \right\vert \nonumber\\
&  =\left\vert \left\{  \sigma\in S_{\left[  n\right]  }\ \mid\ \sigma\left(
i\right)  =i\text{ for each }i\in I\right\}  \right\vert \qquad\left(
\text{since }S_{n}=S_{\left[  n\right]  }\right) \nonumber\\
&  =\left(  n-\underbrace{\left\vert I\right\vert }_{=k}\right)
!\qquad\left(  \text{by Corollary \ref{cor.count.dera.subfix-size}}\right)
\nonumber\\
&  =\left(  n-k\right)  !. \label{sol.perm.sumFixCk.6}%
\end{align}


Now, forget that we fixed $I$. We thus have proved (\ref{sol.perm.sumFixCk.6})
for each $k$-element subset $I$ of $\left[  n\right]  $. Now,
(\ref{sol.perm.sumFixCk.4}) becomes%
\begin{align*}
\sum_{w\in S_{n}}\dbinom{\left\vert \operatorname{Fix}w\right\vert }{k}  &
=\sum_{\substack{I\text{ is a }k\text{-element}\\\text{subset of }\left[
n\right]  }}\ \ \underbrace{\sum_{w\in S_{n}}\left[  I\subseteq
\operatorname*{Fix}w\right]  }_{\substack{=\left(  n-k\right)  !\\\text{(by
(\ref{sol.perm.sumFixCk.6}))}}}=\sum_{\substack{I\text{ is a }k\text{-element}%
\\\text{subset of }\left[  n\right]  }}\left(  n-k\right)  !\\
&  =\underbrace{\left(  \text{\# of }k\text{-element subsets of }\left[
n\right]  \right)  }_{\substack{=\dbinom{n}{k}\\\text{(by
(\ref{sol.perm.sumFixCk.nCk}))}}}\cdot\left(  n-k\right)  !=\dbinom{n}{k}%
\cdot\left(  n-k\right)  !\\
&  =\left(  n-k\right)  !\underbrace{\dbinom{n}{k}}_{\substack{=\dfrac
{n!}{k!\cdot\left(  n-k\right)  !}\\\text{(by Theorem \ref{thm.binom.fac})}%
}}\\
&  =\left(  n-k\right)  !\cdot\dfrac{n!}{k!\cdot\left(  n-k\right)  !}%
=\dfrac{n!}{k!}.
\end{align*}
This solves the exercise.

%----------------------------------------------------------------------------------------
%	EXERCISE 5
%----------------------------------------------------------------------------------------
\rule{\linewidth}{0.3pt} \\[0.4cm]

\section{Exercise 5}

\subsection{Problem}

Let $n\in\mathbb{N}$. A permutation $w$ of $\left[  n\right]  $ will be called
\textit{domino-free} if there exists no $i\in\left[  n-1\right]  $ satisfying
\[
w\left(  i\right)  =i+1\qquad\text{ and }\qquad w\left(  i+1\right)  =i.
\]
Find a formula for the \# of domino-free permutations of $\left[  n\right]  $.

\subsection{Solution sketch}

We claim that\footnote{See \cite[Definition 1.4.4]{notes} for the meaning of
\textquotedblleft$\left\lceil \left(  n-1\right)  /2\right\rceil
$\textquotedblright.}%
\begin{align}
&  \left(  \text{\# of domino-free permutations of }\left[  n\right]  \right)
\nonumber\\
&  =\sum_{k=0}^{\left\lceil \left(  n-1\right)  /2\right\rceil }\left(
-1\right)  ^{k}\dbinom{n-k}{k}\left(  n-2k\right)
!\label{sol.pie.dom-free-perms.goal1}\\
&  =\sum_{k=0}^{\left\lceil \left(  n-1\right)  /2\right\rceil }\left(
-1\right)  ^{k}\dfrac{\left(  n-k\right)  !}{k!}.
\label{sol.pie.dom-free-perms.goal2}%
\end{align}


How do we prove this? First, we WLOG assume that $n$ is positive (because for
$n=0$, the proof is straightforward). Hence, $n-1\in\mathbb{N}$.

Now, recall the notion of a lacunar set (as defined in \cite[Definition
1.4.2]{notes}). We will use the following fact (\cite[Proposition
1.4.10]{notes}):

\begin{proposition}
\label{prop.1.36}Let $n\in\mathbb{Z}$ and $k\in\mathbb{N}$ be such that $k\leq
n+1$. Then,
\[
\left(  \text{\# of }k\text{-element lacunar subsets of }\left[  n\right]
\right)  =\dbinom{n+1-k}{k}.
\]

\end{proposition}

Applying Proposition \ref{prop.1.36} to $n-1$ instead of $n$, we obtain%
\begin{align}
&  \left(  \text{\# of }k\text{-element lacunar subsets of }\left[
n-1\right]  \right)  \nonumber\\
&  =\dbinom{\left(  n-1\right)  +1-k}{k}=\dbinom{n-k}{k}%
\label{sol.pie.dom-free-perms.1}%
\end{align}
for each $k\in\left\{  0,1,\ldots,n\right\}  $. In particular, this holds for
all $k\in\left\{  0,1,\ldots,\left\lceil \left(  n-1\right)  /2\right\rceil
\right\}  $ (since it is easy to see that $\left\lceil \left(  n-1\right)
/2\right\rceil \leq n$ and thus $\left\{  0,1,\ldots,\left\lceil \left(
n-1\right)  /2\right\rceil \right\}  \subseteq\left\{  0,1,\ldots,n\right\}  $).

We will also use the following fact (\cite[Proposition 1.4.6]{notes}):

\begin{proposition}
\label{prop.subsets.lacunar.maxsize}Let $n\in\mathbb{N}$. Then, the largest
size of a lacunar subset of $\left[  n\right]  $ is $\left\lceil
n/2\right\rceil $.
\end{proposition}

Proposition \ref{prop.subsets.lacunar.maxsize} (applied to $n-1$ instead of
$n$) shows that the largest size of a lacunar subset of $\left[  n-1\right]  $
is $\left\lceil \left(  n-1\right)  /2\right\rceil $. Hence, each lacunar
subset $I$ of $\left[  n-1\right]  $ satisfies $\left\vert I\right\vert
\leq\left\lceil \left(  n-1\right)  /2\right\rceil $ and thus%
\begin{equation}
\left\vert I\right\vert \in\left\{  0,1,\ldots,\left\lceil \left(  n-1\right)
/2\right\rceil \right\}  . \label{sol.pie.dom-free-perms.sizeI}%
\end{equation}


Now, let%
\[
U=\left\{  \text{permutations of }\left[  n\right]  \right\}  .
\]


If $w$ is a permutation of $\left[  n\right]  $, then a \textit{domino-entry}
of $w$ shall mean an $i\in\left[  n-1\right]  $ satisfying
\[
w\left(  i\right)  =i+1\qquad\text{ and }\qquad w\left(  i+1\right)  =i.
\]
For each $i\in\left[  n-1\right]  $, let
\[
A_{i}=\left\{  w\in U\ \mid\ i\text{ is a domino-entry of }w\right\}  .
\]
Thus,%
\begin{align*}
U\setminus\left(  A_{1}\cup A_{2}\cup\cdots\cup A_{n-1}\right)   &  =\left\{
w\in U\ \mid\ w\text{ has no domino-entries}\right\} \\
&  =\left\{  w\text{ is a permutation of }\left[  n\right]  \ \mid\ w\text{
has no domino-entries}\right\} \\
&  \qquad\qquad\left(  \text{since }U=\left\{  \text{permutations of }\left[
n\right]  \right\}  \right) \\
&  =\left\{  \text{domino-free permutations of }\left[  n\right]  \right\}
\end{align*}
(since a permutation of $\left[  n\right]  $ has no domino-entries if and only
if it is domino-free\footnote{This follows easily from the definitions.}).
Hence,%
\begin{align}
&  \left\vert U\setminus\left(  A_{1}\cup A_{2}\cup\cdots\cup A_{n-1}\right)
\right\vert \nonumber\\
&  =\left\vert \left\{  \text{domino-free permutations of }\left[  n\right]
\right\}  \right\vert \nonumber\\
&  =\left(  \text{\# of domino-free permutations of }\left[  n\right]
\right)  . \label{sol.pie.dom-free-perms.2}%
\end{align}


Now, we will compute the sizes $\left\vert \left\{  s\in U\ \mid\ s\in
A_{i}\text{ for all }i\in I\right\}  \right\vert $ for $I\subseteq\left[
n-1\right]  $. This is done in the following two observations:

\begin{statement}
\textit{Observation 2:} Let $I$ be a subset of $\left[  n-1\right]  $ that is
not lacunar. Then,
\[
\left\vert \left\{  s\in U\ \mid\ s\in A_{i}\text{ for all }i\in I\right\}
\right\vert =0.
\]

\end{statement}

\begin{statement}
\textit{Observation 3:} Let $I$ be a subset of $\left[  n-1\right]  $ that is
lacunar. Then,
\[
\left\vert \left\{  s\in U\ \mid\ s\in A_{i}\text{ for all }i\in I\right\}
\right\vert =\left(  n-2\cdot\left\vert I\right\vert \right)  !.
\]

\end{statement}

[\textit{Proof of Observation 2:} Let $w\in\left\{  s\in U\ \mid\ s\in
A_{i}\text{ for all }i\in I\right\}  $. Thus, the permutation $w\in U$
satisfies $w\in A_{i}$ for each $i\in I$. In other words, each $i\in I$ is a
domino-entry of $w$.

But the set $I$ is not lacunar; thus, it contains two consecutive integers $m$
and $m+1$. Consider these $m$ and $m+1$.

Recall that each $i\in I$ is a domino-entry of $w$. Thus, $m$ and $m+1$ are
domino-entries of $w$ (since $I$ contains $m$ and $m+1$). Since $m$ is a
domino-entry of $w$, we have%
\[
w\left(  m\right)  =m+1\qquad\text{ and }\qquad w\left(  m+1\right)  =m
\]
(by the definition of \textquotedblleft domino-entry of $w$\textquotedblright%
). Since $m+1$ is a domino-entry of $w$, we have
\[
w\left(  m+1\right)  =m+2\qquad\text{ and }\qquad w\left(  m+2\right)  =m+1
\]
(by the definition of \textquotedblleft domino-entry of $w$\textquotedblright%
). But $w\left(  m+1\right)  =m$ obviously contradicts $w\left(  m+1\right)
=m+2$.

Forget that we fixed $w$. We thus have obtained a contradiction for each
\newline$w\in\left\{  s\in U\ \mid\ s\in A_{i}\text{ for all }i\in I\right\}
$. Therefore, there exists no \newline$w\in\left\{  s\in U\ \mid\ s\in
A_{i}\text{ for all }i\in I\right\}  $. In other words, $\left\{  s\in
U\ \mid\ s\in A_{i}\text{ for all }i\in I\right\}  $ is the empty set. Hence,
$\left\vert \left\{  s\in U\ \mid\ s\in A_{i}\text{ for all }i\in I\right\}
\right\vert =0$. This proves Observation 2.]

[\textit{Proof of Observation 3:} Let $I^{+}$ denote the set $\left\{
i+1\ \mid\ i\in I\right\}  $. From $I\subseteq\left[  n-1\right]  $, we obtain
$I^{+}\subseteq\left\{  2,3,\ldots,n\right\}  \subseteq\left[  n\right]  $.
Hence, both $I$ and $I^{+}$ are subsets of $\left[  n\right]  $. Thus, $I\cup
I^{+}$ is a subset of $\left[  n\right]  $. Moreover, it is easy to
see\footnote{Actually, this is done (with somewhat different notation) in
\cite[proof of Proposition 1.4.6]{notes}.} that the sets $I$ and $I^{+}$ are
disjoint (since $I$ is lacunar)
and satisfy $\left\vert I\right\vert =\left\vert I^{+}\right\vert $.
Hence, the sum rule yields $\left\vert I\cup I^{+}\right\vert =\left\vert
I\right\vert +\underbrace{\left\vert I^{+}\right\vert }_{=\left\vert
I\right\vert }=\left\vert I\right\vert +\left\vert I\right\vert =2\cdot
\left\vert I\right\vert $. Since $I\cup I^{+}$ is a subset of $\left[
n\right]  $, we furthermore have
\begin{equation}
\left\vert \left[  n\right]  \setminus\left(  I\cup I^{+}\right)  \right\vert
=\underbrace{\left\vert \left[  n\right]  \right\vert }_{=n}%
-\underbrace{\left\vert I\cup I^{+}\right\vert }_{=2\cdot\left\vert
I\right\vert }=n-2\cdot\left\vert I\right\vert .
\label{sol.pie.dom-free-perms.o3.pf.1}%
\end{equation}


Now, the elements of $\left\{  s\in U\ \mid\ s\in A_{i}\text{ for all }i\in
I\right\}  $ are precisely the permutations $w$ of $\left[  n\right]  $ such
that each $i\in I$ satisfies $w\in A_{i}$ (since $U=\left\{
\text{permutations of }\left[  n\right]  \right\}  $). In other words, the
elements of $\left\{  s\in U\ \mid\ s\in A_{i}\text{ for all }i\in I\right\}
$ are precisely the permutations $w$ of $\left[  n\right]  $ such that each
$i\in I$ is a domino-entry of $w$.\ \ \ \ \footnote{This is because the
statements \textquotedblleft$w\in A_{i}$\textquotedblright\ and
\textquotedblleft$i$ is a domino-entry of $w$\textquotedblright\ are
equivalent (by the definition of the $A_{i}$).} In other words, the elements
of $\left\{  s\in U\ \mid\ s\in A_{i}\text{ for all }i\in I\right\}  $ are
precisely the permutations $w$ of $\left[  n\right]  $ such that each $i\in I$
satisfies%
\[
w\left(  i\right)  =i+1\qquad\text{ and }\qquad w\left(  i+1\right)  =i
\]
(by the definition of \textquotedblleft domino-entry of $w$\textquotedblright%
). In other words, they are precisely the permutations $w$ of $\left[
n\right]  $ such that%
\begin{equation}
w\left(  i\right)  =i+1\qquad\text{for each }i\in I
\label{sol.pie.dom-free-perms.o3.pf.3}%
\end{equation}
and%
\begin{equation}
w\left(  j\right)  =j-1\qquad\text{for each }j\in I^{+}
\label{sol.pie.dom-free-perms.o3.pf.4}%
\end{equation}
(by the definition of $I^{+}$). This leads to the following algorithm for
constructing any $w\in\left\{  s\in U\ \mid\ s\in A_{i}\text{ for all }i\in
I\right\}  $:

\begin{itemize}
\item First, we define the values $w\left(  i\right)  $ to be $i+1$ for each
$i\in I$. We have no choices here, since we need to ensure that
\eqref{sol.pie.dom-free-perms.o3.pf.3} holds.

\item Then, we define the values $w\left(  j\right)  $ to be $j-1$ for each
$j\in I^{+}$. (These values don't conflict with the values $w\left(  i\right)
$ defined in the previous step, since the sets $I$ and $I^{+}$ are disjoint.)
We have no choices here, since we need to ensure that
\eqref{sol.pie.dom-free-perms.o3.pf.4} holds.

\item At this point, we have determined the values of $w$ at all elements of
$I\cup I^{+}$. Moreover, these values are distinct. (Indeed, the values
$w\left(  i\right)  $ for $i\in I$ are the elements of $I^{+}$, whereas the
values $w\left(  j\right)  $ for $j\in I^{+}$ are the elements of $I$; but we
know that $I$ and $I^{+}$ are disjoint.)

\item It remains to choose the values of $w$ at all remaining elements of
$\left[  n\right]  $ -- that is, at all elements of $\left[  n\right]
\setminus\left(  I\cup I^{+}\right)  $. These values must be distinct elements
of $\left[  n\right]  \setminus\left(  I\cup I^{+}\right)  $ (since the
elements of $I$ and $I^{+}$ have already been used up as values, while all
other elements of $\left[  n\right]  $ are yet unused), and need to cover the
whole the set $\left[  n\right]  \setminus\left(  I\cup I^{+}\right)  $. Thus,
our choice boils down to the choice of a permutation of the set $\left[
n\right]  \setminus\left(  I\cup I^{+}\right)  $. The number of options for
this is $\left\vert \left[  n\right]  \setminus\left(  I\cup I^{+}\right)
\right\vert !=\left(  n-2\cdot\left\vert I\right\vert \right)  !$ (by \eqref{sol.pie.dom-free-perms.o3.pf.1}).
\end{itemize}

Hence, the total \# of options in this algorithm in $\left(  n-2\cdot
\left\vert I\right\vert \right)  !$. Thus,
\[
\left\vert \left\{  s\in U\ \mid\ s\in A_{i}\text{ for all }i\in I\right\}
\right\vert =\left(  n-2\cdot\left\vert I\right\vert \right)  !.
\]
This proves Observation 3.]

Now, \eqref{sol.pie.dom-free-perms.2} yields%
\begin{align*}
&  \left(  \text{\# of domino-free permutations of }\left[  n\right]  \right)
\\
&  =\left\vert U\setminus\left(  A_{1}\cup A_{2}\cup\cdots\cup A_{n-1}\right)
\right\vert \\
&  =\sum_{I\subseteq\left[  n-1\right]  }\left(  -1\right)  ^{\left\vert
I\right\vert }\left\vert \left\{  s\in U\ \mid\ s\in A_{i}\text{ for all }i\in
I\right\}  \right\vert \\
&  \qquad\qquad\left(  \text{by Theorem \ref{thm.pie.bU}, applied to
}n-1\text{ instead of }n\right)  \\
&  =\underbrace{\sum_{\substack{I\subseteq\left[  n-1\right]  ;\\I\text{ is
lacunar}}}}_{\substack{=\sum_{k=0}^{\left\lceil \left(  n-1\right)
/2\right\rceil }\sum_{\substack{I\subseteq\left[  n-1\right]  ;\\I\text{ is
lacunar;}\\\left\vert I\right\vert =k}}\\\text{(since each lacunar subset
}I\text{ of }\left[  n-1\right]  \\\text{satisfies }\left\vert I\right\vert
\in\left\{  0,1,\ldots,\left\lceil \left(  n-1\right)  /2\right\rceil
\right\}  \\\text{(by \eqref{sol.pie.dom-free-perms.sizeI}))}}}\left(
-1\right)  ^{\left\vert I\right\vert }\underbrace{\left\vert \left\{  s\in
U\ \mid\ s\in A_{i}\text{ for all }i\in I\right\}  \right\vert }%
_{\substack{=\left(  n-2\cdot\left\vert I\right\vert \right)  !\\\text{(by
Observation 3)}}}\\
&  \qquad+\sum_{\substack{I\subseteq\left[  n-1\right]  ;\\I\text{ is not
lacunar}}}\left(  -1\right)  ^{\left\vert I\right\vert }\underbrace{\left\vert
\left\{  s\in U\ \mid\ s\in A_{i}\text{ for all }i\in I\right\}  \right\vert
}_{\substack{=0\\\text{(by Observation 2)}}}\\
&  =\sum_{k=0}^{\left\lceil \left(  n-1\right)  /2\right\rceil }%
\sum_{\substack{I\subseteq\left[  n-1\right]  ;\\I\text{ is lacunar;}%
\\\left\vert I\right\vert =k}}\underbrace{\left(  -1\right)  ^{\left\vert
I\right\vert }\left(  n-2\cdot\left\vert I\right\vert \right)  !}%
_{\substack{=\left(  -1\right)  ^{k}\left(  n-2k\right)  !\\\text{(since
}\left\vert I\right\vert =k\text{)}}}+\underbrace{\sum_{\substack{I\subseteq
\left[  n-1\right]  ;\\I\text{ is not lacunar}}}\left(  -1\right)
^{\left\vert I\right\vert }0}_{=0}\\
&  =\sum_{k=0}^{\left\lceil \left(  n-1\right)  /2\right\rceil }%
\underbrace{\sum_{\substack{I\subseteq\left[  n-1\right]  ;\\I\text{ is
lacunar;}\\\left\vert I\right\vert =k}}\left(  -1\right)  ^{k}\left(
n-2k\right)  !}_{=\left(  \text{\# of }k\text{-element lacunar subsets of
}\left[  n-1\right]  \right)  \cdot\left(  -1\right)  ^{k}\left(  n-2k\right)
!}\\
&  =\sum_{k=0}^{\left\lceil \left(  n-1\right)  /2\right\rceil }%
\underbrace{\left(  \text{\# of }k\text{-element lacunar subsets of }\left[
n-1\right]  \right)  }_{\substack{=\dbinom{n-k}{k}\\\text{(by
\eqref{sol.pie.dom-free-perms.1})}}}\cdot\left(  -1\right)  ^{k}\left(
n-2k\right)  !\\
&  =\sum_{k=0}^{\left\lceil \left(  n-1\right)  /2\right\rceil }\dbinom
{n-k}{k}\cdot\left(  -1\right)  ^{k}\left(  n-2k\right)  !=\sum_{k=0}%
^{\left\lceil \left(  n-1\right)  /2\right\rceil }\left(  -1\right)
^{k}\dbinom{n-k}{k}\left(  n-2k\right)  !.
\end{align*}
This proves \eqref{sol.pie.dom-free-perms.goal1}.

In order to derive \eqref{sol.pie.dom-free-perms.goal2} from this, we merely
need to show that
\begin{equation}
\dbinom{n-k}{k}\left(  n-2k\right)  !=\dfrac{\left(  n-k\right)  !}%
{k!}\label{sol.pie.dom-free-perms.end-rewrite}%
\end{equation}
for each $k\in\left\{  0,1,\ldots,\left\lceil \left(  n-1\right)
/2\right\rceil \right\}  $. But this is easy: Fix $k\in\left\{  0,1,\ldots
,\left\lceil \left(  n-1\right)  /2\right\rceil \right\}  $. Thus,
$k\leq\left\lceil \left(  n-1\right)  /2\right\rceil <\left(  n-1\right)
/2+1$ (since $\left\lceil x\right\rceil <x+1$ for any real number $x$).
Multiplying both sides of this inequality by $2$, we obtain $2k<2\left(
\left(  n-1\right)  /2+1\right)  =n+1$. Since $2k$ and $n+1$ are integers,
this entails $2k\leq\left(  n+1\right)  -1=n$. Hence, $n-2k\in\mathbb{N}$
and $n-k\geq k$. Hence, Theorem \ref{thm.binom.fac} (applied to $n-k$
instead of $n$) yields
\[
\dbinom{n-k}{k}=\dfrac{\left(  n-k\right)  !}{k!\cdot\left(  \left(
n-k\right)  -k\right)  !}=\dfrac{\left(  n-k\right)  !}{k!\cdot\left(
n-2k\right)  !}\qquad\left(  \text{since }\left(  n-k\right)  -k=n-2k\right)
.
\]
Multiplying both sides of this equality by $\left(  n-2k\right)  !$, we find
$\dbinom{n-k}{k}\left(  n-2k\right)  !=\dfrac{\left(  n-k\right)  !}{k!}$.
Thus, \eqref{sol.pie.dom-free-perms.end-rewrite} is proved. Thus,
\eqref{sol.pie.dom-free-perms.goal2} follows from
\eqref{sol.pie.dom-free-perms.goal1}. This concludes the solution of the exercise.

%----------------------------------------------------------------------------------------
%	EXERCISE 6
%----------------------------------------------------------------------------------------
\rule{\linewidth}{0.3pt} \\[0.4cm]

\section{Exercise 6}

\subsection{Problem}

Recall that a \textit{composition} means a finite list of positive integers.
(For example, $\left(  2, 3, 2 \right)  $ is a composition, but $\left(  1, 0,
4 \right)  $ is not.)

If $n \in\mathbb{N}$, then a \textit{composition of $n$} means a composition
$\left(  i_{1}, i_{2}, \ldots, i_{k} \right)  $ satisfying $i_{1} + i_{2} +
\cdots+ i_{k} = n$.

\begin{enumerate}
\item[\textbf{(a)}] A composition $\left(  i_{1}, i_{2}, \ldots, i_{k}
\right)  $ is said to be \textit{even} if all its entries $i_{1}, i_{2},
\ldots, i_{k}$ are even. Find a formula for the \# of even compositions of a
given $n \in\mathbb{N}$.

\item[\textbf{(b)}] A composition $\left(  i_{1}, i_{2}, \ldots, i_{k}
\right)  $ is said to be \textit{odd} if all its entries $i_{1}, i_{2},
\ldots, i_{k}$ are odd. Find a formula for the \# of odd compositions of a
given $n \in\mathbb{N}$.
\end{enumerate}

\subsection{Solution sketch}

We shall use the following fact (\cite[Exercise 1 \textbf{(b)}]{19f-hw0s}):

\begin{lemma}
\label{lem.num-comps}Let $n\in\mathbb{N}$. Then, the number of compositions of
$n$ is
\[%
\begin{cases}
2^{n-1}, & \text{if }n>0;\\
1, & \text{if }n=0.
\end{cases}
\]

\end{lemma}

\bigskip

\textbf{(a)} We have%
\begin{equation}
\left(  \text{\# of even compositions of }n\right)  =%
\begin{cases}
0, & \text{if }n\text{ is odd};\\
2^{n/2-1}, & \text{if }n\text{ is even and }n>0;\\
1, & \text{if }n=0.
\end{cases}
\label{sol.count.even-comps.goal}%
\end{equation}


[\textit{Proof of \eqref{sol.count.even-comps.goal}:} The empty list $\left(
{}\right)  $ is an even composition of $0$, and is obviously the only
composition of $0$. Hence, $\left(  \text{\# of even compositions of
}0\right)  =1$. Thus, \eqref{sol.count.even-comps.goal} is proved for $n=0$.
Hence, for the rest of this proof, we WLOG assume that $n\neq0$. Thus, $n>0$.

If $\left(  i_{1},i_{2},\ldots,i_{k}\right)  $ is an even composition of $n$,
then $i_{1}+i_{2}+\cdots+i_{k}=n$, and thus $n=i_{1}+i_{2}+\cdots+i_{k}$ is
even (since all addends $i_{1},i_{2},\ldots,i_{k}$ in this sum are
even\footnote{because the composition $\left(  i_{1},i_{2},\ldots
,i_{k}\right)  $ is even}). Hence, an even composition of $n$ cannot exist
unless $n$ is even. In other words, if $n$ is odd, then $\left(  \text{\# of
even compositions of }n\right)  =0$. Thus, \eqref{sol.count.even-comps.goal}
is proved when $n$ is odd. Hence, for the rest of this proof, we WLOG assume
that $n$ is even. Hence, $n/2\in\mathbb{N}$. Also, $n/2>0$ (since $n>0$). Now,
Lemma \ref{lem.num-comps} (applied to $n/2$ instead of $n$) yields that the
number of compositions of $n/2$ is $%
\begin{cases}
2^{n/2-1}, & \text{if }n/2>0;\\
1, & \text{if }n/2=0
\end{cases}
=2^{n/2-1}$ (since $n/2>0$). In other words,%
\[
\left(  \text{\# of compositions of }n/2\right)  =2^{n/2-1}.
\]


But there is a bijection%
\begin{align*}
\left\{  \text{even compositions of }n\right\}   &  \rightarrow\left\{
\text{compositions of }n/2\right\}  ,\\
\left(  i_{1},i_{2},\ldots,i_{k}\right)   &  \mapsto\left(  i_{1}%
/2,i_{2}/2,\ldots,i_{k}/2\right)  .
\end{align*}
Thus, the bijection principle yields%
\[
\left(  \text{\# of even compositions of }n\right)  =\left(  \text{\# of
compositions of }n/2\right)  =2^{n/2-1}.
\]
This proves \eqref{sol.count.even-comps.goal} (since $n$ is even and $n>0$).]

\bigskip

\textbf{(b)} Recall the Fibonacci sequence $\left(  f_{0},f_{1},f_{2}%
,\ldots\right)  $ as defined in \cite[Definition 1.1.10]{notes}. We have%
\begin{equation}
\left(  \text{\# of odd compositions of }n\right)  =%
\begin{cases}
f_{n}, & \text{if }n>0;\\
1, & \text{if }n=0.
\end{cases}
\label{sol.count.even-comps.b.goal}%
\end{equation}


[\textit{Proof of \eqref{sol.count.even-comps.b.goal}:} We proceed by strong
induction on $n$.

Thus, let $m\in\mathbb{N}$, and assume (as the induction hypothesis) that
\eqref{sol.count.even-comps.b.goal} holds for all $n<m$. We must prove that
\eqref{sol.count.even-comps.b.goal} holds for $n=m$.

We WLOG assume that $m\geq3$, since it is straightforward to verify that
\eqref{sol.count.even-comps.b.goal} holds for all $n<3$. Thus, the induction
hypothesis shows that \eqref{sol.count.even-comps.b.goal} holds for $n=m-1$
and for $n=m-2$. In other words, we have%
\[
\left(  \text{\# of odd compositions of }m-1\right)  =%
\begin{cases}
f_{m-1}, & \text{if }m-1>0;\\
1, & \text{if }m-1=0
\end{cases}
\]
and%
\[
\left(  \text{\# of odd compositions of }m-2\right)  =%
\begin{cases}
f_{m-2}, & \text{if }m-2>0;\\
1, & \text{if }m-2=0.
\end{cases}
\]


Now, let us call an odd composition of $m$

\begin{itemize}
\item \textbf{red} if its last entry is $1$, and

\item \textbf{green} if its last entry is not $1$.
\end{itemize}

\noindent(Note that its last entry is always well-defined, since a composition
of the positive integer $m$ cannot be empty. Likewise, a composition of
$m-1$ and $m-2$ cannot be empty (since $m-1$ and $m-2$, too, are positive
integers), and thus its last entry is well-defined.)

Now, there is a bijection%
\begin{align*}
\left\{  \text{red odd compositions of }m\right\}   &  \rightarrow\left\{
\text{odd compositions of }m-1\right\}  ,\\
\left(  i_{1},i_{2},\ldots,i_{k},1\right)   &  \mapsto\left(  i_{1}%
,i_{2},\ldots,i_{k}\right)  .
\end{align*}
Hence, the bijection principle yields%
\begin{align*}
&  \left(  \text{\# of red odd compositions of }m\right) \\
&  =\left(  \text{\# of odd compositions of }m-1\right)  =%
\begin{cases}
f_{m-1}, & \text{if }m-1>0;\\
1, & \text{if }m-1=0
\end{cases}
\\
&  =f_{m-1}\qquad\left(  \text{since }m-1>0\text{ (because }m\geq
3>1\text{)}\right)  .
\end{align*}


Also, if an odd composition $\left(  i_{1},i_{2},\ldots,i_{k}\right)  $ of $m$
is green, then its last entry $i_{k}$ is not $1$ (by the definition of
\textquotedblleft green\textquotedblright) and therefore must be $\geq3$
(since it is odd\footnote{by the definition of an odd composition}). Thus, if
an odd composition $\left(  i_{1},i_{2},\ldots,i_{k}\right)  $ of $m$ is
green, then $i_{k}\geq3>2$ and therefore $i_{k}-2>0$. Hence, there is a
bijection%
\begin{align*}
\left\{  \text{green odd compositions of }m\right\}   &  \rightarrow\left\{
\text{odd compositions of }m-2\right\}  ,\\
\left(  i_{1},i_{2},\ldots,i_{k}\right)   &  \mapsto\left(  i_{1},i_{2}%
,\ldots,i_{k-1},i_{k}-2\right)  .
\end{align*}
Hence, the bijection principle yields%
\begin{align*}
&  \left(  \text{\# of green odd compositions of }m\right) \\
&  =\left(  \text{\# of odd compositions of }m-2\right)  =%
\begin{cases}
f_{m-2}, & \text{if }m-2>0;\\
1, & \text{if }m-2=0
\end{cases}
\\
&  =f_{m-2}\qquad\left(  \text{since }m-2>0\text{ (because }m\geq
3>2\text{)}\right)  .
\end{align*}


But clearly, any odd composition of $m$ is either red or green (but not both
at the same time). Hence, the sum rule yields%
\begin{align*}
&  \left(  \text{\# of odd compositions of }m\right) \\
&  =\underbrace{\left(  \text{\# of red odd compositions of }m\right)
}_{=f_{m-1}}+\underbrace{\left(  \text{\# of green odd compositions of
}m\right)  }_{=f_{m-2}}\\
&  =f_{m-1}+f_{m-2}=f_{m}%
\end{align*}
(since the definition of the Fibonacci sequence yields $f_{m}=f_{m-1}+f_{m-2}%
$). Comparing this with%
\[%
\begin{cases}
f_{m}, & \text{if }m>0;\\
1, & \text{if }m=0
\end{cases}
=f_{m}\qquad\left(  \text{since }m\geq3>0\right)  ,
\]
we obtain
\[
\left(  \text{\# of odd compositions of }m\right)  =%
\begin{cases}
f_{m}, & \text{if }m>0;\\
1, & \text{if }m=0
\end{cases}
.
\]
In other words, \eqref{sol.count.even-comps.b.goal} holds for $n=m$. This
completes the inductive proof of \eqref{sol.count.even-comps.b.goal}.]

\subsection{Remark}

There are many other ways to solve either part of the exercise. In particular,
there is a solution to part \textbf{(a)} that proceeds similarly to our
solution to part \textbf{(b)} (i.e., by strong induction, using the $n=m-2$
case). See also \cite{Sills11} for results related to odd compositions.

\begin{thebibliography}{99999999}                                                                                         %


\bibitem[17f-hw7s]{17f-hw7s}Darij Grinberg, \textit{UMN Fall 2017 Math 4990
homework set \#7 with solutions}, \url{http://www.cip.ifi.lmu.de/~grinberg/t/17f/hw7os.pdf}

\bibitem[18f-hw3s]{18f-hw3s}Darij Grinberg, \textit{UMN Fall 2018 Math 5705
homework set \#3 with solutions}, \url{http://www.cip.ifi.lmu.de/~grinberg/t/18f/hw3s.pdf}

\bibitem[19f-hw0s]{19f-hw0s}Darij Grinberg, \textit{Drexel Fall 2019 Math 222
homework set \#0 with solutions}, \url{http://www.cip.ifi.lmu.de/~grinberg/t/19fco/hw0s.pdf}

\bibitem[19f-hw3s]{19f-hw3s}Darij Grinberg, \textit{Drexel Fall 2019 Math 222
homework set \#3 with solutions}, \url{http://www.cip.ifi.lmu.de/~grinberg/t/19fco/hw3s.pdf}

\bibitem[19f-mt1s]{19f-mt1s}Darij Grinberg, \textit{Drexel Fall 2019 Math 222
midterm \#1 with solutions}, \url{http://www.cip.ifi.lmu.de/~grinberg/t/19fco/mt1s.pdf}

\bibitem[DuaOli13]{DuaOli13}Rui Duarte, Ant\'{o}nio Guedes de Oliveira,
\textit{A short proof of a famous combinatorial identity},
arXiv:1307.6693v1.\newline\url{https://arxiv.org/abs/1307.6693v1}

\bibitem[Galvin17]{Galvin}David Galvin, \textit{Basic discrete mathematics},
13 December 2017.\newline%
\url{http://www-users.math.umn.edu/~dgrinber/comb/60610lectures2017-Galvin.pdf}
\newline(The URL might change, and the text may get updated. In order to
reliably obtain the version of 13 December 2017, you can use the archive.org
Wayback Machine:
\url{https://web.archive.org/web/20180205122609/http://www-users.math.umn.edu/~dgrinber/comb/60610lectures2017-Galvin.pdf}
.)

\bibitem[Grinbe15]{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[Math222]{notes}
Darij Grinberg,
\textit{Enumerative Combinatorics: class notes},
16 December 2019. \\
\url{http://www.cip.ifi.lmu.de/~grinberg/t/19fco/n/n.pdf} 
Also available on the mirror server
\url{http://darijgrinberg.gitlab.io/t/19fco/n/n.pdf} \\
\textbf{Caution:}
The numbering of theorems and formulas in this link might shift when the
project gets updated; for a ``frozen'' version whose
numbering is guaranteed to match that in the citations above, see
\url{https://gitlab.com/darijgrinberg/darijgrinberg.gitlab.io/blob/2dab2743a181d5ba8fc145a661fd274bc37d03be/public/t/19fco/n/n.pdf}
% Check that this is the numbering you want.


\bibitem[Sills11]{Sills11}Andrew V. Sills, \textit{Compositions, Partitions,
and Fibonacci Numbers}, Fibonacci Quarterly 40 (2011), pp. 348--354,
arXiv:1312.0693v1.\newline\url{https://arxiv.org/abs/1312.0693v1}
\end{thebibliography}


\end{document}