\magnification = \magstep1
\centerline{Mathematics 357 -- Combinatorics}
\centerline{Midterm Exam 2}
\centerline{April 15, 2005}
\bigskip
\noindent
{\it Directions}
\bigskip
Do the following problems I-V in the blue exam booklet.  
There are 100 regular points and 10 Extra Credit points.
\bigskip
\noindent
I.  
\item{A)} (10) {\it Define:}  a {\it derangement\/} of $X = \{1,2,\ldots, n\}$.
\item{A)} (15) Show that the {\it number\/} of derangements of $X$, $D_n$, satisfies  
$$D_n = n!\left(1 - {1\over 1!} + {1\over 2!} - {1 \over 3!} + \cdots
+ (-1)^n {1\over n!}\right).$$

\noindent
II.  
\item{A)} (10)  {\it Define:} the {\it rook polynomial\/} of a rectangular
board $B$ with each square shaded or unshaded.
\item{B)} (15)  Using rook polynomials, determine the number of 
permutations $abcde$ of the set $\{1,2,3,4,5\}$ such that
$a \notin \{2,3\}, b \notin \{1,2\},
           c \notin \{5\},
           d \notin \{4\},
           e \notin \{4,5\}$.
\bigskip           
\noindent
III.  A sequence $c_n$ is defined by the recurrence
$h_n = 3h_{n-1} - 2h_{n-2}$
and the initial conditions $h_0 = 1, h_1 = 3$.
\item{A)} (10)  Derive a general formula for the term $h_n$
as a function of $n$.  
\item{B)} (10)  Check your work in A by using the  
{\it generating function\/} method to solve the recurrence.
\bigskip
\noindent
IV.  
\item{A)} (10) Give a precise statement of  Hall's ``Marriage'' Theorem.
\item{B)} (10) A number $n$ of musicians are participating in a competition.
Each has been assigned $d$ different pieces of music to prepare, and 
no single piece has been assigned to more than $d$ different musicians.
Is it possible to compile a concert program on which each musician will
perform, and on which no piece will be performed twice?  Prove your assertion.
\bigskip
\noindent
V. (10) Show that in any graph $G = (V,E)$, there are an 
{\it even\/} number of vertices of odd degree (possibly 0 of them).  
\bigskip
\noindent
{\it Extra Credit}  
(10) A ``triominoe'' is a $1\times 3$ rectangle:
\bigskip
\noindent
For each positive integer $n$, let $t_n$ be the number of ways of
arranging $n$ triominoes in a $3\times n$ tray with no overlapping.
For instance, $t_3 = 2$, since we have the following two arrangements
\vglue 0.75truein
\noindent
Find a recurrence relation of order 3 for the $t_n$ sequence. 
({\it Don't try to solve it.})

\bye


