% The LaTeX below is mostly computer-generated (for reasons of speed); don't expect it to be very readable. Sorry.

\documentclass[paper=a4, fontsize=12pt]{scrartcl}%
\usepackage[T1]{fontenc}
\usepackage[english]{babel}
\usepackage{amsmath,amsfonts,amsthm,amssymb}
\usepackage{mathrsfs}
\usepackage{sectsty}
\usepackage{hyperref}
\usepackage{graphicx}
\usepackage{framed}
\usepackage{ifthen}
\usepackage{lastpage}
\usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage}
\usepackage[height=10in,a4paper,hmargin={1in,0.8in}]{geometry}
\usepackage[usenames,dvipsnames]{xcolor}
\usepackage{tikz}
\usepackage{verbatim}
\usepackage{ytableau}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}%
\setcounter{MaxMatrixCols}{30}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Thursday, January 10, 2019 01:59:52}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%BeginMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
%EndMSIPreambleData
\allsectionsfont{\centering \normalfont\scshape}
\setlength\parindent{20pt}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\Z}[1]{\mathbb{Z}/#1\mathbb{Z}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\lcm}{\operatorname{lcm}}
\newcommand{\Des}{\operatorname{Des}}
\newcommand{\rev}{\operatorname{rev}}
\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{\floor}[1]{\left\lfloor #1 \right\rfloor}
\newcommand{\verts}[1]{\operatorname{V}\left( #1 \right)}
\newcommand{\edges}[1]{\operatorname{E}\left( #1 \right)}
\newcommand{\arcs}[1]{\operatorname{A}\left( #1 \right)}
\newcommand{\lf}[2]{#1^{\underline{#2}}}
\newcommand{\underbrack}[2]{\underbrace{#1}_{\substack{#2}}}
\newcommand{\horrule}[1]{\rule{\linewidth}{#1}}
\newcommand{\nnn}{\nonumber\\}
\newcommand{\sslash}{\mathbin{/\mkern-6mu/}}
\let\sumnonlimits\sum
\let\prodnonlimits\prod
\let\cupnonlimits\bigcup
\let\capnonlimits\bigcap
\renewcommand{\sum}{\sumnonlimits\limits}
\renewcommand{\prod}{\prodnonlimits\limits}
\renewcommand{\bigcup}{\cupnonlimits\limits}
\renewcommand{\bigcap}{\capnonlimits\limits}
\newtheoremstyle{plainsl}
{8pt plus 2pt minus 4pt}
{8pt plus 2pt minus 4pt}
{\slshape}
{0pt}
{\bfseries}
{.}
{5pt plus 1pt minus 1pt}
{}
\theoremstyle{plainsl}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{exercise}[theorem]{Exercise}
\newtheorem{examples}[theorem]{Examples}
\newtheorem{algorithm}[theorem]{Algorithm}
\newtheorem{question}[theorem]{Question}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newenvironment{statement}{\begin{quote}}{\end{quote}}
\newenvironment{fineprint}{\begin{small}}{\end{small}}
\newcommand{\myname}{Darij Grinberg}
\newcommand{\myid}{00000000}
\newcommand{\mymail}{dgrinber@umn.edu}
\newcommand{\psetnumber}{4}
\ihead{Solutions to homework set \#\psetnumber}
\ohead{page \thepage\ of \pageref{LastPage}}
\ifoot{\myname, \myid}
\ofoot{\mymail}
\begin{document}

\title{ \normalfont {\normalsize \textsc{University of Minnesota, School of
Mathematics} }\\[25pt] \rule{\linewidth}{0.5pt} \\[0.4cm] {\huge Math 5705: Enumerative Combinatorics, }\\Fall 2018: Homework 4 (preliminary version)\\\rule{\linewidth}{2pt} \\[0.5cm] }
\author{Darij Grinberg}
\maketitle

%Print the title


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

\section{Exercise 1}

\subsection{Problem}

Let $n \in\mathbb{N}$ and $\sigma\in S_{n}$. Let $i$ and $j$ be two elements
of $\left[  n \right]  $ such that $i<j$ and $\sigma\left(  i \right)  >
\sigma\left(  j \right)  $. Let $Q$ be the set of all $k \in\left\{
i+1,i+2,\ldots,j-1 \right\}  $ satisfying $\sigma\left(  i \right)  >
\sigma\left(  k \right)  > \sigma\left(  j \right)  $. Prove that
\[
\ell\left(  \sigma\circ t_{i,j} \right)  = \ell\left(  \sigma\right)  - 2
\left|  Q \right|  - 1 .
\]


\subsection{Remark}

This exercise implies that, in particular, $\ell\left(  \sigma\circ t_{i,j}
\right)  < \ell\left(  \sigma\right)  $; this answers the question on page 213
of the
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18f/5705-2018-10-22.pdf}{notes
from class (2018-10-22)}.

\subsection{Solution}

Jacob Elafandi gives a somewhat laborious but simple solution in
\cite{Elafan18}.

I give a different solution in \cite[Exercise 5.20]{detnotes}.

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

\section{Exercise 2}

\subsection{Problem}

Let $n \in\mathbb{N}$ and $\pi\in S_{n}$.

\begin{enumerate}
\item[\textbf{(a)}] Prove that
\[
\sum_{\substack{1\leq i<j\leq n; \\\pi\left(  i \right)  > \pi\left(  j
\right)  }} \left(  \pi\left(  j \right)  - \pi\left(  i \right)  \right)  =
\sum_{\substack{1\leq i<j\leq n; \\\pi\left(  i \right)  > \pi\left(  j
\right)  }} \left(  i - j \right)  .
\]


\item[\textbf{(b)}] Prove that%
\[
\sum_{\substack{1\leq i<j\leq n; \\\pi\left(  i\right)  <\pi\left(  j\right)
}}\left(  \pi\left(  j\right)  -\pi\left(  i\right)  \right)  =\sum
_{\substack{1\leq i<j\leq n; \\\pi\left(  i\right)  <\pi\left(  j\right)
}}\left(  j-i\right)  .
\]

\end{enumerate}

\subsection{Solution}

We shall use the following fact:

\begin{proposition}
\label{prop.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. (Here, \textquotedblleft
number\textquotedblright\ means \textquotedblleft real
number\textquotedblright\ or \textquotedblleft complex
number\textquotedblright\ or \textquotedblleft rational
number\textquotedblright, as you prefer; this makes no difference.) 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 summation sign \textquotedblleft$\sum_{\substack{1\leq i<j\leq n;
\\\sigma\left(  i\right)  >\sigma\left(  j\right)  }}$\textquotedblright%
\ means \textquotedblleft$\sum_{\substack{\left(  i,j\right)  \in\left\{
1,2,\ldots,n\right\}  ^{2}; \\i<j\text{ and }\sigma\left(  i\right)
>\sigma\left(  j\right)  }}$\textquotedblright; this is a sum over all
inversions of $\sigma$.]
\end{proposition}

Proposition \ref{prop.exe.perm.aj-ai-sum} is \cite[Exercise 5.23]{detnotes}.
For a different proof of it, see \cite[Exercise 4]{Gorski18}.

Now, let us solve the exercise. We have $\pi\in S_{n}$. In other words, $\pi$
is a permutation of $\left[  n\right]  $. In other words, $\pi$ is a bijection
$\left[  n\right]  \rightarrow\left[  n\right]  $. Hence, we can substitute
$\pi\left(  i\right)  $ for $i$ in the sum $\sum_{i\in\left[  n\right]  }%
i^{2}$. We thus obtain%
\begin{equation}
\sum_{i\in\left[  n\right]  }i^{2}=\sum_{i\in\left[  n\right]  }\left(
\pi\left(  i\right)  \right)  ^{2}. \label{sol.perm.pij-pii-sum.1}%
\end{equation}


\textbf{(a)} Proposition \ref{prop.exe.perm.aj-ai-sum} (applied to $\sigma
=\pi$ and $a_{k}=\pi\left(  k\right)  +k$) yields%
\begin{align*}
\sum_{\substack{1\leq i<j\leq n;\\\pi\left(  i\right)  >\pi\left(  j\right)
}}\left(  \left(  \pi\left(  j\right)  +j\right)  -\left(  \pi\left(
i\right)  +i\right)  \right)   &  =\underbrace{\sum_{i=1}^{n}}_{=\sum
_{i\in\left[  n\right]  }}\underbrace{\left(  \pi\left(  i\right)  +i\right)
\left(  i-\pi\left(  i\right)  \right)  }_{\substack{=\left(  i+\pi\left(
i\right)  \right)  \left(  i-\pi\left(  i\right)  \right)  \\=i^{2}-\left(
\pi\left(  i\right)  \right)  ^{2}\\\text{(since }\left(  x+y\right)  \left(
x-y\right)  =x^{2}-y^{2}\\\text{for any two numbers }x\text{ and }y\text{)}%
}}\\
&  =\sum_{i\in\left[  n\right]  }\left(  i^{2}-\left(  \pi\left(  i\right)
\right)  ^{2}\right)  =\sum_{i\in\left[  n\right]  }i^{2}-\sum_{i\in\left[
n\right]  }\left(  \pi\left(  i\right)  \right)  ^{2}=0
\end{align*}
(by \eqref{sol.perm.pij-pii-sum.1}). Hence,%
\begin{align*}
0  &  =\sum_{\substack{1\leq i<j\leq n;\\\pi\left(  i\right)  >\pi\left(
j\right)  }}\underbrace{\left(  \left(  \pi\left(  j\right)  +j\right)
-\left(  \pi\left(  i\right)  +i\right)  \right)  }_{=\left(  \pi\left(
j\right)  -\pi\left(  i\right)  \right)  -\left(  i-j\right)  }\\
&  =\sum_{\substack{1\leq i<j\leq n;\\\pi\left(  i\right)  >\pi\left(
j\right)  }}\left(  \left(  \pi\left(  j\right)  -\pi\left(  i\right)
\right)  -\left(  i-j\right)  \right)  =\sum_{\substack{1\leq i<j\leq
n;\\\pi\left(  i\right)  >\pi\left(  j\right)  }}\left(  \pi\left(  j\right)
-\pi\left(  i\right)  \right)  -\sum_{\substack{1\leq i<j\leq n;\\\pi\left(
i\right)  >\pi\left(  j\right)  }}\left(  i-j\right)  .
\end{align*}
Adding $\sum_{\substack{1\leq i<j\leq n;\\\pi\left(  i\right)  >\pi\left(
j\right)  }}\left(  i-j\right)  $ to both sides of this equality, we obtain%
\[
\sum_{\substack{1\leq i<j\leq n;\\\pi\left(  i\right)  >\pi\left(  j\right)
}}\left(  i-j\right)  =\sum_{\substack{1\leq i<j\leq n;\\\pi\left(  i\right)
>\pi\left(  j\right)  }}\left(  \pi\left(  j\right)  -\pi\left(  i\right)
\right)  .
\]
This solves part \textbf{(a)} of the exercise.

\textbf{(b)} Let $w_{0}$ denote the permutation in $S_{n}$ which sends each
$k\in\left[  n\right]  $ to $n+1-k$. Define a permutation $\sigma\in S_{n}$ by
$\sigma=w_{0}\circ\pi$. Thus, each $k\in\left[  n\right]  $ satisfies%
\begin{equation}
\underbrace{\sigma}_{=w_{0}\circ\pi}\left(  k\right)  =\left(  w_{0}\circ
\pi\right)  \left(  k\right)  =w_{0}\left(  \pi\left(  k\right)  \right)
=n+1-\pi\left(  k\right)  \label{sol.perm.pij-pii-sum.b.1}%
\end{equation}
(by the definition of $w_{0}$).

For any $\left(  i,j\right)  \in\left[  n\right]  ^{2}$, we have the following
chain of logical equivalences:%
\begin{align*}
\left(  \underbrace{\sigma\left(  i\right)  }_{\substack{=n+1-\pi\left(
i\right)  \\\text{(by \eqref{sol.perm.pij-pii-sum.b.1}}\\\text{(applied to
}k=i\text{))}}}>\underbrace{\sigma\left(  j\right)  }_{\substack{=n+1-\pi
\left(  j\right)  \\\text{(by \eqref{sol.perm.pij-pii-sum.b.1}}%
\\\text{(applied to }k=j\text{))}}}\right)  \  &  \Longleftrightarrow\ \left(
n+1-\pi\left(  i\right)  >n+1-\pi\left(  j\right)  \right) \\
&  \Longleftrightarrow\ \left(  \pi\left(  i\right)  <\pi\left(  j\right)
\right)  .
\end{align*}
Thus, for any $\left(  i,j\right)  \in\left[  n\right]  ^{2}$, the condition
$\left(  \sigma\left(  i\right)  >\sigma\left(  j\right)  \right)  $ is
equivalent to $\left(  \pi\left(  i\right)  <\pi\left(  j\right)  \right)  $.
Hence, the summation sign \textquotedblleft$\sum_{\substack{1\leq i<j\leq
n;\\\sigma\left(  i\right)  >\sigma\left(  j\right)  }}$\textquotedblright%
\ can be rewritten as \textquotedblleft$\sum_{\substack{1\leq i<j\leq
n;\\\pi\left(  i\right)  <\pi\left(  j\right)  }}$\textquotedblright. In other
words, we have%
\[
\sum_{\substack{1\leq i<j\leq n;\\\sigma\left(  i\right)  >\sigma\left(
j\right)  }}=\sum_{\substack{1\leq i<j\leq n;\\\pi\left(  i\right)
<\pi\left(  j\right)  }}
\]
(an equality between summation signs). Now, part \textbf{(a)} of the exercise
(applied to $\sigma$ instead of $\pi$) yields%
\begin{align*}
\sum_{\substack{1\leq i<j\leq n;\\\sigma\left(  i\right)  >\sigma\left(
j\right)  }}\left(  \sigma\left(  j\right)  -\sigma\left(  i\right)  \right)
&  =\underbrace{\sum_{\substack{1\leq i<j\leq n;\\\sigma\left(  i\right)
>\sigma\left(  j\right)  }}}_{=\sum_{\substack{1\leq i<j\leq n;\\\pi\left(
i\right)  <\pi\left(  j\right)  }}}\underbrace{\left(  i-j\right)
}_{=-\left(  j-i\right)  }=\sum_{\substack{1\leq i<j\leq n;\\\pi\left(
i\right)  <\pi\left(  j\right)  }}\left(  -\left(  j-i\right)  \right) \\
&  =-\sum_{\substack{1\leq i<j\leq n;\\\pi\left(  i\right)  <\pi\left(
j\right)  }}\left(  j-i\right)  .
\end{align*}
Comparing this with%
\begin{align*}
&  \underbrace{\sum_{\substack{1\leq i<j\leq n;\\\sigma\left(  i\right)
>\sigma\left(  j\right)  }}}_{=\sum_{\substack{1\leq i<j\leq n;\\\pi\left(
i\right)  <\pi\left(  j\right)  }}}\left(  \underbrace{\sigma\left(  j\right)
}_{\substack{=n+1-\pi\left(  j\right)  \\\text{(by
\eqref{sol.perm.pij-pii-sum.b.1}}\\\text{(applied to }k=j\text{))}%
}}-\underbrace{\sigma\left(  i\right)  }_{\substack{=n+1-\pi\left(  i\right)
\\\text{(by \eqref{sol.perm.pij-pii-sum.b.1}}\\\text{(applied to }%
k=i\text{))}}}\right) \\
&  =\sum_{\substack{1\leq i<j\leq n;\\\pi\left(  i\right)  <\pi\left(
j\right)  }}\underbrace{\left(  \left(  n+1-\pi\left(  j\right)  \right)
-\left(  n+1-\pi\left(  i\right)  \right)  \right)  }_{=-\left(  \pi\left(
j\right)  -\pi\left(  i\right)  \right)  }=\sum_{\substack{1\leq i<j\leq
n;\\\pi\left(  i\right)  <\pi\left(  j\right)  }}\left(  -\left(  \pi\left(
j\right)  -\pi\left(  i\right)  \right)  \right) \\
&  =-\sum_{\substack{1\leq i<j\leq n;\\\pi\left(  i\right)  <\pi\left(
j\right)  }}\left(  \pi\left(  j\right)  -\pi\left(  i\right)  \right)  ,
\end{align*}
we obtain%
\[
-\sum_{\substack{1\leq i<j\leq n;\\\pi\left(  i\right)  <\pi\left(  j\right)
}}\left(  \pi\left(  j\right)  -\pi\left(  i\right)  \right)  =-\sum
_{\substack{1\leq i<j\leq n;\\\pi\left(  i\right)  <\pi\left(  j\right)
}}\left(  j-i\right)  .
\]
Thus,%
\[
\sum_{\substack{1\leq i<j\leq n;\\\pi\left(  i\right)  <\pi\left(  j\right)
}}\left(  \pi\left(  j\right)  -\pi\left(  i\right)  \right)  =\sum
_{\substack{1\leq i<j\leq n;\\\pi\left(  i\right)  <\pi\left(  j\right)
}}\left(  j-i\right)  .
\]
This solves part \textbf{(b)} of the exercise.

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

\section{Exercise 3}

\subsection{Problem}

Let $n$ be a positive integer. For each $p\in\mathbb{Z}$, we let
\[
D_{n,p}=\left\{  \sigma\in S_{n}\mid\sigma\text{ has exactly $p$
descents}\right\}  .
\]
(Recall that a \textit{descent} of a permutation $\sigma\in S_{n}$ denotes an
element $k\in\left[  n-1\right]  $ satisfying $\sigma\left(  k\right)
>\sigma\left(  k+1\right)  $.)

Let $p \in\mathbb{Z}$. Prove that $\left|  D_{n, p} \right|  = \left|  D_{n,
n-1-p} \right|  $.

\subsection{Solution sketch}

We have $n-1\in\mathbb{N}$ (since $n$ is a positive integer).

Recall that if $\sigma\in S_{n}$ is a permutation, then $\operatorname*{Des}%
\sigma$ denotes the set of all descents of $\sigma$.

Let $w_{0}$ denote the permutation in $S_{n}$ which sends each $k\in\left[
n\right]  $ to $n+1-k$.

Let $\pi\in S_{n}$. Thus, for each $k\in\left[  n-1\right]  $, we have the
following chain of equivalences:%
\begin{align*}
\ \left(  k\in\operatorname*{Des}\left(  w_{0}\circ\pi\right)  \right)  \  &
\Longleftrightarrow\ \left(  k\text{ is a descent of }w_{0}\circ\pi\right) \\
&  \Longleftrightarrow\ \left(  \underbrace{\left(  w_{0}\circ\pi\right)
\left(  k\right)  }_{\substack{=w_{0}\left(  \pi\left(  k\right)  \right)
=n+1-\pi\left(  k\right)  \\\text{(by the definition of }w_{0}\text{)}%
}}>\underbrace{\left(  w_{0}\circ\pi\right)  \left(  k+1\right)
}_{\substack{=w_{0}\left(  \pi\left(  k+1\right)  \right)  =n+1-\pi\left(
k+1\right)  \\\text{(by the definition of }w_{0}\text{)}}}\right) \\
&  \Longleftrightarrow\ \left(  n+1-\pi\left(  k\right)  >n+1-\pi\left(
k+1\right)  \right) \\
&  \Longleftrightarrow\ \left(  \pi\left(  k\right)  <\pi\left(  k+1\right)
\right)  \ \Longleftrightarrow\ \left(  \pi\left(  k\right)  \leq\pi\left(
k+1\right)  \right) \\
&  \qquad\left(  \text{since }\pi\left(  k\right)  =\pi\left(  k+1\right)
\text{ can never hold (because }\pi\in S_{n}\text{)}\right) \\
&  \Longleftrightarrow\ \left(  \text{not }\pi\left(  k\right)  >\pi\left(
k+1\right)  \right)  \ \Longleftrightarrow\ \left(  k\text{ is not a descent
of }\pi\right) \\
&  \Longleftrightarrow\ \left(  k\notin\operatorname*{Des}\pi\right)  .
\end{align*}
In other words, the elements of $\operatorname*{Des}\left(  w_{0}\circ
\pi\right)  $ are precisely the elements of $\left[  n-1\right]  $ that don't
belong to $\operatorname*{Des}\pi$. In other words, the set
$\operatorname*{Des}\left(  w_{0}\circ\pi\right)  $ is the complement of the
set $\operatorname*{Des}\pi$ in $\left[  n-1\right]  $. Thus,%
\begin{equation}
\left\vert \operatorname*{Des}\left(  w_{0}\circ\pi\right)  \right\vert
=\underbrace{\left\vert \left[  n-1\right]  \right\vert }%
_{\substack{=n-1\\\text{(since }n-1\in\mathbb{N}\text{)}}}-\left\vert
\operatorname*{Des}\pi\right\vert =n-1-\left\vert \operatorname*{Des}%
\pi\right\vert . \label{sol.perm.eulerian-num.symm.1}%
\end{equation}


Now, forget that we fixed $\pi$. We thus have proven
\eqref{sol.perm.eulerian-num.symm.1} for each $\pi\in S_{n}$.

Now, let $\pi\in D_{n,p}$. Then, $\pi$ has exactly $p$ descents\footnote{since
$\pi\in D_{n,p}=\left\{  \sigma\in S_{n}\mid\sigma\text{ has exactly $p$
descents}\right\}  $}. In other words, $\left\vert \operatorname*{Des}%
\pi\right\vert =p$. Thus, \eqref{sol.perm.eulerian-num.symm.1} yields
$\left\vert \operatorname*{Des}\left(  w_{0}\circ\pi\right)  \right\vert
=n-1-\underbrace{\left\vert \operatorname*{Des}\pi\right\vert }_{=p}=n-1-p$.
In other words, the permutation $w_{0}\circ\pi$ has exactly $n-1-p$ descents.
In other words, $w_{0}\circ\pi\in D_{n,n-1-p}$ (since the definition of
$D_{n,n-1-p}$ yields $D_{n,n-1-p}=\left\{  \sigma\in S_{n}\mid\sigma\text{ has
exactly $n-1-p$ descents}\right\}  $).

Now, forget that we fixed $\pi$. We thus have proven that $w_{0}\circ\pi\in
D_{n,n-1-p}$ for each $\pi\in D_{n,p}$. Thus, the map
\begin{align}
D_{n,p}  &  \rightarrow D_{n,n-1-p},\nonumber\\
\pi &  \mapsto w_{0}\circ\pi\label{sol.perm.eulerian-num.symm.map1}%
\end{align}
is well-defined. The same argument (but with $p$ replaced by $n-1-p$) shows
that the map%
\begin{align*}
D_{n,n-1-p}  &  \rightarrow D_{n,n-1-\left(  n-1-p\right)  },\\
\pi &  \mapsto w_{0}\circ\pi
\end{align*}
is well-defined. In other words, the map%
\begin{align}
D_{n,n-1-p}  &  \rightarrow D_{n,p},\nonumber\\
\pi &  \mapsto w_{0}\circ\pi\label{sol.perm.eulerian-num.symm.map2}%
\end{align}
is well-defined (since $n-1-\left(  n-1-p\right)  =p$). But $w_{0}\circ
w_{0}=\operatorname*{id}$ (since each $k\in\left[  n\right]  $ satisfies
\begin{align*}
\left(  w_{0}\circ w_{0}\right)  \left(  k\right)   &  =w_{0}\left(
w_{0}\left(  k\right)  \right)  =n+1-\left(  n+1-k\right)  \qquad\left(
\text{by the definition of }w_{0}\right) \\
&  =k=\operatorname*{id}\left(  k\right)
\end{align*}
). Thus, the two maps \eqref{sol.perm.eulerian-num.symm.map1} and
\eqref{sol.perm.eulerian-num.symm.map2} are mutually inverse. Hence, these two
maps are bijections. Thus, we have found a bijection from $D_{n,p}$ to
$D_{n,n-1-p}$. Hence, $\left\vert D_{n,p}\right\vert =\left\vert
D_{n,n-1-p}\right\vert $. This solves the exercise.

\subsection{Remark}

\textbf{1.} A similar solution could have been obtained by using the
permutation $\pi\circ w_{0}$ instead of $w_{0}\circ\pi$. Indeed, similarly to
\eqref{sol.perm.eulerian-num.symm.1}, we also have%
\[
\left\vert \operatorname*{Des}\left(  \pi\circ w_{0}\right)  \right\vert
=n-1-\left\vert \operatorname*{Des}\pi\right\vert \qquad\text{for each }\pi\in
S_{n}.
\]
To prove this, we would have to show that
\[
\operatorname*{Des}\left(  \pi\circ w_{0}\right)  =\left\{  n-k\ \mid
\ k\in\left[  n-1\right]  \setminus\operatorname*{Des}\pi\right\}
\]
(which is only a tad more complicated than proving that $\operatorname*{Des}%
\left(  w_{0}\circ\pi\right)  =\left[  n-1\right]  \setminus
\operatorname*{Des}\pi$).

\textbf{2.} I have snuck a correction into the exercise: It used to only
require $n\in\mathbb{N}$, but now it requires $n$ to be a positive integer.
Indeed, the claim fails for $n=0$. Sorry!

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

\section{Exercise 4}

\subsection{Problem}

Let $n \in\mathbb{N}$. Let $S = \left\{  s_{1} < s_{2} < \cdots< s_{k}
\right\}  $ be a subset of $\left[  n-1 \right]  $. Set $s_{0} = 0$ and
$s_{k+1} = n$. For each $i \in\left[  k+1 \right]  $, set $d_{i} = s_{i} -
s_{i-1}$. (You might remember this construction from the definition of the map
$D$ in the solution to Exercise 1 on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18f/hw-template.pdf}{homework
set \#0}.)

\begin{enumerate}
\item[\textbf{(a)}] Prove that
\[
\left|  \left\{  \sigma\in S_{n} \mid\operatorname{Des} \sigma\subseteq S
\right\}  \right|  = \dbinom{n}{d_{1}, d_{2}, \ldots, d_{k+1}}.
\]
(The term on the right hand side is a multinomial coefficient. The
$\operatorname{Des} \sigma$ on the left hand side denotes the descent set of
$\sigma$, that is, the set of all descents of $\sigma$.)

\item[\textbf{(b)}] Prove that
\[
\left|  \left\{  \sigma\in S_{n} \mid\operatorname{Des} \sigma= S \right\}
\right|  = \sum_{T \subseteq S} \left(  -1 \right)  ^{\left|  S \right|  -
\left|  T \right|  } \left|  \left\{  \sigma\in S_{n} \mid\operatorname{Des}
\sigma\subseteq T \right\}  \right|  .
\]

\end{enumerate}

\subsection{Solution sketch}

\textbf{(a)} A permutation $\sigma\in S_{n}$ satisfies $\operatorname*{Des}%
\sigma\subseteq S$ if and only if it is strictly increasing on each of the
$k+1$ intervals
\[
\left[  s_{0}+1,s_{1}\right]  ,\qquad\left[  s_{1}+1,s_{2}\right]
,\qquad\left[  s_{2}+1,s_{3}\right]  ,\qquad\ldots,\qquad\left[
s_{k}+1,s_{k+1}\right]  .
\]
Hence, a permutation $\sigma\in S_{n}$ satisfying $\operatorname*{Des}%
\sigma\subseteq S$ is uniquely determined by the images%
\[
\sigma\left(  \left[  s_{0}+1,s_{1}\right]  \right)  ,\qquad\sigma\left(
\left[  s_{1}+1,s_{2}\right]  \right)  ,\qquad\sigma\left(  \left[
s_{2}+1,s_{3}\right]  \right)  ,\qquad\ldots,\qquad\sigma\left(  \left[
s_{k}+1,s_{k+1}\right]  \right)
\]
of these $k+1$ intervals (indeed, once these images are known, we can use the
strict increasingness of $\sigma$ on these intervals to reconstruct each value
of $\sigma$). These images must be disjoint subsets of $\left[  n\right]  $
(since $\sigma$ is injective) and have the same sizes as the $k+1$ intervals
themselves (for the same reason); these sizes are%
\[
s_{1}-s_{0}=d_{1},\qquad s_{2}-s_{1}=d_{2},\qquad s_{3}-s_{2}=d_{3}%
,\qquad\ldots,\qquad s_{k+1}-s_{k}=d_{k+1}.
\]
Thus, every permutation $\sigma\in S_{n}$ satisfying $\operatorname*{Des}%
\sigma\subseteq S$ can be constructed by the following algorithm:

\begin{itemize}
\item We choose a $d_{1}$-element subset of $\left[  n\right]  $ to be the
image $\sigma\left(  \left[  s_{0}+1,s_{1}\right]  \right)  $. This subset can
be chosen in $\dbinom{n}{d_{1}}$ ways.

\item Next, we choose a $d_{2}$-element subset of $\left[  n\right]  $ to be
the image $\sigma\left(  \left[  s_{1}+1,s_{2}\right]  \right)  $, requiring
that it be disjoint from the already chosen subset $\sigma\left(  \left[
s_{0}+1,s_{1}\right]  \right)  $. This subset can be chosen in $\dbinom
{n-d_{1}}{d_{2}}$ ways (because by requiring it to be disjoint from the
$d_{1}$-element subset $\sigma\left(  \left[  s_{0}+1,s_{1}\right]  \right)
$, we are forcing it to be a $d_{2}$-element subset of the $\left(
n-d_{1}\right)  $-element set $\left[  n\right]  \setminus\sigma\left(
\left[  s_{0}+1,s_{1}\right]  \right)  $).

\item Next, we choose a $d_{3}$-element subset of $\left[  n\right]  $ to be
the image $\sigma\left(  \left[  s_{2}+1,s_{3}\right]  \right)  $, requiring
that it be disjoint from the already chosen subsets $\sigma\left(  \left[
s_{0}+1,s_{1}\right]  \right)  $ and $\sigma\left(  \left[  s_{1}%
+1,s_{2}\right]  \right)  $. This subset can be chosen in $\dbinom
{n-d_{1}-d_{2}}{d_{3}}$ ways (because by requiring it to be disjoint from the
$d_{1}$-element subset $\sigma\left(  \left[  s_{0}+1,s_{1}\right]  \right)  $
and the $d_{2}$-element subset $\sigma\left(  \left[  s_{1}+1,s_{2}\right]
\right)  $, we are forcing it to be a $d_{3}$-element subset of the $\left(
n-d_{1}-d_{2}\right)  $-element set $\left[  n\right]  \setminus\sigma\left(
\left[  s_{0}+1,s_{1}\right]  \right)  \setminus\sigma\left(  \left[
s_{1}+1,s_{2}\right]  \right)  $\ \ \ \ \footnote{Of course, we are tacitly
using the fact that the two already chosen subsets $\sigma\left(  \left[
s_{0}+1,s_{1}\right]  \right)  $ and $\sigma\left(  \left[  s_{1}%
+1,s_{2}\right]  \right)  $ are disjoint (so that the set $\left[  n\right]
\setminus\sigma\left(  \left[  s_{0}+1,s_{1}\right]  \right)  \setminus
\sigma\left(  \left[  s_{1}+1,s_{2}\right]  \right)  $ really is a $\left(
n-d_{1}-d_{2}\right)  $-element set).}).

\item And so on, until all $k+1$ images%
\[
\sigma\left(  \left[  s_{0}+1,s_{1}\right]  \right)  ,\qquad\sigma\left(
\left[  s_{1}+1,s_{2}\right]  \right)  ,\qquad\sigma\left(  \left[
s_{2}+1,s_{3}\right]  \right)  ,\qquad\ldots,\qquad\sigma\left(  \left[
s_{k}+1,s_{k+1}\right]  \right)
\]
are chosen. As we know, at this point, $\sigma$ is uniquely determined.
\end{itemize}

The total number of ways in which this construction can be carried out is%
\begin{align*}
&  \dbinom{n}{d_{1}}\dbinom{n-d_{1}}{d_{2}}\dbinom{n-d_{1}-d_{2}}{d_{3}}%
\cdots\dbinom{n-d_{1}-d_{2}-\cdots-d_{k}}{d_{k+1}}\\
&  =\prod_{i=0}^{k}\dbinom{n-d_{1}-d_{2}-\cdots-d_{i}}{d_{i+1}}=\prod
_{i=1}^{k+1}\dbinom{n-d_{1}-d_{2}-\cdots-d_{i-1}}{d_{i}}=\dbinom{n}%
{d_{1},d_{2},\ldots,d_{k+1}}%
\end{align*}
(by the first equation in Proposition 2.38 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18f/5705-2018-10-03.pdf}{the
class notes (2018-10-03)}). Thus, the number of permutations $\sigma\in S_{n}$
satisfying $\operatorname*{Des}\sigma\subseteq S$ is $\dbinom{n}{d_{1}%
,d_{2},\ldots,d_{k+1}}$. This solves part \textbf{(a)} of the exercise.

\bigskip

\textbf{(b)} We need the following result:

\begin{proposition}
\label{prop.DIE.destruct2}Let $G$ be a finite set. Let $S$ be a subset of $G$.
Then,%
\[
\sum_{\substack{I\subseteq G;\\S\subseteq I}}\left(  -1\right)  ^{\left\vert
I\right\vert }=\left(  -1\right)  ^{\left\vert S\right\vert }\left[
G=S\right]  .
\]

\end{proposition}

Proposition \ref{prop.DIE.destruct2} was proven during the solution of
Exercise 6 on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18f/hw3s.pdf}{homework set
\#3}.

We have%
\begin{align*}
&  \sum_{T\subseteq S}\left(  -1\right)  ^{\left\vert S\right\vert -\left\vert
T\right\vert }\left\vert \left\{  \sigma\in S_{n}\mid\operatorname{Des}%
\sigma\subseteq T\right\}  \right\vert \\
&  =\sum_{I\subseteq S}\left(  -1\right)  ^{\left\vert S\right\vert
-\left\vert I\right\vert }\underbrace{\left\vert \left\{  \sigma\in S_{n}%
\mid\operatorname{Des}\sigma\subseteq I\right\}  \right\vert }_{=\sum
_{U\subseteq I}\left\vert \left\{  \sigma\in S_{n}\mid\operatorname{Des}%
\sigma=U\right\}  \right\vert }\\
&  \qquad\left(  \text{here, we have renamed the summation index }T\text{ as
}I\right) \\
&  =\sum_{I\subseteq S}\left(  -1\right)  ^{\left\vert S\right\vert
-\left\vert I\right\vert }\sum_{U\subseteq I}\left\vert \left\{  \sigma\in
S_{n}\mid\operatorname{Des}\sigma=U\right\}  \right\vert \\
&  =\underbrace{\sum_{I\subseteq S}\sum_{U\subseteq I}}_{=\sum_{U\subseteq
S}\sum_{\substack{I\subseteq S;\\U\subseteq I}}}\underbrace{\left(  -1\right)
^{\left\vert S\right\vert -\left\vert I\right\vert }}_{=\left(  -1\right)
^{\left\vert S\right\vert }\left(  -1\right)  ^{\left\vert I\right\vert }%
}\left\vert \left\{  \sigma\in S_{n}\mid\operatorname{Des}\sigma=U\right\}
\right\vert \\
&  =\sum_{U\subseteq S}\sum_{\substack{I\subseteq S;\\U\subseteq I}}\left(
-1\right)  ^{\left\vert S\right\vert }\left(  -1\right)  ^{\left\vert
I\right\vert }\left\vert \left\{  \sigma\in S_{n}\mid\operatorname{Des}%
\sigma=U\right\}  \right\vert \\
&  =\sum_{U\subseteq S}\underbrace{\left(  \sum_{\substack{I\subseteq
S;\\U\subseteq I}}\left(  -1\right)  ^{\left\vert I\right\vert }\right)
}_{\substack{=\left(  -1\right)  ^{\left\vert U\right\vert }\left[
S=U\right]  \\\text{(by Proposition \ref{prop.DIE.destruct2},}\\\text{applied
to }S\text{ and }U\text{ instead of }G\text{ and }S\text{)}}}\left(
-1\right)  ^{\left\vert S\right\vert }\left\vert \left\{  \sigma\in S_{n}%
\mid\operatorname{Des}\sigma=U\right\}  \right\vert \\
&  =\sum_{U\subseteq S}\left(  -1\right)  ^{\left\vert U\right\vert }\left[
S=U\right]  \left(  -1\right)  ^{\left\vert S\right\vert }\left\vert \left\{
\sigma\in S_{n}\mid\operatorname{Des}\sigma=U\right\}  \right\vert \\
&  =\sum_{\substack{U\subseteq S;\\U\neq S}}\left(  -1\right)  ^{\left\vert
U\right\vert }\underbrace{\left[  S=U\right]  }_{\substack{=0\\\text{(since
}U\neq S\text{)}}}\left(  -1\right)  ^{\left\vert S\right\vert }\left\vert
\left\{  \sigma\in S_{n}\mid\operatorname{Des}\sigma=U\right\}  \right\vert \\
&  \qquad+\left(  -1\right)  ^{\left\vert S\right\vert }\left[  S=S\right]
\left(  -1\right)  ^{\left\vert S\right\vert }\left\vert \left\{  \sigma\in
S_{n}\mid\operatorname{Des}\sigma=S\right\}  \right\vert \\
&  \qquad\left(  \text{here, we have split off the addend for }U=S\text{ from
the sum}\right)
\end{align*}%
\begin{align*}
&  =\underbrace{\sum_{\substack{U\subseteq S;\\U\neq S}}\left(  -1\right)
^{\left\vert U\right\vert }0\left(  -1\right)  ^{\left\vert S\right\vert
}\left\vert \left\{  \sigma\in S_{n}\mid\operatorname{Des}\sigma=U\right\}
\right\vert }_{=0}\\
&  \qquad+\left(  -1\right)  ^{\left\vert S\right\vert }\underbrace{\left[
S=S\right]  }_{=1}\left(  -1\right)  ^{\left\vert S\right\vert }\left\vert
\left\{  \sigma\in S_{n}\mid\operatorname{Des}\sigma=S\right\}  \right\vert \\
&  =\underbrace{\left(  -1\right)  ^{\left\vert S\right\vert }\left(
-1\right)  ^{\left\vert S\right\vert }}_{=\left(  \left(  -1\right)
^{\left\vert S\right\vert }\right)  ^{2}=1}\left\vert \left\{  \sigma\in
S_{n}\mid\operatorname{Des}\sigma=S\right\}  \right\vert =\left\vert \left\{
\sigma\in S_{n}\mid\operatorname{Des}\sigma=S\right\}  \right\vert .
\end{align*}
This solves part \textbf{(b)} of the exercise.

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

\section{Exercise 5}

\subsection{Problem}

Let $n \in\mathbb{N}$. We shall follow the convention that $t_{i, i}$ denotes
the identity permutation $\operatorname{id} \in S_{n}$ for each $i \in\left[
n \right]  $.

Let $\sigma\in S_{n}$.

It is known that there is a unique $n$-tuple $\left(  i_{1},i_{2},\ldots
,i_{n}\right)  \in\left[  1\right]  \times\left[  2\right]  \times\cdots
\times\left[  n\right]  $ satisfying $\sigma=t_{1,i_{1}}\circ t_{2,i_{2}}%
\circ\cdots\circ t_{n,i_{n}}$. (See \cite[Exercise 5.9]{detnotes} for the
proof of this fact, or -- easier -- do it on your own.) Consider this
$n$-tuple. (It is sometimes called the \textit{transposition code} of $\sigma$.)

For each $k \in\left\{  0, 1, \ldots, n \right\}  $, we define a permutation
$\sigma_{k} \in S_{n}$ by $\sigma_{k} = t_{1, i_{1}} \circ t_{2, i_{2}}
\circ\cdots\circ t_{k, i_{k}}$. Note that this permutation $\sigma_{k}$ leaves
each of the numbers $k+1,k+2,\ldots,n$ unchanged (since all of $i_{1}, i_{2},
\ldots, i_{k}$, as well as $1, 2, \ldots, k$, are $\leq k$).

For each $k \in\left[  n \right]  $, let $m_{k} = \sigma_{k} \left(  k
\right)  $.

\begin{enumerate}
\item[\textbf{(a)}] Show that $m_{k} \in\left[  k \right]  $ for all $k
\in\left[  n \right]  $.

\item[\textbf{(b)}] Show that $\sigma_{k} \left(  i_{k} \right)  = k$ for all
$k \in\left[  n \right]  $.

\item[\textbf{(c)}] Show that $\sigma^{-1} = t_{1, m_{1}} \circ t_{2, m_{2}}
\circ\cdots\circ t_{n, m_{n}}$.

\item[\textbf{(d)}] Let $x_{1}, x_{2}, \ldots, x_{n}, y_{1}, y_{2}, \ldots,
y_{n}$ be any $2n$ numbers. Prove that
\[
\sum_{k=1}^{n} x_{k} y_{k} - \sum_{k=1}^{n} x_{k} y_{\sigma\left(  k \right)
} = \sum_{k=1}^{n} \left(  x_{i_{k}} - x_{k} \right)  \left(  y_{m_{k}} -
y_{k} \right)  .
\]


\item[\textbf{(e)}] Now assume that the numbers $x_{1}, x_{2}, \ldots, x_{n},
y_{1}, y_{2}, \ldots, y_{n}$ are real and satisfy $x_{1} \geq x_{2} \geq
\cdots\geq x_{n}$ and $y_{1} \geq y_{2} \geq\cdots\geq y_{n}$. Conclude that
\[
\sum_{k=1}^{n} x_{k} y_{k} \geq\sum_{k=1}^{n} x_{k} y_{\sigma\left(  k
\right)  }.
\]

\end{enumerate}

\subsection{Remark}

This exercise is part of \cite[Exercise 5.25]{detnotes}.

Parts \textbf{(a)} and \textbf{(c)}, combined, show that $\left(  m_{1},
m_{2}, \ldots, m_{n} \right)  $ is the transposition code of $\sigma^{-1}$.

Part \textbf{(e)} of the exercise is known as the \textit{rearrangement
inequality}. The proof in this exercise is far from its easiest proof, but has
the advantage of ``manifest positivity'' -- i.e., it gives an explicit formula
for the difference between the two sides as a sum of products of nonnegative numbers.

\subsection{Solution sketch}

Let us first notice that any two elements $u,v\in\left[  n\right]  $ and any
permutation $\pi\in S_{n}$ satisfy%
\begin{equation}
t_{\pi\left(  u\right)  ,\pi\left(  v\right)  }\circ\pi=\pi\circ t_{u,v}.
\label{sol.perm.rearrangement.tpi}%
\end{equation}


[\textit{Proof of \eqref{sol.perm.rearrangement.tpi}:} Let $u,v\in\left[
n\right]  $ and $\pi\in S_{n}$. Fix $k\in\left[  n\right]  $. We shall prove
that $\left(  t_{\pi\left(  u\right)  ,\pi\left(  v\right)  }\circ\pi\right)
\left(  k\right)  =\left(  \pi\circ t_{u,v}\right)  \left(  k\right)  $.

Indeed, we are in one of the following three cases:

\textit{Case 1:} We have $k=u$.

\textit{Case 2:} We have $k=v$.

\textit{Case 3:} We have neither $k=u$ nor $k=v$.

Let us first consider Case 1. In this case, we have $k=u$. Thus,
$t_{u,v}\left(  k\right)  =t_{u,v}\left(  u\right)  =v$ (independently of
whether $u=v$ or $u\neq v$). Also, from $k=u$, we obtain%
\[
\left(  t_{\pi\left(  u\right)  ,\pi\left(  v\right)  }\circ\pi\right)
\left(  k\right)  =\left(  t_{\pi\left(  u\right)  ,\pi\left(  v\right)
}\circ\pi\right)  \left(  u\right)  =t_{\pi\left(  u\right)  ,\pi\left(
v\right)  }\left(  \pi\left(  u\right)  \right)  =\pi\left(  v\right)
\]
(again, independently of whether $\pi\left(  u\right)  =\pi\left(  v\right)  $
holds or not). Comparing this with%
\[
\left(  \pi\circ t_{u,v}\right)  \left(  k\right)  =\pi\left(  t_{u,v}\left(
k\right)  \right)  =\pi\left(  v\right)  \qquad\left(  \text{since }%
t_{u,v}\left(  k\right)  =v\right)  ,
\]
we obtain $\left(  t_{\pi\left(  u\right)  ,\pi\left(  v\right)  }\circ
\pi\right)  \left(  k\right)  =\left(  \pi\circ t_{u,v}\right)  \left(
k\right)  $. Hence, $\left(  t_{\pi\left(  u\right)  ,\pi\left(  v\right)
}\circ\pi\right)  \left(  k\right)  =\left(  \pi\circ t_{u,v}\right)  \left(
k\right)  $ is proven in Case 1.

The argument in Case 2 is analogous, and we leave it to the reader.

Let us now consider Case 3. In this case, we have neither $k=u$ nor $k=v$.
Thus, $t_{u,v}\left(  k\right)  =k$ (independently of whether $u=v$ or $u\neq
v$). Also, recall that we have neither $k=u$ nor $k=v$. Thus, we have neither
$\pi\left(  k\right)  =\pi\left(  u\right)  $ nor $\pi\left(  k\right)
=\pi\left(  v\right)  $ (since the map $\pi$ is injective (because $\pi\in
S_{n}$)). Hence, $t_{\pi\left(  u\right)  ,\pi\left(  v\right)  }\left(
\pi\left(  k\right)  \right)  =\pi\left(  k\right)  $ (again, independently of
whether $\pi\left(  u\right)  =\pi\left(  v\right)  $ holds or not). Now,%
\[
\left(  t_{\pi\left(  u\right)  ,\pi\left(  v\right)  }\circ\pi\right)
\left(  k\right)  =t_{\pi\left(  u\right)  ,\pi\left(  v\right)  }\left(
\pi\left(  k\right)  \right)  =\pi\left(  k\right)  .
\]
Comparing this with%
\[
\left(  \pi\circ t_{u,v}\right)  \left(  k\right)  =\pi\left(  t_{u,v}\left(
k\right)  \right)  =\pi\left(  k\right)  \qquad\left(  \text{since }%
t_{u,v}\left(  k\right)  =k\right)  ,
\]
we obtain $\left(  t_{\pi\left(  u\right)  ,\pi\left(  v\right)  }\circ
\pi\right)  \left(  k\right)  =\left(  \pi\circ t_{u,v}\right)  \left(
k\right)  $. Hence, $\left(  t_{\pi\left(  u\right)  ,\pi\left(  v\right)
}\circ\pi\right)  \left(  k\right)  =\left(  \pi\circ t_{u,v}\right)  \left(
k\right)  $ is proven in Case 3.

We have now proven $\left(  t_{\pi\left(  u\right)  ,\pi\left(  v\right)
}\circ\pi\right)  \left(  k\right)  =\left(  \pi\circ t_{u,v}\right)  \left(
k\right)  $ in each of the three Cases 1, 2 and 3. Thus, $\left(
t_{\pi\left(  u\right)  ,\pi\left(  v\right)  }\circ\pi\right)  \left(
k\right)  =\left(  \pi\circ t_{u,v}\right)  \left(  k\right)  $ always holds.

Forget now that we fixed $k$. We thus have shown that $\left(  t_{\pi\left(
u\right)  ,\pi\left(  v\right)  }\circ\pi\right)  \left(  k\right)  =\left(
\pi\circ t_{u,v}\right)  \left(  k\right)  $ for each $k\in\left[  n\right]
$. In other words, $t_{\pi\left(  u\right)  ,\pi\left(  v\right)  }\circ
\pi=\pi\circ t_{u,v}$. Thus, \eqref{sol.perm.rearrangement.tpi} is proven.]

\bigskip

Recall that $\left(  i_{1},i_{2},\ldots,i_{n}\right)  \in\left[  1\right]
\times\left[  2\right]  \times\cdots\times\left[  n\right]  $. Thus,%
\begin{equation}
i_{j}\in\left[  j\right]  \qquad\text{for each }j\in\left[  n\right]  .
\label{sol.perm.rearrangement.1}%
\end{equation}


The definition of $\sigma_{0}$ shows that%
\[
\sigma_{0}=t_{1,i_{1}}\circ t_{2,i_{2}}\circ\cdots\circ t_{0,i_{0}}=\left(
\text{composition of }0\text{ permutations}\right)  =\operatorname*{id}.
\]
The definition of $\sigma_{n}$ shows that%
\[
\sigma_{n}=t_{1,i_{1}}\circ t_{2,i_{2}}\circ\cdots\circ t_{n,i_{n}}=\sigma.
\]


\bigskip

\textbf{(a)} Let $k\in\left[  n\right]  $. Then, from
\eqref{sol.perm.rearrangement.1}, we conclude that each $j\in\left[  k\right]
$ satisfies $i_{j}\in\left[  j\right]  \subseteq\left[  k\right]  $ (since
$j\leq k$). Hence, the $k$ numbers $i_{1},i_{2},\ldots,i_{k}$ all belong to
$\left[  k\right]  $. The same holds for the $k$ numbers $1,2,\ldots,k$. Thus,
the $k$ permutations $t_{1,i_{1}},t_{2,i_{2}},\ldots,t_{k,i_{k}}$ all preserve
the set $\left[  k\right]  $\ \ \ \ \footnote{We say that a map $\tau:\left[
n\right]  \rightarrow\left[  n\right]  $ \textit{preserves} a subset $S$ of
$\left[  n\right]  $ if and only if it satisfies $\tau\left(  S\right)
\subseteq S$. This does \textbf{not} mean that $\tau\left(  s\right)  =s$ for
each $s\in S$; it only means that $\tau$ sends each element of $S$ to a
(possibly different) element of $S$.}. Hence, their composition $t_{1,i_{1}%
}\circ t_{2,i_{2}}\circ\cdots\circ t_{k,i_{k}}$ preserves the set $\left[
k\right]  $ as well\footnote{Here, we are using the following fact: If $S$ is
a subset of $\left[  n\right]  $, and if $\alpha_{1},\alpha_{2},\ldots
,\alpha_{k}$ are $k$ maps from $\left[  n\right]  $ to $\left[  n\right]  $
that all preserve the set $S$, then the composition $\alpha_{1}\circ\alpha
_{2}\circ\cdots\circ\alpha_{k}$ of these $k$ maps must preserve the set $S$ as
well. (This is easy to prove by induction on $k$.)}. In view of $\sigma
_{k}=t_{1,i_{1}}\circ t_{2,i_{2}}\circ\cdots\circ t_{k,i_{k}}$, this rewrites
as follows: The map $\sigma_{k}$ preserves the set $\left[  k\right]  $. In
other words, $\sigma_{k}\left(  \left[  k\right]  \right)  \subseteq\left[
k\right]  $. Now, $k\in\left[  k\right]  $, so that $\sigma_{k}\left(
k\right)  \in\sigma_{k}\left(  \left[  k\right]  \right)  \subseteq\left[
k\right]  $. Hence, $m_{k}=\sigma_{k}\left(  k\right)  \in\left[  k\right]  $.
This solves part \textbf{(a)} of the exercise.

\bigskip

\textbf{(b)} Let $k\in\left[  n\right]  $. Then, from
\eqref{sol.perm.rearrangement.1}, we conclude that each $j\in\left[
k-1\right]  $ satisfies $i_{j}\in\left[  j\right]  \subseteq\left[
k-1\right]  $ (since $j\leq k-1$). Hence, the $k-1$ numbers $i_{1}%
,i_{2},\ldots,i_{k-1}$ all belong to $\left[  k-1\right]  $. The same holds
for the $k-1$ numbers $1,2,\ldots,k-1$. Thus, the $k-1$ permutations
$t_{1,i_{1}},t_{2,i_{2}},\ldots,t_{k-1,i_{k-1}}$ all leave each of the numbers
$k,k+1,\ldots,n$ unchanged. Hence, their composition $t_{1,i_{1}}\circ
t_{2,i_{2}}\circ\cdots\circ t_{k-1,i_{k-1}}$ leaves each of the numbers
$k,k+1,\ldots,n$ unchanged. In particular, it thus leaves the number $k$
unchanged. In other words,%
\[
\left(  t_{1,i_{1}}\circ t_{2,i_{2}}\circ\cdots\circ t_{k-1,i_{k-1}}\right)
\left(  k\right)  =k.
\]


The definition of $\sigma_{k}$ yields%
\[
\sigma_{k}=t_{1,i_{1}}\circ t_{2,i_{2}}\circ\cdots\circ t_{k,i_{k}}=\left(
t_{1,i_{1}}\circ t_{2,i_{2}}\circ\cdots\circ t_{k-1,i_{k-1}}\right)  \circ
t_{k,i_{k}}.
\]
Hence,%
\begin{align*}
\sigma_{k}\left(  i_{k}\right)   &  =\left(  \left(  t_{1,i_{1}}\circ
t_{2,i_{2}}\circ\cdots\circ t_{k-1,i_{k-1}}\right)  \circ t_{k,i_{k}}\right)
\left(  i_{k}\right)  =\left(  t_{1,i_{1}}\circ t_{2,i_{2}}\circ\cdots\circ
t_{k-1,i_{k-1}}\right)  \left(  \underbrace{t_{k,i_{k}}\left(  i_{k}\right)
}_{=k}\right) \\
&  =\left(  t_{1,i_{1}}\circ t_{2,i_{2}}\circ\cdots\circ t_{k-1,i_{k-1}%
}\right)  \left(  k\right)  =k.
\end{align*}
This solves part \textbf{(b)} of the exercise.

\bigskip

\textbf{(c)} We shall show that%
\begin{equation}
\sigma_{p}^{-1}=t_{1,m_{1}}\circ t_{2,m_{2}}\circ\cdots\circ t_{p,m_{p}}%
\qquad\text{for each }p\in\left\{  0,1,\ldots,n\right\}  .
\label{sol.perm.rearrangement.c.goal}%
\end{equation}


[\textit{Proof of \eqref{sol.perm.rearrangement.c.goal}:} We shall prove
\eqref{sol.perm.rearrangement.c.goal} by induction on $p$:

\textit{Induction base:} In the case of $p=0$, the equality
\eqref{sol.perm.rearrangement.c.goal} holds, since $\sigma_{0}$ is defined as
an empty composition whereas the right hand side of
\eqref{sol.perm.rearrangement.c.goal} also is an empty composition in this
case. This completes the induction base.

\textit{Induction step:} Let $k\in\left[  n\right]  $. Assume that
\eqref{sol.perm.rearrangement.c.goal} holds for $p=k-1$. We must prove that
\eqref{sol.perm.rearrangement.c.goal} holds for $p=k$.

We have assumed that \eqref{sol.perm.rearrangement.c.goal} holds for $p=k-1$.
That is, we have%
\[
\sigma_{k-1}^{-1}=t_{1,m_{1}}\circ t_{2,m_{2}}\circ\cdots\circ t_{k-1,m_{k-1}%
}.
\]


Part \textbf{(b)} of the exercise yields $\sigma_{k}\left(  i_{k}\right)  =k$,
whereas the definition of $m_{k}$ yields $\sigma_{k}\left(  k\right)  =m_{k}$.
But \eqref{sol.perm.rearrangement.tpi} (applied to $\pi=\sigma_{k}$, $u=i_{k}$
and $v=k$) yields
\[
t_{\sigma_{k}\left(  i_{k}\right)  ,\sigma_{k}\left(  k\right)  }\circ
\sigma_{k}=\sigma_{k}\circ t_{i_{k},k}.
\]
In view of $\sigma_{k}\left(  i_{k}\right)  =k$ and $\sigma_{k}\left(
k\right)  =m_{k}$, this rewrites as
\begin{equation}
t_{k,m_{k}}\circ\sigma_{k}=\sigma_{k}\circ\underbrace{t_{i_{k},k}%
}_{=t_{k,i_{k}}}=\sigma_{k}\circ t_{k,i_{k}}.
\label{sol.perm.rearrangement.c.4}%
\end{equation}


We have $\sigma_{k-1}=t_{1,i_{1}}\circ t_{2,i_{2}}\circ\cdots\circ
t_{k-1,i_{k-1}}$ (by the definition of $\sigma_{k-1}$). Now, the definition of
$\sigma_{k}$ yields%
\begin{equation}
\sigma_{k}=t_{1,i_{1}}\circ t_{2,i_{2}}\circ\cdots\circ t_{k,i_{k}%
}=\underbrace{\left(  t_{1,i_{1}}\circ t_{2,i_{2}}\circ\cdots\circ
t_{k-1,i_{k-1}}\right)  }_{=\sigma_{k-1}}\circ t_{k,i_{k}}=\sigma_{k-1}\circ
t_{k,i_{k}}. \label{sol.perm.rearrangement.c.3}%
\end{equation}
Solving this equation for $\sigma_{k-1}$, we obtain%
\begin{equation}
\sigma_{k-1}=\sigma_{k}\circ\underbrace{t_{k,i_{k}}^{-1}}_{=t_{k,i_{k}}%
}=\sigma_{k}\circ t_{k,i_{k}}=t_{k,m_{k}}\circ\sigma_{k}\qquad\left(  \text{by
\eqref{sol.perm.rearrangement.c.4}}\right)  .
\label{sol.perm.rearrangement.c.5}%
\end{equation}
Solving this equation for $\sigma_{k}$, we find
\[
\sigma_{k}=\underbrace{t_{k,m_{k}}^{-1}}_{=t_{k,m_{k}}}\circ\sigma
_{k-1}=t_{k,m_{k}}\circ\sigma_{k-1}.
\]
Hence,%
\begin{align*}
\sigma_{k}^{-1}  &  =\left(  t_{k,m_{k}}\circ\sigma_{k-1}\right)
^{-1}=\underbrace{\sigma_{k-1}^{-1}}_{=t_{1,m_{1}}\circ t_{2,m_{2}}\circ
\cdots\circ t_{k-1,m_{k-1}}}\circ\underbrace{t_{k,m_{k}}^{-1}}_{=t_{k,m_{k}}%
}\\
&  =\left(  t_{1,m_{1}}\circ t_{2,m_{2}}\circ\cdots\circ t_{k-1,m_{k-1}%
}\right)  \circ t_{k,m_{k}}=t_{1,m_{1}}\circ t_{2,m_{2}}\circ\cdots\circ
t_{k,m_{k}}.
\end{align*}
In other words, \eqref{sol.perm.rearrangement.c.goal} holds for $p=k$. This
completes the induction step. Thus, \eqref{sol.perm.rearrangement.c.goal} is
proven by induction.]

Applying \eqref{sol.perm.rearrangement.c.goal} to $p=n$, we obtain $\sigma
_{n}^{-1}=t_{1,m_{1}}\circ t_{2,m_{2}}\circ\cdots\circ t_{n,m_{n}}$. In view
of $\sigma_{n}=\sigma$, this rewrites as $\sigma^{-1}=t_{1,m_{1}}\circ
t_{2,m_{2}}\circ\cdots\circ t_{n,m_{n}}$. This solves part \textbf{(c)} of the exercise.

\bigskip

\textbf{(d)} For each permutation $\tau\in S_{n}$, we define a number
$z\left(  \tau\right)  $ by
\[
z\left(  \tau\right)  =\sum_{k=1}^{n}x_{k}y_{\tau\left(  k\right)  }.
\]


We shall show that
\begin{equation}
z\left(  \sigma_{p-1}\right)  -z\left(  \sigma_{p}\right)  =\left(  x_{i_{p}%
}-x_{p}\right)  \left(  y_{m_{p}}-y_{p}\right)  \qquad\text{for each }%
p\in\left[  n\right]  . \label{sol.perm.rearrangement.d.goal}%
\end{equation}


[\textit{Proof of \eqref{sol.perm.rearrangement.d.goal}:} Let $p\in\left[
n\right]  $. Applying \eqref{sol.perm.rearrangement.c.3} to $k=p$, we obtain
$\sigma_{p}=\sigma_{p-1}\circ t_{p,i_{p}}$. Hence, if $p=i_{p}$, then
\eqref{sol.perm.rearrangement.d.goal} holds\footnote{\textit{Proof.} Assume
that $p=i_{p}$. Thus, $i_{p}=p$, so that $x_{i_{p}}-x_{p}=x_{p}-x_{p}=0$.
Hence, the right hand side of \eqref{sol.perm.rearrangement.d.goal} equals
$0$. Also, $\sigma_{p}=\sigma_{p-1}\circ\underbrace{t_{p,i_{p}}}%
_{\substack{=\operatorname*{id}\\\text{(since }p=i_{p}\text{)}}}=\sigma_{p-1}%
$, so that $z\left(  \sigma_{p-1}\right)  -z\left(  \sigma_{p}\right)
=z\left(  \sigma_{p-1}\right)  -z\left(  \sigma_{p-1}\right)  =0$. Thus, the
left hand side of \eqref{sol.perm.rearrangement.d.goal} equals $0$ as well.
Hence, the equality \eqref{sol.perm.rearrangement.d.goal} holds (since both
its right hand side and its left hand side equal $0$).}. Thus, for the rest of
this proof, we WLOG assume that $p\neq i_{p}$. Hence, $t_{p,i_{p}}$ is an
actual transposition (not the identity map).

From $\sigma_{p}=\sigma_{p-1}\circ t_{p,i_{p}}$, we obtain%
\[
\sigma_{p}\left(  p\right)  =\left(  \sigma_{p-1}\circ t_{p,i_{p}}\right)
\left(  p\right)  =\sigma_{p-1}\left(  \underbrace{t_{p,i_{p}}\left(
p\right)  }_{=i_{p}}\right)  =\sigma_{p-1}\left(  i_{p}\right)  ,
\]
so that%
\begin{equation}
\sigma_{p-1}\left(  i_{p}\right)  =\sigma_{p}\left(  p\right)  =m_{p}
\label{sol.perm.rearrangement.d.1}%
\end{equation}
(since the definition of $m_{p}$ yields $m_{p}=\sigma_{p}\left(  p\right)  $).

From $\sigma_{p}=\sigma_{p-1}\circ t_{p,i_{p}}$, we also obtain%
\[
\sigma_{p}\left(  i_{p}\right)  =\left(  \sigma_{p-1}\circ t_{p,i_{p}}\right)
\left(  i_{p}\right)  =\sigma_{p-1}\left(  \underbrace{t_{p,i_{p}}\left(
i_{p}\right)  }_{=p}\right)  =\sigma_{p-1}\left(  p\right)  ,
\]
so that%
\begin{equation}
\sigma_{p-1}\left(  p\right)  =\sigma_{p}\left(  i_{p}\right)  =p
\label{sol.perm.rearrangement.d.2}%
\end{equation}
(by part \textbf{(b)} of the exercise, applied to $k=p$).

Every $k\in\left[  n\right]  $ satisfying $k\neq p$ and $k\neq i_{p}$
satisfies
\begin{equation}
\sigma_{p-1}\left(  k\right)  =\sigma_{p}\left(  k\right)
\label{sol.perm.rearrangement.d.3}%
\end{equation}
\footnote{\textit{Proof:} Let $k\in\left[  n\right]  $ be such that $k\neq p$
and $k\neq i_{p}$. Thus, $t_{p,i_{p}}\left(  k\right)  =k$. But $\sigma
_{p}=\sigma_{p-1}\circ t_{p,i_{p}}$; hence, $\sigma_{p}\left(  k\right)
=\left(  \sigma_{p-1}\circ t_{p,i_{p}}\right)  \left(  k\right)  =\sigma
_{p-1}\left(  \underbrace{t_{p,i_{p}}\left(  k\right)  }_{=k}\right)
=\sigma_{p-1}\left(  k\right)  $, so that $\sigma_{p-1}\left(  k\right)
=\sigma_{p}\left(  k\right)  $, qed.}. Now, the definition of $z\left(
\sigma_{p-1}\right)  $ yields%
\begin{align*}
z\left(  \sigma_{p-1}\right)   &  =\sum_{k=1}^{n}x_{k}y_{\sigma_{p-1}\left(
k\right)  }=x_{p}\underbrace{y_{\sigma_{p-1}\left(  p\right)  }}%
_{\substack{=y_{p}\\\text{(by \eqref{sol.perm.rearrangement.d.2})}}}+x_{i_{p}%
}\underbrace{y_{\sigma_{p-1}\left(  i_{p}\right)  }}_{\substack{=y_{m_{p}%
}\\\text{(by \eqref{sol.perm.rearrangement.d.1})}}}+\sum_{\substack{k\in
\left[  n\right]  ;\\k\neq p\text{ and }k\neq i_{p}}}x_{k}%
\underbrace{y_{\sigma_{p-1}\left(  k\right)  }}_{\substack{=y_{\sigma
_{p}\left(  k\right)  }\\\text{(by \eqref{sol.perm.rearrangement.d.3})}}}\\
&  \qquad\left(
\begin{array}
[c]{c}%
\text{here, we have split the addends for }k=p\text{ and}\\
\text{for }k=i_{p}\text{ from the sum (and these are}\\
\text{two distinct addends, since }p\neq i_{p}\text{)}%
\end{array}
\right) \\
&  =x_{p}y_{p}+x_{i_{p}}y_{m_{p}}+\sum_{\substack{k\in\left[  n\right]
;\\k\neq p\text{ and }k\neq i_{p}}}x_{k}y_{\sigma_{p}\left(  k\right)  }.
\end{align*}
On the other hand, the definition of $z\left(  \sigma_{p}\right)  $ yields%
\begin{align*}
z\left(  \sigma_{p}\right)   &  =\sum_{k=1}^{n}x_{k}y_{\sigma_{p}\left(
k\right)  }=x_{p}\underbrace{y_{\sigma_{p}\left(  p\right)  }}%
_{\substack{=y_{m_{p}}\\\text{(since }\sigma_{p}\left(  p\right)
=m_{p}\text{)}}}+x_{i_{p}}\underbrace{y_{\sigma_{p}\left(  i_{p}\right)  }%
}_{\substack{=y_{p}\\\text{(since }\sigma_{p}\left(  i_{p}\right)  =p\text{)}%
}}+\sum_{\substack{k\in\left[  n\right]  ;\\k\neq p\text{ and }k\neq i_{p}%
}}x_{k}y_{\sigma_{p}\left(  k\right)  }\\
&  \qquad\left(
\begin{array}
[c]{c}%
\text{here, we have split the addends for }k=p\text{ and}\\
\text{for }k=i_{p}\text{ from the sum (and these are}\\
\text{two distinct addends, since }p\neq i_{p}\text{)}%
\end{array}
\right) \\
&  =x_{p}y_{m_{p}}+x_{i_{p}}y_{p}+\sum_{\substack{k\in\left[  n\right]
;\\k\neq p\text{ and }k\neq i_{p}}}x_{k}y_{\sigma_{p}\left(  k\right)  }.
\end{align*}
Subtracting this equality from the preceding equality, we obtain%
\begin{align*}
&  z\left(  \sigma_{p-1}\right)  -z\left(  \sigma_{p}\right) \\
&  =\left(  x_{p}y_{p}+x_{i_{p}}y_{m_{p}}+\sum_{\substack{k\in\left[
n\right]  ;\\k\neq p\text{ and }k\neq i_{p}}}x_{k}y_{\sigma_{p}\left(
k\right)  }\right)  -\left(  x_{p}y_{m_{p}}+x_{i_{p}}y_{p}+\sum
_{\substack{k\in\left[  n\right]  ;\\k\neq p\text{ and }k\neq i_{p}}%
}x_{k}y_{\sigma_{p}\left(  k\right)  }\right) \\
&  =x_{p}y_{p}+x_{i_{p}}y_{m_{p}}-x_{p}y_{m_{p}}-x_{i_{p}}y_{p}=\left(
x_{i_{p}}-x_{p}\right)  \left(  y_{m_{p}}-y_{p}\right)  .
\end{align*}
This proves \eqref{sol.perm.rearrangement.d.goal}.]

Now, the telescope principle yields%
\begin{align*}
\sum_{p=1}^{n}\left(  z\left(  \sigma_{p-1}\right)  -z\left(  \sigma
_{p}\right)  \right)   &  =z\left(  \underbrace{\sigma_{0}}%
_{=\operatorname*{id}}\right)  -z\left(  \underbrace{\sigma_{n}}_{=\sigma
}\right)  =\underbrace{z\left(  \operatorname*{id}\right)  }_{\substack{=\sum
_{k=1}^{n}x_{k}y_{\operatorname*{id}\left(  k\right)  }\\\text{(by the
definition of }z\left(  \operatorname*{id}\right)  \text{)}}%
}-\underbrace{z\left(  \sigma\right)  }_{\substack{=\sum_{k=1}^{n}%
x_{k}y_{\sigma\left(  k\right)  }\\\text{(by the definition of }z\left(
\sigma\right)  \text{)}}}\\
&  =\sum_{k=1}^{n}x_{k}\underbrace{y_{\operatorname*{id}\left(  k\right)  }%
}_{=y_{k}}-\sum_{k=1}^{n}x_{k}y_{\sigma\left(  k\right)  }=\sum_{k=1}^{n}%
x_{k}y_{k}-\sum_{k=1}^{n}x_{k}y_{\sigma\left(  k\right)  }.
\end{align*}
Hence,%
\begin{align*}
&  \sum_{k=1}^{n}x_{k}y_{k}-\sum_{k=1}^{n}x_{k}y_{\sigma\left(  k\right)  }\\
&  =\sum_{p=1}^{n}\underbrace{\left(  z\left(  \sigma_{p-1}\right)  -z\left(
\sigma_{p}\right)  \right)  }_{\substack{=\left(  x_{i_{p}}-x_{p}\right)
\left(  y_{m_{p}}-y_{p}\right)  \\\text{(by
\eqref{sol.perm.rearrangement.d.goal})}}}=\sum_{p=1}^{n}\left(  x_{i_{p}%
}-x_{p}\right)  \left(  y_{m_{p}}-y_{p}\right)  =\sum_{k=1}^{n}\left(
x_{i_{k}}-x_{k}\right)  \left(  y_{m_{k}}-y_{k}\right)
\end{align*}
(here, we have renamed the summation index $p$ as $k$). This solves part
\textbf{(d)} of the exercise.

\bigskip

\textbf{(e)} Fix $k\in\left[  n\right]  $. Then, $i_{k}\in\left[  k\right]  $
(by \eqref{sol.perm.rearrangement.1}), so that $i_{k}\leq k$ and therefore
$x_{i_{k}}\geq x_{k}$ (since $x_{1}\geq x_{2}\geq\cdots\geq x_{n}$). Hence,
$x_{i_{k}}-x_{k}\geq0$.

Also, $m_{k}\in\left[  k\right]  $ (by part \textbf{(a)} of the exercise), so
that $m_{k}\leq k$ and thus $y_{m_{k}}\geq y_{k}$ (since $y_{1}\geq y_{2}%
\geq\cdots\geq y_{n}$). Hence, $y_{m_{k}}-y_{k}\geq0$. Now,%
\begin{equation}
\underbrace{\left(  x_{i_{k}}-x_{k}\right)  }_{\geq0}\underbrace{\left(
y_{m_{k}}-y_{k}\right)  }_{\geq0}\geq0. \label{sol.perm.rearrangement.e.1}%
\end{equation}


Now, forget that we fixed $k$. We thus have proven
\eqref{sol.perm.rearrangement.e.1} for each $k\in\left[  n\right]  $. Now,
part \textbf{(d)} of the exercise yields
\[
\sum_{k=1}^{n}x_{k}y_{k}-\sum_{k=1}^{n}x_{k}y_{\sigma\left(  k\right)  }%
=\sum_{k=1}^{n}\underbrace{\left(  x_{i_{k}}-x_{k}\right)  \left(  y_{m_{k}%
}-y_{k}\right)  }_{\substack{\geq0\\\text{(by
\eqref{sol.perm.rearrangement.e.1})}}}\geq0.
\]
In other words,%
\[
\sum_{k=1}^{n}x_{k}y_{k}\geq\sum_{k=1}^{n}x_{k}y_{\sigma\left(  k\right)  }.
\]
This solves part \textbf{(e)} of the exercise.

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

\section{Exercise 6}

\subsection{Problem}

Prove the following:

\begin{enumerate}
\item[\textbf{(a)}] If $m \in\mathbb{N}$ and $n \in\mathbb{N}$ are such that
$m<n$, then
\[
\sum_{k=0}^{n} \left(  -1 \right)  ^{k} \dbinom{n}{k} \left(  n-k \right)
^{m} = 0.
\]


\item[\textbf{(b)}] If $n\in\mathbb{N}$ and $r\in\left[  n-1\right]  $, then
\[
\sum_{k=0}^{n}\left(  -1\right)  ^{k}\dbinom{2n}{k}\left(  n-k\right)
^{2r}=0.
\]

\end{enumerate}

\subsection{Solution sketch}

\textbf{(a)} \textit{First solution to part \textbf{(a)}:} Let $m\in
\mathbb{N}$ and $n\in\mathbb{N}$ be such that $m<n$. We have $\left\vert
\left[  m\right]  \right\vert =m<n=\left\vert \left[  n\right]  \right\vert $.
Thus, there are no surjections from $\left[  m\right]  $ to $\left[  n\right]
$ (by the Pigeonhole Principle for Surjections). Recall that
$\operatorname*{sur}\left(  m,n\right)  $ denotes the number of all
surjections from $\left[  m\right]  $ to $\left[  n\right]  $. Thus,
$\operatorname*{sur}\left(  m,n\right)  =0$ (since there are no surjections
from $\left[  m\right]  $ to $\left[  n\right]  $).

But Theorem 2.28 from
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18f/5705-2018-10-01.pdf}{class
(2018-10-01)} shows that%
\[
\operatorname*{sur}\left(  m,n\right)  =\sum_{i=0}^{n}\left(  -1\right)
^{i}\dbinom{n}{i}\left(  n-i\right)  ^{m}=\sum_{k=0}^{n}\left(  -1\right)
^{k}\dbinom{n}{k}\left(  n-k\right)  ^{m}%
\]
(here, we have renamed the summation index $i$ as $k$). Comparing this with
$\operatorname*{sur}\left(  m,n\right)  =0$, we obtain $\sum_{k=0}^{n}\left(
-1\right)  ^{k}\dbinom{n}{k}\left(  n-k\right)  ^{m}=0$. This solves part
\textbf{(a)} of the exercise.

\bigskip

\textit{Second solution to part \textbf{(a)}:} Let $m\in\mathbb{N}$ and
$n\in\mathbb{N}$ be such that $m<n$. Exercise 6 \textbf{(b)} on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18f/hw3s.pdf}{homework set
\#3} yields that if $A_{1},A_{2},\ldots,A_{n}$ are $n$ numbers, then
\[
\sum_{I\subseteq\left[  n\right]  }\left(  -1\right)  ^{n-\left\vert
I\right\vert }\left(  \sum_{i\in I}A_{i}\right)  ^{m}=0.
\]
Applying this to $A_{i}=1$, we obtain%
\[
\sum_{I\subseteq\left[  n\right]  }\left(  -1\right)  ^{n-\left\vert
I\right\vert }\left(  \sum_{i\in I}1\right)  ^{m}=0.
\]
Thus,%
\begin{align*}
0  &  =\sum_{I\subseteq\left[  n\right]  }\left(  -1\right)  ^{n-\left\vert
I\right\vert }\left(  \underbrace{\sum_{i\in I}1}_{=\left\vert I\right\vert
\cdot1=\left\vert I\right\vert }\right)  ^{m}=\underbrace{\sum_{I\subseteq
\left[  n\right]  }}_{=\sum_{i=0}^{n}\sum_{\substack{I\subseteq\left[
n\right]  ;\\\left\vert I\right\vert =i}}}\left(  -1\right)  ^{n-\left\vert
I\right\vert }\left\vert I\right\vert ^{m}\\
&  =\sum_{i=0}^{n}\sum_{\substack{I\subseteq\left[  n\right]  ;\\\left\vert
I\right\vert =i}}\underbrace{\left(  -1\right)  ^{n-\left\vert I\right\vert
}\left\vert I\right\vert ^{m}}_{\substack{=\left(  -1\right)  ^{n-i}%
i^{m}\\\text{(since }\left\vert I\right\vert =i\text{)}}}=\sum_{i=0}%
^{n}\underbrace{\sum_{\substack{I\subseteq\left[  n\right]  ;\\\left\vert
I\right\vert =i}}\left(  -1\right)  ^{n-i}i^{m}}_{=\left(  \text{the number of
all }I\subseteq\left[  n\right]  \text{ satisfying }\left\vert I\right\vert
=i\right)  \cdot\left(  -1\right)  ^{n-i}i^{m}}\\
&  =\sum_{i=0}^{n}\underbrace{\left(  \text{the number of all }I\subseteq
\left[  n\right]  \text{ satisfying }\left\vert I\right\vert =i\right)
}_{\substack{=\left(  \text{the number of all }i\text{-element subsets of
}\left[  n\right]  \right)  \\=\dbinom{n}{i}}}\cdot\left(  -1\right)
^{n-i}i^{m}\\
&  =\sum_{i=0}^{n}\dbinom{n}{i}\cdot\left(  -1\right)  ^{n-i}i^{m}=\sum
_{i=0}^{n}\left(  -1\right)  ^{n-i}\dbinom{n}{i}i^{m}=\sum_{k=0}^{n}\left(
-1\right)  ^{k}\underbrace{\dbinom{n}{n-k}}_{\substack{=\dbinom{n}%
{k}\\\text{(by the symmetry}\\\text{of Pascal's triangle)}}}\left(
n-k\right)  ^{m}\\
&  \qquad\left(  \text{here, we have substituted }n-k\text{ for }i\text{ in
the sum}\right) \\
&  =\sum_{k=0}^{n}\left(  -1\right)  ^{k}\dbinom{n}{k}\left(  n-k\right)
^{m}.
\end{align*}
This solves part \textbf{(a)} of the exercise again.

\bigskip

\textit{Third solution to part \textbf{(a)}:} Part \textbf{(a)} of the
exercise is a particular case of Theorem \ref{thm.DIE.count-surjs.c-gen}
further below (applied to $a=m$, $b=n$ and $c=n$).

\bigskip

\textbf{(b)} We need a generalization of part \textbf{(a)} of the exercise:

\begin{theorem}
\label{thm.DIE.count-surjs.c-gen}Let $a\in\mathbb{N}$, $b\in\mathbb{Q}$ and
$c\in\mathbb{N}$ be such that $c>a$. Then,%
\[
\sum_{k=0}^{c}\left(  -1\right)  ^{k}\dbinom{c}{k}\left(  b-k\right)  ^{a}=0.
\]

\end{theorem}

For the proof of Theorem \ref{thm.DIE.count-surjs.c-gen}, see \cite[Theorem
0.2]{Grinbe18}.

Let $n\in\mathbb{N}$ and $r\in\left[  n-1\right]  $. We have $r\in\left[
n-1\right]  $, thus $r\leq n-1$ and therefore $2r\leq2\left(  n-1\right)
<2n$. Thus, $2n>2r$. Hence, Theorem \ref{thm.DIE.count-surjs.c-gen} (applied
to $a=2r$, $b=n$ and $c=2n$) yields
\[
\sum_{k=0}^{2n}\left(  -1\right)  ^{k}\dbinom{2n}{k}\left(  n-k\right)
^{2r}=0.
\]
Thus,%
\begin{align}
0  &  =\sum_{k=0}^{2n}\left(  -1\right)  ^{k}\dbinom{2n}{k}\left(  n-k\right)
^{2r}\nonumber\\
&  =\sum_{k=0}^{n}\left(  -1\right)  ^{k}\dbinom{2n}{k}\left(  n-k\right)
^{2r}+\sum_{k=n+1}^{2n}\left(  -1\right)  ^{k}\dbinom{2n}{k}\left(
n-k\right)  ^{2r} \label{sol.binom.alt-sum-symmetry-mo.b.1}%
\end{align}
(since $0\leq n\leq2n$). But%
\begin{align*}
&  \sum_{k=n+1}^{2n}\left(  -1\right)  ^{k}\dbinom{2n}{k}\left(  n-k\right)
^{2r}\\
&  =\sum_{k=0}^{n-1}\underbrace{\left(  -1\right)  ^{2n-k}}_{=\left(
-1\right)  ^{k}}\underbrace{\dbinom{2n}{2n-k}}_{\substack{=\dbinom{2n}%
{k}\\\text{(by the symmetry}\\\text{of Pascal's triangle)}}}\left(
\underbrace{n-\left(  2n-k\right)  }_{=-\left(  n-k\right)  }\right)  ^{2r}\\
&  \qquad\left(  \text{here, we have substituted }2n-k\text{ for }k\text{ in
the sum}\right) \\
&  =\sum_{k=0}^{n-1}\left(  -1\right)  ^{k}\dbinom{2n}{k}\underbrace{\left(
-\left(  n-k\right)  \right)  ^{2r}}_{\substack{=\left(  n-k\right)
^{2r}\\\text{(since }2r\text{ is even)}}}=\sum_{k=0}^{n-1}\left(  -1\right)
^{k}\dbinom{2n}{k}\left(  n-k\right)  ^{2r}\\
&  =\sum_{k=0}^{n}\left(  -1\right)  ^{k}\dbinom{2n}{k}\left(  n-k\right)
^{2r}-\left(  -1\right)  ^{n}\dbinom{2n}{n}\underbrace{\left(  n-n\right)
^{2r}}_{\substack{=0^{2r}=0\\\text{(since }r>0\text{)}}}\\
&  \qquad\left(
\begin{array}
[c]{c}%
\text{here, we have extended the range of the sum to include a}\\
\text{new addend for }k=n\text{, and then subtracted that addend}%
\end{array}
\right) \\
&  =\sum_{k=0}^{n}\left(  -1\right)  ^{k}\dbinom{2n}{k}\left(  n-k\right)
^{2r}.
\end{align*}
Hence, \eqref{sol.binom.alt-sum-symmetry-mo.b.1} becomes%
\begin{align*}
0  &  =\sum_{k=0}^{n}\left(  -1\right)  ^{k}\dbinom{2n}{k}\left(  n-k\right)
^{2r}+\underbrace{\sum_{k=n+1}^{2n}\left(  -1\right)  ^{k}\dbinom{2n}%
{k}\left(  n-k\right)  ^{2r}}_{=\sum_{k=0}^{n}\left(  -1\right)  ^{k}%
\dbinom{2n}{k}\left(  n-k\right)  ^{2r}}\\
&  =\sum_{k=0}^{n}\left(  -1\right)  ^{k}\dbinom{2n}{k}\left(  n-k\right)
^{2r}+\sum_{k=0}^{n}\left(  -1\right)  ^{k}\dbinom{2n}{k}\left(  n-k\right)
^{2r}=2\sum_{k=0}^{n}\left(  -1\right)  ^{k}\dbinom{2n}{k}\left(  n-k\right)
^{2r}.
\end{align*}
Dividing this equality by $2$, we find $0=\sum_{k=0}^{n}\left(  -1\right)
^{k}\dbinom{2n}{k}\left(  n-k\right)  ^{2r}$. This solves part \textbf{(b)} of
the exercise.

\subsection{Remark}

I have learnt part \textbf{(b)} of the exercise from
\href{https://mathoverflow.net/q/312839/}{MathOverflow question \#312839},
which also asks if the sum is $\neq0$ when $2r$ is replaced by an \textbf{odd}
integer between $1$ and $2n-1$.

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

\section{Exercise 7}

\subsection{Problem}

Let $n \in\mathbb{N}$ and $d \in\mathbb{N}$. An $n$-tuple $\left(  x_{1},
x_{2}, \ldots, x_{n} \right)  \in\left[  d \right]  ^{n}$ is said to be
\textit{all-even} if each element of $\left[  d \right]  $ occurs an even
number of times in this $n$-tuple (i.e., if for each $k \in\left[  d \right]
$, the number of all $i \in\left[  n \right]  $ satisfying $x_{i} = k$ is
even). For example, the $4$-tuple $\left(  1,4,4,1 \right)  $ and the
$6$-tuples $\left(  1,3,3,5,1,5 \right)  $ and $\left(  2,4,2,4,3,3 \right)  $
are all-even, while the $4$-tuples $\left(  1,2,2,4 \right)  $ and $\left(
2,4,6,4 \right)  $ are not.

Prove that the number of all all-even $n$-tuples $\left(  x_{1}, x_{2},
\ldots, x_{n} \right)  \in\left[  d \right]  ^{n}$ is
\[
\dfrac{1}{2^{d}}\sum_{k=0}^{d}\dbinom{d}{k}\left(  d-2k\right)  ^{n}.
\]


[\textbf{Hint:} Compute the sum $\sum_{\left(  e_{1}, e_{2}, \ldots, e_{d}
\right)  \in\left\{  -1, 1 \right\}  ^{d}} \left(  e_{1} + e_{2} + \cdots+
e_{d} \right)  ^{n}$ in two ways. One way is to split it according to the
number of $i \in\left[  d \right]  $ satisfying $e_{i} = -1$; this is a number
$k \in\left\{  0, 1, \ldots, d \right\}  $. Another way is by using the
product rule:
\[
\left(  e_{1} + e_{2} + \cdots+ e_{d} \right)  ^{n} = \sum_{\left(  x_{1},
x_{2}, \ldots, x_{n} \right)  \in\left[  d \right]  ^{n}} e_{x_{1}} e_{x_{2}}
\cdots e_{x_{n}}%
\]
and then simplifying each sum $\sum_{\left(  e_{1}, e_{2}, \ldots, e_{d}
\right)  \in\left\{  -1, 1 \right\}  ^{d}} e_{x_{1}} e_{x_{2}} \cdots
e_{x_{n}}$ using a form of destructive interference. This is not unlike the
number of 1-even $n$-tuples, which we computed at the end of
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18f/5705-2018-10-10.pdf}{the
2018-10-10 class}.]

\subsection{Solution sketch}

Recall the \textit{product rule} (which we have already used when solving
Exercise 6 on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18f/hw3s.pdf}{homework set
\#3}):

\begin{proposition}
[Product rule]\label{prop.exe.polariz-id.prodruleI}Let $m\in\mathbb{N}$. Let
$I$ be a finite set. Let $P_{u,v}$, for all $u\in\left[  m\right]  $ and $v\in
I$, be numbers or polynomials or square matrices of the same size. Then,
\[
\left(  \sum_{i\in I}P_{1,i}\right)  \left(  \sum_{i\in I}P_{2,i}\right)
\cdots\left(  \sum_{i\in I}P_{m,i}\right)  =\sum_{\left(  i_{1},i_{2}%
,\ldots,i_{m}\right)  \in I^{m}}P_{1,i_{1}}P_{2,i_{2}}\cdots P_{m,i_{m}}.
\]

\end{proposition}

Fix a $d$-tuple $\left(  e_{1},e_{2},\ldots,e_{d}\right)  \in\left\{
-1,1\right\}  ^{d}$. We now apply Proposition
\ref{prop.exe.polariz-id.prodruleI} to $m=n$, $I=\left[  d\right]  $ and
$P_{u,v}=e_{v}$. As a result, we obtain%
\[
\underbrace{\left(  \sum_{i\in\left[  d\right]  }e_{i}\right)  \left(
\sum_{i\in\left[  d\right]  }e_{i}\right)  \cdots\left(  \sum_{i\in\left[
d\right]  }e_{i}\right)  }_{n\text{ times}}=\sum_{\left(  i_{1},i_{2}%
,\ldots,i_{n}\right)  \in\left[  d\right]  ^{n}}e_{i_{1}}e_{i_{2}}\cdots
e_{i_{n}}=\sum_{\left(  x_{1},x_{2},\ldots,x_{n}\right)  \in\left[  d\right]
^{n}}e_{x_{1}}e_{x_{2}}\cdots e_{x_{n}}%
\]
(here, we have renamed the summation index $\left(  i_{1},i_{2},\ldots
,i_{n}\right)  $ as $\left(  x_{1},x_{2},\ldots,x_{n}\right)  $). Thus,%
\begin{align}
\sum_{\left(  x_{1},x_{2},\ldots,x_{n}\right)  \in\left[  d\right]  ^{n}%
}e_{x_{1}}e_{x_{2}}\cdots e_{x_{n}}  &  =\underbrace{\left(  \sum_{i\in\left[
d\right]  }e_{i}\right)  \left(  \sum_{i\in\left[  d\right]  }e_{i}\right)
\cdots\left(  \sum_{i\in\left[  d\right]  }e_{i}\right)  }_{n\text{ times}%
}=\left(  \underbrace{\sum_{i\in\left[  d\right]  }e_{i}}_{=e_{1}+e_{2}%
+\cdots+e_{d}}\right)  ^{n}\nonumber\\
&  =\left(  e_{1}+e_{2}+\cdots+e_{d}\right)  ^{n}.
\label{sol.count.all-even-tups.1}%
\end{align}


Now, forget that we fixed $\left(  e_{1},e_{2},\ldots,e_{d}\right)  $. We thus
have proven the equality \eqref{sol.count.all-even-tups.1} for each $\left(
e_{1},e_{2},\ldots,e_{d}\right)  \in\left\{  -1,1\right\}  ^{d}$.

Now,%
\begin{align}
&  \sum_{\left(  e_{1},e_{2},\ldots,e_{d}\right)  \in\left\{  -1,1\right\}
^{d}}\underbrace{\left(  e_{1}+e_{2}+\cdots+e_{d}\right)  ^{n}}%
_{\substack{=\sum_{\left(  x_{1},x_{2},\ldots,x_{n}\right)  \in\left[
d\right]  ^{n}}e_{x_{1}}e_{x_{2}}\cdots e_{x_{n}}\\\text{(by
\eqref{sol.count.all-even-tups.1})}}}\nonumber\\
&  =\underbrace{\sum_{\left(  e_{1},e_{2},\ldots,e_{d}\right)  \in\left\{
-1,1\right\}  ^{d}}\sum_{\left(  x_{1},x_{2},\ldots,x_{n}\right)  \in\left[
d\right]  ^{n}}}_{=\sum_{\left(  x_{1},x_{2},\ldots,x_{n}\right)  \in\left[
d\right]  ^{n}}\sum_{\left(  e_{1},e_{2},\ldots,e_{d}\right)  \in\left\{
-1,1\right\}  ^{d}}}e_{x_{1}}e_{x_{2}}\cdots e_{x_{n}}\nonumber\\
&  =\sum_{\left(  x_{1},x_{2},\ldots,x_{n}\right)  \in\left[  d\right]  ^{n}%
}\sum_{\left(  e_{1},e_{2},\ldots,e_{d}\right)  \in\left\{  -1,1\right\}
^{d}}e_{x_{1}}e_{x_{2}}\cdots e_{x_{n}}. \label{sol.count.all-even-tups.2}%
\end{align}


We shall now simplify the inner sum on the right hand side of this equality.
Indeed, we claim the following:

\begin{statement}
\textit{Claim 1:} Let $\left(  x_{1},x_{2},\ldots,x_{n}\right)  \in\left[
d\right]  ^{n}$.

\textbf{(a)} If the $n$-tuple $\left(  x_{1},x_{2},\ldots,x_{n}\right)  $ is
not all-even, then%
\[
\sum_{\left(  e_{1},e_{2},\ldots,e_{d}\right)  \in\left\{  -1,1\right\}  ^{d}%
}e_{x_{1}}e_{x_{2}}\cdots e_{x_{n}}=0.
\]


\textbf{(b)} If the $n$-tuple $\left(  x_{1},x_{2},\ldots,x_{n}\right)  $ is
all-even, then%
\[
\sum_{\left(  e_{1},e_{2},\ldots,e_{d}\right)  \in\left\{  -1,1\right\}  ^{d}%
}e_{x_{1}}e_{x_{2}}\cdots e_{x_{n}}=2^{d}.
\]

\end{statement}

[\textit{Proof of Claim 1:} \textbf{(a)} Assume that the $n$-tuple $\left(
x_{1},x_{2},\ldots,x_{n}\right)  $ is not all-even. Thus, it is \textbf{not}
true that for each $k\in\left[  d\right]  $, the number of all $i\in\left[
n\right]  $ satisfying $x_{i}=k$ is even (by the definition of
\textquotedblleft all-even\textquotedblright). In other words, there exists
some $k\in\left[  d\right]  $ such that the number of all $i\in\left[
n\right]  $ satisfying $x_{i}=k$ is odd. Consider this $k$.

The number%
\begin{align*}
\sum_{i\in\left[  n\right]  }\left[  x_{i}=k\right]   &  =\sum_{\substack{i\in
\left[  n\right]  ;\\x_{i}=k}}\underbrace{\left[  x_{i}=k\right]
}_{\substack{=1\\\text{(since }x_{i}=k\text{)}}}+\sum_{\substack{i\in\left[
n\right]  ;\\x_{i}\neq k}}\underbrace{\left[  x_{i}=k\right]  }%
_{\substack{=0\\\text{(since }x_{i}\neq k\text{)}}}=\sum_{\substack{i\in
\left[  n\right]  ;\\x_{i}=k}}1+\underbrace{\sum_{\substack{i\in\left[
n\right]  ;\\x_{i}\neq k}}0}_{=0}\\
&  =\sum_{\substack{i\in\left[  n\right]  ;\\x_{i}=k}}1=\left(  \text{the
number of all }i\in\left[  n\right]  \text{ satisfying }x_{i}=k\right)
\cdot1\\
&  =\left(  \text{the number of all }i\in\left[  n\right]  \text{ satisfying
}x_{i}=k\right)
\end{align*}
is odd (by the definition of $k$). Now,%
\[
\left(  -1\right)  ^{\left[  x_{1}=k\right]  }\left(  -1\right)  ^{\left[
x_{2}=k\right]  }\cdots\left(  -1\right)  ^{\left[  x_{n}=k\right]  }%
=\prod_{i\in\left[  n\right]  }\left(  -1\right)  ^{\left[  x_{i}=k\right]
}=\left(  -1\right)  ^{\sum_{i\in\left[  n\right]  }\left[  x_{i}=k\right]
}=-1
\]
(since the number $\sum_{i\in\left[  n\right]  }\left[  x_{i}=k\right]  $ is odd).

Now, define the two subsets%
\begin{align*}
N  &  =\left\{  \left(  e_{1},e_{2},\ldots,e_{d}\right)  \in\left\{
-1,1\right\}  ^{d}\ \mid\ e_{k}=-1\right\}  \qquad\text{and}\\
P  &  =\left\{  \left(  e_{1},e_{2},\ldots,e_{d}\right)  \in\left\{
-1,1\right\}  ^{d}\ \mid\ e_{k}=1\right\}
\end{align*}
of the set $\left\{  -1,1\right\}  ^{d}$. Clearly, each element of $\left\{
-1,1\right\}  ^{d}$ belongs to exactly one of these two subsets $N$ and $P$
(because for each $\left(  e_{1},e_{2},\ldots,e_{d}\right)  \in\left\{
-1,1\right\}  ^{d}$, we have either $e_{k}=-1$ or $e_{k}=1$ but not both).

Clearly, the map%
\[
N\rightarrow P,\qquad\left(  e_{1},e_{2},\ldots,e_{d}\right)  \mapsto\left(
e_{1},e_{2},\ldots,e_{k-1},-e_{k},e_{k+1},e_{k+2},\ldots,e_{d}\right)
\]
(which replaces the $k$-th entry of a $d$-tuple by its negative, while leaving
all other entries unchanged) is well-defined and bijective (indeed, its
inverse map is defined by the same rule). We can rewrite this map (using the
Iverson bracket notation) as the map%
\[
N\rightarrow P,\qquad\left(  e_{1},e_{2},\ldots,e_{d}\right)  \mapsto\left(
\left(  -1\right)  ^{\left[  1=k\right]  }e_{1},\left(  -1\right)  ^{\left[
2=k\right]  }e_{2},\ldots,\left(  -1\right)  ^{\left[  d=k\right]  }%
e_{d}\right)
\]
(because each $\left(  e_{1},e_{2},\ldots,e_{d}\right)  \in N$ satisfies
\[
\left(  \left(  -1\right)  ^{\left[  1=k\right]  }e_{1},\left(  -1\right)
^{\left[  2=k\right]  }e_{2},\ldots,\left(  -1\right)  ^{\left[  d=k\right]
}e_{d}\right)  =\left(  e_{1},e_{2},\ldots,e_{k-1},-e_{k},e_{k+1}%
,e_{k+2},\ldots,e_{d}\right)
\]
\footnote{\textit{Proof.} Let $\left(  e_{1},e_{2},\ldots,e_{d}\right)  \in
N$. Then, each $i\in\left[  d\right]  $ satisfying $i\neq k$ satisfies
$\left[  i=k\right]  =0$ and therefore $\left(  -1\right)  ^{\left[
i=k\right]  }e_{i}=\underbrace{\left(  -1\right)  ^{0}}_{=1}e_{i}=e_{i}$.
Hence, the $d$-tuple $\left(  \left(  -1\right)  ^{\left[  1=k\right]  }%
e_{1},\left(  -1\right)  ^{\left[  2=k\right]  }e_{2},\ldots,\left(
-1\right)  ^{\left[  d=k\right]  }e_{d}\right)  $ differs from the $d$-tuple
$\left(  e_{1},e_{2},\ldots,e_{d}\right)  $ only in its $k$-th entry. As for
its $k$-th entry, it is $\underbrace{\left(  -1\right)  ^{\left[  k=k\right]
}}_{=\left(  -1\right)  ^{1}=-1}e_{k}=-e_{k}$. Thus, this $d$-tuple $\left(
\left(  -1\right)  ^{\left[  1=k\right]  }e_{1},\left(  -1\right)  ^{\left[
2=k\right]  }e_{2},\ldots,\left(  -1\right)  ^{\left[  d=k\right]  }%
e_{d}\right)  $ is obtained from the $d$-tuple $\left(  e_{1},e_{2}%
,\ldots,e_{d}\right)  $ by replacing its $k$-th entry by $-e_{k}$. In other
words,
\[
\left(  \left(  -1\right)  ^{\left[  1=k\right]  }e_{1},\left(  -1\right)
^{\left[  2=k\right]  }e_{2},\ldots,\left(  -1\right)  ^{\left[  d=k\right]
}e_{d}\right)  =\left(  e_{1},e_{2},\ldots,e_{k-1},-e_{k},e_{k+1}%
,e_{k+2},\ldots,e_{d}\right)  .
\]
}). Hence, the map%
\[
N\rightarrow P,\qquad\left(  e_{1},e_{2},\ldots,e_{d}\right)  \mapsto\left(
\left(  -1\right)  ^{\left[  1=k\right]  }e_{1},\left(  -1\right)  ^{\left[
2=k\right]  }e_{2},\ldots,\left(  -1\right)  ^{\left[  d=k\right]  }%
e_{d}\right)
\]
is bijective, i.e., is a bijection from $N$ to $P$.

Recall that each element of $\left\{  -1,1\right\}  ^{d}$ belongs to exactly
one of the two subsets $N$ and $P$. Hence, we can split the sum $\sum_{\left(
e_{1},e_{2},\ldots,e_{d}\right)  \in\left\{  -1,1\right\}  ^{d}}e_{x_{1}%
}e_{x_{2}}\cdots e_{x_{n}}$ as follows:%
\begin{align*}
&  \sum_{\left(  e_{1},e_{2},\ldots,e_{d}\right)  \in\left\{  -1,1\right\}
^{d}}e_{x_{1}}e_{x_{2}}\cdots e_{x_{n}}\\
&  =\sum_{\left(  e_{1},e_{2},\ldots,e_{d}\right)  \in N}e_{x_{1}}e_{x_{2}%
}\cdots e_{x_{n}}+\sum_{\left(  e_{1},e_{2},\ldots,e_{d}\right)  \in
P}e_{x_{1}}e_{x_{2}}\cdots e_{x_{n}}\\
&  =\sum_{\left(  e_{1},e_{2},\ldots,e_{d}\right)  \in N}e_{x_{1}}e_{x_{2}%
}\cdots e_{x_{n}}+\sum_{\left(  e_{1},e_{2},\ldots,e_{d}\right)  \in
N}\underbrace{\left(  \left(  -1\right)  ^{\left[  x_{1}=k\right]  }e_{x_{1}%
}\right)  \left(  \left(  -1\right)  ^{\left[  x_{2}=k\right]  }e_{x_{2}%
}\right)  \cdots\left(  \left(  -1\right)  ^{\left[  x_{n}=k\right]  }%
e_{x_{n}}\right)  }_{=\left(  \left(  -1\right)  ^{\left[  x_{1}=k\right]
}\left(  -1\right)  ^{\left[  x_{2}=k\right]  }\cdots\left(  -1\right)
^{\left[  x_{n}=k\right]  }\right)  \left(  e_{x_{1}}e_{x_{2}}\cdots e_{x_{n}%
}\right)  }\\
&  \qquad\left(
\begin{array}
[c]{c}%
\text{here, we have substituted }\left(  \left(  -1\right)  ^{\left[
1=k\right]  }e_{1},\left(  -1\right)  ^{\left[  2=k\right]  }e_{2}%
,\ldots,\left(  -1\right)  ^{\left[  d=k\right]  }e_{d}\right) \\
\text{for }\left(  e_{1},e_{2},\ldots,e_{d}\right)  \text{ in the second sum,
since}\\
\text{the map }N\rightarrow P,\qquad\left(  e_{1},e_{2},\ldots,e_{d}\right)
\mapsto\left(  \left(  -1\right)  ^{\left[  1=k\right]  }e_{1},\left(
-1\right)  ^{\left[  2=k\right]  }e_{2},\ldots,\left(  -1\right)  ^{\left[
d=k\right]  }e_{d}\right) \\
\text{is a bijection}%
\end{array}
\right) \\
&  =\sum_{\left(  e_{1},e_{2},\ldots,e_{d}\right)  \in N}e_{x_{1}}e_{x_{2}%
}\cdots e_{x_{n}}+\sum_{\left(  e_{1},e_{2},\ldots,e_{d}\right)  \in
N}\underbrace{\left(  \left(  -1\right)  ^{\left[  x_{1}=k\right]  }\left(
-1\right)  ^{\left[  x_{2}=k\right]  }\cdots\left(  -1\right)  ^{\left[
x_{n}=k\right]  }\right)  }_{=-1}\left(  e_{x_{1}}e_{x_{2}}\cdots e_{x_{n}%
}\right) \\
&  =\sum_{\left(  e_{1},e_{2},\ldots,e_{d}\right)  \in N}e_{x_{1}}e_{x_{2}%
}\cdots e_{x_{n}}-\sum_{\left(  e_{1},e_{2},\ldots,e_{d}\right)  \in
N}e_{x_{1}}e_{x_{2}}\cdots e_{x_{n}}=0.
\end{align*}
This proves Claim 1 \textbf{(a)}.

\textbf{(b)} Assume that the $n$-tuple $\left(  x_{1},x_{2},\ldots
,x_{n}\right)  $ is all-even. Thus, for each $k\in\left[  d\right]  $, the
number of all $i\in\left[  n\right]  $ satisfying $x_{i}=k$ is even (by the
definition of \textquotedblleft all-even\textquotedblright).

Let $k\in\left[  d\right]  $. As we have just seen, the number of all
$i\in\left[  n\right]  $ satisfying $x_{i}=k$ is even. In other words, there
exists some $h\in\mathbb{Z}$ such that
\begin{equation}
\left(  \text{the number of all }i\in\left[  n\right]  \text{ satisfying
}x_{i}=k\right)  =2h. \label{sol.count.all-even-tups.c1.pf.b.1}%
\end{equation}
Consider this $h$.

Now, let $\left(  e_{1},e_{2},\ldots,e_{d}\right)  \in\left\{  -1,1\right\}
^{d}$ be arbitrary. Thus, $e_{k}\in\left\{  -1,1\right\}  $, so that
$e_{k}^{2}=1$. Now,%
\begin{align}
\prod_{\substack{i\in\left[  n\right]  ;\\x_{i}=k}}\underbrace{e_{x_{i}}%
}_{\substack{=e_{k}\\\text{(since }x_{i}=k\text{)}}}  &  =\prod
_{\substack{i\in\left[  n\right]  ;\\x_{i}=k}}e_{k}=e_{k}^{\left(  \text{the
number of all }i\in\left[  n\right]  \text{ satisfying }x_{i}=k\right)
}=e_{k}^{2h}\qquad\left(  \text{by \eqref{sol.count.all-even-tups.c1.pf.b.1}}%
\right) \nonumber\\
&  =\left(  \underbrace{e_{k}^{2}}_{=1}\right)  ^{h}=1^{h}=1.
\label{sol.count.all-even-tups.c1.pf.b.2}%
\end{align}


Now, forget that we fixed $\left(  e_{1},e_{2},\ldots,e_{d}\right)  $ and $k$.
We thus have proven \eqref{sol.count.all-even-tups.c1.pf.b.2} for each
$\left(  e_{1},e_{2},\ldots,e_{d}\right)  \in\left\{  -1,1\right\}  ^{d}$ and
$k\in\left[  d\right]  $.

Now, each $\left(  e_{1},e_{2},\ldots,e_{d}\right)  \in\left\{  -1,1\right\}
^{d}$ satisfies%
\[
e_{x_{1}}e_{x_{2}}\cdots e_{x_{n}}=\underbrace{\prod_{i\in\left[  n\right]  }%
}_{=\prod_{k\in\left[  d\right]  }\prod_{\substack{i\in\left[  n\right]
;\\x_{i}=k}}}e_{x_{i}}=\prod_{k\in\left[  d\right]  }\underbrace{\prod
_{\substack{i\in\left[  n\right]  ;\\x_{i}=k}}e_{x_{i}}}%
_{\substack{=1\\\text{(by \eqref{sol.count.all-even-tups.c1.pf.b.2})}}%
}=\prod_{k\in\left[  d\right]  }1=1.
\]
Hence,%
\begin{align*}
\sum_{\left(  e_{1},e_{2},\ldots,e_{d}\right)  \in\left\{  -1,1\right\}  ^{d}%
}\underbrace{e_{x_{1}}e_{x_{2}}\cdots e_{x_{n}}}_{=1}  &  =\sum_{\left(
e_{1},e_{2},\ldots,e_{d}\right)  \in\left\{  -1,1\right\}  ^{d}}1=\left\vert
\left\{  -1,1\right\}  ^{d}\right\vert \cdot1\\
&  =\left\vert \left\{  -1,1\right\}  ^{d}\right\vert =\left\vert \left\{
-1,1\right\}  \right\vert ^{d}=2^{d}.
\end{align*}
This proves Claim 1 \textbf{(b)}.]

Now, \eqref{sol.count.all-even-tups.2} becomes%
\begin{align}
&  \sum_{\left(  e_{1},e_{2},\ldots,e_{d}\right)  \in\left\{  -1,1\right\}
^{d}}\left(  e_{1}+e_{2}+\cdots+e_{d}\right)  ^{n}\nonumber\\
&  =\sum_{\left(  x_{1},x_{2},\ldots,x_{n}\right)  \in\left[  d\right]  ^{n}%
}\sum_{\left(  e_{1},e_{2},\ldots,e_{d}\right)  \in\left\{  -1,1\right\}
^{d}}e_{x_{1}}e_{x_{2}}\cdots e_{x_{n}}\nonumber\\
&  =\sum_{\substack{\left(  x_{1},x_{2},\ldots,x_{n}\right)  \in\left[
d\right]  ^{n};\\\left(  x_{1},x_{2},\ldots,x_{n}\right)  \text{ is all-even}%
}}\underbrace{\sum_{\left(  e_{1},e_{2},\ldots,e_{d}\right)  \in\left\{
-1,1\right\}  ^{d}}e_{x_{1}}e_{x_{2}}\cdots e_{x_{n}}}_{\substack{=2^{d}%
\\\text{(by Claim 1 \textbf{(b)})}}}\nonumber\\
&  \qquad+\sum_{\substack{\left(  x_{1},x_{2},\ldots,x_{n}\right)  \in\left[
d\right]  ^{n};\\\left(  x_{1},x_{2},\ldots,x_{n}\right)  \text{ is not
all-even}}}\underbrace{\sum_{\left(  e_{1},e_{2},\ldots,e_{d}\right)
\in\left\{  -1,1\right\}  ^{d}}e_{x_{1}}e_{x_{2}}\cdots e_{x_{n}}%
}_{\substack{=0\\\text{(by Claim 1 \textbf{(a)})}}}\nonumber\\
&  =\sum_{\substack{\left(  x_{1},x_{2},\ldots,x_{n}\right)  \in\left[
d\right]  ^{n};\\\left(  x_{1},x_{2},\ldots,x_{n}\right)  \text{ is all-even}%
}}2^{d}+\underbrace{\sum_{\substack{\left(  x_{1},x_{2},\ldots,x_{n}\right)
\in\left[  d\right]  ^{n};\\\left(  x_{1},x_{2},\ldots,x_{n}\right)  \text{ is
not all-even}}}0}_{=0}=\sum_{\substack{\left(  x_{1},x_{2},\ldots
,x_{n}\right)  \in\left[  d\right]  ^{n};\\\left(  x_{1},x_{2},\ldots
,x_{n}\right)  \text{ is all-even}}}2^{d}\nonumber\\
&  =\left(  \text{the number of all all-even }\left(  x_{1},x_{2},\ldots
,x_{n}\right)  \in\left[  d\right]  ^{n}\right)  \cdot2^{d}.
\label{sol.count.all-even-tups.c1.pf.b.lhs}%
\end{align}


For each $d$-tuple $\left(  e_{1},e_{2},\ldots,e_{d}\right)  \in\left\{
-1,1\right\}  ^{d}$, we have%
\begin{align*}
d-\left(  e_{1}+e_{2}+\cdots+e_{d}\right)   &  =\underbrace{d}_{=\sum
_{i\in\left[  d\right]  }1}-\sum_{i\in\left[  d\right]  }e_{i}=\sum
_{i\in\left[  d\right]  }1-\sum_{i\in\left[  d\right]  }e_{i}=\sum
_{i\in\left[  d\right]  }\left(  1-e_{i}\right) \\
&  =\sum_{\substack{i\in\left[  d\right]  ;\\e_{i}=-1}}\left(
1-\underbrace{e_{i}}_{=-1}\right)  +\sum_{\substack{i\in\left[  d\right]
;\\e_{i}=1}}\left(  1-\underbrace{e_{i}}_{=1}\right) \\
&  \qquad\left(
\begin{array}
[c]{c}%
\text{since each }i\in\left[  d\right]  \text{ satisfies either }%
e_{i}=-1\text{ or }e_{i}=1\\
\text{(but not both) (because }\left(  e_{1},e_{2},\ldots,e_{d}\right)
\in\left\{  -1,1\right\}  ^{d}\text{)}%
\end{array}
\right) \\
&  =\sum_{\substack{i\in\left[  d\right]  ;\\e_{i}=-1}}\underbrace{\left(
1-\left(  -1\right)  \right)  }_{=2}+\sum_{\substack{i\in\left[  d\right]
;\\e_{i}=1}}\underbrace{\left(  1-1\right)  }_{=0}=\sum_{\substack{i\in\left[
d\right]  ;\\e_{i}=-1}}2+\underbrace{\sum_{\substack{i\in\left[  d\right]
;\\e_{i}=1}}0}_{=0}\\
&  =\sum_{\substack{i\in\left[  d\right]  ;\\e_{i}=-1}}2=\left\vert \left\{
i\in\left[  d\right]  \ \mid\ e_{i}=-1\right\}  \right\vert \cdot
2=2\cdot\left\vert \left\{  i\in\left[  d\right]  \ \mid\ e_{i}=-1\right\}
\right\vert
\end{align*}
and thus%
\[
e_{1}+e_{2}+\cdots+e_{d}=d-2\cdot\left\vert \left\{  i\in\left[  d\right]
\ \mid\ e_{i}=-1\right\}  \right\vert .
\]
Hence,%
\begin{align}
&  \sum_{\left(  e_{1},e_{2},\ldots,e_{d}\right)  \in\left\{  -1,1\right\}
^{d}}\left(  \underbrace{e_{1}+e_{2}+\cdots+e_{d}}_{=d-2\cdot\left\vert
\left\{  i\in\left[  d\right]  \ \mid\ e_{i}=-1\right\}  \right\vert }\right)
^{n}\nonumber\\
&  =\sum_{\left(  e_{1},e_{2},\ldots,e_{d}\right)  \in\left\{  -1,1\right\}
^{d}}\left(  d-2\cdot\left\vert \left\{  i\in\left[  d\right]  \ \mid
\ e_{i}=-1\right\}  \right\vert \right)  ^{n}.
\label{sol.count.all-even-tups.c1.pf.b.8}%
\end{align}


On the other hand, a $d$-tuple $\left(  e_{1},e_{2},\ldots,e_{d}\right)
\in\left\{  -1,1\right\}  ^{d}$ is uniquely determined by the set $\left\{
i\in\left[  d\right]  \ \mid\ e_{i}=-1\right\}  $ of all positions at which it
contains a $-1$ (and conversely, for every subset $S$ of $\left[  d\right]  $,
there exists such a $d$-tuple whose set $\left\{  i\in\left[  d\right]
\ \mid\ e_{i}=-1\right\}  $ is $S$). Thus, the map
\[
\left\{  -1,1\right\}  ^{d}\rightarrow\left\{  S\subseteq\left[  d\right]
\right\}  ,\qquad\left(  e_{1},e_{2},\ldots,e_{d}\right)  \mapsto\left\{
i\in\left[  d\right]  \ \mid\ e_{i}=-1\right\}
\]
is a bijection. Hence, we can substitute $S$ for $\left\{  i\in\left[
d\right]  \ \mid\ e_{i}=-1\right\}  $ in the sum on the right hand side of
\eqref{sol.count.all-even-tups.c1.pf.b.8}. We thus obtain%
\begin{align*}
&  \sum_{\left(  e_{1},e_{2},\ldots,e_{d}\right)  \in\left\{  -1,1\right\}
^{d}}\left(  d-2\cdot\left\vert \left\{  i\in\left[  d\right]  \ \mid
\ e_{i}=-1\right\}  \right\vert \right)  ^{n}\\
&  =\underbrace{\sum_{S\subseteq\left[  d\right]  }}_{=\sum_{k=0}^{d}%
\sum_{\substack{S\subseteq\left[  d\right]  ;\\\left\vert S\right\vert =k}%
}}\left(  d-2\cdot\left\vert S\right\vert \right)  ^{n}=\sum_{k=0}^{d}%
\sum_{\substack{S\subseteq\left[  d\right]  ;\\\left\vert S\right\vert
=k}}\left(  d-2\cdot\underbrace{\left\vert S\right\vert }_{=k}\right)  ^{n}\\
&  =\sum_{k=0}^{d}\underbrace{\sum_{\substack{S\subseteq\left[  d\right]
;\\\left\vert S\right\vert =k}}\left(  d-2k\right)  ^{n}}_{=\left(  \text{the
number of all }S\subseteq\left[  d\right]  \text{ satisfying }\left\vert
S\right\vert =k\right)  \cdot\left(  d-2k\right)  ^{n}}\\
&  =\sum_{k=0}^{d}\underbrace{\left(  \text{the number of all }S\subseteq
\left[  d\right]  \text{ satisfying }\left\vert S\right\vert =k\right)
}_{=\left(  \text{the number of all }k\text{-element subsets of }\left[
d\right]  \right)  =\dbinom{d}{k}}\cdot\left(  d-2k\right)  ^{n}\\
&  =\sum_{k=0}^{d}\dbinom{d}{k}\left(  d-2k\right)  ^{n}.
\end{align*}
Hence, \eqref{sol.count.all-even-tups.c1.pf.b.8} becomes%
\begin{align*}
&  \sum_{\left(  e_{1},e_{2},\ldots,e_{d}\right)  \in\left\{  -1,1\right\}
^{d}}\left(  e_{1}+e_{2}+\cdots+e_{d}\right)  ^{n}\\
&  =\sum_{\left(  e_{1},e_{2},\ldots,e_{d}\right)  \in\left\{  -1,1\right\}
^{d}}\left(  d-2\cdot\left\vert \left\{  i\in\left[  d\right]  \ \mid
\ e_{i}=-1\right\}  \right\vert \right)  ^{n}=\sum_{k=0}^{d}\dbinom{d}%
{k}\left(  d-2k\right)  ^{n}.
\end{align*}
Comparing this with \eqref{sol.count.all-even-tups.c1.pf.b.lhs}, we obtain%
\[
\left(  \text{the number of all all-even }\left(  x_{1},x_{2},\ldots
,x_{n}\right)  \in\left[  d\right]  ^{n}\right)  \cdot2^{d}=\sum_{k=0}%
^{d}\dbinom{d}{k}\left(  d-2k\right)  ^{n}.
\]
Solving this for $\left(  \text{the number of all all-even }\left(
x_{1},x_{2},\ldots,x_{n}\right)  \in\left[  d\right]  ^{n}\right)  $, we
obtain%
\[
\left(  \text{the number of all all-even }\left(  x_{1},x_{2},\ldots
,x_{n}\right)  \in\left[  d\right]  ^{n}\right)  =\dfrac{1}{2^{d}}\sum
_{k=0}^{d}\dbinom{d}{k}\left(  d-2k\right)  ^{n}.
\]
This solves the exercise.

\begin{thebibliography}{99999999}                                                                                         %


\bibitem[Elafan18]{Elafan18}Jacob Elafandi,
\textit{\href{http://www.cip.ifi.lmu.de/~grinberg/t/18f/hw4s-elafandi.pdf}{\textit{Solutions
to UMN Fall 2018 Math 5705 homework set \#4}}}.\newline\url{http://www.cip.ifi.lmu.de/~grinberg/t/18f/hw4s-elafandi.pdf}

\bibitem[Gorski18]{Gorski18}Nathaniel Gorski,
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18s/hw4s-gorski.pdf}{\textit{Solutions
to UMN Spring 2018 Math 4707 homework set \#4}}.\newline\url{http://www.cip.ifi.lmu.de/~grinberg/t/18s/hw4s-gorski.pdf}

\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[Grinbe18]{Grinbe18}Darij Grinberg,
\textit{\href{http://www.cip.ifi.lmu.de/~grinberg/t/18s/hw3s.pdf}{\textit{Solutions
to UMN Spring 2018 Math 4707 homework set \#3}}}.\newline\url{http://www.cip.ifi.lmu.de/~grinberg/t/18s/hw3s.pdf}
\end{thebibliography}


\end{document}