% Like most advanced LaTeX files, this one begins with a lot of
% boilerplate. You don't need to understand (or even read) most of it.
% All you need to do is fill in your name, UMN ID, email address,
% and the number of the pset. (Search for "METADATA" to find the place
% for this.) Then, you can go straight to the "EXERCISE 1"
% section and start writing your solutions.
% The "VARIOUS USEFUL COMMANDS" section is probably worth taking a
% look at at some point.

%----------------------------------------------------------------------------------------
%	PACKAGES AND OTHER DOCUMENT CONFIGURATIONS
%----------------------------------------------------------------------------------------
\documentclass[paper=a4, fontsize=12pt]{scrartcl} % A4 paper and 12pt font size
\usepackage[T1]{fontenc} % Use 8-bit encoding that has 256 glyphs
\usepackage[english]{babel} % English language/hyphenation
\usepackage{amsmath,amsfonts,amsthm,amssymb} % Math packages
\usepackage{mathrsfs}    % More math packages
\usepackage{sectsty}  % Allows customizing section commands
\allsectionsfont{\centering \normalfont\scshape} % Make all section titles centered, the default font and small caps %remove this to left align section tites
\usepackage{hyperref} % Turns cross-references into hyperlinks,
                      % and defines \url and \href commands.
\usepackage{graphicx} % For embedding graphics files.
\usepackage{framed}   % For the "leftbar" environment used below.
\usepackage{ifthen}   % Used for the \powset command below.
\usepackage{lastpage} % for counting the number of pages
\usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage}
\usepackage[height=10in,a4paper,hmargin={1in,0.8in}]{geometry}
\usepackage[usenames,dvipsnames]{xcolor}
\usepackage{tikz}     % This is a powerful tool to draw vector
                      % graphics inside LaTeX. In particular, you can
                      % use it to draw graphs.
\usepackage{verbatim} % For the "verbatim" environment, in which
                      % special symbols can be used freely without
                      % confusing the compiler. (And it's typeset in
                      % a constant-width font.)
                      % Useful, e.g., for quoting code (or ASCII art).
\usepackage{ytableau}

%\numberwithin{table}{section} % Number tables within sections (i.e. 1.1, 1.2, 2.1, 2.2 instead of 1, 2, 3, 4)

\setlength\parindent{20pt} % Makes indentation for paragraphs longer.
                           % This makes paragraphs stand out more.

%----------------------------------------------------------------------------------------
%	VARIOUS USEFUL COMMANDS
%----------------------------------------------------------------------------------------
% The commands below might be convenient. For example, you probably
% prefer to write $\powset[2]{V}$ for the set of $2$-element subsets
% of $V$, rather than writing $\mathcal{P}_2(V)$.
% Notice that you can easily define your own commands like this.
% Caveat: Some of these commands need to be properly "guarded" when
% they occur in subscripts or superscripts. So you should not write
% $K_\CC$, but rather $K_{\CC}$.
\newcommand{\CC}{\mathbb{C}} % complex numbers
\newcommand{\RR}{\mathbb{R}} % real numbers
\newcommand{\QQ}{\mathbb{Q}} % rational numbers
\newcommand{\NN}{\mathbb{N}} % nonnegative integers
\newcommand{\Z}[1]{\mathbb{Z}/#1\mathbb{Z}} % integers modulo k
                                            % (syntax: "\Z{k}")
\newcommand{\ZZ}{\mathbb{Z}} % integers
\newcommand{\id}{\operatorname{id}} % identity map
\newcommand{\lcm}{\operatorname{lcm}}
% Lowest common multiple. For historical reasons, LaTeX has a \gcd
% command built in, but not an \lcm command. The preceding line
% rectifies that.
\newcommand{\Des}{\operatorname{Des}} % descent set of a permutation
\newcommand{\rev}{\operatorname{rev}} % reversal of a walk
\newcommand{\powset}[2][]{\ifthenelse{\equal{#2}{}}{\mathcal{P}\left(#1\right)}{\mathcal{P}_{#1}\left(#2\right)}}
% $\powset[k]{S}$ stands for the set of all $k$-element subsets of
% $S$. The argument $k$ is optional, and if not provided, the result
% is the whole powerset of $S$.
\newcommand{\set}[1]{\left\{ #1 \right\}}
% $\set{...}$ compiles to {...} (set-brackets).
\newcommand{\abs}[1]{\left| #1 \right|}
% $\abs{...}$ compiles to |...| (absolute value, or size of a set).
\newcommand{\tup}[1]{\left( #1 \right)}
% $\tup{...}$ compiles to (...) (parentheses, or tuple-brackets).
\newcommand{\ive}[1]{\left[ #1 \right]}
% $\ive{...}$ compiles to [...] (Iverson bracket, aka truth value).
\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}
% $\floor{...}$ compiles to |_..._| (floor function).
\newcommand{\verts}[1]{\operatorname{V}\left( #1 \right)}
% $\verts{...}$ compiles to V(...) (vertex set of a graph/digraph).
\newcommand{\edges}[1]{\operatorname{E}\left( #1 \right)}
% $\edges{...}$ compiles to E(...) (edge set of a graph).
\newcommand{\arcs}[1]{\operatorname{A}\left( #1 \right)}
% $\arcs{...}$ compiles to A(...) (arc set of a digraph).
\newcommand{\lf}[2]{#1^{\underline{#2}}}
% $\lf{...1}{...2}$ compiles to $...1^{\underline{...2}}$.
% This is a notation for the falling factorial.
\newcommand{\underbrack}[2]{\underbrace{#1}_{\substack{#2}}}
% $\underbrack{...1}{...2}$ yields
% $\underbrace{...1}_{\substack{...2}}$. This is useful for doing
% local rewriting transformations on mathematical expressions with
% justifications. For example, try this out:
% $ \underbrack{(a+b)^2}{= a^2 + 2ab + b^2 \\ \text{(by the binomial formula)}} $
\newcommand{\horrule}[1]{\rule{\linewidth}{#1}} % Create horizontal rule command with 1 argument of height
\newcommand{\nnn}{\nonumber\\} % Don't number this line in an "align" environment, and move on to the next line.
\newcommand{\sslash}{\mathbin{/\mkern-6mu/}} % Quotient of division with remainder.

%----------------------------------------------------------------------------------------
%	MAKING SUMMATION SIGNS ALWAYS PUT THEIR BOUNDS ABOVE AND BELOW
%	THE SIGN
%----------------------------------------------------------------------------------------
% The following are hacks to ensure that sums (such as
% $\sum_{k=1}^n k$) always put their bounds (i.e., the $k=1$ and the
% $n$) underneath and above the sign, as opposed to on its right.
% Same for products (\prod), set unions (\bigcup) and set
% intersections (\bigcap). Remove the 8 lines below if you do not want
% this behavior.
\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}

%----------------------------------------------------------------------------------------
%	ENVIRONMENTS
%----------------------------------------------------------------------------------------
% The incantations below define how theorem environments
% (\begin{theorem} ... \end{theorem}) and their likes will look like.
\newtheoremstyle{plainsl}% <name>
  {8pt plus 2pt minus 4pt}% <Space above>
  {8pt plus 2pt minus 4pt}% <Space below>
  {\slshape}% <Body font>
  {0pt}% <Indent amount>
  {\bfseries}% <Theorem head font>
  {.}% <Punctuation after theorem head>
  {5pt plus 1pt minus 1pt}% <Space after theorem headi>
  {}% <Theorem head spec (can be left empty, meaning `normal')>

% Environments which make the text inside them slanted:
\theoremstyle{plainsl}
  \newtheorem{theorem}{Theorem}[section]
  \newtheorem{proposition}[theorem]{Proposition}
  \newtheorem{lemma}[theorem]{Lemma}
  \newtheorem{corollary}[theorem]{Corollary}
  \newtheorem{conjecture}[theorem]{Conjecture}
% Environments that don't:
\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}}

%----------------------------------------------------------------------------------------
%	METADATA
%----------------------------------------------------------------------------------------
\newcommand{\myname}{Darij Grinberg} % ENTER YOUR NAME HERE
\newcommand{\myid}{00000000} % ENTER YOUR UMN ID HERE
\newcommand{\mymail}{dgrinber@umn.edu} % ENTER YOUR EMAIL HERE
\newcommand{\psetnumber}{4} % ENTER THE NUMBER OF THIS PSET HERE

%----------------------------------------------------------------------------------------
%	HEADER AND FOOTER
%----------------------------------------------------------------------------------------
\ihead{Solutions to homework set \#\psetnumber} % Page header left
\ohead{page \thepage\ of \pageref{LastPage}} % Page header right
\ifoot{\myname, \myid} % left footer
\ofoot{\mymail} % right footer

%----------------------------------------------------------------------------------------
%	TITLE SECTION
%----------------------------------------------------------------------------------------
\title{	
\normalfont \normalsize 
\textsc{University of Minnesota, School of Mathematics} \\ [25pt] % Your university, school and/or department name(s)
\horrule{0.5pt} \\[0.4cm] % Thin top horizontal rule
\huge Math 5705: Enumerative Combinatorics, \\
Fall 2018:
Homework \psetnumber\\% The assignment title
\horrule{2pt} \\[0.5cm] % Thick bottom horizontal rule
}
\author{\myname}

\begin{document}

\maketitle % Print the title

\begin{center} % Delete this if you want to save space!
{\large due date: \textbf{Wednesday, 31 October 2018} at the beginning of class, \\
or before that by email or canvas.

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

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

\section{Exercise 1}

\subsection{Problem}

Let $n \in \NN$ and $\sigma \in S_n$.
Let $i$ and $j$ be two elements of $\ive{n}$ such that
$i<j$ and $\sigma \tup{i} > \sigma \tup{j}$.
Let $Q$ be the set of all $k \in \set{ i+1,i+2,\ldots,j-1 }$
satisfying $\sigma \tup{i} > \sigma \tup{k} > \sigma \tup{j}$.
Prove that
\[
\ell \tup{ \sigma\circ t_{i,j} }
= \ell \tup{\sigma} - 2 \abs{Q} - 1 .
\]

\subsection{Remark}

This exercise implies that, in particular,
$\ell \tup{ \sigma\circ t_{i,j} } < \ell \tup{\sigma}$;
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}

[...]

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

\section{Exercise 2}

\subsection{Problem}

Let $n \in \NN$ and $\pi \in S_n$.

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


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

\end{enumerate}

[\textbf{Hint:} Exercise 5.23 in \cite{detnotes}
says something about sums of the form appearing in part \textbf{(a)}.
(See also Nathaniel Gorski's solution of the same exercise in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18s/hw4s-gorski.pdf}{Spring 2018 Math 4707 homework set \#4}.)
You may want to use the result or the ideas.]

\subsection{Solution}

[...]

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

\section{Exercise 3}

\subsection{Problem}

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

Let $p \in \ZZ$.
Prove that $\abs{D_{n, p}} = \abs{D_{n, n-1-p}}$.

\subsection{Solution}

[...]

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

\section{Exercise 4}

\subsection{Problem}

Let $n \in \NN$.
Let $S = \set{ s_1 < s_2 < \cdots < s_k }$ be a subset of $\ive{n-1}$.
Set $s_0 = 0$ and $s_{k+1} = n$.
For each $i \in \ive{k+1}$, 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
\[
\abs{ \set{ \sigma \in S_n \mid \Des \sigma \subseteq S } }
= \dbinom{n}{d_1, d_2, \ldots, d_{k+1}}.
\]
(The term on the right hand side is a multinomial coefficient.
The $\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
\[
\abs{ \set{ \sigma \in S_n \mid \Des \sigma = S } }
= \sum_{T \subseteq S} \tup{-1}^{\abs{S} - \abs{T}}
    \abs{ \set{ \sigma \in S_n \mid \Des \sigma \subseteq T } }.
\]

\end{enumerate}

\subsection{Solution}

[...]

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

\section{Exercise 5}

\subsection{Problem}

Let $n \in \NN$.
We shall follow the convention that $t_{i, i}$ denotes the
identity permutation $\id \in S_n$ for each $i \in \ive{n}$.

Let $\sigma \in S_n$.

It is known that there is a unique $n$-tuple
$\tup{i_1, i_2, \ldots, i_n} \in \ive{1} \times \ive{2} \times \cdots \times \ive{n}$
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 \set{0, 1, \ldots, n}$, 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 \ive{n}$, let $m_k = \sigma_k \tup{k}$.

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

\item[\textbf{(b)}]
Show that $\sigma_k \tup{i_k} = k$ for all $k \in \ive{n}$.

\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\tup{k}}
=
\sum_{k=1}^{n} \tup{x_{i_k} - x_k} \tup{y_{m_k} - y_k}
.
\]

\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\tup{k}}.
\]

\end{enumerate}

\subsection{Remark}

Parts \textbf{(a)} and \textbf{(c)}, combined, show that
$\tup{m_1, m_2, \ldots, m_n}$ 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}

[...]

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

\section{Exercise 6}

\subsection{Problem}

Prove the following:

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

\item[\textbf{(b)}]
If $n \in \NN$ and $r \in \ive{n-1}$, then
\[
\sum_{k=0}^{n} \tup{-1}^k \dbinom{2n}{k} \tup{n-k}^{2r} = 0.
\]
\end{enumerate}

\subsection{Solution}

[...]

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

\section{Exercise 7}

\subsection{Problem}

Let $n \in \NN$ and $d \in \NN$.
An $n$-tuple $\tup{x_1, x_2, \ldots, x_n} \in \ive{d}^n$ is said to be
\textit{all-even} if each element of $\ive{d}$ occurs an even
number of times in this $n$-tuple (i.e., if for each $k \in \ive{d}$,
the number of all $i \in \ive{n}$ satisfying $x_i = k$ is even).
For example, the $4$-tuple $\tup{1,4,4,1}$ and the $6$-tuples
$\tup{1,3,3,5,1,5}$ and $\tup{2,4,2,4,3,3}$ are all-even, while
the $4$-tuples $\tup{1,2,2,4}$ and $\tup{2,4,6,4}$ are not.

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


[\textbf{Hint:} Compute the sum
$\sum_{\tup{e_1, e_2, \ldots, e_d} \in \set{-1, 1}^d}
\tup{ e_1 + e_2 + \cdots + e_d }^n$ in two ways.
One way is to split it according to the
number of $i \in \ive{d}$ satisfying $e_i = -1$;
this is a number $k \in \set{0, 1, \ldots, d}$.
Another way is by using the product rule:
\[
\tup{ e_1 + e_2 + \cdots + e_d }^n
= \sum_{\tup{x_1, x_2, \ldots, x_n} \in \ive{d}^{n}}
e_{x_1} e_{x_2} \cdots e_{x_n}
\]
and then simplifying each sum
$\sum_{\tup{e_1, e_2, \ldots, e_d} \in \set{-1, 1}^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}

[...]

\begin{thebibliography}{99999999}                                                                                         %

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

