\documentclass[11pt]{article}
\usepackage{jeffe,handout,multicol,tikz,kgm}

\newcommand{\kgmcomment}[1]{}

\begin{document}
\headers{Math571}{Homework 1}{Due Fri Feb 7, 2025}

%\makeatletter
%\def\@oddfoot{\hfill \tikz \node[draw] {over} ; }
%\makeatother

\makeatletter
\def\@oddfoot{}
\makeatother

\noindent
\textbf{Directions:} Solve 5 of the following 6 problems.  See the course syllabus and the Homework Webpage on the course website for general directions and guidelines that apply to all homeworks.

\begin{enumerate}

\item \emph{Counting}
\begin{enumerate}
	\item How many ways can the letters in ``MISSISSIPPI'' be ordered?  (Hint: relate this to the number of ways to arrange $MI_1S_1S_2I_2S_3S_4I_3P_1P_2I_4$, where for example $I_2$ and $I_3$ are distinct symbols.)
	\item Find the probability that six cards randomly drawn from a standard deck of cards have at least one card in every suit.
\end{enumerate}

\item The \emph{chords} of a convex $n$-gon are the segments that join two corners.  Count the pairs of chords that cross inside the $n$-gon.

\item Recall that $[n] = \{1,2,\ldots,n\}$.
\begin{enumerate}
	\item Count the subsets of $[n]$ that contain at least one odd integer.
	\item Count the $k$-sets in $[n]$ having no two consecutive integers.
	\item Count the lists of subsets $A_0$, $A_1, \ldots, A_n$ of $[n]$ such that $A_0 \subsetneq A_1 \subsetneq \cdots \subsetneq A_n$.  
	\item Count the lists such that $A_0 \subseteq A_1 \subseteq \cdots \subseteq A_n$.
\end{enumerate}

\item{} Count the lists of $m$ ones and $n$ zeros that have exactly $k$ runs of ones, where a \emph{run} is a maximal set of consecutive entries with the same value.

\item{} A permutation is \emph{graceful} if the absolute differences between successive elements are distinct.  Prove that if the set of elements in even-indexed positions of a graceful permutation of $[2n]$ is $[n]$, then the first and last elements differ by $n$.  (\emph{Hint}: Let $\pi$ be a graceful permutation of $[2n]$ such that $\pi(i)\le n$ if and only if $i$ is even, and evaluate $|\pi(2n) - \pi(1)| + \sum_{i=1}^{2n-1} |\pi(i)-\pi(i+1)|$ in two different ways).

\item {} The \emph{displacement} of a permutation $\pi$ of $[n]$ is $\sum_{i=1}^n |\pi(i)-i|$.  Note that the displacement of $\pi$ is zero if and only if $\pi$ is the identity permutation.
\begin{enumerate}
	\item For each $n$, give an example of a permutation of $[n]$ with displacement $\floor{n^2/2}$.
	\item Let $\pi$ be a permutation of $[n]$, let $S=\{(i,\pi(i))\st i\in [n]\}$, let $A=\{(x,y)\in S\st y\ge x\}$, and let $B=\{(x,y)\in S\st y<x\}$.  (Think of $A$ as the set of points in the graph of $\pi$ on or above the line $y=x$ and $B$ as the set of points in the graph of $\pi$ below the line $y=x$.)  Prove that if $\pi$ is a permutation with maximum displacement, $(x,y) \in A$, and $(x',y')\in B$, then $x<x'$ and $y>y'$.
	\item Use part (b) to show that every permutation of $[n]$ has displacement at most $\floor{n^2/2}$.
	\item For even $n$, count the number of permutations of $[n]$ that have maximum displacement.  (Remark: the analysis above also makes it possible to count the maximum displacement permutations for general $n$, but the computation is not as nice when $n$ is odd.)
\end{enumerate}

\end{enumerate}
\end{document}
