\documentclass[numbers=enddot,12pt,final,onecolumn,notitlepage]{scrartcl}%
\usepackage{amsfonts}
\usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage}
\usepackage[all,cmtip]{xy}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{framed}
\usepackage{comment}
\usepackage{color}
\usepackage{hyperref}
\usepackage{ifthen}
\usepackage[sc]{mathpazo}
\usepackage[T1]{fontenc}
\usepackage{needspace}
\usepackage{tabls}
\usepackage{tikz}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Wednesday, February 21, 2018 19:11:43}
%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}}
\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): homework set 2}
\ohead{page \thepage}
\cfoot{}
\begin{document}

\begin{center}
\textbf{Math 4707 Spring 2018 (Darij Grinberg): homework set 2}

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

Please solve \textbf{at most 3} of the 7 exercises!
\end{center}

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).

See \cite[solution to Exercise 8]{fall2017-hw1s} for an example of how a
counting proof can be written.

Recall that if $n \in\mathbb{N}$, then $\left[  n \right]  $ denotes the
$n$-element set $\left\{  1, 2, \ldots, n \right\}  $.

\subsection{Instances of the \textquotedblleft Laurent
phenomenon\textquotedblright: Sequences that produce integers despite division
in their definition}

There is a whole genre of theorem where you define a sequence recursively and
then it turns out that all entries of the sequence are integers, although this
is not obvious from the definition.

Here are two results from this genre, illustrating strategic use of induction.

\begin{exercise}
\label{exe.laurent.t}Define a sequence $\left(  t_{0},t_{1},t_{2}%
,\ldots\right)  $ of positive rational numbers recursively by setting%
\begin{align*}
t_{0}  &  =1,\ \ \ \ \ \ \ \ \ \ t_{1}=1,\ \ \ \ \ \ \ \ \ \ t_{2}%
=1,\ \ \ \ \ \ \ \ \ \ \text{and}\\
t_{n}  &  =\dfrac{1+t_{n-1}t_{n-2}}{t_{n-3}}\ \ \ \ \ \ \ \ \ \ \text{for each
}n\geq3.
\end{align*}
(For example, $t_{3}=\dfrac{1+t_{2} t_{1}}{t_{0}}=\dfrac{1+1\cdot1}{1}=2$ and
$t_{4} =\dfrac{1+t_{3} t_{2}}{t_{1}}=\dfrac{1+2\cdot1}{1}=3$.)

\textbf{(a)} Prove that $t_{n+2}=4t_{n}-t_{n-2}$ for each $n\geq2$.

\textbf{(b)} Prove that $t_{n}\in\mathbb{N}$ for each $n\in\mathbb{N}$.

\textbf{[Hint:} First prove part \textbf{(a)} by induction on $n$. Then prove
part \textbf{(b)} by induction on $n$, using part \textbf{(a)}.]
\end{exercise}

\begin{exercise}
\label{exe.laurent.ml}Fix a positive integer $r$. Define a sequence $\left(
b_{0},b_{1},b_{2},\ldots\right)  $ of positive rational numbers recursively by
setting%
\begin{align*}
b_{0}  &  =1,\ \ \ \ \ \ \ \ \ \ b_{1}=1,\ \ \ \ \ \ \ \ \ \ \text{and}\\
b_{n}  &  =\dfrac{b_{n-1}^{r}+1}{b_{n-2}}\ \ \ \ \ \ \ \ \ \ \text{for each
}n\geq2.
\end{align*}
(For example, $b_{2}=\dfrac{b_{1}^{r}+1}{b_{0}}=\dfrac{1^{r}+1}{1}=2$ and
$b_{3}=\dfrac{b_{2}^{r}+1}{b_{1}}=\dfrac{2^{r}+1}{1}=2^{r}+1$.)

\textbf{(a)} Prove that $b_{n}\in\mathbb{N}$ for each $n\in\mathbb{N}$.

\textbf{(b)} If $r\geq2$, then prove that $b_{n}\mid b_{n-2}+b_{n+2}$ for each
$n\geq2$.

[\textbf{Hint:} For every nonzero $x\in\mathbb{Q}$, we set $H\left(  x\right)
=\dfrac{\left(  x+1\right)  ^{r}-1}{x}$. Show that $H\left(  x\right)
\in\mathbb{Z}$ whenever $x$ is a nonzero integer. Next, show that
$b_{n+2}=b_{n-2}b_{n+1}^{r}-b_{n}^{r-1}H\left(  b_{n}^{r}\right)  $ for each
$n\geq2$. Use this to prove \textbf{(a)}.]
\end{exercise}

\subsection{Lacunar subsets with a given number of even and a given number of
odd elements}

Recall the following definition: A set $S$ of integers is said to be
\textit{lacunar} if no two consecutive integers occur in $S$ (that is, there
exists no $i\in\mathbb{Z}$ such that both $i$ and $i+1$ belong to $S$). For
example, $\left\{  1,3,6\right\}  $ is lacunar, but $\left\{  2,4,5\right\}  $
is not. (The empty set and any $1$-element set are lacunar, of course.)

Also recall the \textit{Iverson bracket notation:} If $\mathcal{A}$ is any
logical statement, then the \textit{truth value} of $\mathcal{A}$ is defined
to be the integer
\[%
\begin{cases}
1, & \text{if }\mathcal{A}\text{ is true};\\
0, & \text{if }\mathcal{A}\text{ is false}%
\end{cases}
\in\left\{  0, 1 \right\}  .
\]
This truth value is denoted by $\left[  \mathcal{A} \right]  $. For example,
$\left[  1+1=2\right]  =1$ (since $1+1=2$ is true), whereas $\left[
1+1=1\right]  =0$ (since $1+1=1$ is false).

\begin{exercise}
\label{exe.count.lacunar-oe}For any $n\in\mathbb{N}$, $a\in\mathbb{Z}$ and
$b\in\mathbb{Z}$, we let $N\left(  n,a,b\right)  $ denote the number of all
lacunar subsets of $\left[  n\right]  $ that contain exactly $a$ even and
exactly $b$ odd elements.

\textbf{(a)} Prove that $N\left(  2m,a,b\right)  = \left[  a \leq m \right]
\left[  b \leq m \right]  \dbinom{m-a}{b}\dbinom{m-b}{a}$ for all
$m\in\mathbb{N}$, $a\in\mathbb{N}$ and $b\in\mathbb{N}$.

\textbf{(b)} Prove that $N\left(  2m+1,a,b\right)  = \left[  a \leq m \right]
\left[  b \leq m+1 \right]  \dbinom{m+1-a}{b}\dbinom{m-b}{a}$ for all
$m\in\mathbb{N}$, $a\in\mathbb{N}$ and $b\in\mathbb{N}$.

[\textbf{Hint:} One way is to prove parts \textbf{(a)} and \textbf{(b)}
simultaneously by induction (that is, let $\mathcal{A}\left(  m\right)  $ be
the statement \textquotedblleft$N\left(  2m,a,b\right)  =\left[  a \leq m
\right]  \left[  b \leq m \right]  \dbinom{m-a}{b}\dbinom{m-b}{a}$ and
$N\left(  2m+1,a,b\right)  =\left[  a \leq m \right]  \left[  b \leq m+1
\right]  \dbinom{m+1-a}{b}\dbinom{m-b}{a}$ for all $a\in\mathbb{N}$ and
$b\in\mathbb{N}$\textquotedblright, and prove this by induction on $m$). One
part of the induction step is an expression for $N\left(  2m+2,a,b\right)  $
through $N\left(  2m+1,a,b\right)  $ and $N\left(  2m,a-1,b\right)  $. Another
similar expression will be needed for $N\left(  2m+3,a,b\right)  $. Make sure
to treat the base case properly, as well as justifying the switch between the
truth values necessary at one point in the induction step. There is also a
bijective proof.]
\end{exercise}

\subsection{Delannoy numbers}

Fix two positive integers $r$ and $s$.

If $\left(  a,b\right)  \in\mathbb{Z}^{2}$ and $\left(  c,d\right)
\in\mathbb{Z}^{2}$ are two points on the integer lattice, then a
\textit{$\left(  r,s \right)  $-Delannoy path} from $\left(  a,b\right)  $ to
$\left(  c,d\right)  $ is a path from $\left(  a,b\right)  $ to $\left(
c,d\right)  $ that uses only three kinds of steps:

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

\item right-steps ($R$), which have the form $\left(  x,y\right)
\mapsto\left(  x+1,y\right)  $;

\item diagonal steps ($D$), which have the form $\left(  x,y\right)
\mapsto\left(  x+r,y+s\right)  $.
\end{itemize}

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

For two integers $n$ and $m$, we let $d_{n,m}$ be the number of $\left(  r,s
\right)  $-Delannoy paths from $\left(  0,0\right)  $ to $\left(  n,m\right)
$. (This depends on $r$ and $s$, too, but we regard $r$ and $s$ as fixed.)
Note that $d_{n,m}=0$ if (at least) one of $n$ and $m$ is negative (because
neither the x-coordinate nor the y-coordinate can ever decrease along an
$\left(  r,s \right)  $-Delannoy path).

For example, if $r = 1$ and $s = 1$, then $d_{2,1}=5$, the five $\left(  1,1
\right)  $-Delannoy paths being $RRU$, $RD$, $RUR$, $DR$ and $URR$. Here are
these five paths drawn in the plane:
\[
\begin{tikzpicture}
\delannoypath{0,0}{2}{1}{1,1,0};
\end{tikzpicture},\qquad\begin{tikzpicture}
\delannoypath{0,0}{2}{1}{1,2};
\end{tikzpicture},\qquad\begin{tikzpicture}
\delannoypath{0,0}{2}{1}{1,0,1};
\end{tikzpicture},\qquad\begin{tikzpicture}
\delannoypath{0,0}{2}{1}{2,1};
\end{tikzpicture},\qquad\begin{tikzpicture}
\delannoypath{0,0}{2}{1}{0,1,1};
\end{tikzpicture}.
\]


\begin{exercise}
\label{exe.delannoy1}(\textbf{a)} Show that $d_{n,m}=d_{n-1,m}+d_{n,m-1}%
+d_{n-r,m-s}$ for all $n\in\mathbb{N}$ and $m\in\mathbb{N}$, unless $\left(
n,m\right)  =\left(  0,0\right)  $.

\textbf{(b)} Show that
\[
d_{n,m}=\sum_{k=0}^{n} \left[  n+m \geq\left(  r+s-1 \right)  k \right]
\binom{n - \left(  r-1 \right)  k}{k}\binom{n+m-\left(  r+s-1 \right)  k}{n -
\left(  r-1 \right)  k}%
\]
for all $n\in\mathbb{N}$ and $m\in\mathbb{N}$.

\textbf{(c)} Assume that $r = s$. Show that $d_{n,m}=d_{m,n}$ for all
$n\in\mathbb{N}$ and $m\in\mathbb{N}$.

[\textbf{Hint:} The case $r = 1$ and $s = 1$ is studied in \cite[\S 28]%
{Galvin}.]
\end{exercise}

\begin{comment}
\begin{exercise}
\label{exe.delannoy2}Assume that $r = 1$ and $s = 1$.
Let $n\in\mathbb{N}$ and $m\in\mathbb{N}$. Show that%
\[
d_{n,m}=\sum_{j=0}^{n}2^{j}\dbinom{n}{j}\dbinom{m}{j}.
\]
[\textbf{Hint:} This can be derived algebraically from Exercise
\ref{exe.delannoy1} \textbf{(b)} (which you can use even if you did not solve
it). The first step is to rewrite $\dbinom{n+m-k}{n}$ as $\sum_{j=0}%
^{n}\dbinom{n-k}{n-j}\dbinom{m}{j}$ using Vandermonde convolution. Try to use
trinomial revision afterwards. There are also other proofs.]
\end{exercise}
\end{comment}


\subsection{On inclusion/exclusion}

One version of the Principle of Inclusion and Exclusion is the following
theorem (see, e.g., \cite[Theorem 16.1 and (11)]{Galvin}):

\begin{theorem}
\label{thm.pie}Let $n\in\mathbb{N}$. Let $A_{1},A_{2},\ldots,A_{n}$ be finite sets.

\textbf{(a)} We have%
\[
\left\vert \bigcup_{i=1}^{n}A_{i}\right\vert =\sum_{\substack{I\subseteq
\left[  n\right]  ;\\I\neq\varnothing}}\left(  -1\right)  ^{\left\vert
I\right\vert -1}\left\vert \bigcap_{i\in I}A_{i}\right\vert .
\]


\textbf{(b)} Let $S$ be a finite set. Assume that each of $A_{1},A_{2}%
,\ldots,A_{n}$ is a subset of $S$. Then,%
\[
\left\vert S\setminus\bigcup_{i=1}^{n}A_{i}\right\vert =\sum_{I\subseteq
\left[  n\right]  }\left(  -1\right)  ^{\left\vert I\right\vert }\left\vert
\bigcap_{i\in I}A_{i}\right\vert .
\]
Here, the \textquotedblleft empty\textquotedblright\ intersection
$\bigcap_{i\in\varnothing}A_{i}$ is understood to mean the set $S$.
\end{theorem}

Here is another way to write Theorem \ref{thm.pie} \textbf{(a)}:

\begin{corollary}
\label{cor.pie.seq}Let $n\in\mathbb{N}$. Let $A_{1},A_{2},\ldots,A_{n}$ be
finite sets. Then,%
\[
\left\vert A_{1}\cup A_{2}\cup\cdots\cup A_{n}\right\vert =\sum_{k=1}%
^{n}\left(  -1\right)  ^{k-1}\sum_{1\leq i_{1}<i_{2}<\cdots<i_{k}\leq
n}\left\vert A_{i_{1}}\cap A_{i_{2}}\cap\cdots\cap A_{i_{k}}\right\vert .
\]

\end{corollary}

\begin{exercise}
\label{exe.pie.min}Let $n$ be a positive integer. Let $a_{1},a_{2}%
,\ldots,a_{n}$ be $n$ integers. Prove that%
\begin{align}
&  \max\left\{  a_{1},a_{2},\ldots,a_{n}\right\}  \nonumber\\
&  =\sum_{k=1}^{n}\left(  -1\right)  ^{k-1}\sum_{1\leq i_{1}<i_{2}%
<\cdots<i_{k}\leq n}\min\left\{  a_{i_{1}},a_{i_{2}},\ldots,a_{i_{k}}\right\}
.\label{eq.exe.pie.min.eq}%
\end{align}


For example, if $n=3$, then this says that%
\begin{align*}
\max\left\{  a_{1},a_{2},a_{3}\right\}   &  =\min\left\{  a_{1}\right\}
+\min\left\{  a_{2}\right\}  +\min\left\{  a_{3}\right\} \\
&  \ \ \ \ \ \ \ \ \ \ -\min\left\{  a_{1},a_{2}\right\}  -\min\left\{
a_{1},a_{3}\right\}  -\min\left\{  a_{2},a_{3}\right\} \\
&  \ \ \ \ \ \ \ \ \ \ +\min\left\{  a_{1},a_{2},a_{3}\right\}  .
\end{align*}


[\textbf{Hint:} You can derive this from Corollary \ref{cor.pie.seq} by
constructing $n$ sets $A_{1},A_{2},\ldots,A_{n}$ such that $\left\vert
A_{i_{1}}\cap A_{i_{2}}\cap\cdots\cap A_{i_{k}}\right\vert =\min\left\{
a_{i_{1}},a_{i_{2}},\ldots,a_{i_{k}}\right\}  $, if the $a_{i}$ are
nonnegative. If some $a_{i}$ are negative, a slight tweak is required.
Alternatively, and perhaps more easily, there is a proof without using the
Principle of Inclusion and Exclusion.

Note that (\ref{eq.exe.pie.min.eq}) can be rewritten as%
\begin{equation}
\max\left\{  a_{1},a_{2},\ldots,a_{n}\right\}  =\sum_{\substack{I\subseteq
\left[  n\right]  ;\\I\neq\varnothing}}\left(  -1\right)  ^{\left\vert
I\right\vert -1}\min\left\{  a_{i}\ \mid\ i\in I\right\}  .
\label{eq.exe.pie.min.eq2}%
\end{equation}
It might be easier to prove this equivalent form.]
\end{exercise}

\subsection{Not-quite-derangements}

\begin{exercise}
\label{exe.pie.nqd}Let $n$ be a positive integer. An \textit{nqd}
(\textquotedblleft not-quite-derangement\textquotedblright) of $\left[
n\right]  $ shall denote a permutation $\sigma$ of $\left[  n\right]  $ such
that every $i\in\left[  n-1\right]  $ satisfies $\sigma\left(  i\right)  \neq
i+1$. Prove that the number of nqds of $\left[  n\right]  $ is%
\[
\left(  n-1\right)  !\sum_{k=0}^{n-1}\left(  -1\right)  ^{k}\cdot\dfrac
{n-k}{k!}.
\]

\end{exercise}

(Compare with the formula, proven in \cite[\S 16]{Galvin}, which says that the
number of derangements of $\left[  n\right]  $ is $n!\sum_{k=0}^{n}\left(
-1\right)  ^{k}\cdot\dfrac{1}{k!}$.)

\subsection{Socks}

\begin{exercise}
Let $n$ and $s$ be two even positive integers. Let $q$ and $r$ be the quotient
and the remainder of division of $n$ by $s$. (Thus, $q \in\mathbb{Z}$, $r
\in\left\{  0, 1, \ldots, s-1 \right\}  $ and $n = qs + r$.)

Assume that $n$ socks are hanging on a clothesline, with $n/2$ of these socks
being black and the remaining $n/2$ white.

A \textit{balanced window} will mean a choice of $s$ consecutive socks on the
clothesline such that $s/2$ of these socks are black and the remaining $s/2$
are white.

\textbf{(a)} If $r < 2q$, then show that there is a balanced window.

\textbf{(b)} If $s \leq2q + r$, then show that there is a balanced window.

[\textbf{Hint:} Number the socks by $1, 2, \ldots, n$ in the order in which
they appear on the clothesline. For each $i \in\left[  n-s+1 \right]  $,
define the integer
\[
b_{i} = \left(  \text{the number of black socks among socks } i, i+1, \ldots,
i+s-1 \right)  - s/2 .
\]
Proceed as in class, and take a look at the last $r$ socks on the clothesline
(i.e., those not counted in $b_{1}, b_{s+1}, b_{2s+1}, \ldots, b_{\left(  q-1
\right)  s+1}$). For part \textbf{(b)}, take a closer look at the last $s$
socks on the clothesline.]
\end{exercise}

(In class, we mostly considered the case when $n = 30$ and $s = 10$; this
falls under the situation of part \textbf{(a)}. For an example of part
\textbf{(b)}, try $n = 26$ and $s = 10$.)

\begin{remark}
A converse can also be shown: If neither $r < 2q$ nor $s \leq2q + r$ holds,
then one can place $n$ socks ($n/2$ black, $n/2$ white) on a clothesline in
such a way that no balanced window exists.
\end{remark}

\begin{thebibliography}{9999999999999}                                                                                    %


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

\bibitem[Fall2017-HW1s]{fall2017-hw1s}Darij Grinberg, \textit{Math 4707 \&
Math 4990 Fall 2017 (Darij Grinberg): homework set 1 with solutions.}\newline\url{http://www.cip.ifi.lmu.de/~grinberg/t/17f/hw1s.pdf}
\end{thebibliography}


\end{document}