\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=Saturday, April 14, 2018 22:20:06}
%TCIDATA{SuppressPackageManagement}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%BeginMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
%EndMSIPreambleData
\newcounter{exer}
\theoremstyle{definition}
\newtheorem{theo}{Theorem}[section]
\newenvironment{theorem}[1][]
{\begin{theo}[#1]\begin{leftbar}}
{\end{leftbar}\end{theo}}
\newtheorem{lem}[theo]{Lemma}
\newenvironment{lemma}[1][]
{\begin{lem}[#1]\begin{leftbar}}
{\end{leftbar}\end{lem}}
\newtheorem{prop}[theo]{Proposition}
\newenvironment{proposition}[1][]
{\begin{prop}[#1]\begin{leftbar}}
{\end{leftbar}\end{prop}}
\newtheorem{defi}[theo]{Definition}
\newenvironment{definition}[1][]
{\begin{defi}[#1]\begin{leftbar}}
{\end{leftbar}\end{defi}}
\newtheorem{remk}[theo]{Remark}
\newenvironment{remark}[1][]
{\begin{remk}[#1]\begin{leftbar}}
{\end{leftbar}\end{remk}}
\newtheorem{coro}[theo]{Corollary}
\newenvironment{corollary}[1][]
{\begin{coro}[#1]\begin{leftbar}}
{\end{leftbar}\end{coro}}
\newtheorem{conv}[theo]{Convention}
\newenvironment{condition}[1][]
{\begin{conv}[#1]\begin{leftbar}}
{\end{leftbar}\end{conv}}
\newtheorem{quest}[theo]{Question}
\newenvironment{algorithm}[1][]
{\begin{quest}[#1]\begin{leftbar}}
{\end{leftbar}\end{quest}}
\newtheorem{warn}[theo]{Warning}
\newenvironment{conclusion}[1][]
{\begin{warn}[#1]\begin{leftbar}}
{\end{leftbar}\end{warn}}
\newtheorem{conj}[theo]{Conjecture}
\newenvironment{conjecture}[1][]
{\begin{conj}[#1]\begin{leftbar}}
{\end{leftbar}\end{conj}}
\newtheorem{exam}[theo]{Example}
\newenvironment{example}[1][]
{\begin{exam}[#1]\begin{leftbar}}
{\end{leftbar}\end{exam}}
\newtheorem{exmp}[exer]{Exercise}
\newenvironment{exercise}[1][]
{\begin{exmp}[#1]\begin{leftbar}}
{\end{leftbar}\end{exmp}}
\newenvironment{statement}{\begin{quote}}{\end{quote}}
\newenvironment{fns}{\begin{footnotesize}}{\end{footnotesize}}
\iffalse
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\fi
\let\sumnonlimits\sum
\let\prodnonlimits\prod
\let\cupnonlimits\bigcup
\let\capnonlimits\bigcap
\renewcommand{\sum}{\sumnonlimits\limits}
\renewcommand{\prod}{\prodnonlimits\limits}
\renewcommand{\bigcup}{\cupnonlimits\limits}
\renewcommand{\bigcap}{\capnonlimits\limits}
\setlength\tablinesep{3pt}
\setlength\arraylinesep{3pt}
\setlength\extrarulesep{3pt}
\voffset=0cm
\hoffset=-0.7cm
\setlength\textheight{22.5cm}
\setlength\textwidth{15.5cm}
\newenvironment{verlong}{}{}
\newenvironment{vershort}{}{}
\newenvironment{noncompile}{}{}
\excludecomment{verlong}
\includecomment{vershort}
\excludecomment{noncompile}
\newcommand{\id}{\operatorname{id}}
\newcommand{\rev}{\operatorname{rev}}
\newcommand{\conncomp}{\operatorname{conncomp}}
\newcommand{\conn}{\operatorname{conn}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\powset}[2][]{\ifthenelse{\equal{#2}{}}{\mathcal{P}\left(#1\right)}{\mathcal{P}_{#1}\left(#2\right)}}
\newcommand{\set}[1]{\left\{ #1 \right\}}
\newcommand{\abs}[1]{\left| #1 \right|}
\newcommand{\tup}[1]{\left( #1 \right)}
\newcommand{\ive}[1]{\left[ #1 \right]}
\newcommand{\verts}[1]{\operatorname{V}\left( #1 \right)}
\newcommand{\edges}[1]{\operatorname{E}\left( #1 \right)}
\newcommand{\arcs}[1]{\operatorname{A}\left( #1 \right)}
\newcommand{\underbrack}[2]{\underbrace{#1}_{\substack{#2}}}
\newcommand{\are}{\ar@{-}}
\newcommand{\arebi}[1][]{\ar@{<-}@/_/[#1] \ar@/^/[#1]}
\newcommand\staircasepath[4]{
\fill[cyan!25]  (#1) rectangle +(#2,#3);
\fill[fill=lime]
(#1)
\foreach \dir in {#4}{
\ifnum\dir=1
-- ++(1,0)
\else
-- ++(0,1)
\fi
} |- (#1);
\draw[help lines] (#1) grid +(#2,#3);
\draw[dashed] (#1) -- +(#2,#2);
\coordinate (prev) at (#1);
\foreach \dir in {#4}{
\ifnum\dir=1
\coordinate (dep) at (1,0);
\else
\coordinate (dep) at (0,1);
\fi
\draw[line width=2pt,-stealth] (prev) -- ++(dep) coordinate (prev);
};
}
\newcommand\delannoypath[4]{
\fill[cyan!25]  (#1) rectangle +(#2,#3);
\fill[fill=lime]
(#1)
\foreach \dir in {#4}{
\ifnum\dir=1
-- ++(1,0)
\else
	  \ifnum\dir=0
-- ++(0,1)
	  \else
	  -- ++(1,1)
	  \fi
\fi
} |- (#1);
\draw[help lines] (#1) grid +(#2,#3);
\coordinate (prev) at (#1);
\foreach \dir in {#4}{
\ifnum\dir=1
\coordinate (dep) at (1,0);
\else
	  \ifnum\dir=0
\coordinate (dep) at (0,1);
	  \else
	  \coordinate (dep) at (1,1);
	  \fi
\fi
\draw[line width=2pt,-stealth] (prev) -- ++(dep) coordinate (prev);
};
}
\newcommand\dyckpath[3]{
\fill[fill=lime]
(#1)
\foreach \dir in {#3}{
\ifnum\dir=1
-- ++(1,-1)
\else
-- ++(1,1)
\fi
} |- (#1);
\draw[help lines] (#1) grid +(2*#2, #2);
\coordinate (prev) at (#1);
\foreach \dir in {#3}{
\ifnum\dir=1
\coordinate (dep) at (1,-1);
\else
\coordinate (dep) at (1,1);
\fi
\draw[line width=2pt,-stealth] (prev) -- ++(dep) coordinate (prev);
};
}
\ihead{Math 4707 Spring 2018 (Darij Grinberg): midterm 2}
\ohead{page \thepage}
\cfoot{}
\begin{document}

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

due date: Wednesday 4 April 2018 at the beginning of class, or before that by
email or moodle

Please solve \textbf{at most 4} of the 6 exercises!

\textbf{Collaboration is not allowed!}
\end{center}

%

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


\bigskip

Please write your name on each page. Feel free to use LaTeX
(\href{http://www.cip.ifi.lmu.de/~grinberg/t/18s/hw-template.tex}{here} is
a sample file with lots of amenities included).

Recall the following:

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

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

\subsection{Counting first-even tuples}

\begin{exercise}
Let $n$ and $d$ be two positive integers.

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

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

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

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

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

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

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

For any $n\in\mathbb{Z}$ and $m\in\mathbb{Z}$, we let $L_{n,m}$ be the number
of all legal lattice paths from $\left(  0,0\right)  $ to $\left(  n,m\right)
$. Clearly, $L_{n,m}=0$ if any of $n$ and $m$ is negative. Also, $L_{n,m}=0$
if $m>n$ (because if $m>n$, then the point $\left(  n,m\right)  $ is off-limits).

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

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

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

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

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

[You \textbf{cannot} use generating functions in this exercise.]

[\textbf{Hint:} You may know part \textbf{(d)} from Vic's lectures, but the
whole exercise can be solved by induction without recourse to any of what Vic
did -- I even think this is the easiest way to solve it!]
\end{exercise}

\subsection{Scary fractions}

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

\end{exercise}

\subsection{Derangements that are involutions}

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

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

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

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

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

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

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

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

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

\subsection{Hypergreen permutations}

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

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

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

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

\subsection{Counting the parts of all compositions}

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

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

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

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


\end{document}