\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=Thursday, December 10, 2020 23:20:57}
%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 with solutions}
\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}
\label{exe.perm.s2=s1+1}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}

\begin{proof}
[Solution to Exercise \ref{exe.perm.s2=s1+1} (sketched).]The following method
constructs every permutation $\sigma\in S_{n}$ satisfying $\sigma\left(
2\right)  =\sigma\left(  1\right)  +1$:

\begin{itemize}
\item First, choose the value $\sigma\left(  1\right)  $. This value must
belong to the set $\left[  n-1\right]  $ (because we want our $\sigma$ to
satisfy $\sigma\left(  2\right)  =\sigma\left(  1\right)  +1$, whence
$\sigma\left(  1\right)  +1=\sigma\left(  2\right)  \leq n$ (since
$\sigma\left(  2\right)  \in\left[  n\right]  $) and therefore $\sigma\left(
1\right)  \leq n-1$). Thus, there are $n-1$ choices at this step.

\item Then, the value $\sigma\left(  2\right)  $ is uniquely determined by the
equality $\sigma\left(  2\right)  =\sigma\left(  1\right)  +1$. Note that
$\sigma\left(  1\right)  $ and $\sigma\left(  2\right)  $ are thus distinct.

\item Now, choose the remaining $n-2$ values $\sigma\left(  3\right)
,\sigma\left(  4\right)  ,\ldots,\sigma\left(  n\right)  $ of $\sigma$. These
$n-2$ values must be distinct from each other and from the already chosen two
values $\sigma\left(  1\right)  $ and $\sigma\left(  2\right)  $ (since we
want $\sigma$ to be a permutation); thus, we are choosing $n-2$ distinct
values from the $\left(  n-2\right)  $-element set $\left[  n\right]
\setminus\left\{  \sigma\left(  1\right)  ,\sigma\left(  2\right)  \right\}  $
at this step. There are clearly $\left(  n-2\right)  !$ ways to do that.
\end{itemize}

The total number of possible ways to perform this method is thus $\left(
n-1\right)  \cdot\left(  n-2\right)  !=\left(  n-1\right)  !$. Hence, there
are precisely $\left(  n-1\right)  !$ permutations $\sigma\in S_{n}$
satisfying $\sigma\left(  2\right)  =\sigma\left(  1\right)  +1$. This solves
Exercise \ref{exe.perm.s2=s1+1}.
\end{proof}

\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}
\label{exe.lower-fac.lin-indep1}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%
\begin{equation}
\sum_{k=0}^{n}a_{k}x^{\underline{k}}=0,
\label{eq.exe.lower-fac.lin-indep1.a.ass}%
\end{equation}
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%
\begin{equation}
\sum_{k=0}^{n}a_{k}x^{\underline{k}}=\sum_{k=0}^{n}b_{k}x^{\underline{k}},
\label{eq.exe.lower-fac.lin-indep1.b.ass}%
\end{equation}
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}

\begin{proof}
[Solution to Exercise \ref{exe.lower-fac.lin-indep1}.]Let us first observe
that
\begin{equation}
j^{\underline{k}}=0\ \ \ \ \ \ \ \ \ \ \text{for any }j\in\mathbb{N}\text{ and
}k\in\mathbb{N}\text{ satisfying }k\geq j+1.
\label{sol.lower-fac.lin-indep1.lem}%
\end{equation}


[\textit{Proof of (\ref{sol.lower-fac.lin-indep1.lem}):} Let $j\in\mathbb{N}$
and $k\in\mathbb{N}$ be such that $k\geq j+1$. Hence, $j+1\leq k$, so that
$j\leq k-1$ and thus $j\in\left\{  0,1,\ldots,k-1\right\}  $ (since
$j\in\mathbb{N}$). The definition of $j^{\underline{k}}$ yields%
\begin{align*}
j^{\underline{k}}  &  =j\left(  j-1\right)  \cdots\left(  j-k+1\right)
=\prod_{u=0}^{k-1}\left(  j-u\right)  =\prod_{u\in\left\{  0,1,\ldots
,k-1\right\}  }\left(  j-u\right) \\
&  =\underbrace{\left(  j-j\right)  }_{=0}\prod_{\substack{u\in\left\{
0,1,\ldots,k-1\right\}  ;\\u\neq j}}\left(  j-u\right) \\
&  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{here, we have split off the factor for }u=j\text{ from}\\
\text{the product, since }j\in\left\{  0,1,\ldots,k-1\right\}
\end{array}
\right) \\
&  =0\prod_{\substack{u\in\left\{  0,1,\ldots,k-1\right\}  ;\\u\neq j}}\left(
j-u\right)  =0.
\end{align*}
This proves (\ref{sol.lower-fac.lin-indep1.lem}).]

\textbf{(a)} Let $\left(  a_{0},a_{1},\ldots,a_{n}\right)  $ be an $\left(
n+1\right)  $-tuple of rational numbers such that each $x\in\left\{
0,1,\ldots,n\right\}  $ satisfies (\ref{eq.exe.lower-fac.lin-indep1.a.ass}).
We must prove that $\left(  a_{0},a_{1},\ldots,a_{n}\right)  =\left(
0,0,\ldots,0\right)  $.

We claim that%
\begin{equation}
a_{k}=0\ \ \ \ \ \ \ \ \ \ \text{for each }k\in\left\{  0,1,\ldots,n\right\}
. \label{sol.lower-fac.lin-indep1.a.claim}%
\end{equation}


[\textit{Proof of (\ref{sol.lower-fac.lin-indep1.a.claim}):} We shall prove
(\ref{sol.lower-fac.lin-indep1.a.claim}) by strong induction on $k$:

\textit{Induction step:} Let $j\in\left\{  0,1,\ldots,n\right\}  $. Assume
that (\ref{sol.lower-fac.lin-indep1.a.claim}) holds whenever $k<j$. We must
then prove that (\ref{sol.lower-fac.lin-indep1.a.claim}) holds for $k=j$.

We have assumed that (\ref{sol.lower-fac.lin-indep1.a.claim}) holds whenever
$k<j$. In other words, we have%
\begin{equation}
a_{k}=0\ \ \ \ \ \ \ \ \ \ \text{for each }k\in\left\{  0,1,\ldots,n\right\}
\text{ satisfying }k<j. \label{sol.lower-fac.lin-indep1.a.claim.pf.IH}%
\end{equation}


From $j\in\left\{  0,1,\ldots,n\right\}  $, we obtain $0\leq j\leq n$. Also,
$j-1\leq j\leq n$, so that $\left\{  0,1,\ldots,j-1\right\}  \subseteq\left\{
0,1,\ldots,n\right\}  $. The definition of $j^{\underline{j}}$ yields
$j^{\underline{j}}=j\left(  j-1\right)  \cdots\left(  j-j+1\right)  =j\left(
j-1\right)  \cdots1=j!$.

But we have assumed that each $x\in\left\{  0,1,\ldots,n\right\}  $ satisfies
(\ref{eq.exe.lower-fac.lin-indep1.a.ass}). Applying this to $x=j$, we thus
conclude that%
\[
\sum_{k=0}^{n}a_{k}j^{\underline{k}}=0.
\]
Hence,%
\begin{align*}
0 &  =\sum_{k=0}^{n}a_{k}j^{\underline{k}}=\sum_{k=0}^{j}a_{k}j^{\underline{k}%
}+\sum_{k=j+1}^{n}a_{k}\underbrace{j^{\underline{k}}}_{\substack{=0\\\text{(by
(\ref{sol.lower-fac.lin-indep1.lem})}\\\text{(since }j\geq k+1\text{))}}}\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{here, we have split the sum at }k=j\text{
(since }0\leq j\leq n\text{)}\right)  \\
&  =\sum_{k=0}^{j}a_{k}j^{\underline{k}}+\underbrace{\sum_{k=j+1}^{n}a_{k}%
0}_{=0}=\sum_{k=0}^{j}a_{k}j^{\underline{k}}\\
&  =\sum_{k=0}^{j-1}\underbrace{a_{k}}_{\substack{=0\\\text{(by
(\ref{sol.lower-fac.lin-indep1.a.claim.pf.IH})}\\\text{(since }k\in\left\{
0,1,\ldots,j-1\right\}  \subseteq\left\{  0,1,\ldots,n\right\}  \text{ and
}k\leq j-1<j\text{))}}}j^{\underline{k}}+a_{j}\underbrace{j^{\underline{j}}%
}_{=j!}\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{here, we have split off the addend for
}k=j\text{ from the sum}\right)  \\
&  =\underbrace{\sum_{k=0}^{j-1}0j^{\underline{k}}}_{=0}+a_{j}j!=a_{j}j!.
\end{align*}
Dividing this equality by $j!$, we obtain $0=a_{j}$ (since $j!$ is nonzero).
In other words, $a_{j}=0$. In other words,
(\ref{sol.lower-fac.lin-indep1.a.claim}) holds for $k=j$. This completes the
induction step. Thus, (\ref{sol.lower-fac.lin-indep1.a.claim}) is proven by
strong induction.]

Now, (\ref{sol.lower-fac.lin-indep1.a.claim}) immediately yields $\left(
a_{0},a_{1},\ldots,a_{n}\right)  =\left(  0,0,\ldots,0\right)  $. This solves
Exercise \ref{exe.lower-fac.lin-indep1} \textbf{(a)}.

\textbf{(b)} Let $\left(  a_{0},a_{1},\ldots,a_{n}\right)  $ and $\left(
b_{0},b_{1},\ldots,b_{n}\right)  $ be two $\left(  n+1\right)  $-tuples of
rational numbers such that each $x\in\left\{  0,1,\ldots,n\right\}  $
satisfies (\ref{eq.exe.lower-fac.lin-indep1.b.ass}). We must prove that
$\left(  a_{0},a_{1},\ldots,a_{n}\right)  =\left(  b_{0},b_{1},\ldots
,b_{n}\right)  $.

Clearly, $\left(  a_{0}-b_{0},a_{1}-b_{1},\ldots,a_{n}-b_{n}\right)  $ is an
$\left(  n+1\right)  $-tuple of rational numbers (since $\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). Moreover, each
$x\in\left\{  0,1,\ldots,n\right\}  $ satisfies%
\[
\sum_{k=0}^{n}\underbrace{\left(  a_{k}-b_{k}\right)  x^{\underline{k}}%
}_{=a_{k}x^{\underline{k}}-b_{k}x^{\underline{k}}}=\sum_{k=0}^{n}\left(
a_{k}x^{\underline{k}}-b_{k}x^{\underline{k}}\right)  =\underbrace{\sum
_{k=0}^{n}a_{k}x^{\underline{k}}}_{\substack{=\sum_{k=0}^{n}b_{k}%
x^{\underline{k}}\\\text{(by (\ref{eq.exe.lower-fac.lin-indep1.b.ass}))}%
}}-\sum_{k=0}^{n}b_{k}x^{\underline{k}}=\sum_{k=0}^{n}b_{k}x^{\underline{k}%
}-\sum_{k=0}^{n}b_{k}x^{\underline{k}}=0.
\]
Hence, Exercise \ref{exe.lower-fac.lin-indep1} \textbf{(a)} (applied to
$a_{k}-b_{k}$ instead of $a_{k}$) yields $\left(  a_{0}-b_{0},a_{1}%
-b_{1},\ldots,a_{n}-b_{n}\right)  =\left(  0,0,\ldots,0\right)  $. In other
words, $a_{k}-b_{k}=0$ for each $k\in\left\{  0,1,\ldots,n\right\}  $. In
other words, $a_{k}=b_{k}$ for each $k\in\left\{  0,1,\ldots,n\right\}  $. In
other words, $\left(  a_{0},a_{1},\ldots,a_{n}\right)  =\left(  b_{0}%
,b_{1},\ldots,b_{n}\right)  $. This solves Exercise
\ref{exe.lower-fac.lin-indep1} \textbf{(b)}.
\end{proof}

\begin{remark}
There are other solutions to Exercise \ref{exe.lower-fac.lin-indep1}, using
linear algebra or the properties of polynomials. But I think the above
solution is the easiest one. Of course, the analogue of Exercise
\ref{exe.lower-fac.lin-indep1} in which the lower factorials $x^{\underline{k}%
}$ are replaced by (usual) powers $x^{k}$ is well-known, and follows (e.g.)
from Lagrange interpolation.
\end{remark}

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 an \textquotedblleft irregular
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 irregular
chessboard\textquotedblright%
\[
\ydiagram{0+2,0+1,0+4,0+1}.
\]


The set (or \textquotedblleft irregular 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{Z}$, 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;\\
R_{k}\left(  \mathbf{u}\right)   &  =0\text{ for all }k<0.
\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)  $.

We have%
\begin{equation}
R_{k}\left(  \mathbf{u}\right)  =0\ \ \ \ \ \ \ \ \ \ \text{for all integers
}k>n, \label{eq.rook.Rk=0}%
\end{equation}
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 exactly 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\footnote{Why exactly $u_{n-2}-2$? Because the two previous rooks lie
in two \textbf{different} columns (due to the way we placed the second rook),
and thus there are $u_{n-2}-2$ of the $u_{n-2}$ columns $1,2,\ldots,u_{n-2}$
left for us to place our third rook in.}.

\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}}%
\]
for each $x\in\mathbb{N}$.

[\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}

We notice that Exercise \ref{exe.rook.main-thm} \textbf{(b)} is part of
\cite[Theorem 12.10]{Loehr-BC}. (The other part is a converse statement: If
$R_{k}\left(  \mathbf{u}\right)  =R_{k}\left(  \mathbf{v}\right)  $ for each
$k\in\mathbb{N}$, then 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.)
Our solution to Exercise \ref{exe.rook.main-thm} \textbf{(b)} is not a
bijective proof; nevertheless, I believe that bijective proofs exist in the literature.

\begin{proof}
[Solution to Exercise \ref{exe.rook.main-thm} (sketched).]\textbf{(a)} Let
$x\in\mathbb{N}$. Consider the \textquotedblleft irregular
chessboard\textquotedblright\ $D\left(  \mathbf{u}+x\right)  $. Define a
subset $B$ of $\mathbb{Z}^{2}$ by $B=\left[  n\right]  \times\left[  x\right]
$. Thus, $B$ consists of all the $nx$ squares that lie in rows $1,2,\ldots,n$
and columns $1,2,\ldots,x$ of the (infinite) chessboard. All these $nx$
squares belong to $D\left(  \mathbf{u}+x\right)  $ (since all entries of the
$n$-tuple $\mathbf{u}+x$ are $\geq x$, and therefore each row of $D\left(
\mathbf{u}+x\right)  $ has length $\geq x$). In other words, $B\subseteq
D\left(  \mathbf{u}+x\right)  $.

For example, if $\mathbf{u}=\left(  2,1,4,1\right)  $ and $x=3$, then
$D\left(  \mathbf{u}+x\right)  $ is the following \textquotedblleft irregular
chessboard\textquotedblright:%
\[%
%TCIMACRO{\TeXButton{ytableau of an extended chessboard}{\ytableausetup
%{centertableaux}
%\begin{ytableau}
%B & B & B & \  & \\
%B & B & B & \  \\
%B & B & B & \  & \ & &\\
%B & B & B & \
%\end{ytableau}}}%
%BeginExpansion
\ytableausetup{centertableaux}
\begin{ytableau}
B & B & B & \  & \\
B & B & B & \  \\
B & B & B & \  & \ & &\\
B & B & B & \
\end{ytableau}%
%EndExpansion
\]
(where the cells lying in $B$ are marked with the letter \textquotedblleft%
$B$\textquotedblright).

Let $p\in\mathbb{Z}$.

Each row of $D\left(  \mathbf{u}+x\right)  $ is longer than the corresponding
row of $D\left(  \mathbf{u}\right)  $ by precisely $x$ cells. If we subtract
the set $B$ from $D\left(  \mathbf{u}+x\right)  $, then each row loses its
first $x$ cells, and thus it becomes as long as the corresponding row of
$D\left(  \mathbf{u}\right)  $ but lying $x$ units further right. Hence, the
set difference $D\left(  \mathbf{u}+x\right)  \setminus B$ is the same as the
set $D\left(  \mathbf{u}\right)  $ with all its rows shifted to the right by
$x$ units. Hence, there is a bijection%
\begin{align*}
&  \left\{  \text{subsets of }D\left(  \mathbf{u}\right)  \text{ that are rook
placements}\right\} \\
&  \rightarrow\left\{  \text{subsets of }D\left(  \mathbf{u}+x\right)
\setminus B\text{ that are rook placements}\right\}
\end{align*}
(which simply shifts each rook placement to the right by $x$ units). This
bijection clearly preserves the size of a rook placement. Thus, it gives rise
(by restriction) to a bijection%
\begin{align*}
&  \left\{  \text{subsets }X\text{ of }D\left(  \mathbf{u}\right)  \text{ that
are rook placements and satisfy }\left\vert X\right\vert =p\right\} \\
&  \rightarrow\left\{  \text{subsets }X\text{ of }D\left(  \mathbf{u}%
+x\right)  \setminus B\text{ that are rook placements and satisfy }\left\vert
X\right\vert =p\right\}  .
\end{align*}
Hence,%
\begin{align*}
&  \left\vert \left\{  \text{subsets }X\text{ of }D\left(  \mathbf{u}\right)
\text{ that are rook placements and satisfy }\left\vert X\right\vert
=p\right\}  \right\vert \\
&  =\left\vert \left\{  \text{subsets }X\text{ of }D\left(  \mathbf{u}%
+x\right)  \setminus B\text{ that are rook placements and satisfy }\left\vert
X\right\vert =p\right\}  \right\vert \\
&  =\left\vert \left\{  \text{rook placements in }D\left(  \mathbf{u}%
+x\right)  \text{ that are disjoint from }B\text{ and satisfy }\left\vert
X\right\vert =p\right\}  \right\vert
\end{align*}
(because the subsets $X$ of $D\left(  \mathbf{u}+x\right)  \setminus B$ that
are rook placements are precisely the rook placements in $D\left(
\mathbf{u}+x\right)  $ that are disjoint from $B$). Therefore,%
\begin{align}
&  \left\vert \left\{  \text{rook placements in }D\left(  \mathbf{u}+x\right)
\text{ that are disjoint from }B\text{ and satisfy }\left\vert X\right\vert
=p\right\}  \right\vert \nonumber\\
&  =\left\vert \left\{  \text{subsets }X\text{ of }D\left(  \mathbf{u}\right)
\text{ that are rook placements and satisfy }\left\vert X\right\vert
=p\right\}  \right\vert \nonumber\\
&  =\left\vert \left\{  \text{rook placements }X\text{ in }D\left(
\mathbf{u}\right)  \text{ that satisfy }\left\vert X\right\vert =p\right\}
\right\vert \nonumber\\
&  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{because the subsets of }D\left(  \mathbf{u}\right)  \text{ that are rook
placements}\\
\text{are precisely the rook placements in }D\left(  \mathbf{u}\right)
\end{array}
\right) \nonumber\\
&  =\left\vert \left\{  \text{rook placements }X\text{ in }D\left(
\mathbf{u}\right)  \text{ of size }p\right\}  \right\vert \nonumber\\
&  =\left(  \text{the number of all rook placements in }D\left(
\mathbf{u}\right)  \text{ of size }p\right) \nonumber\\
&  =R_{p}\left(  \mathbf{u}\right)  \label{sol.rook.main-thm.a.3}%
\end{align}
(since $R_{p}\left(  \mathbf{u}\right)  $ was defined to be the number of all
rook placements in $D\left(  \mathbf{u}\right)  $ of size $p$).

Now, forget that we fixed $p$. We thus have proven
(\ref{sol.rook.main-thm.a.3}) for each $p\in\mathbb{Z}$.

On the other hand, recall that $R_{n}\left(  \mathbf{u}+x\right)  $ is the
number of all rook placements in $D\left(  \mathbf{u}+x\right)  $ of size $n$
(by the definition of $R_{n}\left(  \mathbf{u}+x\right)  $). Any such rook
placement must contain $n$ rooks, and thus must contain \textbf{exactly one
rook} in each of the $n$ rows $1,2,\ldots,n$ (this was proven during our proof
of Proposition \ref{prop.rook.Rn}). Thus, we can construct every rook
placement in $D\left(  \mathbf{u}+x\right)  $ of size $n$ by the following algorithm:

\begin{itemize}
\item First, we decide how many rooks will lie in $B$. In other words, we
choose the number $k\in\left\{  0,1,\ldots,n\right\}  $ such that $k$ of the
$n$ rooks of our rook placement will lie in $B$.

\item Next, we choose the $n-k$ rooks of our rook placement that will not lie
in $B$. These $n-k$ rooks must therefore form a rook placement $X$ in
$D\left(  \mathbf{u}+x\right)  $ that is disjoint from $B$ and satisfies
$\left\vert X\right\vert =n-k$. The number of such rook placements is
$R_{n-k}\left(  \mathbf{u}\right)  $ (by (\ref{sol.rook.main-thm.a.3}),
applied to $p=n-k$). Thus, this step can be performed in $R_{n-k}\left(
\mathbf{u}\right)  $ many ways.

\item Note that $X$ is a rook placement, and thus any two distinct rooks from
$X$ occupy distinct rows. Hence, exactly $n-k$ of the $n$ rows $1,2,\ldots,n$
contain a rook from $X$. We call these $n-k$ rows \textit{occupied}. The
remaining $k$ among the $n$ rows $1,2,\ldots,n$ will be called
\textit{unoccupied}.

\item Next, we choose the remaining $k$ rooks of our rook placement. These $k$
rooks must lie in $B$, and they must occupy the $k$ unoccupied rows (because
no two distinct rooks in a rook placement may occupy the same row). Thus, for
each of the $k$ unoccupied rows, we must place a rook in this row in one of
the columns $1,2,\ldots,x$ (because this rook must lie in $B$). This can be
done in as follows:

\begin{itemize}
\item First, place a rook in the topmost unoccupied row. This can be done in
$x$ many ways (since it must lie in one of the columns $1,2,\ldots,x$).

\item Next, place a rook in the second (from the top) unoccupied row. This can
be done in $x-1$ many ways (since it must lie in one of the columns
$1,2,\ldots,x$, but not in the same column as the previously placed rook).

\item Next, place a rook in the third (from the top) unoccupied row. This can
be done in $x-2$ many ways (since it must lie in one of the columns
$1,2,\ldots,x$, but not in any of the same columns as the two previously
placed rooks).

\item And so on, until all unoccupied rows have been used up.
\end{itemize}

Thus, in total, these last $k$ rooks may be placed in $x\left(  x-1\right)
\cdots\left(  x-k+1\right)  $ many ways.
\end{itemize}

Thus, the number of rook placements in $D\left(  \mathbf{u}+x\right)  $ of
size $n$ is $\sum_{k\in\left\{  0,1,\ldots,n\right\}  }R_{n-k}\left(
\mathbf{u}\right)  \cdot\left(  x\left(  x-1\right)  \cdots\left(
x-k+1\right)  \right)  $ (because the above algorithm starts out by choosing
$k\in\left\{  0,1,\ldots,n\right\}  $, and then involves $R_{n-k}\left(
\mathbf{u}\right)  $ choices in the first step and $x\left(  x-1\right)
\cdots\left(  x-k+1\right)  $ choices in the second). In other words,%
\[
R_{n}\left(  \mathbf{u}+x\right)  =\sum_{k\in\left\{  0,1,\ldots,n\right\}
}R_{n-k}\left(  \mathbf{u}\right)  \cdot\left(  x\left(  x-1\right)
\cdots\left(  x-k+1\right)  \right)
\]
(since $R_{n}\left(  \mathbf{u}+x\right)  $ is the number of all rook
placements in $D\left(  \mathbf{u}+x\right)  $ of size $n$). Hence,%
\[
R_{n}\left(  \mathbf{u}+x\right)  =\underbrace{\sum_{k\in\left\{
0,1,\ldots,n\right\}  }}_{=\sum_{k=0}^{n}}R_{n-k}\left(  \mathbf{u}\right)
\cdot\underbrace{\left(  x\left(  x-1\right)  \cdots\left(  x-k+1\right)
\right)  }_{\substack{=x^{\underline{k}}\\\text{(by the definition of
}x^{\underline{k}}\text{)}}}=\sum_{k=0}^{n}R_{n-k}\left(  \mathbf{u}\right)
x^{\underline{k}}.
\]
This solves Exercise \ref{exe.rook.main-thm} \textbf{(a)}.

\textbf{(b)} Let $x\in\mathbb{N}$. Then, $u_{1}+x\geq u_{2}+x\geq\cdots\geq
u_{n}+x$ (since $u_{1}\geq u_{2}\geq\cdots\geq u_{n}$) and $\mathbf{u}%
+x=\left(  u_{1}+x,u_{2}+x,\ldots,u_{n}+x\right)  $. Hence, Proposition
\ref{prop.rook.Rn} (applied to $\mathbf{u}+x$ and $u_{i}+x$ instead of
$\mathbf{u}$ and $u_{i}$) yields%
\begin{align}
R_{n}\left(  \mathbf{u}+x\right)   &  =\prod_{i=0}^{n-1}\left(  \left(
u_{n-i}+x\right)  -i\right)  =\prod_{i=1}^{n}\left(  \left(
\underbrace{u_{n-\left(  n-i\right)  }}_{=u_{i}}+x\right)  -\left(
n-i\right)  \right) \nonumber\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{here, we have substituted }n-i\text{ for
}i\text{ in the product}\right) \nonumber\\
&  =\prod_{i=1}^{n}\underbrace{\left(  \left(  u_{i}+x\right)  -\left(
n-i\right)  \right)  }_{=\left(  u_{i}+i\right)  -n+x}=\prod_{i=1}^{n}\left(
\left(  u_{i}+i\right)  -n+x\right)  . \label{sol.rook.main-thm.b.Rnu}%
\end{align}


Exercise \ref{exe.rook.main-thm} \textbf{(a)} yields%
\[
R_{n}\left(  \mathbf{u}+x\right)  =\sum_{k=0}^{n}R_{n-k}\left(  \mathbf{u}%
\right)  x^{\underline{k}}.
\]
Hence,%
\begin{equation}
\sum_{k=0}^{n}R_{n-k}\left(  \mathbf{u}\right)  x^{\underline{k}}=R_{n}\left(
\mathbf{u}+x\right)  =\prod_{i=1}^{n}\left(  \left(  u_{i}+i\right)
-n+x\right)  \label{sol.rook.main-thm.b.1}%
\end{equation}
(by (\ref{sol.rook.main-thm.b.Rnu})). The same argument (applied to
$\mathbf{v}$ and $v_{i}$ instead of $\mathbf{u}$ and $u_{i}$) yields%
\begin{equation}
\sum_{k=0}^{n}R_{n-k}\left(  \mathbf{v}\right)  x^{\underline{k}}=\prod
_{i=1}^{n}\left(  \left(  v_{i}+i\right)  -n+x\right)  .
\label{sol.rook.main-thm.b.2}%
\end{equation}


But we have assumed 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.
Hence, the products $\prod_{i=1}^{n}\left(  \left(  u_{i}+i\right)
-n+x\right)  $ and $\prod_{i=1}^{n}\left(  \left(  v_{i}+i\right)
-n+x\right)  $ contain the same factors, up to order. Therefore, these two
products are equal. In other words,%
\[
\prod_{i=1}^{n}\left(  \left(  u_{i}+i\right)  -n+x\right)  =\prod_{i=1}%
^{n}\left(  \left(  v_{i}+i\right)  -n+x\right)  .
\]
Hence, (\ref{sol.rook.main-thm.b.1}) becomes%
\begin{align*}
\sum_{k=0}^{n}R_{n-k}\left(  \mathbf{u}\right)  x^{\underline{k}}  &
=\prod_{i=1}^{n}\left(  \left(  u_{i}+i\right)  -n+x\right)  =\prod_{i=1}%
^{n}\left(  \left(  v_{i}+i\right)  -n+x\right) \\
&  =\sum_{k=0}^{n}R_{n-k}\left(  \mathbf{v}\right)  x^{\underline{k}%
}\ \ \ \ \ \ \ \ \ \ \left(  \text{by (\ref{sol.rook.main-thm.b.2})}\right)  .
\end{align*}


Now, forget that we fixed $x$. We thus have proven that each $x\in\mathbb{N}$
satisfies $\sum_{k=0}^{n}R_{n-k}\left(  \mathbf{u}\right)  x^{\underline{k}%
}=\sum_{k=0}^{n}R_{n-k}\left(  \mathbf{v}\right)  x^{\underline{k}}$. Hence,
each $x\in\left\{  0,1,\ldots,n\right\}  $ satisfies $\sum_{k=0}^{n}%
R_{n-k}\left(  \mathbf{u}\right)  x^{\underline{k}}=\sum_{k=0}^{n}%
R_{n-k}\left(  \mathbf{v}\right)  x^{\underline{k}}$. Thus, Exercise
\ref{exe.lower-fac.lin-indep1} \textbf{(b)} (applied to $a_{k}=R_{n-k}\left(
\mathbf{u}\right)  $ and $b_{k}=R_{n-k}\left(  \mathbf{v}\right)  $) yields
that $\left(  R_{n-0}\left(  \mathbf{u}\right)  ,R_{n-1}\left(  \mathbf{u}%
\right)  ,\ldots,R_{n-n}\left(  \mathbf{u}\right)  \right)  =\left(
R_{n-0}\left(  \mathbf{v}\right)  ,R_{n-1}\left(  \mathbf{v}\right)
,\ldots,R_{n-n}\left(  \mathbf{v}\right)  \right)  $. In other words,%
\begin{equation}
R_{n-i}\left(  \mathbf{u}\right)  =R_{n-i}\left(  \mathbf{v}\right)
\ \ \ \ \ \ \ \ \ \ \text{for each }i\in\left\{  0,1,\ldots,n\right\}
\text{.} \label{sol.rook.main-thm.b.4}%
\end{equation}


Recall that we want to prove that $R_{k}\left(  \mathbf{u}\right)
=R_{k}\left(  \mathbf{v}\right)  $ for each $k\in\mathbb{N}$. So let us fix
$k\in\mathbb{N}$. If $k>n$, then $R_{k}\left(  \mathbf{u}\right)
=R_{k}\left(  \mathbf{v}\right)  $ is obvious\footnote{\textit{Proof.} Assume
that $k>n$. Then, (\ref{eq.rook.Rk=0}) yields $R_{k}\left(  \mathbf{u}\right)
=0$. Also, (\ref{eq.rook.Rk=0}) (applied to $\mathbf{v}$ instead of
$\mathbf{u}$) yields $R_{k}\left(  \mathbf{v}\right)  =0$. Thus, $R_{k}\left(
\mathbf{u}\right)  =0=R_{k}\left(  \mathbf{v}\right)  $. Hence, we have proven
$R_{k}\left(  \mathbf{u}\right)  =R_{k}\left(  \mathbf{v}\right)  $ in the
case when $k>n$.}. Hence, for the rest of this proof, we WLOG assume that we
don't have $k>n$. Thus, $k\leq n$, so that $k\in\left\{  0,1,\ldots,n\right\}
$ and therefore $n-k\in\left\{  0,1,\ldots,n\right\}  $. Applying
(\ref{sol.rook.main-thm.b.4}) to $i=n-k$, we thus obtain $R_{n-\left(
n-k\right)  }\left(  \mathbf{u}\right)  =R_{n-\left(  n-k\right)  }\left(
\mathbf{v}\right)  $. This simplifies to $R_{k}\left(  \mathbf{u}\right)
=R_{k}\left(  \mathbf{v}\right)  $. This solves Exercise
\ref{exe.rook.main-thm} \textbf{(b)}.
\end{proof}

\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}

\begin{remark}
Corollary \ref{cor.rook.ISL} has appeared in disguise as
\href{https://mks.mff.cuni.cz/kalva/short/soln/sh9713.html}{Problem 13 on the
IMO Shortlist 1997}. This problem asked:

\begin{statement}
Let $n\in\mathbb{N}$ and $k\in\mathbb{N}$. In town $A$ there are $n$ girls and
$n$ boys and every girl knows every boy. Let $a\left(  n,k\right)  $ be the
number of ways in which $k$ girls can dance with $k$ boys, so that each girl
knows her partner. In town $B$ there are $n$ girls and $2n-1$ boys such that
girl $i$ knows boys $1,2,...,2i-1$ (and no others). Let $b\left(  n,k\right)
$ be the number of ways in which $k$ girls from town $B$ can dance with $k$
boys from town $B$ so that each girl knows her partner. Show that $a\left(
n,k\right)  =b\left(  n,k\right)  $.
\end{statement}

I claim that this follows easily from Corollary \ref{cor.rook.ISL}. Namely,
define an $n$-tuple $\mathbf{u}\in\mathbb{N}^{n}$ by $\mathbf{u}=\left(
2n-1,2n-3,\ldots,5,3,1\right)  $. Then, each rook placement $X$ in $D\left(
\mathbf{u}\right)  $ of size $k$ gives rise to a way in which $k$ girls from
town $B$ can dance with $k$ boys from town $B$ so that each girl knows her
partner (namely, for each $\left(  i,j\right)  \in X$, we let girl $n+1-i$
dance with boy $j$). Conversely, every way in which $k$ girls from town $B$
can dance with $k$ boys from town $B$ so that each girl knows her partner
gives rise to a rook placement $X$ in $D\left(  \mathbf{u}\right)  $ (namely,
$X=\left\{  \left(  i,j\right)  \ \mid\ \text{girl }n+1-i\text{ dances with
boy }j\right\}  $). Thus, we obtain a bijection%
\begin{align*}
&  \left\{  \text{rook placements in }D\left(  \mathbf{u}\right)  \text{ of
size }k\right\} \\
&  \rightarrow\left\{  \text{ways in which }k\text{ girls from town }B\text{
can dance with }k\text{ boys from town }B\right. \\
&  \ \ \ \ \ \ \ \ \ \ \left.  \text{so that each girl knows her
partner}\right\}  .
\end{align*}
This shows that the sizes of the two sets involved in this bijection are
equal. Since the size of the first set is $R_{k}\left(  \mathbf{u}\right)  $,
while the size of the second set is $b\left(  n,k\right)  $, we thus conclude
that $R_{k}\left(  \mathbf{u}\right)  =b\left(  n,k\right)  $.

Similarly, we can prove that $R_{k}\left(  \mathbf{v}\right)  =a\left(
n,k\right)  $, where $\mathbf{v}\in\mathbb{N}^{n}$ is the $n$-tuple defined by
$\mathbf{v}=\left(  \underbrace{n,n,\ldots,n}_{n\text{ times}}\right)  $. But
we have $R_{k}\left(  \mathbf{u}\right)  =R_{k}\left(  \mathbf{v}\right)  $
(as we showed in the proof of Corollary \ref{cor.rook.ISL}). Thus, $a\left(
n,k\right)  =R_{k}\left(  \mathbf{v}\right)  =R_{k}\left(  \mathbf{u}\right)
=b\left(  n,k\right)  $; this solves the above problem from the IMO Shortlist 1997.

This problem also appears in \cite[Exercise 5.12]{AndFen04}.
\end{remark}

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}
\label{exe.perm.aj-ai-sum}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}

Exercise \ref{exe.perm.aj-ai-sum} is \cite[Exercise 5.23]{detnotes}; we refer
to that place for its solution.

\begin{noncompile}
(I obtained Exercise \ref{exe.perm.aj-ai-sum} by generalizing \cite[Corollary
2.6]{SacUlf12}, after some transformations.)
\end{noncompile}

\subsection{A hollowed-out determinant}

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

Recall that for any $n\in\mathbb{N}$, the determinant $\det A$ of an $n\times
n$-matrix $A=\left(  a_{i,j}\right)  _{1\leq i\leq n,\ 1\leq j\leq n}$ (this
notation means that $A$ is an $n\times n$-matrix whose $\left(  i,j\right)
$-th entry is $a_{i,j}$ for all $i$ and $j$) is given by%
\begin{align}
\det A  &  =\sum_{\sigma\in S_{n}}\left(  -1\right)  ^{\sigma}%
\underbrace{a_{1,\sigma\left(  1\right)  }a_{2,\sigma\left(  2\right)  }\cdots
a_{n,\sigma\left(  n\right)  }}_{=\prod_{i=1}^{n}a_{i,\sigma\left(  i\right)
}}\label{eq.det.eq.1}\\
&  =\sum_{\sigma\in S_{n}}\left(  -1\right)  ^{\sigma}\prod_{i=1}%
^{n}a_{i,\sigma\left(  i\right)  }. \label{eq.det.eq.2}%
\end{align}
Here, as usual, $S_{n}$ denotes the set of all permutations of $\left[
n\right]  =\left\{  1,2,\ldots,n\right\}  $.

\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%
\begin{equation}
\text{every }i\in P\text{ and }j\in Q\text{ satisfy }a_{i,j}=0.
\label{eq.exe.det.0-via-PQ.ass}%
\end{equation}
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}

Exercise \ref{exe.det.0-via-PQ} is \cite[Exercise 6.47 \textbf{(a)}]{detnotes}.

\begin{proof}
[Solution to Exercise \ref{exe.det.0-via-PQ} (sketched).]Let $\sigma\in S_{n}$.

Assume (for the sake of contradiction) that $\sigma\left(  P\right)
\subseteq\left[  n\right]  \setminus Q$. Thus,%
\begin{align*}
\left\vert \sigma\left(  P\right)  \right\vert  &  \leq\left\vert \left[
n\right]  \setminus Q\right\vert =\underbrace{\left\vert \left[  n\right]
\right\vert }_{=n}-\left\vert Q\right\vert \ \ \ \ \ \ \ \ \ \ \left(
\text{since }Q\subseteq\left[  n\right]  \right) \\
&  =n-\left\vert Q\right\vert <\left\vert P\right\vert
\ \ \ \ \ \ \ \ \ \ \left(  \text{since }\left\vert P\right\vert +\left\vert
Q\right\vert >n\right)  .
\end{align*}
But the map $\sigma$ is injective (since it is a permutation); thus,
$\left\vert \sigma\left(  P\right)  \right\vert =\left\vert P\right\vert $.
Hence, $\left\vert P\right\vert =\left\vert \sigma\left(  P\right)
\right\vert <\left\vert P\right\vert $, which is absurd. This contradiction
shows that our assumption (that $\sigma\left(  P\right)  \subseteq\left[
n\right]  \setminus Q$) was false. Hence, $\sigma\left(  P\right)
\not \subseteq \left[  n\right]  \setminus Q$. In other words, there exists
some $p\in P$ such that $\sigma\left(  p\right)  \notin\left[  n\right]
\setminus Q$. Consider this $p$.

From $\sigma\left(  p\right)  \in\left[  n\right]  $ and $\sigma\left(
p\right)  \notin\left[  n\right]  \setminus Q$, we obtain $\sigma\left(
p\right)  \in\left[  n\right]  \setminus\left(  \left[  n\right]  \setminus
Q\right)  \subseteq Q$. Hence, (\ref{eq.exe.det.0-via-PQ.ass}) (applied to
$i=p$ and $j=\sigma\left(  p\right)  $) yields $a_{p,\sigma\left(  p\right)
}=0$.

Now, $a_{p,\sigma\left(  p\right)  }$ is a factor of the product $\prod
_{i=1}^{n}a_{i,\sigma\left(  i\right)  }$. Thus, at least one factor of the
product $\prod_{i=1}^{n}a_{i,\sigma\left(  i\right)  }$ is $0$ (namely,
$a_{p,\sigma\left(  p\right)  }=0$). Hence, the whole product must be $0$. In
other words, $\prod_{i=1}^{n}a_{i,\sigma\left(  i\right)  }=0$.

Now, forget that we fixed $\sigma$. We thus have shown that $\prod_{i=1}%
^{n}a_{i,\sigma\left(  i\right)  }=0$ for each $\sigma\in S_{n}$. Hence,
(\ref{eq.det.eq.2}) becomes%
\[
\det A=\sum_{\sigma\in S_{n}}\left(  -1\right)  ^{\sigma}\underbrace{\prod
_{i=1}^{n}a_{i,\sigma\left(  i\right)  }}_{=0}=\sum_{\sigma\in S_{n}}\left(
-1\right)  ^{\sigma}0=0.
\]
This solves Exercise \ref{exe.det.0-via-PQ}.
\end{proof}

\begin{remark}
Exercise \ref{exe.det.0-via-PQ} can also be solved using linear algebra, at
least when the entries of our matrix $A$ belong to a field $\mathbb{F}$ (say,
$\mathbb{Q}$ or $\mathbb{R}$ or $\mathbb{C}$). Namely, in this case, we can
consider the $n$-dimensional $\mathbb{F}$-vector space $\mathbb{F}^{n}$ of all
column vectors with $n$ entries. A vector $v=\left(  v_{1},v_{2},\ldots
,v_{n}\right)  ^{T}$ in $\mathbb{F}^{n}$ is said to be $P$\textit{-trivial} if
all $i\in P$ satisfy $v_{i}=0$. The set $W$ of all $P$-trivial vectors
$v\in\mathbb{F}^{n}$ is an $\mathbb{F}$-vector subspace of $\mathbb{F}^{n}$ of
dimension $n-\left\vert P\right\vert $.

The condition (\ref{eq.exe.det.0-via-PQ.ass}) says that for each $j\in Q$, the
$j$-th column of $A$ is $P$-trivial. Thus, the matrix $A$ has (at least)
$\left\vert Q\right\vert $ many $P$-trivial columns. Thus, the matrix $A$ has
$>n-\left\vert P\right\vert $ many $P$-trivial columns (since $\left\vert
Q\right\vert >n-\left\vert P\right\vert $ (since $\left\vert P\right\vert
+\left\vert Q\right\vert >n$)). But any collection of $>n-\left\vert
P\right\vert $ many $P$-trivial columns must necessarily be linearly dependent
(because all these columns lie in the $\left(  n-\left\vert P\right\vert
\right)  $-dimensional vector space $W$). Hence, the matrix $A$ has some
linearly dependent columns. Consequently, the matrix $A$ cannot be full-rank;
thus, $\det A=0$.

This argument is a valid solution to Exercise \ref{exe.det.0-via-PQ} as it is
stated. However, the combinatorial solution given before is \textquotedblleft
better\textquotedblright\ because it immediately generalizes to situations
where the entries of $A$ don't belong to a field but merely belong to a
commutative ring. (The solution using linear algebra can also be extended to
these situations, but this requires more work, since much of linear algebra
only works over a field.)
\end{remark}

\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}\prod_{\substack{j\in
\left[  n-1\right]  ;\\j\neq i}}a_{j}.
\]

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

Exercise \ref{exe.arrowhead} \textbf{(b)} is a fairly easy exercise on
evaluating determinants, and can be solved in various ways, some of which use
no combinatorics at all. Notice also that Exercise \ref{exe.arrowhead}
\textbf{(b)} is equivalent to \cite[Exercise 6.60 \textbf{(b)}]{detnotes}
(applied to $n-1$, $a_{i}$, $b_{i}$ and $c_{i}$ instead of $n$, $d_{i}$,
$v_{i}$ and $u_{i}$). We shall give a purely combinatorial solution to
Exercise \ref{exe.arrowhead}, which uses the following lemma:

\begin{lemma}
\label{lem.sol.powerdet.gen.allbut1}Let $n\in\mathbb{N}$ and $p\in\left[
n\right]  $. Let $\alpha\in S_{n}$ and $\beta\in S_{n}$. Assume that%
\[
\alpha\left(  i\right)  =\beta\left(  i\right)  \ \ \ \ \ \ \ \ \ \ \text{for
each }i\in\left[  n\right]  \setminus\left\{  p\right\}  .
\]
Then, $\alpha=\beta$.
\end{lemma}

Lemma \ref{lem.sol.powerdet.gen.allbut1} is \cite[Lemma 7.232]{detnotes}, but
you're likely to prove it faster than you can look it up in \cite{detnotes}.
(Also, I might have mentioned it in class.) Basically, Lemma
\ref{lem.sol.powerdet.gen.allbut1} says that a permutation in $S_{n}$ is
uniquely determined by any $n-1$ of its values.

\begin{proof}
[Solution to Exercise \ref{exe.arrowhead} (sketched).]Recall that if $u$ and
$v$ are two distinct elements of $\left[  n\right]  $, then $t_{u,v}$ denotes
the permutation in $S_{n}$ that swaps $u$ with $v$ and leaves all other
numbers unchanged. This is called the transposition of $u$ with $v$.

\textbf{(a)} We claim the following:

\begin{statement}
\textit{Observation 1:} The arrowheaded permutations $\sigma\in S_{n}$ are
precisely the $n-1$ transpositions $t_{1,n},t_{2,n},\ldots,t_{n-1,n}$ and the
identity map $\operatorname*{id}$.
\end{statement}

[\textit{Proof of Observation 1:} It is trivial to check that the $n-1$
transpositions $t_{1,n},t_{2,n},\ldots,t_{n-1,n}$ and the identity map
$\operatorname*{id}$ are arrowheaded. It thus remains to prove that these are
the \textbf{only} arrowheaded permutations $\sigma\in S_{n}$. In other words,
it remains to prove that every arrowheaded permutation $\sigma\in S_{n}$ is
one of these $n-1$ transpositions $t_{1,n},t_{2,n},\ldots,t_{n-1,n}$ or is the
identity map $\operatorname*{id}$.

Assume the contrary. Thus, there exists some arrowheaded permutation
$\sigma\in S_{n}$ that is neither one of the $n-1$ transpositions
$t_{1,n},t_{2,n},\ldots,t_{n-1,n}$ nor is the identity map $\operatorname*{id}%
$. Consider this $\sigma$. There must exist some $j\in\left[  n-1\right]  $
such that $\sigma\left(  j\right)  \neq j$\ \ \ \ \footnote{\textit{Proof.}
Assume the contrary. Thus, $\sigma\left(  i\right)  =i$ for each $i\in\left[
n-1\right]  $. In other words, $\sigma\left(  i\right)  =i$ for each
$i\in\left[  n\right]  \setminus\left\{  n\right\}  $ (since $\left[
n-1\right]  =\left[  n\right]  \setminus\left\{  n\right\}  $). Hence,
$\sigma\left(  i\right)  =i=\operatorname*{id}\left(  i\right)  $ for each
$i\in\left[  n\right]  \setminus\left\{  n\right\}  $. Hence, Lemma
\ref{lem.sol.powerdet.gen.allbut1} (applied to $p=n$, $\alpha=\sigma$ and
$\beta=\operatorname*{id}$) yields $\sigma=\operatorname*{id}$. This
contradicts $\sigma\neq\operatorname*{id}$. This contradiction proves that our
assumption was false, qed.}. Consider such a $j$. Since $\sigma$ is
arrowheaded, we know that each $i\in\left[  n-1\right]  $ satisfies
$\sigma\left(  i\right)  =i$ or $\sigma\left(  i\right)  =n$. Applying this to
$i=j$, we obtain $\sigma\left(  j\right)  =j$ or $\sigma\left(  j\right)  =n$.
Since $\sigma\left(  j\right)  \neq j$, we thus have $\sigma\left(  j\right)
=n=t_{j,n}\left(  j\right)  $ (since the transposition $t_{j,n}$ maps $j$ to
$n$).

Now, let $i\in\left[  n-1\right]  $ be arbitrary. We shall show that
$\sigma\left(  i\right)  =t_{j,n}\left(  i\right)  $.

Indeed, if $i=j$, then this follows immediately from $\sigma\left(  j\right)
=t_{j,n}\left(  j\right)  $. Hence, for the rest of this proof, we WLOG assume
that $i\neq j$. Hence, $\sigma\left(  i\right)  \neq\sigma\left(  j\right)  $
(since $\sigma$ is injective (since $\sigma$ is a permutation)). Thus,
$\sigma\left(  i\right)  \neq\sigma\left(  j\right)  =n$.

Since $i\neq j$ and $i\neq n$ (because $i\in\left[  n-1\right]  $), we have
$t_{j,n}\left(  i\right)  =i$. But recall that $i\in\left[  n-1\right]  $;
thus, $\sigma\left(  i\right)  =i$ or $\sigma\left(  i\right)  =n$ (since
$\sigma$ is arrowheaded). Since $\sigma\left(  i\right)  \neq n$, we thus
conclude that $\sigma\left(  i\right)  =i=t_{j,n}\left(  i\right)  $. Thus, we
have proven that $\sigma\left(  i\right)  =t_{j,n}\left(  i\right)  $.

Now, forget that we fixed $i$. We thus have shown that $\sigma\left(
i\right)  =t_{j,n}\left(  i\right)  $ for each $i\in\left[  n-1\right]  $. In
other words, $\sigma\left(  i\right)  =t_{j,n}\left(  i\right)  $ for each
$i\in\left[  n\right]  \setminus\left\{  n\right\}  $ (since $\left[
n-1\right]  =\left[  n\right]  \setminus\left\{  n\right\}  $). Hence, Lemma
\ref{lem.sol.powerdet.gen.allbut1} (applied to $p=n$, $\alpha=\sigma$ and
$\beta=t_{j,n}$) yields $\sigma=t_{j,n}$. This contradicts the fact that
$\sigma$ is none of the $n-1$ transpositions $t_{1,n},t_{2,n},\ldots
,t_{n-1,n}$. This contradiction concludes our proof of Observation 1.]

Observation 1 describes all arrowheaded permutations $\sigma\in S_{n}$. We
thus only need to find their number.

The $n-1$ transpositions $t_{1,n},t_{2,n},\ldots,t_{n-1,n}$ and the identity
map $\operatorname*{id}$ are $n$ distinct permutations (indeed, they are
distinct, since their values at $n$ are distinct). Thus, Observation 1 yields
that the number of all arrowheaded permutations $\sigma\in S_{n}$ is $n$. This
completes the solution of Exercise \ref{exe.arrowhead} \textbf{(a)}.

\textbf{(b)} Write the $n\times n$-matrix $A$ in the form $A=\left(
a_{i,j}\right)  _{1\leq i\leq n,\ 1\leq j\leq n}$. Thus, for each $i\in\left[
n\right]  $ and $j\in\left[  n\right]  $, we have%
\[
a_{i,j}=%
\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}
.
\]
Hence, in particular,%
\begin{equation}
a_{i,j}=0\ \ \ \ \ \ \ \ \ \ \text{whenever }i\neq n\text{ and }j\neq n\text{
and }i\neq j. \label{sol.arrowhead.b.=01}%
\end{equation}
Hence, if a permutation $\sigma\in S_{n}$ is not arrowheaded, then
\begin{equation}
\prod_{i=1}^{n}a_{i,\sigma\left(  i\right)  }=0. \label{sol.arrowhead.b.=02}%
\end{equation}


[\textit{Proof of (\ref{sol.arrowhead.b.=02}):} Let $\sigma\in S_{n}$ be a
permutation that is not arrowheaded. Thus, not every $i\in\left[  n-1\right]
$ satisfies $\sigma\left(  i\right)  =i$ or $\sigma\left(  i\right)  =n$ (by
the definition of \textquotedblleft arrowheaded\textquotedblright). In other
words, there exists some $p\in\left[  n-1\right]  $ satisfying $\sigma\left(
p\right)  \neq p$ and $\sigma\left(  p\right)  \neq n$. Consider this $p$. We
have $p\neq n$ (since $p\in\left[  n-1\right]  $) and $\sigma\left(  p\right)
\neq n$ and $p\neq\sigma\left(  p\right)  $. Hence, (\ref{sol.arrowhead.b.=01}%
) (applied to $i=p$ and $j=\sigma\left(  p\right)  $) yields $a_{p,\sigma
\left(  p\right)  }=0$. Thus, one of the factors of the product $\prod
_{i=1}^{n}a_{i,\sigma\left(  i\right)  }$ is zero (namely, the factor
$a_{p,\sigma\left(  p\right)  }=0$). Hence, the whole product is zero. This
proves (\ref{sol.arrowhead.b.=02}).]

Now, (\ref{eq.det.eq.2}) yields%
\begin{align}
\det A  &  =\sum_{\sigma\in S_{n}}\left(  -1\right)  ^{\sigma}\prod_{i=1}%
^{n}a_{i,\sigma\left(  i\right)  }\nonumber\\
&  =\sum_{\substack{\sigma\in S_{n};\\\sigma\text{ is arrowheaded}}}\left(
-1\right)  ^{\sigma}\prod_{i=1}^{n}a_{i,\sigma\left(  i\right)  }%
+\sum_{\substack{\sigma\in S_{n};\\\sigma\text{ is not arrowheaded}}}\left(
-1\right)  ^{\sigma}\underbrace{\prod_{i=1}^{n}a_{i,\sigma\left(  i\right)  }%
}_{\substack{=0\\\text{(by (\ref{sol.arrowhead.b.=02}))}}}\nonumber\\
&  =\sum_{\substack{\sigma\in S_{n};\\\sigma\text{ is arrowheaded}}}\left(
-1\right)  ^{\sigma}\prod_{i=1}^{n}a_{i,\sigma\left(  i\right)  }.
\label{sol.arrowhead.b.3}%
\end{align}


But Observation 1 above shows that the arrowheaded permutations $\sigma\in
S_{n}$ are precisely the $n-1$ transpositions $t_{1,n},t_{2,n},\ldots
,t_{n-1,n}$ and the identity map $\operatorname*{id}$. Moreover, as we have
seen in our solution of Exercise \ref{exe.arrowhead} \textbf{(a)}, these are
altogether $n$ distinct permutations. Hence, the sum on the right hand side of
(\ref{sol.arrowhead.b.3}) can be rewritten as follows:%
\begin{align}
&  \sum_{\substack{\sigma\in S_{n};\\\sigma\text{ is arrowheaded}}}\left(
-1\right)  ^{\sigma}\prod_{i=1}^{n}a_{i,\sigma\left(  i\right)  }\nonumber\\
&  =\sum_{k=1}^{n-1}\underbrace{\left(  -1\right)  ^{t_{k,n}}}%
_{\substack{=-1\\\text{(since }t_{k,n}\text{ is a transposition)}}}\prod
_{i=1}^{n}a_{i,t_{k,n}\left(  i\right)  }+\underbrace{\left(  -1\right)
^{\operatorname*{id}}}_{=1}\prod_{i=1}^{n}\underbrace{a_{i,\operatorname*{id}%
\left(  i\right)  }}_{\substack{=a_{i,i}=a_{i}\\\text{(by the definition of
}A\text{)}}}\nonumber\\
&  =\sum_{k=1}^{n-1}\left(  -1\right)  \prod_{i=1}^{n}a_{i,t_{k,n}\left(
i\right)  }+\prod_{i=1}^{n}a_{i}. \label{sol.arrowhead.b.4}%
\end{align}
But each $k\in\left[  n-1\right]  $ satisfies%
\begin{align*}
\prod_{i=1}^{n}a_{i,t_{k,n}\left(  i\right)  }  &  =\underbrace{a_{n,t_{k,n}%
\left(  n\right)  }}_{\substack{=a_{n,k}\\\text{(since }t_{k,n}\left(
n\right)  =k\text{)}}}\underbrace{a_{k,t_{k,n}\left(  k\right)  }%
}_{\substack{=a_{k,n}\\\text{(since }t_{k,n}\left(  k\right)  =n\text{)}%
}}\prod_{\substack{i\in\left[  n\right]  ;\\i\neq n\text{ and }i\neq
k}}\underbrace{a_{i,t_{k,n}\left(  i\right)  }}_{\substack{=a_{i,i}%
\\\text{(since }t_{k,n}\left(  i\right)  =i\\\text{(because }i\neq k\text{ and
}i\neq n\text{))}}}\\
&  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{here, we have split off the factors for }i=n\text{ and for }i=k\\
\text{from the product}%
\end{array}
\right) \\
&  =\underbrace{a_{n,k}}_{\substack{=b_{k}\\\text{(by the definition of
}A\text{)}}}\underbrace{a_{k,n}}_{\substack{=c_{k}\\\text{(by the definition
of }A\text{)}}}\underbrace{\prod_{\substack{i\in\left[  n\right]  ;\\i\neq
n\text{ and }i\neq k}}}_{=\prod_{\substack{i\in\left[  n-1\right]  ;\\i\neq
k}}}\underbrace{a_{i,i}}_{\substack{=a_{i}\\\text{(by the definition of
}A\text{)}}}\\
&  =b_{k}c_{k}\prod_{\substack{i\in\left[  n-1\right]  ;\\i\neq k}}a_{i}%
=b_{k}c_{k}\prod_{\substack{j\in\left[  n-1\right]  ;\\j\neq k}}a_{j}%
\end{align*}
(here, we have renamed the index $i$ as $j$ in the product). Hence,
(\ref{sol.arrowhead.b.4}) becomes%
\begin{align*}
&  \sum_{\substack{\sigma\in S_{n};\\\sigma\text{ is arrowheaded}}}\left(
-1\right)  ^{\sigma}\prod_{i=1}^{n}a_{i,\sigma\left(  i\right)  }\\
&  =\sum_{k=1}^{n-1}\left(  -1\right)  \underbrace{\prod_{i=1}^{n}%
a_{i,t_{k,n}\left(  i\right)  }}_{=b_{k}c_{k}\prod_{\substack{j\in\left[
n-1\right]  ;\\j\neq k}}a_{j}}+\prod_{i=1}^{n}a_{i}\\
&  =\underbrace{\sum_{k=1}^{n-1}\left(  -1\right)  b_{k}c_{k}\prod
_{\substack{j\in\left[  n-1\right]  ;\\j\neq k}}a_{j}}_{=-\sum_{k=1}%
^{n-1}b_{k}c_{k}\prod_{\substack{j\in\left[  n-1\right]  ;\\j\neq k}}a_{j}%
}+\underbrace{\prod_{i=1}^{n}a_{i}}_{=a_{1}a_{2}\cdots a_{n}}\\
&  =-\sum_{k=1}^{n-1}b_{k}c_{k}\prod_{\substack{j\in\left[  n-1\right]
;\\j\neq k}}a_{j}+a_{1}a_{2}\cdots a_{n}=a_{1}a_{2}\cdots a_{n}-\sum
_{k=1}^{n-1}b_{k}c_{k}\prod_{\substack{j\in\left[  n-1\right]  ;\\j\neq
k}}a_{j}\\
&  =a_{1}a_{2}\cdots a_{n}-\sum_{i=1}^{n-1}b_{i}c_{i}\prod_{\substack{j\in
\left[  n-1\right]  ;\\j\neq i}}a_{j}%
\end{align*}
(here, we have renamed the summation index $k$ as $i$). Thus,
(\ref{sol.arrowhead.b.3}) becomes%
\[
\det A=\sum_{\substack{\sigma\in S_{n};\\\sigma\text{ is arrowheaded}}}\left(
-1\right)  ^{\sigma}\prod_{i=1}^{n}a_{i,\sigma\left(  i\right)  }=a_{1}%
a_{2}\cdots a_{n}-\sum_{i=1}^{n-1}b_{i}c_{i}\prod_{\substack{j\in\left[
n-1\right]  ;\\j\neq i}}a_{j}.
\]
This solves Exercise \ref{exe.arrowhead} \textbf{(b)}.
\end{proof}

\begin{thebibliography}{99999999}                                                                                         %


\bibitem[AndFen04]{AndFen04}Titu Andreescu, Zuming Feng, \textit{A Path to
Combinatorics for Undergraduates: Counting Strategies}, Springer 2004.

\bibitem[Grinbe16]{detnotes}Darij Grinberg, \textit{Notes on the combinatorial
fundamentals of algebra}, 10 January 2019.\newline%
\url{http://www.cip.ifi.lmu.de/~grinberg/primes2015/sols.pdf} \newline The
numbering of theorems and formulas in this link might shift when the project
gets updated; for a \textquotedblleft frozen\textquotedblright\ version whose
numbering is guaranteed to match that in the citations above, see
\url{https://github.com/darijgr/detnotes/releases/tag/2019-01-10} .

\bibitem[Loehr11]{Loehr-BC}%
\href{http://www.math.vt.edu/people/nloehr/bijbook.html}{Nicholas A. Loehr,
\textit{Bijective Combinatorics}, Chapman \& Hall/CRC 2011.}

\begin{verlong}


\bibitem[SacUlf12]{SacUlf12}Joshua Sack, Henning \'{U}lfarsson,
\textit{Refined inversion statistics on permutations},
arXiv:1106.1995v2.\newline\url{https://arxiv.org/abs/1106.1995v2}
\end{verlong}
\end{thebibliography}


\end{document}