\magnification = \magstep1
\centerline{Mathematics 357 -- Combinatorics}
\centerline{Final Examination}
\centerline{May 12, 2005}
\bigskip
\noindent
{\it Directions}
\bigskip
This exam consists of problems I - VII and {\it either VIII or VIII'}.
If you submit solutions for both VIII and VIII', I will count one as 
extra credit.
Do all your work in the blue exam booklet. There are 200 possible points.
Good hunting!
\bigskip
\noindent
\bigskip
\noindent
I.  $n$ men and $n$ women attend a wedding reception
on a rainy day and check their coats and umbrellas.
When the reception is over, they retrieve the umbrellas,
but ({\it gasp}!) things have gotten {\it mixed up} at the coat check stand.
\bigskip
\item{A)}  (5) In how many different ways is it possible
for none of the people to get his or her own umbrella back?
\item{B)} (10)  In how many different ways is it possible
for none of the men to get his own umbrella back
and none of the women to get her own umbrella back, but for
each man's umbrella to go to another man, and each woman's 
umbrella to go to another woman?
\item{C)} (10)  In how many different ways is it possible
for all of the men to get women's umbrellas back, and 
all of the women to get men's umbrellas back?
\bigskip
\noindent
II.  (25)  Using a combinatorial or algebraic proof, as you prefer,
show that for all $n \ge 1$, 
$${n \choose 1} + 2{n\choose 2} + \cdots + n{n \choose n} = n 2^{n-1}$$
\bigskip
\noindent
III.  A professor makes up a review sheet for an exam 
including 15 practice questions, subdivided
into parts I,II,III, each with 5 questions.  The actual exam 
will consist of exactly 8 of the 15 practice questions.
\bigskip
\item{A)} (5)  Taking the ordering of the exam problems
into account, how many different possible exams are there?
\item{B)} (10) How many possible exams are there
containing at least two questions from each part, if we 
ignore the order in which the problems are listed?
\item{C)}  (10) How many possible exams are there
using between two and four questions from each of the
three parts?  Again, ignore the ordering of the questions
on the exam.
\bigskip
\noindent
IV.  (25)  Use an appropriate {\it generating
function} to answer the following question: 180 pencils are divided into four
lots of sizes $n_1,n_2,n_3,n_4$
and placed in 4 different classrooms where students
are taking a standardized exam.
Each room receives {\it at least 20\/} pencils, and the number
of pencils for each room is to be {\it a multiple of 20\/}.  
How many different vectors $(n_1,n_2,n_3,n_4)$ of numbers
of pencils satisfy these conditions?
\vfill\eject
\noindent
V.  A sequence $h_n$ is defined by the recurrence
$$h_n = 6h_{n-1} - 8h_{n-2}$$
and the initial terms $h_0 = 3, h_1 = 1$.
\item{A)} (10)  Express the 
{\it generating function\/} of the sequence as a rational function
of $t$. 
\item{B)} (15)  Derive a general formula for the term $h_n$
as a function of $n$.  
\bigskip 
\noindent
VI.  
\item{A)} (5)  {\it Define:} the {\it rook polynomial\/} of a rectangular
board $B$ with each square shaded or unshaded.
\item{B)} (5)  Explain why the coefficient of $t^6$ in 
the rook polynomial of any $5\times 7$ board $B$ must be zero.
\item{C)} (15)  Determine the rook polynomial of a $4\times 4$
board in which the shaded and unshaded squares alternate in
each row and each column, starting from a shaded square in the 
upper left corner. 
\bigskip
\noindent
VII.
\item{A)} (10)  State Hall's ``marriage'' theorem.
\item{B)} (15)  Use Hall's theorem to show that if $G = (X,E,Y)$
is a bipartite graph, in which $|X| = |Y|$ and all vertices
have degree $d\ge 1$, then the edges of $G$ can be partitioned into 
$d$ disjoint matchings.  (Hint: It may help 
to think of the $(0,1)-$matrix $M$ where $m_{ij} = 1$ if and only if
there is an edge from $x_i\in X$ to $y_j \in Y$.) 
\bigskip
\noindent
VIII. 
\item{A)} (15) State and prove Burnside's Theorem for group 
actions.
\item{B)} (10) The corners of an equilateral triangle are
colored with $p$ different colors.  How many different colorings
are there, up to symmetries of the triangle?
\bigskip
\noindent
\bigskip
\noindent
VIII'.  Consider the rectangular $7\times 7$ grid $L$ of integer
lattice points:
$$L = \{(i,j) : 0 \le i \le 6, 0 \le j \le 6\} \subset {\bf R}^2.$$
\bigskip
\item{A)} (5) Show that if we have a subset $S\subset L$ with
$|S| = 8$, then there are two points in $S$ on the same 
vertical line $x = c$.
\item{B)} (10)  Show that if we have $S \subset L$ with
$|S| = 15$, then some three  points in $S$ lie
on the same vertical line $x = c$.  
\item{C)} (10)  Consider the points in $L$ and the vertical and 
horizontal line
segments joining them as a graph.  Does this graph have
an Euler trail?  Why or why not?
\bigskip
\centerline{\it Have a productive, safe, and enjoyable summer!}
\bye



