% 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, 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{tabls}

%\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{\OLN}{\operatorname{OLN}} % one-line notation
\newcommand{\Fix}{\operatorname{Fix}} % fixed points of a map
\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(...) (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{\explain}[1]{\tup{\hspace{-0.5pc}\text{\begin{tabular}{c}#1\end{tabular}\hspace{-0.5pc}}}}
% $\explain{...}$ interprets the "..." as text (you can
% nest some math inside by putting it in $...$'s as you
% would in any other text block) and puts it in parentheses.

%----------------------------------------------------------------------------------------
%	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{\mymail}{darij.grinberg@drexel.edu} % ENTER YOUR EMAIL HERE
\newcommand{\psetnumber}{3} % ENTER THE NUMBER OF THIS PSET HERE

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

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

\begin{document}

\maketitle % This command causes the title part to be printed.

\begin{center} % Delete this if you want to save space!
{\vspace{-1pc} \large due date: \textbf{Wednesday, 2019-12-04} at the beginning of class, \\
or before that through Blackboard. \\[0.4cm]

Please solve \textbf{3 of the 5 exercises}!

This is a midterm, so \textbf{collaboration is not allowed}!}
\end{center}

\section*{Notations}

Here is a list of notations that are used in this homework:

\begin{itemize}
\item We shall use the notation
$\ive{n}$ for the set $\set{ 1, 2, \ldots, n }$ (when
$n \in \ZZ$).

\item If $n \in \NN$, then $S_n$ denotes the set of all permutations
of $\ive{n}$.

\item If $n \in \NN$ and $\sigma \in S_n$, then:

\begin{itemize}
\item the \textit{one-line notation} $\OLN \sigma$ of $\sigma$
is defined as the $n$-tuple
$\tup{ \sigma\tup{1}, \sigma\tup{2}, \ldots, \sigma\tup{n} }$.
% Often, this
% $n$-tuple is written with square brackets, i.e., as $\left[  \sigma\left(  1
% \right)  , \sigma\left(  2 \right)  , \ldots, \sigma\left(  n \right)
% \right]  $.

\item the \textit{inversions} of $\sigma$ are defined to be the pairs
$\tup{i, j}$ of integers satisfying $1 \leq i < j \leq n$
and $\sigma\tup{i} > \sigma\tup{j}$.

\item the \textit{length} $\ell\tup{\sigma}$ of $\sigma$ is defined to
be the \# of inversions of $\sigma$.

\item the \textit{sign} $\tup{-1}^{\sigma}$ of $\sigma$ is defined to be
$\tup{-1}^{\ell\tup{\sigma}}$.

\item we say that $\sigma$ is \textit{even} if $\tup{-1}^{\sigma} = 1$
(that is, if $\ell\tup{\sigma}$ is even).

\item we say that $\sigma$ is \textit{odd} if $\tup{-1}^{\sigma} = -1$
(that is, if $\ell\tup{\sigma}$ is odd).

\item we let $\Fix \sigma$ denote the set of all fixed points of
$\sigma$;
in other words,
\[
\Fix \sigma = \set{ i \in \ive{n} \mid \sigma\tup{i} = i } .
\]
\end{itemize}
\end{itemize}

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

\section{Exercise 1}

\subsection{Problem}

Let $n$ be an integer such that $n \geq 2$.
If $w \in S_n$ is a permutation, then the \textit{peaks} of $w$ are
defined to be the elements $i \in \set{2, 3, \ldots, n-1}$ satisfying
$w \tup{i-1} < w \tup{i} > w \tup{i+1}$.
(For example, if $n = 7$ and if $\OLN w = \tup{4,1,2,5,3,7,6}$,
then the peaks of $w$ are $4$ and $6$.
The name ``peak'' is explained by a look at the plot of $w$.)

An \textit{$n$-peak set} shall mean a subset $P$ of
$\set{2, 3, \ldots, n-1}$ such that there exists a $w \in S_n$
satisfying $\set{\text{peaks of } w } = P$.
(For example, the example we just gave shows
that $\set{4, 6}$ is a $7$-peak set.)

Find the \# of all $n$-peak sets (for our given $n$).

\subsection{Solution}

[...] % Enter your solution here!

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

\section{Exercise 2}

\subsection{Problem}

Let $n$ be an integer such that $n \geq 3$.
For each $k \in \ZZ$, set
\[
m_k
= \tup{ \text{\# of permutations $\sigma \in S_n$ such that
              $\ell\tup{\sigma} \equiv k \mod 3$} } .
\]

(\textit{Example:}
If $n = 3$, then $m_0$ counts the two permutations with
one-line notations $\tup{1, 2, 3}$ and $\tup{3, 2, 1}$,
while $m_1$ counts the two permutations with one-line
notations $\tup{1, 3, 2}$ and $\tup{2, 1, 3}$,
and while $m_2$ counts the two permutations with one-line
notations $\tup{2, 3, 1}$ and $\tup{3, 1, 2}$.)

Prove that $m_0 = m_1 = m_2 = n! / 3$.

[\textbf{Hint:} The Lehmer code (see \cite[\S 5.8]{detnotes}
or \cite[\S 0.4]{17f-hw8s}) may be of use.]

\subsection{Solution}

[...] % Enter your solution here!

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

\section{Exercise 3}

\subsection{Problem}

Let $n$ be an integer such that $n \geq 3$. Find
\[
\sum_{w \in S_n \text{ is even}} \abs{\Fix w} .
\]

[\textbf{Hint:} For each $i \in \ive{n}$, compare
\[
\tup{ \text{\# of even $w \in S_n$ such that $w\tup{i} = i$} }
\text{ with }
\tup{ \text{\# of odd $w \in S_n$ such that $w\tup{i} = i$} } .
\]
]

\subsection{Solution}

[...] % Enter your solution here!

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

\section{Exercise 4}

\subsection{Problem}

An $n$-tuple $\tup{i_1, i_2, \ldots, i_n} \in \set{0, 1}^n$
(where $n \in \NN$) will be called \textit{upsided} if
it satisfies $i_1 + i_2 + \cdots + i_p \geq p/2$ for each
$p \in \ive{n}$.

(\textit{Example:} The $3$-tuple $\tup{1, 0, 1}$ is
upsided (since $1 \geq 1/2$ and $1 + 0 \geq 2/2$
and $1 + 0 + 1 \geq 3/2$), and so is the $3$-tuple
$\tup{1, 1, 0}$ (for similar reasons),
but the $3$-tuples $\tup{1, 0, 0}$ and $\tup{0, 1, 1}$ are not
(indeed, $\tup{1, 0, 0}$ is not upsided because $1+0+0 < 3/2$,
whereas $\tup{0, 1, 1}$ is not upsided because $0 < 1/2$).
The $0$-tuple $\tup{}$ is upsided (for vacuous reasons).)

For given $n \in \NN$ and $k \in \ZZ$, let $U \tup{n, k}$
denote the \# of upsided $n$-tuples
$\tup{i_1, i_2, \ldots, i_n} \in \set{0, 1}^n$ satisfying
$i_1 + i_2 + \cdots + i_n = k$.

\begin{enumerate}

\item[\textbf{(a)}]
Prove that if $n \in \NN$ and $k \in \ZZ$ satisfy
$k < n/2$, then $U \tup{n, k} = 0$.

\item[\textbf{(b)}]
Prove that if $n \in \NN$ and $k \in \ZZ$ satisfy
$k \geq \tup{n-1} / 2$, then
\[
U \tup{n, k} = \dbinom{n}{k} - \dbinom{n}{k+1} .
\]

\item[\textbf{(c)}]
Prove that
$\dbinom{n}{0} < \dbinom{n}{1} < \cdots < \dbinom{n}{\floor{n/2}}$
for each $n \in \NN$.

\end{enumerate}

[\textbf{Hint:} Induction can be helpful. There are many ways to solve part
\textbf{(c)}, but the one using part \textbf{(b)} is perhaps the nicest.]

\subsection{Solution}

[...] % Enter your solution here!

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

\section{Exercise 5}

\subsection{Problem}

Let $n \in \NN$. Recall that a \textit{composition of $n$} means a
tuple $\tup{a_1, a_2, \ldots, a_k}$ of positive integers
satisfying $a_1 + a_2 + \cdots + a_k = n$. Such a composition
$\tup{a_1, a_2, \ldots, a_k}$ is called \textit{odd} if all of
$a_1, a_2, \ldots, a_k$ are odd.

Let us also say that a composition $\tup{a_1, a_2, \ldots, a_k}$
is \textit{odd-but-one} if $a_i$ is even for exactly one
$i \in \ive{k}$.
(For example, the composition $\tup{3,5,5}$ of $13$ is
odd; the composition $\tup{3,4,1,5}$ of $13$ is odd-but-one; the
composition $\tup{6,6,1}$ of $13$ is neither.)

Prove that
\begin{align*}
&  \sum_{\substack{\tup{a_1, a_2, \ldots, a_k}\text{ is an}\\
                   \text{odd composition of } n}} k\\
&  = \tup{ \text{\# of odd-but-one compositions of } n+1 } \\
&  = \dfrac{\tup{n+4} f_n + 2n f_{n-1}}{5},
\end{align*}
where $\tup{f_0, f_1, f_2, \ldots}$ is the Fibonacci sequence
(defined in \cite[Definition 1.1.10]{notes}).

\subsection{Solution}

[...] % Enter your solution here!

\begin{thebibliography}{99999999}                                                                                         %

% This is the bibliography: The list of papers/books/articles/blogs/...
% cited. The syntax is: "\bibitem[name]{tag}Reference",
% where "name" is the name that will appear in the compiled
% bibliography, and "tag" is the tag by which you will refer to
% the source in the TeX file. For example, the following source
% has name "Math222" (so you will see it referenced as
% "[Math222]" in the compiled PDF) and tag "notes" (so you
% can cite it by writing "\cite{notes}").

\bibitem[17f-hw8s]{17f-hw8s}Darij Grinberg, \textit{UMN Fall 2017 Math 4990
homework set \#8 with solutions}, \url{http://www.cip.ifi.lmu.de/~grinberg/t/17f/hw8os.pdf}
\\ Also available on the mirror server
\url{http://darijgrinberg.gitlab.io/t/17f/hw8os.pdf}

\bibitem[Grinbe15]{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}
\\ Also available on the mirror server
\url{http://darijgrinberg.gitlab.io/primes2015/sols.pdf}
\newline The
numbering of theorems and formulas in this link might shift when the project
gets updated; for a ``frozen'' version whose
numbering is guaranteed to match that in the citations above, see
\url{https://github.com/darijgr/detnotes/releases/tag/2019-01-10} .

\bibitem[Math222]{notes}
Darij Grinberg,
\textit{Enumerative Combinatorics: class notes},
16 December 2019. \\
\url{http://www.cip.ifi.lmu.de/~grinberg/t/19fco/n/n.pdf} 
Also available on the mirror server
\url{http://darijgrinberg.gitlab.io/t/19fco/n/n.pdf} \\
\textbf{Caution:}
The numbering of theorems and formulas in this link might shift when the
project gets updated; for a ``frozen'' version whose
numbering is guaranteed to match that in the citations above, see
\url{https://gitlab.com/darijgrinberg/darijgrinberg.gitlab.io/blob/2dab2743a181d5ba8fc145a661fd274bc37d03be/public/t/19fco/n/n.pdf}
% Check that this is the numbering you want.

\end{thebibliography}

\end{document}

