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

\newcommand{\kgmcomment}[1]{}

\begin{document}
\headers{Math571}{Homework 1}{Due January 28, 2012}

%\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{}[CM 1.1.\{7,15\}] 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$.  Count the lists such that $A_0 \subseteq A_1 \subseteq \cdots \subseteq A_n$.
	\item Use binomial coefficients to prove that $n^3 + 5n$ is divisible by $6$ for every integer $n$.  \emph{Hint}: express $n^3 + 5n$ as the sum of binomial coefficients.
\end{enumerate}

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

\item{}[CM 1.1.19] Recall that $[3]^n = \{1,2,3\}^n = \{(a_1, \ldots, a_n)\st \mbox{$1\le a_i\le 3$ for each $i$}\}$.  Give a summation for the number of elements of $[3]^n$ with $k$ odd entries that have no consecutive $1$ and $3$.

\item{}[CM 1.1.28] For a permutation $\pi$ of $[n]$, the \textbf{displacement} of $\pi$ is $\sum_{i=1}^n |\pi(i)-i|$.  Prove that the largest displacement of a permutation of $[n]$ is $\floor{n^2/2}$.

\item{}[CM 1.1.31] A permutation is \textbf{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.  Evaluate $\sum_{i=1}^n |\pi(i)-\pi(i+1)|$ in two different ways, where all addition is modulo $n$ (including $\pi(n+1)=\pi(1)$).

\item{}[CM 1.1.34] Flags on poles.
\begin{enumerate}
\item Obtain a simple formula for the number of ways to put $m$ distinct flags on a row of $r$ flagpoles.  Poles may be empty, and changing the order of flags on a pole changes the arrangement.  The formula must only use one ``$m$'' and one ``$r$''.  (The answer is 6 for $m=r=2$, as shown below.)
\newcommand{\drawemptypole}
{
	\draw (0,0) -- (0, 5) ;
}
\newcommand{\drawoneflag}[1]
{
	\drawemptypole
	\node[draw,rectangle,anchor=south west,minimum width=0.95cm,minimum height=0.5cm] at (0, 1) {#1} ;
}
\newcommand{\drawtwoflags}[2]
{
	\drawoneflag{#1}
	\node[draw,rectangle,anchor=south west,minimum width=0.95cm,minimum height=0.5cm] at (0, 3) {#2} ;
}
\newcommand{\drawpairpoles}[2]
{
	\draw (-3,0) -- (5,0) ;
	\begin{scope}[shift={(-2,0)}]
		#1
	\end{scope}
	\begin{scope}[shift={(2,0)}]
		#2
	\end{scope}
}
\begin{center}
\begin{tikzpicture}[scale=0.40]
	\foreach \n/\leftfl/\rightfl in {
						1/\drawtwoflags{1}{2}/\drawemptypole,
						2/\drawtwoflags{2}{1}/\drawemptypole,
						3/\drawoneflag{1}/\drawoneflag{2}
					}
	{
		\begin{scope}[shift={(12*\n,0)}]
			\drawpairpoles{\leftfl}{\rightfl}
		\end{scope}
	}

	\begin{scope}[shift={(0,-7)}]
		\foreach \n/\leftfl/\rightfl in {
						1/\drawemptypole/\drawtwoflags{1}{2},
						2/\drawemptypole/\drawtwoflags{2}{1},
						3/\drawoneflag{2}/\drawoneflag{1}
					}
		{
			\begin{scope}[shift={(12*\n,0)}]
				\drawpairpoles{\leftfl}{\rightfl}
			\end{scope}
		}
	\end{scope}
\end{tikzpicture}
\end{center}
\item Prove that the identity below for rising factorials hods for all $x,y\in \R$.
\[ (x+y)^{(n)} = \sum_k \binom{n}{k}x^{(k)}y^{(n-k)} \]
\end{enumerate}

\end{enumerate}
\end{document}
