\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{graphicx}%
\setcounter{MaxMatrixCols}{30}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Sunday, December 17, 2017 19:57:14}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%BeginMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
%EndMSIPreambleData
\newcounter{exer}
\theoremstyle{definition}
\newtheorem{theo}{Theorem}[section]
\newenvironment{theorem}[1][]
{\begin{theo}[#1]\begin{leftbar}}
{\end{leftbar}\end{theo}}
\newtheorem{lem}[theo]{Lemma}
\newenvironment{lemma}[1][]
{\begin{lem}[#1]\begin{leftbar}}
{\end{leftbar}\end{lem}}
\newtheorem{prop}[theo]{Proposition}
\newenvironment{proposition}[1][]
{\begin{prop}[#1]\begin{leftbar}}
{\end{leftbar}\end{prop}}
\newtheorem{defi}[theo]{Definition}
\newenvironment{definition}[1][]
{\begin{defi}[#1]\begin{leftbar}}
{\end{leftbar}\end{defi}}
\newtheorem{remk}[theo]{Remark}
\newenvironment{remark}[1][]
{\begin{remk}[#1]\begin{leftbar}}
{\end{leftbar}\end{remk}}
\newtheorem{coro}[theo]{Corollary}
\newenvironment{corollary}[1][]
{\begin{coro}[#1]\begin{leftbar}}
{\end{leftbar}\end{coro}}
\newtheorem{conv}[theo]{Convention}
\newenvironment{condition}[1][]
{\begin{conv}[#1]\begin{leftbar}}
{\end{leftbar}\end{conv}}
\newtheorem{quest}[theo]{Question}
\newenvironment{algorithm}[1][]
{\begin{quest}[#1]\begin{leftbar}}
{\end{leftbar}\end{quest}}
\newtheorem{warn}[theo]{Warning}
\newenvironment{conclusion}[1][]
{\begin{warn}[#1]\begin{leftbar}}
{\end{leftbar}\end{warn}}
\newtheorem{conj}[theo]{Conjecture}
\newenvironment{conjecture}[1][]
{\begin{conj}[#1]\begin{leftbar}}
{\end{leftbar}\end{conj}}
\newtheorem{exam}[theo]{Example}
\newenvironment{example}[1][]
{\begin{exam}[#1]\begin{leftbar}}
{\end{leftbar}\end{exam}}
\newtheorem{exmp}[exer]{Exercise}
\newenvironment{exercise}[1][]
{\begin{exmp}[#1]\begin{leftbar}}
{\end{leftbar}\end{exmp}}
\newenvironment{statement}{\begin{quote}}{\end{quote}}
\iffalse
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\fi
\let\sumnonlimits\sum
\let\prodnonlimits\prod
\let\cupnonlimits\bigcup
\let\capnonlimits\bigcap
\renewcommand{\sum}{\sumnonlimits\limits}
\renewcommand{\prod}{\prodnonlimits\limits}
\renewcommand{\bigcup}{\cupnonlimits\limits}
\renewcommand{\bigcap}{\capnonlimits\limits}
\setlength\tablinesep{3pt}
\setlength\arraylinesep{3pt}
\setlength\extrarulesep{3pt}
\voffset=0cm
\hoffset=-0.7cm
\setlength\textheight{22.5cm}
\setlength\textwidth{15.5cm}
\newenvironment{verlong}{}{}
\newenvironment{vershort}{}{}
\newenvironment{noncompile}{}{}
\excludecomment{verlong}
\includecomment{vershort}
\excludecomment{noncompile}
\newcommand{\id}{\operatorname{id}}
\newcommand{\rev}{\operatorname{rev}}
\newcommand{\conncomp}{\operatorname{conncomp}}
\newcommand{\conn}{\operatorname{conn}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\powset}[2][]{\ifthenelse{\equal{#2}{}}{\mathcal{P}\left(#1\right)}{\mathcal{P}_{#1}\left(#2\right)}}
\newcommand{\set}[1]{\left\{ #1 \right\}}
\newcommand{\abs}[1]{\left| #1 \right|}
\newcommand{\tup}[1]{\left( #1 \right)}
\newcommand{\ive}[1]{\left[ #1 \right]}
\newcommand{\verts}[1]{\operatorname{V}\left( #1 \right)}
\newcommand{\edges}[1]{\operatorname{E}\left( #1 \right)}
\newcommand{\arcs}[1]{\operatorname{A}\left( #1 \right)}
\newcommand{\underbrack}[2]{\underbrace{#1}_{\substack{#2}}}
\newcommand{\are}{\ar@{-}}
\newcommand{\arebi}[1][]{\ar@{<-}@/_/[#1] \ar@/^/[#1]}
\ihead{Math 4990 Fall 2017 (Darij Grinberg): homework set 8}
\ohead{page \thepage}
\cfoot{}
\begin{document}

\begin{center}
\textbf{Math 4990 Fall 2017 (Darij Grinberg): homework set 8 [corrected 17 Dec
2017]}

due date: Tuesday 28 Nov 2017 at the beginning of class, or before that by
email or moodle

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

\subsection{Strange integers}

\begin{exercise}
\label{exe.supercat}For any $m\in\mathbb{N}$ and $n\in\mathbb{N}$, define a
rational number $T\left(  m,n\right)  $ by%
\[
T\left(  m,n\right)  =\dfrac{\left(  2m\right)  !\left(  2n\right)
!}{m!n!\left(  m+n\right)  !}.
\]


\textbf{(a)} Prove that $4T\left(  m,n\right)  =T\left(  m+1,n\right)
+T\left(  m,n+1\right)  $ for every $m\in\mathbb{N}$ and $n\in\mathbb{N}$.

\textbf{(b)} Prove that $T\left(  m,n\right)  \in\mathbb{N}$ for every
$m\in\mathbb{N}$ and $n\in\mathbb{N}$.

\textbf{(c)} Prove that $T\left(  m,n\right)  $ is an \textbf{even} integer
for every $m\in\mathbb{N}$ and $n\in\mathbb{N}$ unless $\left(  m,n\right)
=\left(  0,0\right)  $.

\textbf{(d)} If $m\in\mathbb{N}$ and $n\in\mathbb{N}$ are such that $m+n$ is
odd and $m+n>1$, then prove that $4\mid T\left(  m,n\right)  $.

[\textbf{Hint:} Don't be afraid to use induction. Part \textbf{(b)} suggests
that the numbers $T\left(  m,n\right)  $ count something, but no one has so
far discovered what; combinatorial proofs aren't always the easiest to find.
For \textbf{(c)}, start by showing that $\dbinom{2g}{g}$ is even whenever $g$
is a positive integer. For \textbf{(d)}, start by showing that $\dbinom
{2g-1}{g-1}$ is even whenever $g>1$ is odd.]
\end{exercise}

\begin{exercise}
\label{exe.supercat2}Let $m\in\mathbb{N}$ and $n\in\mathbb{N}$. Let
$p=\min\left\{  m,n\right\}  $.

\textbf{(a)} Prove that%
\[
\sum_{k=-p}^{p}\left(  -1\right)  ^{k}\dbinom{m+n}{m+k}\dbinom{m+n}%
{n+k}=\dbinom{m+n}{m}.
\]


\textbf{(b)} Prove that%
\[
T\left(  m,n\right)  =\sum_{k=-p}^{p}\left(  -1\right)  ^{k}\dbinom{2m}%
{m+k}\dbinom{2n}{n-k},
\]
where $T\left(  m,n\right)  $ is defined as in Exercise \ref{exe.supercat}.

[\textbf{Hint:} Part \textbf{(a)} should follow from something done in class.
Then, compare part \textbf{(b)} with part \textbf{(a)}.]
\end{exercise}

\subsection{The length of a permutation}

\begin{definition}
Let $n\in\mathbb{N}$.

\textbf{(a)} We let $S_{n}$ denote the set of all permutations of $\left[
n\right]  $.

Let $\sigma\in S_{n}$ be a permutation of $\left[  n\right]  $.

\textbf{(b)} An \textit{inversion} of $\sigma$ means a pair $\left(
i,j\right)  $ of elements of $\left[  n\right]  $ satisfying $i<j$ and
$\sigma\left(  i\right)  >\sigma\left(  j\right)  $.

\textbf{(c)} The \textit{length} of $\sigma$ is defined to be the number of
inversions of $\sigma$. This length is denoted by $\ell\left(  \sigma\right)
$.

\textbf{(d)} The \textit{sign} of $\sigma$ is defined to be the integer
$\left(  -1\right)  ^{\ell\left(  \sigma\right)  }$. It is denoted by $\left(
-1\right)  ^{\sigma}$.
\end{definition}

\begin{exercise}
\label{exe.sign-matrix}Let $p\in\mathbb{N}$ and $q\in\mathbb{N}$. Let $n=pq$.
Consider the permutation $\sigma\in S_{n}$ that maps $\left(  i-1\right)  q+j$
to $\left(  j-1\right)  p+i$ for every $i\in\left[  p\right]  $ and
$j\in\left[  q\right]  $.

(This permutation $\sigma$ can be visualized as follows: Fill in a $p\times
q$-matrix $A$ with the entries $1,2,\ldots,n$ by going row by row from top to
bottom:%
\[
A=\left(
\begin{array}
[c]{ccccc}%
1 & 2 & 3 & \cdots & q\\
q+1 & q+2 & q+3 & \cdots & 2q\\
2q+1 & 2q+2 & 2q+3 & \cdots & 3q\\
\vdots & \vdots & \vdots & \ddots & \vdots\\
\left(  p-1\right)  q+1 & \left(  p-1\right)  q+2 & \left(  p-1\right)  q+3 &
\cdots & pq
\end{array}
\right)  .
\]
Fill in a $p\times q$-matrix $B$ with the entries $1,2,\ldots,n$ by going
column by column from left to right:%
\[
B=\left(
\begin{array}
[c]{ccccc}%
1 & p+1 & 2p+1 & \cdots & \left(  q-1\right)  p+1\\
2 & p+2 & 2p+2 & \cdots & \left(  q-1\right)  p+2\\
3 & p+3 & 2p+3 & \cdots & \left(  q-1\right)  p+3\\
\vdots & \vdots & \vdots & \ddots & \vdots\\
p & 2p & 3p & \cdots & qp
\end{array}
\right)  .
\]
The permutation $\sigma$ then sends each entry of $A$ to the corresponding
entry of $B$.)

Find the length $\ell\left(  \sigma\right)  $ of the permutation $\sigma$.
\end{exercise}

\subsection{Two equal counts}

\begin{exercise}
\label{exe.dumont-in-han-denert}Let $n\in\mathbb{N}$ and $\sigma\in S_{n}$.
Prove that%
\begin{align*}
&  \left(  \text{the number of all }\left(  i,j\right)  \in\left[  n\right]
\times\left[  n\right]  \text{ such that }i\geq j>\sigma\left(  i\right)
\right) \\
&  =\left(  \text{the number of all }\left(  i,j\right)  \in\left[  n\right]
\times\left[  n\right]  \text{ such that }\sigma\left(  i\right)  \geq
j>i\right)  .
\end{align*}

\end{exercise}

\subsection{Lehmer codes}

Recall the following definition from the preceding homework set:

\begin{definition}
Let $n\in\mathbb{N}$. Let $\sigma\in S_{n}$ be a permutation. For any
$i\in\left[  n\right]  $, we let $\ell_{i}\left(  \sigma\right)  $ denote the
number of $j\in\left\{  i+1,i+2,\ldots,n\right\}  $ such that $\sigma\left(
i\right)  >\sigma\left(  j\right)  $.
\end{definition}

\begin{exercise}
\label{exe.perm.lehmer2}Let $n\in\mathbb{N}$. Let $G$ be the set of all
$n$-tuples $\left(  j_{1},j_{2},\ldots,j_{n}\right)  $ of integers satisfying
$0\leq j_{k}\leq n-k$ for each $k\in\left[  n\right]  $. (In other words,
$G=\left\{  0,1,\ldots,n-1\right\}  \times\left\{  0,1,\ldots,n-2\right\}
\times\cdots\times\left\{  0,1,\ldots,n-n\right\}  $.)

\textbf{(a)} For any $\sigma\in S_{n}$ and $i\in\left[  n\right]  $, prove
that $\sigma\left(  i\right)  $ is the $\left(  \ell_{i}\left(  \sigma\right)
+1\right)  $-th smallest element of the set $\left[  n\right]  \setminus
\left\{  \sigma\left(  1\right)  ,\sigma\left(  2\right)  ,\ldots
,\sigma\left(  i-1\right)  \right\}  $.

\textbf{(b)} For any $\sigma\in S_{n}$, prove that
\[
\left(  \ell_{1}\left(  \sigma\right)  ,\ell_{2}\left(  \sigma\right)
,\ldots,\ell_{n}\left(  \sigma\right)  \right)  \in G.
\]


\textbf{(c)} Prove that the map%
\begin{align*}
S_{n}  &  \rightarrow G,\\
\sigma &  \mapsto\left(  \ell_{1}\left(  \sigma\right)  ,\ell_{2}\left(
\sigma\right)  ,\ldots,\ell_{n}\left(  \sigma\right)  \right)
\end{align*}
is bijective.

\textbf{(d)} Show that $\ell\left(  \sigma\right)  =\ell_{1}\left(
\sigma\right)  +\ell_{2}\left(  \sigma\right)  +\cdots+\ell_{n}\left(
\sigma\right)  $ for each $\sigma\in S_{n}$.

\textbf{(e)} Show that%
\[
\sum_{\sigma\in S_{n}}x^{\ell\left(  \sigma\right)  }=\left(  1+x\right)
\left(  1+x+x^{2}\right)  \cdots\left(  1+x+x^{2}+\cdots+x^{n-1}\right)
\]
(an equality between polynomials in $x$). (If $n\leq1$, then the right hand
side of this equality is an empty product, and thus equals $1$.)
\end{exercise}

Note that the $n$-tuple $\left(  \ell_{1}\left(  \sigma\right)  ,\ell
_{2}\left(  \sigma\right)  ,\ldots,\ell_{n}\left(  \sigma\right)  \right)  $
is known as the \textit{Lehmer code} of the permutation $\sigma$.

\subsection{Permutations as composed transpositions}

Recall a basic notation regarding permutations, which we shall now extend:

\begin{definition}
\label{def.transpos}Let $n\in\mathbb{N}$. Let $i$ and $j$ be two distinct
elements of $\left[  n\right]  $. We let $t_{i,j}$ be the permutation in
$S_{n}$ which switches $i$ with $j$ while leaving all other elements of
$\left[  n\right]  $ unchanged. Such a permutation is called a
\textit{transposition}.

Let us furthermore set $t_{i,i}=\operatorname*{id}$ for each $i\in\left[
n\right]  $. Thus, $t_{i,j}$ is defined even when $i$ and $j$ are not distinct.
\end{definition}

\begin{exercise}
\label{exe.perm.transpos-code}Let $n\in\mathbb{N}$. Let $\sigma\in S_{n}$.

\textbf{(a)} Prove 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]  $ such that%
\[
\sigma=t_{1,i_{1}}\circ t_{2,i_{2}}\circ\cdots\circ t_{n,i_{n}}.
\]


\textbf{(b)} Consider this $n$-tuple $\left(  i_{1},i_{2},\ldots,i_{n}\right)
$. Define the relation $\sim$ and the $\sim$-equivalence classes $E_{1}%
,E_{2},\ldots,E_{m}$ as in Exercise 7 on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/17f/hw7o.pdf}{homework set \#7}
(for $X=\left[  n\right]  $). (Thus, $m$ is the number of cycles in the cycle
decomposition of $\sigma$.)

Prove that $m$ is the number of all $k\in\left[  n\right]  $ satisfying
$i_{k}=k$.
\end{exercise}

\subsection{Another partition identity}

Recall the following:

\begin{definition}
Let $n\in\mathbb{Z}$. A \textit{partition} of $n$ means a finite list $\left(
i_{1},i_{2},\ldots,i_{k}\right)  $ of positive integers satisfying%
\[
i_{1}\geq i_{2}\geq\cdots\geq i_{k}\ \ \ \ \ \ \ \ \ \ \text{and}%
\ \ \ \ \ \ \ \ \ \ i_{1}+i_{2}+\cdots+i_{k}=n.
\]

\end{definition}

\begin{exercise}
\label{exe.partitions.atleastp}Let $n\in\mathbb{N}$ and $p\in\mathbb{N}$. Let
$a$ be the number of all partitions $\left(  i_{1},i_{2},\ldots,i_{k}\right)
$ of $n$ satisfying $k\geq p$ and $i_{1}=i_{2}=\cdots=i_{p}$.
Let $b$ be the number of all nonempty
partitions $\left(  i_{1},i_{2},\ldots,i_{k}\right)  $ of $n$
such that all of $i_{1},i_{2},\ldots,i_{k}$ are $\geq p$. Prove that $a=b$.
\end{exercise}

\begin{example}
Let $n=9$ and $p=3$. Then, the partitions counted by $a$ in Exercise
\ref{exe.partitions.atleastp} are%
\[
\left(  3,3,3\right)  ,\ \ \ \ \ \ \ \ \ \ \left(  2,2,2,2,1\right)
,\ \ \ \ \ \ \ \ \ \ \left(  2,2,2,1,1,1\right)  ,\ \ \ \ \ \ \ \ \ \ \left(
1,1,1,1,1,1,1,1,1\right)  .
\]
Meanwhile, the partitions counted by $b$ in Exercise
\ref{exe.partitions.atleastp} are%
\[
\left(  9\right)  ,\ \ \ \ \ \ \ \ \ \ \left(  6,3\right)
,\ \ \ \ \ \ \ \ \ \ \left(  5,4\right)  ,\ \ \ \ \ \ \ \ \ \ \left(
3,3,3\right)  .
\]
Thus, $a=4$ and $b=4$ in this case.
\end{example}

Further reading on partitions includes:

\begin{itemize}
\item Herbert S. Wilf, \textit{Lectures on Integer Partitions}, 2009.\newline\url{https://www.math.upenn.edu/~wilf/PIMS/PIMSLectures.pdf}

\item George E. Andrews, Kimmo Eriksson, \textit{Integer Partitions},
Cambridge University Press 2004.

\item Igor Pak, \textit{Partition bijections, a survey}, Ramanujan Journal,
vol. 12 (2006), pp. 5--75.\newline\url{http://www.math.ucla.edu/~pak/papers/psurvey.pdf}
\end{itemize}

The Wikipedia articles on
\href{https://en.wikipedia.org/wiki/Partition_(number_theory)}{partitions},
the \href{https://en.wikipedia.org/wiki/Pentagonal_number_theorem}{pentagonal
number theorem} and
\href{https://en.wikipedia.org/wiki/Ramanujan's_congruences}{Ramanujan's
congruences} are also useful. That said, none of these is necessary for the
above exercise.
\end{document}