\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=Tuesday, November 07, 2017 03:10:32}
%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 7}
\ohead{page \thepage}
\cfoot{}
\begin{document}

\begin{center}
\textbf{Math 4990 Fall 2017 (Darij Grinberg): homework set 7}

due date: Tuesday 14 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{A generalized principle of inclusion/exclusion}

\begin{exercise}
\label{exe.pie.dan}Let $n\in\mathbb{N}$. Let $S$ be a finite set. Let
$A_{1},A_{2},\ldots,A_{n}$ be finite subsets of $S$. Let $k\in\mathbb{N}$. Let
$S_{k}$ be the set of all elements of $S$ that belong to exactly $k$ of the
subsets $A_{1},A_{2},\ldots,A_{n}$. (In other words, let $S_{k}=\left\{  s\in
S\ \mid\ \text{the number of }i\in\left[  n\right]  \text{ satisfying }s\in
A_{i}\text{ equals }k\right\}  $.) Prove that%
\[
\left\vert S_{k}\right\vert =\sum_{I\subseteq\left[  n\right]  }\left(
-1\right)  ^{\left\vert I\right\vert -k}\dbinom{\left\vert I\right\vert }%
{k}\left\vert \bigcap_{i\in I}A_{i}\right\vert .
\]

\end{exercise}

Note that the principle of inclusion and exclusion (see, e.g., \cite[\S 16]%
{Galvin}) is the particular case of Exercise \ref{exe.pie.dan} for $k=0$
(since $S_{0}=S\setminus\bigcup_{i=1}^{n}A_{i}$).

\subsection{Summing fixed point numbers of permutations}

Recall that for any $n\in\mathbb{N}$, we let $S_{n}$ denote the set of all
permutations of $\left[  n\right]  $.

If $S$ is a finite set, and if $f:S\rightarrow S$ is a map, then we let
$\operatorname*{Fix}f$ denote the set of all fixed points of $f$. (That is,
$\operatorname*{Fix}f=\left\{  s\in S\ \mid\ f\left(  s\right)  =s\right\}  $.)

\begin{exercise}
Let $n$ be a positive integer. Prove that $\sum_{w\in S_{n}}\left\vert
\operatorname*{Fix}w\right\vert =n!$.

[\textbf{Hint:} Rewrite $\left\vert \operatorname*{Fix}w\right\vert $ as
$\sum_{i\in\left[  n\right]  }\left[  w\left(  i\right)  =i\right]  $.]
\end{exercise}

(In other words, this exercise states that the average number of fixed points
of a permutation of $\left[  n\right]  $ is $1$.)

\subsection{Transpositions $t_{1,i}$ generate permutations}

Recall a basic notation regarding permutations:

\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}.
\end{definition}

\begin{exercise}
\label{exe.t1i-gen-Sn}Let $n\in\mathbb{N}$. Prove that each permutation in
$S_{n}$ can be written as a composition of some of the transpositions
$t_{1,2},t_{1,3},\ldots,t_{1,n}$.

(Note that this composition can be empty -- in which case it is understood to
be $\operatorname*{id}$ --, and it can contain any given transposition
multiple times.)
\end{exercise}

You are allowed to use the well-known fact (\cite[Exercise 5.1 \textbf{(b)}%
]{detnotes}) that each permutation in $S_{n}$ can be written as a composition
of some of the transpositions $s_{1},s_{2},\ldots,s_{n-1}$, where $s_{i}$ is
defined to be $t_{i,i+1}$.

\subsection{V-permutations as products of cycles}

Recall the following notation:

\begin{definition}
\label{def.cyc}Let $X$ be a set. Let $k$ be a positive integer. Let
$i_{1},i_{2},\ldots,i_{k}$ be $k$ distinct elements of $X$. We define
$\operatorname*{cyc}\nolimits_{i_{1},i_{2},\ldots,i_{k}}$ to be the
permutation of $X$ that sends $i_{1},i_{2},\ldots,i_{k}$ to $i_{2}%
,i_{3},\ldots,i_{k},i_{1}$, respectively, while leaving all other elements of
$X$ fixed. In other words, we define $\operatorname*{cyc}\nolimits_{i_{1}%
,i_{2},\ldots,i_{k}}$ to be the permutation of $X$ given by%
\[
\operatorname*{cyc}\nolimits_{i_{1},i_{2},\ldots,i_{k}}\left(  p\right)  =%
\begin{cases}
i_{j+1}, & \text{if }p=i_{j}\text{ for some }j\in\left\{  1,2,\ldots
,k\right\}  ;\\
p, & \text{otherwise}%
\end{cases}
\ \ \ \ \ \ \ \ \ \ \text{for every }p\in X,
\]
where $i_{k+1}$ means $i_{1}$.
\end{definition}

\begin{exercise}
\label{exe.V-perm-as-cyc}Let $n\in\mathbb{N}$. For each $r\in\left[  n\right]
$, let $c_{r}$ denote the permutation $\operatorname*{cyc}%
\nolimits_{r,r-1,\ldots,2,1}\in S_{n}$. (Thus, $c_{1}=\operatorname*{cyc}%
\nolimits_{1}=\operatorname*{id}$ and $c_{2}=\operatorname*{cyc}%
\nolimits_{2,1}=s_{1}$.)

Let $G=\left\{  g_{1}<g_{2}<\cdots<g_{p}\right\}  $ be a subset of $\left[
n\right]  $. Let $\sigma\in S_{n}$ be the permutation $c_{g_{1}}\circ
c_{g_{2}}\circ\cdots\circ c_{g_{p}}$.

Prove the following:

\textbf{(a)} We have $\sigma\left(  1\right)  >\sigma\left(  2\right)
>\cdots>\sigma\left(  p\right)  $.

\textbf{(b)} We have $\sigma\left(  \left[  p\right]  \right)  =G$.

\textbf{(c)} We have $\sigma\left(  p+1\right)  <\sigma\left(  p+2\right)
<\cdots<\sigma\left(  n\right)  $.

(Note that a chain of inequalities that involves less than two numbers is
considered to be vacuously true. For example, Exercise \ref{exe.V-perm-as-cyc}
\textbf{(c)} is vacuously true when $p=n-1$ and also when $p=n$.)
\end{exercise}

Permutations $\sigma\in S_{n}$ satisfying the inequalities $\sigma\left(
1\right)  >\sigma\left(  2\right)  >\cdots>\sigma\left(  p\right)  $ and
$\sigma\left(  p+1\right)  <\sigma\left(  p+2\right)  <\cdots<\sigma\left(
n\right)  $ for some $p\in\left\{  0,1,\ldots,n\right\}  $ are known as
\textquotedblleft V-permutations\textquotedblright\ (as their plot looks
somewhat like the letter \textquotedblleft V\textquotedblright: first
decreasing for a while, then increasing). Can you guess how permutations
$\sigma\in S_{n}$ satisfying $\sigma\left(  1\right)  <\sigma\left(  2\right)
<\cdots<\sigma\left(  p\right)  $ and $\sigma\left(  p+1\right)
>\sigma\left(  p+2\right)  >\cdots>\sigma\left(  n\right)  $ are called?

\subsection{Lexicographic comparison of permutations}

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

For example, if $\sigma$ is the permutation of $\left[  5\right]  $ written in
one-line notation as $\left[  4,1,5,2,3\right]  $, then $\ell_{1}\left(
\sigma\right)  =3$, $\ell_{2}\left(  \sigma\right)  =0$, $\ell_{3}\left(
\sigma\right)  =2$, $\ell_{4}\left(  \sigma\right)  =0$ and $\ell_{5}\left(
\sigma\right)  =0$.

\begin{definition}
Let $n\in\mathbb{N}$. Let $\left(  a_{1},a_{2},\ldots,a_{n}\right)  $ and
$\left(  b_{1},b_{2},\ldots,b_{n}\right)  $ be two $n$-tuples of integers. We
say that $\left(  a_{1},a_{2},\ldots,a_{n}\right)  <_{\operatorname*{lex}%
}\left(  b_{1},b_{2},\ldots,b_{n}\right)  $ if and only if there exists some
$k\in\left[  n\right]  $ such that $a_{k}\neq b_{k}$, and the
\textbf{smallest} such $k$ satisfies $a_{k}<b_{k}$.
\end{definition}

For example, $\left(  4,1,2,5\right)  <_{\operatorname*{lex}}\left(
4,1,3,0\right)  $ and $\left(  1,1,0,1\right)  <_{\operatorname*{lex}}\left(
2,0,0,0\right)  $. The relation $<_{\operatorname*{lex}}$ is usually
pronounced \textquotedblleft is lexicographically smaller
than\textquotedblright; the word \textquotedblleft
lexicographic\textquotedblright\ comes from the idea that if numbers were
letters, then a \textquotedblleft word\textquotedblright\ $a_{1}a_{2}\cdots
a_{n}$ would appear earlier in a dictionary than $b_{1}b_{2}\cdots b_{n}$ if
and only if $\left(  a_{1},a_{2},\ldots,a_{n}\right)  <_{\operatorname*{lex}%
}\left(  b_{1},b_{2},\ldots,b_{n}\right)  $.

\begin{exercise}
\label{exe.perm.lexico1}Let $n\in\mathbb{N}$. Let $\sigma\in S_{n}$ and
$\tau\in S_{n}$. Prove the following:

\textbf{(a)} If
\[
\left(  \sigma\left(  1\right)  ,\sigma\left(  2\right)  ,\ldots,\sigma\left(
n\right)  \right)  <_{\operatorname*{lex}}\left(  \tau\left(  1\right)
,\tau\left(  2\right)  ,\ldots,\tau\left(  n\right)  \right)  ,
\]
then
\[
\left(  \ell_{1}\left(  \sigma\right)  ,\ell_{2}\left(  \sigma\right)
,\ldots,\ell_{n}\left(  \sigma\right)  \right)  <_{\operatorname*{lex}}\left(
\ell_{1}\left(  \tau\right)  ,\ell_{2}\left(  \tau\right)  ,\ldots,\ell
_{n}\left(  \tau\right)  \right)  .
\]


\textbf{(b)} If $\left(  \ell_{1}\left(  \sigma\right)  ,\ell_{2}\left(
\sigma\right)  ,\ldots,\ell_{n}\left(  \sigma\right)  \right)  =\left(
\ell_{1}\left(  \tau\right)  ,\ell_{2}\left(  \tau\right)  ,\ldots,\ell
_{n}\left(  \tau\right)  \right)  $, then $\sigma=\tau$.
\end{exercise}

\begin{noncompile}
\textbf{(a)} An \textit{inversion} of $\sigma$ means a pair $\left(
i,j\right)  \in\left[  n\right]  ^{2}$ such that $i<j$ and $\sigma\left(
i\right)  >\sigma\left(  j\right)  $. (For example, the permutation of
$\left[  5\right]  $ written in one-line notation as $\left[
4,1,5,2,3\right]  $ has inversions $\left(  1,2\right)  ,\left(  1,4\right)
,\left(  1,5\right)  ,\left(  3,4\right)  ,\left(  3,5\right)  $.)
\end{noncompile}

\subsection{Comparing subsets of $\left[  n\right]  $}

If $I$ and $J$ are two finite sets of integers, then we write $I\leq_{\#}J$ if
and only if the following two properties hold:

\begin{itemize}
\item We have $\left\vert I\right\vert \geq\left\vert J\right\vert $.

\item For every $r\in\left\{  1,2,\ldots,\left\vert J\right\vert \right\}  $,
the $r$-th smallest element of $I$ is $\leq$ to the $r$-th smallest element of
$J$.
\end{itemize}

For example, $\left\{  2,4\right\}  \leq_{\#}\left\{  2,5\right\}  $ and
$\left\{  1,3\right\}  \leq_{\#}\left\{  2,4\right\}  $ and $\left\{
1,3,5\right\}  \leq_{\#}\left\{  2,4\right\}  $. (But not $\left\{
1,3\right\}  \leq_{\#}\left\{  2,4,5\right\}  $.)

\begin{exercise}
\label{exe.gale}Let $n\in\mathbb{N}$. Let $I$ and $J$ be two subsets of
$\left[  n\right]  $.

\textbf{(a)} For every subset $S$ of $\left[  n\right]  $ and every $\ell
\in\left[  n\right]  $, let $\alpha_{S}\left(  \ell\right)  $ denote the
number of all elements of $S$ that are $\leq\ell$. Prove that $I\leq_{\#}J$
holds if and only if every $\ell\in\left[  n\right]  $ satisfies $\alpha
_{I}\left(  \ell\right)  \geq\alpha_{J}\left(  \ell\right)  $.

\textbf{(b)} Prove that $I\leq_{\#}J$ if and only if $\left[  n\right]
\setminus J\leq_{\#}\left[  n\right]  \setminus I$.
\end{exercise}

\begin{remark}
Recall that we have defined a \textit{Dyck word} as a list $w$ of $2n$
numbers, exactly $n$ of which are $0$'s while the other $n$ are $1$'s, and
having the property that for each $k\in\left[  2n\right]  $, the number of
$0$'s among the first $k$ entries of $w$ is $\leq$ to the number of $1$'s
among the first $k$ entries of $w$.

It is not hard to see the connection between the relation $\leq_{\#}$ and Dyck
words: Let $w=\left(  w_{1},w_{2},\ldots,w_{2n}\right)  \in\left\{
0,1\right\}  ^{2n}$ be a list of $2n$ numbers, exactly $n$ of which are $0$'s
while the other $n$ are $1$'s. Then, $w$ is a Dyck word if and only if%
\[
\left\{  i\in\left[  2n\right]  \ \mid\ w_{i}=1\right\}  \leq_{\#}\left\{
i\in\left[  2n\right]  \ \mid\ w_{i}=0\right\}
\]
(in other words, for every $r\in\left[  n\right]  $, the $r$-th appearance of
$1$ in $w$ precedes the $r$-th appearance of $0$ in $w$).
\end{remark}

\subsection{A rigorous approach to the existence of a cycle decomposition}

The purpose of the following exercise is to give a rigorous proof of the fact
that any permutation can be decomposed into disjoint cycles.

\begin{exercise}
\label{exe.perm.rig-cyc.1}Let $X$ be a finite set. Let $\sigma$ be a
permutation of $X$.

Define a binary relation $\sim$ on the set $X$ as follows: For two elements
$x\in X$ and $y\in X$, we set $x\sim y$ if and only if there exists some
$k\in\mathbb{N}$ such that $y=\sigma^{k}\left(  x\right)  $.

\textbf{(a)} Prove that $\sim$ is an equivalence relation.

For any $x\in X$, we let $\left[  x\right]  _{\sim}$ denote the $\sim
$-equivalence class of $x$.

\textbf{(b)} For any $x\in X$, prove that $\left[  x\right]  _{\sim}=\left\{
\sigma^{0}\left(  x\right)  ,\sigma^{1}\left(  x\right)  ,\ldots,\sigma
^{k-1}\left(  x\right)  \right\}  $, where $k=\left\vert \left[  x\right]
_{\sim}\right\vert $.

\textbf{(c)} For any $\sim$-equivalence class $E$, let us define $c_{E}$ to be
the map
\[
X\rightarrow X,\ \ \ \ \ \ \ \ \ \ x\mapsto%
\begin{cases}
\sigma\left(  x\right)  , & \text{if }x\in E;\\
x, & \text{if }x\notin E
\end{cases}
.
\]
Prove that $c_{E}$ is a permutation of $X$.

\textbf{(d)} Prove that if $E=\left[  x\right]  _{\sim}$ for some $x\in X$,
then $c_{E}$ can be written as $\operatorname*{cyc}\nolimits_{\sigma
^{0}\left(  x\right)  ,\sigma^{1}\left(  x\right)  ,\ldots,\sigma^{k-1}\left(
x\right)  }$, where $k=\left\vert \left[  x\right]  _{\sim}\right\vert $.
(Don't forget to show that $\sigma^{0}\left(  x\right)  ,\sigma^{1}\left(
x\right)  ,\ldots,\sigma^{k-1}\left(  x\right)  $ are distinct, so that
$\operatorname*{cyc}\nolimits_{\sigma^{0}\left(  x\right)  ,\sigma^{1}\left(
x\right)  ,\ldots,\sigma^{k-1}\left(  x\right)  }$ is well-defined.)

\textbf{(e)} Let $E_{1},E_{2},\ldots,E_{m}$ be all $\sim$-equivalence classes
(listed without repetitions -- that is, $E_{i}\neq E_{j}$ whenever $i\neq j$).
Prove that%
\[
\sigma=c_{E_{1}}\circ c_{E_{2}}\circ\cdots\circ c_{E_{m}}.
\]

\end{exercise}

\begin{thebibliography}{99999999}                                                                                         %


\bibitem[Galvin17]{Galvin}David Galvin, \textit{Basic discrete mathematics}, 5
November 2017.\newline\url{http://www.cip.ifi.lmu.de/~grinberg/t/17f/60610lectures2017-Galvin.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} .

\end{thebibliography}


\end{document}