\documentclass[12pt]{amsart} 


% Call packages that allow you to invoke certain mathematical symbols.
\usepackage{amssymb,amsmath,amsthm}
\usepackage[margin=0.9in]{geometry}
\usepackage{cases}

% Set the title, author, and date information.


% Formally begin the document and make the title.

\begin{document}
\noindent \textbf{Math 315 - Fall 2017 \\
 Homework 4} \\
Due October 18, 2017 \vspace{-4mm}\\

\noindent \small \textit{Last time, I asked: ``What does mathematics mean to you?” And some people answered: “The manipulation of numbers, the manipulation of structures.'' And if I had asked what music means to you, would you have answered: ``The manipulation of notes?''
}\\\vspace{1mm} \hfill---
Serge Lang


\vspace{-5mm}
\normalsize
\noindent \hrulefill
\vspace{3mm}\\
\noindent \textbf{Turn in:} 

\vspace{5mm}

\bigskip

\begin{enumerate}
\item Find the number of permutations of length 6 who's square is the identity permutation. (What cycle types result in the identity when squared?)

\bigskip



\bigskip 

\item Let $\pi=p_1p_2\cdots p_n$ be a permutation of $n$ (in one line notation).  An inversion of $\pi$ is a pair $\{p_i,p_j\}$ so that $i<j$ but $p_i>p_j$.  Let us call a permutation \textit{odd} (respectively \textit{even}) of it has an odd (respectively even) number of inversions.  Prove that any permutation of length $n$ consisting entirely of one cycle is even if $n$ is odd and odd if $n$ is even.

\bigskip
\item Let $a(n,k)$ be the number of permutations of length $n$ with $k$ cycles in which the entries 1 and 2 are in the same cycle.  Prove that
for $n \ge 2$:
\[\sum_{k=1}^n a(n,k) x^k = x(x+2)(x+3) \cdots (x+n-1)\]

\bigskip

\item  A group of $n$ tourists arrive at a restaurant.  They sit down around an unspecified number of tables, leaving no table empty.  Then each table orders one of the $r$ possible drinks.  Prove that the number of ways this can happen is \[r^{(n)} = r(r+1)(r+2)\cdots(r+n-1)\]

\item Let $n\geq 6$ be even.  How many permutations $p_1p_2 \cdots p_n$ are there in which at least one of $p_1$, $p_2$ or $p_3$ is even?

\end{enumerate}

\end{document}
