\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{}
%TCIDATA{}
%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\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}