\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}
\usepackage{ytableau}
\usepackage{skak}
\usepackage{rotating}
\usepackage[framemethod=tikz]{mdframed}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Tuesday, March 27, 2018 23:18:37}
%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{\lf}[2]{{#1}^{\underline{#2}}}
\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 4}
\ohead{page \thepage}
\cfoot{}
\begin{document}

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

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

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

%

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


\bigskip

Recall the following:

\begin{itemize}
\item We have $\mathbb{N}=\left\{  0,1,2,\ldots\right\}  $.

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

\item For each $n\in\mathbb{N}$, we let $S_{n}$ denote the set of all
permutations of $\left[  n\right]  $.
\end{itemize}

\subsection{Permutations $\sigma$ with $\sigma\left(  2\right)  =\sigma\left(
1\right)  +1$}

\begin{exercise}
Let $n\geq2$ be an integer. Prove that there are precisely $\left(
n-1\right)  !$ permutations $\sigma\in S_{n}$ satisfying $\sigma\left(
2\right)  =\sigma\left(  1\right)  +1$.
\end{exercise}

\subsection{An introduction to rook theory}

\begin{definition}
For any $x\in\mathbb{R}$ and $n\in\mathbb{N}$, we let $x^{\underline{n}}$
denote the \textquotedblleft$n$-th lower factorial of $x$\textquotedblright;
this is the real number $x\left(  x-1\right)  \cdots\left(  x-n+1\right)  $.
(Thus, $x^{\underline{n}}=n!\cdot\dbinom{x}{n}$.)
\end{definition}

For example, $x^{\underline{0}}=1$, $x^{\underline{1}}=x$, $x^{\underline{2}%
}=x\left(  x-1\right)  $, etc.\footnote{For all \LaTeX\ users:
$x^{\underline{n}}$ is \textquotedblleft\texttt{x\symbol{94}\{%
%TCIMACRO{\TEXTsymbol{\backslash}}%
%BeginExpansion
$\backslash$%
%EndExpansion
underline\{n\}\}}\textquotedblright. Feel free to create a macro for this,
e.g., by putting the following line into the header of your TeX file (along
with the other \textquotedblleft VARIOUS USEFUL COMMANDS\textquotedblright):
\par
\texttt{%
%TCIMACRO{\TEXTsymbol{\backslash}}%
%BeginExpansion
$\backslash$%
%EndExpansion
newcommand\{%
%TCIMACRO{\TEXTsymbol{\backslash}}%
%BeginExpansion
$\backslash$%
%EndExpansion
lf\}[2]\{\{\#1\}\symbol{94}\{%
%TCIMACRO{\TEXTsymbol{\backslash}}%
%BeginExpansion
$\backslash$%
%EndExpansion
underline\{\#2\}\}\}}
\par
Then, you can use \textquotedblleft\texttt{%
%TCIMACRO{\TEXTsymbol{\backslash}}%
%BeginExpansion
$\backslash$%
%EndExpansion
lf\{x\}\{n\}}\textquotedblright\ to obtain \textquotedblleft$%
%TCIMACRO{\TeXButton{lf example}{\lf{x}{n}}}%
%BeginExpansion
\lf{x}{n}%
%EndExpansion
$\textquotedblright.}.

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

\textbf{(a)} If $\left(  a_{0},a_{1},\ldots,a_{n}\right)  $ is an $\left(
n+1\right)  $-tuple of rational numbers such that each $x\in\left\{
0,1,\ldots,n\right\}  $ satisfies%
\[
\sum_{k=0}^{n}a_{k}x^{\underline{k}}=0,
\]
then $\left(  a_{0},a_{1},\ldots,a_{n}\right)  =\left(  0,0,\ldots,0\right)  $.

\textbf{(b)} If $\left(  a_{0},a_{1},\ldots,a_{n}\right)  $ and $\left(
b_{0},b_{1},\ldots,b_{n}\right)  $ are two $\left(  n+1\right)  $-tuples of
rational numbers such that each $x\in\left\{  0,1,\ldots,n\right\}  $
satisfies%
\[
\sum_{k=0}^{n}a_{k}x^{\underline{k}}=\sum_{k=0}^{n}b_{k}x^{\underline{k}},
\]
then $\left(  a_{0},a_{1},\ldots,a_{n}\right)  =\left(  b_{0},b_{1}%
,\ldots,b_{n}\right)  $.

[\textbf{Hint:} In terms of linear algebra, part \textbf{(a)} is saying that
the $n+1$ vectors $\left(  0^{\underline{k}},1^{\underline{k}},\ldots
,n^{\underline{k}}\right)  ^{T}\in\mathbb{Q}^{n+1}$ for $k\in\left\{
0,1,\ldots,n\right\}  $ are linearly independent. You may find this useful or
not; the exercise has a fully elementary solution.]
\end{exercise}

In the following, we will consider each pair $\left(  i,j\right)
\in\mathbb{Z}^{2}$ of two integers as a square on an (infinite) chessboard; we
say that it lies in \textit{row }$i$ and in \textit{column }$j$. A
\textit{rook placement} shall mean a subset $X$ of $\mathbb{Z}^{2}$ such that
any two distinct elements of $X$ lie in different rows and in different
columns\footnote{In other words, a rook placement means a subset $X$ of
$\mathbb{Z}^{2}$ such that any two distinct elements $\left(  i,j\right)  $
and $\left(  i^{\prime},j^{\prime}\right)  $ of $X$ satisfy $i\neq i^{\prime}$
and $j\neq j^{\prime}$.}. (The idea behind this name is that if we place rooks
into the squares $\left(  i,j\right)  \in X$, then no two rooks will attack
each other.) For example, $\left\{  \left(  1,3\right)  ,\left(  2,2\right)
,\left(  3,7\right)  \right\}  $ is a rook placement, whereas $\left\{
\left(  1,3\right)  ,\left(  2,2\right)  ,\left(  7,3\right)  \right\}  $ is
not (since the distinct squares $\left(  1,3\right)  $ and $\left(
7,3\right)  $ lie in the same column). If $X$ is a rook placement, then the
elements of $X$ are called the \textit{rooks} of $X$.

Now, fix $n\in\mathbb{N}$. If $\mathbf{u}=\left(  u_{1},u_{2},\ldots
,u_{n}\right)  \in\mathbb{N}^{n}$ is an $n$-tuple of nonnegative integers,
then we define the $\mathbf{u}$\textit{-board} $D\left(  \mathbf{u}\right)  $
to be the set%
\[
\left\{  \left(  i,j\right)  \ \mid\ i\in\left[  n\right]  \text{ and }%
j\in\left[  u_{i}\right]  \right\}  .
\]
We visually represent this set as a \textquotedblleft
chessboard\textquotedblright\ consisting of $n$ left-aligned rows\footnote{or
\textquotedblleft ranks\textquotedblright, to use the terminology of chess
(but we label them $1,2,\ldots,n$ from top to bottom, not from bottom to top
as on an actual chessboard)}, where the $i$-th row consists of $u_{i}$ boxes
(which occupy columns $1,2,\ldots,u_{i}$).

For example, if $n=4$ and $\mathbf{u}=\left(  2,1,4,1\right)  $, then
$D\left(  \mathbf{u}\right)  $ is the set%
\[
\left\{  \left(  1,1\right)  ,\left(  1,2\right)  ,\left(  2,1\right)
,\left(  3,1\right)  ,\left(  3,2\right)  ,\left(  3,3\right)  ,\left(
3,4\right)  ,\left(  4,1\right)  \right\}  ,
\]
and is visually represented as the \textquotedblleft
chessboard\textquotedblright%
\[
\ydiagram{0+2,0+1,0+4,0+1}.
\]


The set (or \textquotedblleft chessboard\textquotedblright) $D\left(
\mathbf{u}\right)  $ is also known as the \textit{Young diagram} (or
\textit{Ferrers diagram}) of $\mathbf{u}$; we have briefly seen its use in the
proof of Proposition 4.13 on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18s/4707-2018mar21.pdf}{March
21st}.

If $\mathbf{u}\in\mathbb{N}^{n}$, then a \textit{rook placement in }$D\left(
\mathbf{u}\right)  $ means a subset $X$ of $D\left(  \mathbf{u}\right)  $ that
is a rook placement. For example, if $n=4$ and $\mathbf{u}=\left(
2,1,4,1\right)  $, then $\left\{  \left(  1,2\right)  ,\left(  3,3\right)
,\left(  4,1\right)  \right\}  $ is a rook placement in $D\left(
\mathbf{u}\right)  $. We represent this rook placement by putting rooks (i.e.,
$\symrook$ symbols) into the squares that belong to it; so we get%
\[%
%TCIMACRO{\TeXButton{ytableau of a rook placement}{\ytableausetup
%{centertableaux}
%\begin{ytableau}
%\  & \symrook\\
%\  \\
%\  & \ & \symrook&\\
%\symrook\end{ytableau}}}%
%BeginExpansion
\ytableausetup{centertableaux}
\begin{ytableau}
\  & \symrook\\
\  \\
\  & \ & \symrook&\\
\symrook\end{ytableau}%
%EndExpansion
.
\]


Note that the empty set $\varnothing$ is always a rook placement in $D\left(
\mathbf{u}\right)  $; so is any $1$-element subset of $D\left(  \mathbf{u}%
\right)  $.

If $\mathbf{u}\in\mathbb{N}^{n}$ and $k\in\mathbb{N}$, then we let
$R_{k}\left(  \mathbf{u}\right)  $ denote the number of all rook placements in
$D\left(  \mathbf{u}\right)  $ of size $k$. (In terms of the picture,
\textquotedblleft size $k$\textquotedblright\ means that it contains exactly
$k$ rooks.) For example, if $n=3$ and $\mathbf{u}=\left(  2,1,3\right)  $,
then
\begin{align*}
R_{0}\left(  \mathbf{u}\right)   &  =1;\ \ \ \ \ \ \ \ \ \ R_{1}\left(
\mathbf{u}\right)  =6;\ \ \ \ \ \ \ \ \ \ R_{2}\left(  \mathbf{u}\right)
=7;\\
R_{3}\left(  \mathbf{u}\right)   &  =1;\ \ \ \ \ \ \ \ \ \ R_{k}\left(
\mathbf{u}\right)  =0\text{ for all }k\geq4.
\end{align*}


It is easy to see that if $\mathbf{u}=\left(  \underbrace{u,u,\ldots
,u}_{n\text{ times}}\right)  $ for some $u\in\mathbb{N}$, then%
\begin{equation}
R_{k}\left(  \mathbf{u}\right)  =\dbinom{n}{k}\dbinom{u}{k}%
k!\ \ \ \ \ \ \ \ \ \ \text{for each }k\in\mathbb{N}. \label{eq.rook.recta}%
\end{equation}
(Indeed, in order to place $k$ non-attacking rooks in $D\left(  \mathbf{u}%
\right)  $, we first choose the $k$ rows they will occupy, then the $k$
columns they will occupy, and finally an appropriate permutation of $\left[
k\right]  $ that will determine which column has a rook in which row.) For
other $n$-tuples $\mathbf{u}$, finding $R_{k}\left(  \mathbf{u}\right)  $ is harder.

\begin{fns}
For example, if you try the same reasoning for $\mathbf{u}=\left(
2n-1,2n-3,\ldots,5,3,1\right)  $, then you still have $\dbinom{n}{k}$ choices
for the $k$ rows occupied by rooks; but the number of options in the following
steps will depend on the specific $k$ rows you have chosen (the lower the
rows, the fewer options). This way, you get the formula%
\[
R_{k}\left(  2n-1,2n-3,\ldots,5,3,1\right)  =\sum_{1\leq s_{1}<s_{2}%
<\cdots<s_{k}\leq n}\left(  s_{k}-0\right)  \left(  s_{k-1}-1\right)  \left(
s_{k-2}-2\right)  \cdots\left(  s_{1}-\left(  k-1\right)  \right)  ,
\]
which is a far cry from the simplicity of (\ref{eq.rook.recta}). But there is
a simple formula, which we'll see in Corollary \ref{cor.rook.ISL}!
\end{fns}

We can restrict ourselves to $n$-tuples $\mathbf{u}=\left(  u_{1},u_{2}%
,\ldots,u_{n}\right)  $ satisfying $u_{1}\geq u_{2}\geq\cdots\geq u_{n}$,
because switching some of the entries of $\mathbf{u}$ does not change the
values of $R_{k}\left(  \mathbf{u}\right)  $.

In general, $R_{k}\left(  \mathbf{u}\right)  =0$ for all $k>n$, because each
of the $n$ rows $1,2,\ldots,n$ contains at most one rook. For $k=n$, we have a
neat formula:

\begin{proposition}
\label{prop.rook.Rn}Let $\mathbf{u}=\left(  u_{1},u_{2},\ldots,u_{n}\right)
\in\mathbb{N}^{n}$ be such that $u_{1}\geq u_{2}\geq\cdots\geq u_{n}$. Then,%
\[
R_{n}\left(  \mathbf{u}\right)  =\prod_{i=0}^{n-1}\left(  u_{n-i}-i\right)  .
\]

\end{proposition}

\begin{proof}
[Proof of Proposition \ref{prop.rook.Rn}.]Each square in $D\left(
\mathbf{u}\right)  $ belongs to one of the $n$ rows $1,2,\ldots,n$. In a rook
placement, each row contains at most one rook. Thus, any rook placement in
$D\left(  \mathbf{u}\right)  $ contains at most $n$ rooks, and the only way it
can contain $n$ rooks is if it contains one rook in each of the $n$ rows
$1,2,\ldots,n$.

Hence, a rook placement in $D\left(  \mathbf{u}\right)  $ of size $n$ is the
same as a rook placement in $D\left(  \mathbf{u}\right)  $ that contains a
rook in each of the $n$ rows $1,2,\ldots,n$. We can construct such a rook
placement by the following algorithm:

\begin{itemize}
\item First, we place the rook in row $n$. This rook must lie in one of the
$u_{n}$ columns $1,2,\ldots,u_{n}$; so we have $u_{n}$ options.

\item Then, we place the rook in row $n-1$. This rook must lie in one of the
$u_{n-1}$ columns $1,2,\ldots,u_{n-1}$, but \textbf{not} in the column that
contains the previous rook; so we have $u_{n-1}-1$ options.

\item Then, we place the rook in row $n-2$. This rook must lie in one of the
$u_{n-2}$ columns $1,2,\ldots,u_{n-2}$, but \textbf{not} in either of the two
columns that contain the previous rooks; so we have $u_{n-2}-2$ options.

\item And so on.
\end{itemize}

Thus, the total number of choices (and therefore the total number of rook
placements in $D\left(  \mathbf{u}\right)  $ of size $n$) is%
\begin{align*}
&  u_{n}\left(  u_{n-1}-1\right)  \left(  u_{n-2}-2\right)  \cdots\left(
u_{n-\left(  n-1\right)  }-\left(  n-1\right)  \right) \\
&  =\left(  u_{n}-0\right)  \left(  u_{n-1}-1\right)  \left(  u_{n-2}%
-2\right)  \cdots\left(  u_{1}-\left(  n-1\right)  \right)  =\prod_{i=0}%
^{n-1}\left(  u_{n-i}-i\right)  .
\end{align*}
Since the total number of rook placements in $D\left(  \mathbf{u}\right)  $ of
size $n$ has been denoted by $R_{n}\left(  \mathbf{u}\right)  $, we thus
conclude that%
\[
R_{n}\left(  \mathbf{u}\right)  =\prod_{i=0}^{n-1}\left(  u_{n-i}-i\right)  .
\]
This proves Proposition \ref{prop.rook.Rn}.

[Are you wondering where we have used the condition $u_{1}\geq u_{2}\geq
\cdots\geq u_{n}$ ?

\pagebreak

\hrule


\noindent\textbf{Answer:} \newline\rotatebox[origin=c]{180}{
$1,2,\ldots,u_{n-2}$ (since $u_{n-2} \geq u_n$),
and similarly for the second ``forbidden'' column.
} \newline\rotatebox[origin=c]{180}{
column is among the columns $1,2,\ldots,u_n$
and therefore also among the columns
} \newline\rotatebox[origin=c]{180}{
$u_{n-2}-2$ options for our rook).
This fact is true because the first ``forbidden''
} \newline\rotatebox[origin=c]{180}{
columns $1,2,\ldots,u_{n-2}$ (if this was not the case,
then
we would have more than
} \newline\rotatebox[origin=c]{180}{
columns (i.e., the two columns
that contain the previous rooks) are among the $u_{n-2}$
} \newline\rotatebox[origin=c]{180}{
contain the previous rooks.
This tacitly relied on the fact that the two ``forbidden''
} \newline\rotatebox[origin=c]{180}{
placed in any of the
$u_{n-2}$ columns $1,2,\ldots,u_{n-2}$ except for the two
columns that
} \newline\rotatebox[origin=c]{180}{
in row $n-2$, we argued that we had
$u_{n-2}-2$ options, because the rook
could be
} \newline\rotatebox[origin=c]{180}{
\textbf{Answer:} Consider the algorithm above.
When we placed the rook \\
} \newline

\hrule
]
\end{proof}

\begin{exercise}
\label{exe.rook.main-thm}Let $\mathbf{u}=\left(  u_{1},u_{2},\ldots
,u_{n}\right)  \in\mathbb{N}^{n}$ be such that $u_{1}\geq u_{2}\geq\cdots\geq
u_{n}$.

\textbf{(a)} For each $x\in\mathbb{N}$, define an $n$-tuple $\mathbf{u}%
+x\in\mathbb{N}^{n}$ by $\mathbf{u}+x=\left(  u_{1}+x,u_{2}+x,\ldots
,u_{n}+x\right)  $. Prove that
\[
R_{n}\left(  \mathbf{u}+x\right)  =\sum_{k=0}^{n}R_{n-k}\left(  \mathbf{u}%
\right)  x^{\underline{k}}.
\]


[\textbf{Hint:} When $\mathbf{u}$ is replaced by $\mathbf{u}+x$, the
$\mathbf{u}$-board \textquotedblleft grows by $x$ extra (full)
columns\textquotedblright.]

\textbf{(b)} Now, let $\mathbf{v}=\left(  v_{1},v_{2},\ldots,v_{n}\right)
\in\mathbb{N}^{n}$ be such that $v_{1}\geq v_{2}\geq\cdots\geq v_{n}$. Assume
further that the $n$ numbers $u_{1}+1,u_{2}+2,\ldots,u_{n}+n$ are the same as
the $n$ numbers $v_{1}+1,v_{2}+2,\ldots,v_{n}+n$, up to order. (In other
words, there exists a permutation $\sigma\in S_{n}$ such that $u_{i}%
+i=v_{\sigma\left(  i\right)  }+\sigma\left(  i\right)  $ for all $i\in\left[
n\right]  $.) Prove that%
\[
R_{k}\left(  \mathbf{u}\right)  =R_{k}\left(  \mathbf{v}\right)
\ \ \ \ \ \ \ \ \ \ \text{for each }k\in\mathbb{N}.
\]


[\textbf{Hint:} First, prove that $R_{n}\left(  \mathbf{u}+x\right)
=R_{n}\left(  \mathbf{v}+x\right)  $ for each $x\in\mathbb{N}$. Then, use part
\textbf{(a)} and the previous exercise.]
\end{exercise}

\begin{fns}
To illustrate the usefulness of Exercise \ref{exe.rook.main-thm}, let me
express $R_{k}\left(  2n-1,2n-3,\ldots,5,3,1\right)  $ in a much simpler way
than before:

\begin{corollary}
\label{cor.rook.ISL}Let $k\in\mathbb{N}$. Then,%
\[
R_{k}\left(  2n-1,2n-3,\ldots,5,3,1\right)  =\dbinom{n}{k}^{2}k!.
\]

\end{corollary}

\begin{proof}
[Proof of Corollary \ref{cor.rook.ISL}.]Define an $n$-tuple $\mathbf{u}%
=\left(  u_{1},u_{2},\ldots,u_{n}\right)  \in\mathbb{N}^{n}$ by $\left(
u_{i}=2\left(  n-i\right)  +1\text{ for each }i\in\left[  n\right]  \right)
$. Thus,%
\[
\mathbf{u}=\left(  u_{1},u_{2},\ldots,u_{n}\right)  =\left(  2n-1,2n-3,\ldots
,5,3,1\right)  ,
\]
so that $u_{1}\geq u_{2}\geq\cdots\geq u_{n}$.

Define an $n$-tuple $\mathbf{v}=\left(  v_{1},v_{2},\ldots,v_{n}\right)
\in\mathbb{N}^{n}$ by $\left(  v_{i}=n\text{ for each }i\in\left[  n\right]
\right)  $. Thus,%
\[
\mathbf{v}=\left(  v_{1},v_{2},\ldots,v_{n}\right)  =\left(  n,n,\ldots
,n\right)  ,
\]
so that $v_{1}\geq v_{2}\geq\cdots\geq v_{n}$.

The $n$ numbers $u_{1}+1,u_{2}+2,\ldots,u_{n}+n$ are the same as the $n$
numbers $v_{1}+1,v_{2}+2,\ldots,v_{n}+n$, up to order. (In fact, the former
$n$ numbers are $2n,2n-1,2n-2,\ldots,n+2,n+1$, whereas the latter $n$ numbers
are $n+1,n+2,\ldots,2n-2,2n-1,2n$; these are just two different ways to list
all numbers from $n+1$ to $2n$.)

Hence, Exercise \ref{exe.rook.main-thm} \textbf{(b)} yields $R_{k}\left(
\mathbf{u}\right)  =R_{k}\left(  \mathbf{v}\right)  $. In view of
$\mathbf{u}=\left(  2n-1,2n-3,\ldots,5,3,1\right)  $ and $\mathbf{v}=\left(
n,n,\ldots,n\right)  $, this rewrites as $R_{k}\left(  2n-1,2n-3,\ldots
,5,3,1\right)  =R_{k}\left(  n,n,\ldots,n\right)  $.

But (\ref{eq.rook.recta}) (applied to $u=n$) yields $R_{k}\left(
n,n,\ldots,n\right)  =\dbinom{n}{k}\dbinom{n}{k}k!$. Hence,%
\[
R_{k}\left(  2n-1,2n-3,\ldots,5,3,1\right)  =R_{k}\left(  n,n,\ldots,n\right)
=\dbinom{n}{k}\dbinom{n}{k}k!=\dbinom{n}{k}^{2}k!.
\]
This proves Corollary \ref{cor.rook.ISL}.
\end{proof}

Rook theory is the study of rook placements -- not only in boards of the form
$D\left(  \mathbf{u}\right)  $, but also in more general subsets of
$\mathbb{Z}^{2}$. For example, the permutations of $\left[  n\right]  $ can be
regarded as rook placements in the board $\left[  n\right]  \times\left[
n\right]  $, whereas the derangements of $\left[  n\right]  $ can be regarded
as rook placements in the board $\left\{  \left(  i,j\right)  \in\left[
n\right]  \times\left[  n\right]  \ \mid\ i\neq j\right\}  $ (the
\textquotedblleft$n\times n$-chessboard without the main
diagonal\textquotedblright). The theory has been developed in the 70s at the
UMN (by Jay Goldman, J. T. Joichi, Victor Reiner and Dennis White).
\end{fns}

\subsection{The sum of the \textquotedblleft widths\textquotedblright\ of all
inversions of $\sigma$}

In the following, \textquotedblleft number\textquotedblright\ means
\textquotedblleft real number\textquotedblright\ or \textquotedblleft complex
number\textquotedblright\ or \textquotedblleft rational
number\textquotedblright, as you prefer (this doesn't make a difference in
these exercises).

\begin{exercise}
Let $n\in\mathbb{N}$. Let $\sigma\in S_{n}$. Let $a_{1},a_{2},\ldots,a_{n}$ be
any $n$ numbers. Prove that%
\[
\sum_{\substack{1\leq i<j\leq n;\\\sigma\left(  i\right)  >\sigma\left(
j\right)  }}\left(  a_{j}-a_{i}\right)  =\sum_{i=1}^{n}a_{i}\left(
i-\sigma\left(  i\right)  \right)  .
\]
[Here, the symbol \textquotedblleft$\sum_{\substack{1\leq i<j\leq
n;\\\sigma\left(  i\right)  >\sigma\left(  j\right)  }}$\textquotedblright%
\ means \textquotedblleft sum over all pairs $\left(  i,j\right)  \in\left[
n\right]  ^{2}$ satisfying $i<j$ and $\sigma\left(  i\right)  >\sigma\left(
j\right)  $\textquotedblright, that is, \textquotedblleft sum over all
inversions of $\sigma$\textquotedblright.]
\end{exercise}

\subsection{A hollowed-out determinant}

In the following, matrices are understood to be matrices whose entries are
numbers (see above).

\begin{exercise}
\label{exe.det.0-via-PQ}Let $n\in\mathbb{N}$. Let $P$ and $Q$ be two subsets
of $\left[  n\right]  $ such that $\left\vert P\right\vert +\left\vert
Q\right\vert >n$. Let $A=\left(  a_{i,j}\right)  _{1\leq i\leq n,\ 1\leq j\leq
n}$ be an $n\times n$-matrix such that%
\[
\text{every }i\in P\text{ and }j\in Q\text{ satisfy }a_{i,j}=0.
\]
Then, prove that $\det A=0$.
\end{exercise}

\begin{example}
Applying Exercise \ref{exe.det.0-via-PQ} to $n=5$, $P=\left\{  1,3,5\right\}
$ and $Q=\left\{  2,3,4\right\}  $, we see that%
\[
\det\left(
\begin{array}
[c]{ccccc}%
a_{1} & 0 & 0 & 0 & a_{5}\\
b_{1} & b_{2} & b_{3} & b_{4} & b_{5}\\
c_{1} & 0 & 0 & 0 & c_{5}\\
d_{1} & d_{2} & d_{3} & d_{4} & d_{5}\\
e_{1} & 0 & 0 & 0 & e_{5}%
\end{array}
\right)  =0\ \ \ \ \ \ \ \ \ \ \text{for any numbers }a_{1},a_{5},\ldots
,e_{5}.
\]

\end{example}

\subsection{Arrowhead matrices}

\begin{exercise}
\label{exe.arrowhead}Let $n$ be a positive integer.

\textbf{(a)} A permutation $\sigma\in S_{n}$ will be called
\textit{arrowheaded} if each $i\in\left[  n-1\right]  $ satisfies
$\sigma\left(  i\right)  =i$ or $\sigma\left(  i\right)  =n$.

[For example, the permutation in $S_{5}$ whose one-line notation is $\left[
1,5,3,4,2\right]  $ is arrowheaded.]

Describe all arrowheaded permutations $\sigma\in S_{n}$ and find their number.

\textbf{(b)} Given $n$ numbers $a_{1},a_{2},\ldots,a_{n}$ as well as $n-1$
numbers $b_{1},b_{2},\ldots,b_{n-1}$ and $n-1$ further numbers $c_{1}%
,c_{2},\ldots,c_{n-1}$. Let $A$ be the $n\times n$-matrix%
\[
\left(
\begin{array}
[c]{ccccc}%
a_{1} & 0 & \cdots & 0 & c_{1}\\
0 & a_{2} & \cdots & 0 & c_{2}\\
\vdots & \vdots & \ddots & \vdots & \vdots\\
0 & 0 & \cdots & a_{n-1} & c_{n-1}\\
b_{1} & b_{2} & \cdots & b_{n-1} & a_{n}%
\end{array}
\right)  .
\]
(This is the matrix whose $\left(  i,j\right)  $-th entry is $%
\begin{cases}
a_{i}, & \text{if }i=j;\\
b_{j}, & \text{if }i=n\text{ and }j\neq n;\\
c_{i}, & \text{if }i\neq n\text{ and }j=n;\\
0, & \text{if }i\neq n\text{ and }j\neq n\text{ and }i\neq j
\end{cases}
$ for all $i\in\left[  n\right]  $ and $j\in\left[  n\right]  $.) Prove that%
\[
\det A=a_{1}a_{2}\cdots a_{n}-\sum_{i=1}^{n-1}b_{i}c_{i}\left(  \prod
_{\substack{j\in\left[  n-1\right]  ;\\j\neq i}}a_{j}\right)  .
\]

\end{exercise}

The matrix $A$ is called a \textquotedblleft reverse arrowhead
matrix\textquotedblright\ due to the shape that its nonzero entries form.
(\textquotedblleft Reverse\textquotedblright\ because the usual arrowhead
matrix has its arrow pointing northwest rather than southeast.)


\end{document}