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

\newcommand{\kgmcomment}[1]{}

\begin{document}
\headers{Math571}{Homework 5}{Due April 15, 2013}

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

%\newcommand{\seq}[1]{\left\langle #1\right\rangle}

\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.

\begin{enumerate}

\item{} [CM 3.1.21] Let $A(x)$ be the generating function for the sequence $\seq{\hat F}$ of adjusted Fibonacci numbers.
\begin{enumerate}
\item Obtain $A(x)$ from the Fibonacci recurrence.
\item Obtain $A(x)$ by building it combinatorially (without the recurrence), using the model that $\hat F_n$ is the number of $1,2$-lists with sum $n$.
\item Expand the generating function to prove that $\hat F_n = \sum_{k=0}^n \binom{k}{n-k}$.
\end{enumerate}

\item{} [CM 3.1.28] The keys to $n$ boxes are put randomly in the boxes, one per box.  The boxes are locked by closing them (a box may contain its own key).  Determine the probability that breaking open $k$ random boxes will allow unlocking the remaining boxes.  (Hint: consider canonical cycle representations.)

\item{} [CM 4.1.\{19,20\}] Applications of PIE.
\begin{enumerate}
	\item A mathematics department has $n$ professors and $2n$ courses; each professor teaches two courses each semester.  How many ways are there to assign the courses in the fall semester?  How many ways are there to assign them in the spring so that no professor teaches the same two courses in the spring as in the fall?  (Your answer for the spring semester may be a summation.)
	\item At a circular table are $n$ students taking an exam.  The exam has four versions.  Given that no two neighboring students have the same version, how many ways are there to assign the exams?  Do not leave the answer as a sum.
\end{enumerate}

\item{} [CM 4.1.31] For $n\in \N$, give a combinatorial proof (via inclusion-exclusion) for the identity below.
\[ \sum_{k=0}^n (-1)^k \binom{n}{k} \binom{2n-2k}{n-1} = 0 \]

\item{} [CM 10.1.14] Let $f(n)$ be the least $k$ such that every set of $k$ elements in $[n]$ has two disjoint subsets with the same sum.  Prove that $1 + \floor{\lg n} < f(n) \le \ceil{1 + \lg n + \lg \lg n}$ for sufficiently large $n$.  (Here, $\lg n = \log_2 n$.)  (Hint: for the upper bound, show that if $2^k > nk + 1$, then $f(n) \le k$.)

\item{} [CM 10.1.32] A function $f\st [n]\to [n]$ is \textbf{contractive} if $f(i) \le i$ for all $i$.  A \textbf{monotone $k$-list} for $f$ is a strictly increasing list $a_1, \ldots, a_k$ from $[n]$ such that $f(a_1) \le \cdots \le f(a_k)$.  Prove that $2^{k-1}$ is the least $n$ such that for every contractive mapping on $[n]$ there is a monotone $k$-list.  (Note: there are 2 things to prove.  First, you must provide an example of a contractive function $f\st [n]\to[n]$ for $n=2^{k-1}-1$ that has no monotone $k$-list.  Next, you must show that every contractive function $f\st [n]\to[n]$ with $n\ge 2^{k-1}$ has a monotone $k$-list.) (Hint: For how many $a$ in $[n]$ can the longest monotone list ending with $a$ have $j$ elements?)
\end{enumerate}
\end{document}
