% 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{\inv}{\operatorname{inv}}
% Number of inversions of a lattice path.
\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.
\newcommand\kstaircasepath[6]{
\fill[cyan!25]  (#1) rectangle +(#2,#3);
\fill[fill=lime]
(#1)
\foreach \dir in {#4}{
\ifnum\dir=1
-- ++(1,0)
\else
-- ++(0,1)
\fi
} |- (#1);
\draw[help lines] (#1) grid +(#2,#3);
\draw[dashed] (#1) -- +(#5,#6);
\coordinate (prev) at (#1);
\foreach \dir in {#4}{
\ifnum\dir=1
\coordinate (dep) at (1,0);
\else
\coordinate (dep) at (0,1);
\fi
\draw[line width=2pt,-stealth] (prev) -- ++(dep) coordinate (prev);
};
} % lattice paths with custom diagonal; see below for examples.

%----------------------------------------------------------------------------------------
%	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}{5} % 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, 28 November 2018} at the beginning of class, \\
or before that by email or canvas.

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

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

\section{Exercise 1}

\subsection{Problem}

A \textit{point} shall mean an element of $\ZZ^2$, that is, a pair of
integers. We depict these points as lattice points on the Cartesian plane, and
add and subtract them as vectors.

Recall the notion of a \textit{lattice path}, defined in \S 6.1
(\href{http://www.cip.ifi.lmu.de/~grinberg/t/18f/5705-2018-11-12.pdf}{class
notes from 2018-11-12}) and (equivalently) in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18s/mt1s.pdf}{UMN Spring 2018
Math 4707 Midterm 1}. (Lattice paths have up-steps and right-steps.)

Fix a positive integer $k$.

We say that a point $\tup{x, y} \in \ZZ^2$ is \textit{off-limits}
if $ky > x$.
(Thus, the off-limits points are the ones that
lie strictly above the $x = ky$ diagonal in Cartesian coordinates.)

A lattice path $\tup{v_0, v_1, \ldots, v_n}$ is said to be
\textit{$k$-legal} if none of the points $v_0, v_1, \ldots, v_n$ is
off-limits.
Equivalently, a lattice path $\tup{v_0, v_1, \ldots, v_n}$ is
$k$-legal if each point $\tup{x, y} \in \set{v_0, v_1, \ldots, v_n}$
satisfies $x \geq ky$.

For example, the lattice path from $\tup{0, 0}$ to $\tup{5, 2}$
drawn in the picture
\[
\begin{tikzpicture}
\kstaircasepath{0,0}{5}{3}{1,0,1,1,1,0,1}{6}{3};
% This is to be understood as follows: The "{0, 0}" means that the
% path starts at (0, 0). The "{5}{3}" are the width and the height
% of the total grid. The "{1,0,1,1,1,0,1}" are the steps of the
% path ("1" means right-step; "0" means up-step).
% The "{6}{3}" at the end determine where the dotted diagonal ends.
\end{tikzpicture}
\]
\footnote{Formally speaking, this lattice path is the list \newline
$\tup{\tup{0, 0}, \tup{1, 0}, \tup{1, 1}, \tup{2, 1}, \tup{3, 1},
\tup{4, 1}, \tup{4, 2}, \tup{5, 2}}$.} is not $2$-legal, since it
contains the off-limits point $\tup{1, 1}$.
Meanwhile, the lattice path from
$\tup{0, 0}$ to $\tup{5, 2}$ drawn in the picture
\[
\begin{tikzpicture}
\kstaircasepath{0,0}{5}{3}{1,1,1,0,1,0,1}{6}{3};
\end{tikzpicture}
\]
is $2$-legal.

For any $n \in \ZZ$ and $m \in \ZZ$, we let $L_{n,m,k}$ be the
number of all $k$-legal lattice paths from $\tup{0, 0}$ to
$\tup{n, m}$.

\begin{enumerate}
\item[\textbf{(a)}] Prove that
$L_{n,m,k} = L_{n-1,m,k} + L_{n,m-1,k}$ for any
$n \in \ZZ$ and $m \in \ZZ$ satisfying $n \geq km$
and $\tup{n, m} \neq \tup{0, 0}$.

\item[\textbf{(b)}] Prove that
\[
L_{n,m,k} = \dbinom{n+m}{m} - k\dbinom{n+m}{m-1}
\]
for all $n \in \NN$ and $m \in \NN$ satisfying
$n \geq km-1$.

[The requirement $n \geq km-1$ as opposed to $n \geq km$ is not a typo; the
equality still holds for $n = km-1$, albeit for fairly simple reasons.]

\item[\textbf{(c)}] Prove that
$L_{n,m,k} = \dfrac{n+1-km}{n+1} \dbinom{n+m}{m}$
for all $n \in \NN$ and $m \in \NN$ satisfying $n \geq km-1$.

\item[\textbf{(d)}] Prove that
\[
L_{km,m,k}
= \dfrac{1}{km+1} \dbinom{\tup{k+1} m}{m}
= \dfrac{1}{\tup{k+1} m + 1}\dbinom{\tup{k+1} m + 1}{m}
\]
for any $m \in \NN$.
\end{enumerate}

\subsection{Remark}

This exercise generalizes Exercise 2 from
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18s/mt2s.pdf}{UMN Spring 2018
Math 4707 Midterm 2} (except that I've added an extra equality to part
\textbf{(d)}). You are free to solve it by copypasting the solution of the
latter (\href{http://www.cip.ifi.lmu.de/~grinberg/t/18s/mt2s.tex}{download
its TeX source} -- alas, computer-generated), or by referencing the solution
of the latter and pointing out what changes are necessary and where.

\subsection{Solution}

[...]

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

\section{Exercise 2}

\subsection{Problem}

We shall abbreviate ``lattice path'' as ``LP''.

Recall that an LP is said to be \textit{legal} if it is $k$-legal
for $k = 1$.

Recall also that $C_n$ denotes the $n$-th Catalan number (that is,
$\dfrac{1}{n+1} \dbinom{2n}{n}$) for any $n \in \NN$.

If $\mathbf{v} = \tup{v_0, v_1, \ldots, v_n}$ is an LP, then an
\textit{inversion} of $\mathbf{v}$ means a pair $\tup{i, j} \in \ive{n}^2$
such that $i < j$ and such that
the $i$-th step of $\mathbf{v}$ is an up-step (i.e., we
have $v_i - v_{i-1} = \tup{0, 1}$) but the $j$-th step of $\mathbf{v}$
is a right-step (i.e., we have $v_j - v_{j-1} = \tup{1, 0}$).

For example, the LP depicted in
\begin{equation}
\begin{tikzpicture}
\kstaircasepath{0,0}{4}{4}{1,0,1,1,0,0,1,0}{0}{0};
\end{tikzpicture}
%\label{eq.exe.cat.inversion-sign.ex1}
\end{equation}
has the $5$ inversions $\tup{2, 3}$ and $\tup{2, 4}$ and
$\tup{2, 7}$ and $\tup{5, 7}$ and $\tup{6, 7}$
(and no others).
It is easy to see that these inversions correspond to the $5$
green squares under the LP in the above picture; more generally, any LP
$\mathbf{v} = \tup{v_0, v_1, \ldots, v_n}$ from a point $s$ to a
point $t$ subdivides its ``bounding box'' (i.e., the
rectangle with opposing corners $s$ and $t$) into two parts, and
the area of the part under the LP is exactly the number of inversions of
$\mathbf{v}$.

If $\mathbf{v} = \tup{v_0, v_1, \ldots, v_n}$ is a LP, then
$\inv \mathbf{v}$ denotes the number of inversions of $\mathbf{v}$.

Now, let $n \in \NN$. Prove that
\[
\sum_{\substack{\mathbf{v}\text{ is a legal LP}\\\text{from }
\tup{0, 0} \text{ to } \tup{n, n} }}
\tup{-1}^{\inv \mathbf{v}}
=
\begin{cases}
C_{\tup{n-1}/2}, & \text{if } n \text{ is odd};\\
0,               & \text{if } n \text{ is even.}
\end{cases}
\]

[\textbf{Hint:} What happens to a legal LP from $\tup{0, 0}$ to
$\tup{n, n}$ if we swap its $2$-nd and $3$-rd steps? If the answer
is ``nothing'', then what if we swap its
$4$-th and $5$-th steps? If nothing again, its $6$-th and $7$-th steps?]

\subsection{Solution}

[...]

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

\section{Exercise 3}

\subsection{Problem}

Let $x \in \QQ$ and $p \in \NN$. Prove that
\[
\sum_{k=0}^{p} C_k \dbinom{x-2k}{p-k} = \dbinom{x+1}{p}.
\]

[\textbf{Hint:} By the ``polynomial identity
trick'', it suffices to prove this in the case when
$x+1 \geq 2p$.]

\subsection{Solution}

[...]

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

\section{Exercise 4}

\subsection{Problem}

Let $n$ be a positive integer. Prove that
\[
\sum_{k=0}^{n}  \tup{-1}^k C_k \dbinom{n+k}{2k} = 0.
\]

\subsection{Solution}

[...]

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

\section{Exercise 5}

\subsection{Problem}

Let $n \in \NN$.
A \textit{deranged involution} of $\ive{2n}$
shall mean a fixed-point-free involution $\sigma : \ive{2n} \to \ive{2n}$
such that every $i \in \ive{n}$ satisfies
$\sigma\tup{2i-1} \neq 2i$.

(For example, the permutation of $\ive{6}$ whose one-line notation
is $\ive{4,5,6,1,2,3}$ is a deranged involution, but the
permutation of $\ive{6}$ whose one-line notation is
$\ive{6,5,4,3,2,1}$ is not.)

Let $a_n$ be the number of deranged involutions of $\ive{2n}$.

\begin{enumerate}
\item[\textbf{(a)}]
Prove that $a_0 = 1$ and $a_1 = 0$ and
$a_n = 2 \tup{n-1} \tup{ a_{n-1}+a_{n-2} }$ for all $n \geq 2$.

\item[\textbf{(b)}]
Prove that
\[
a_n
= \sum_{k=0}^{n} \tup{-1}^{n-k} \dbinom{n}{k}
\tup{1 \cdot 3 \cdot 5 \cdot \cdots \cdot \tup{2k-1}}
\qquad\text{for all } n \in \NN .
\]

\end{enumerate}

\subsection{Solution}

[...]

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

\section{Exercise 6}

\subsection{Problem}

Let $n \in \NN$. Let $\sigma\in S_n$.
Set $h \tup{\sigma} = \sum_{i \in \ive{n}} \abs{ \sigma\tup{i} - i }$.

\begin{enumerate}
\item[\textbf{(a)}] Prove that
\[
h\tup{\sigma}
= 2\sum_{\substack{i\in \ive{n} ;\\\sigma \tup{i} > i}} \tup{ \sigma\tup{i} - i }
= 2\sum_{\substack{i\in \ive{n} ;\\\sigma \tup{i} < i}} \tup{ i - \sigma\tup{i} } .
\]


\item[\textbf{(b)}] Prove that
$h\tup{s_i \circ \sigma} \leq h\tup{\sigma} + 2$
for each $i \in \ive{n-1}$.

\item[\textbf{(c)}] Prove that
\[
h\tup{\sigma} /2 \leq \ell\tup{\sigma} \leq h\tup{\sigma} .
\]

\end{enumerate}

[\textbf{Hint:} As mentioned, you are free to use previous homework sets and midterms.]

\subsection{Solution}

[...]

% Uncomment the bibliography below if you want to cite things.
% \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}

