\magnification = \magstep1
\def\answer{\bigskip \item{} {\it Answer}:\ }
\def\solution{\bigskip \item{} {\it Solution}:\ }
\centerline{Mathematics 357 -- Combinatorics}
\centerline{Final Examination Answers and Solutions}
\centerline{May 13, 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?

\answer The derangement number $D_{2n}$.
\bigskip
\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?

\answer There are $D_n$ possible assignments of men's umbrellas
to men other than their owners, and similarly for the women.
Each combination of a derangement of the men's umbrellas together
with a derangement of the women's umbrellas is possible.
By the multiplication rule, the number here is $D_n\cdot D_n =D_n^2$.

\bigskip
\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?

\answer The men's umbrellas can be returned to the women
in $n\cdot (n-1)\cdots 2\cdot 1 = n!$ ways, and similarly
for the women's umbrellas.  By the multiplication rule again,
the number is $n! \cdot n! = (n!)^2$.

\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}$$

\solution (algebraic) By the binomial theorem,
$$\sum_{k=0}^n {n\choose k} x^k = (1 + x)^n$$
Differentiate both sides with respect to $x$ and substitute $x = 1$:
$$\eqalign{
\sum_{k=1}^n k {n\choose k} x^{k-1} &= n(1 + x)^{n-1}\cr
\Rightarrow
\sum_{k=1}^n k {n\choose k} &= n 2^{n-1},\cr}$$
which is what we had to show.

\solution (combinatorial)  Consider counting the number of
committees of sizes $1 \le k \le n$ with a chairperson, chosen
from a pool of $n$ people.  We can count this number in two
ways.  First, consider choosing the committee from the pool
and then choosing the chairperson from the membership.  This gives
the sum on the left hand side.  Second, choose the chairperson first
($n$ possibilities), then go through the $n-1$ remaining people one at
a time and decide whether each is on the committee or not.  This
gives $n2^{n-1}$ different committees with chairperson.

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

\answer The number is the number of permutations of 
$15$ things $8$ at a time $P(15,8) = {15!\over 7!}$.

\bigskip
\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?

\answer The correct way to make this count is to think of the
different breakdowns of how many questions can come from each
part of the review sheet.  There are six possibilities:
$(4,2,2),(2,4,2),(2,2,4),(3,3,2),(3,2,3),(2,3,3)$.  Hence the number
of exams is:
$$3\cdot {5\choose 4}{5\choose 2}{5\choose 2} + 3\cdot {5\choose 3}{5\choose 3}{5\choose 2}$$
Note:  The tempting answer ${5\choose 2}{5\choose 2}{5\choose 2}{9\choose 2}$
is {\it not correct} because it multiple counts. You get the same collection
of 8 questions multiple times because the same 4 questions from part I,
for instance, could be broken down in different ways as coming from 
the fixed 2 from part I and questions from the remaining 9.
Another common mistake here was to try to do this count
using our formulas for multisets.  That is {\it not correct}
because it treats the exam questions as
{\it interchangeable}.  That is certainly not the case for 
the situation here.

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

\answer Same as in part B.

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

\answer The generating function for the number of ways to distribute
the pencils is 
$$(t^{20} + t^{40} + \cdots )^4 = {t^{80}\over (1 - t^{20})^4}$$
We want to determine the coefficient of $t^{180}$ in the
expanded form.
To simplify, write $u = t^{20}$.  Then we want the coefficient 
of $u^9$ in ${u^4\over (1 - u)^4}$, or equivalently, the 
coefficient of $u^5$ in ${1\over (1 - u)^4}$.  By one of our
standard series identities, we know:
$${1\over (1 - u)^4} = \sum_{k=0}^\infty {k + 3\choose 3} u^k$$
So the coefficient of $u^5$ is ${8 \choose 3} = 56$.

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

\answer The generating function is 
$$H(t) = {3 - 17t \over (1 - 2t)(1-4t)}$$
\bigskip
\item{B)} (15)  Derive a general formula for the term $h_n$
as a function of $n$.  

\answer Applying the partial fraction decomposition to our
answer in part A, we find
$$H(t) =  {3 - 17t \over (1 - 2t)(1-4t)} = {{11\over 2}\over 1 - 2t} + {{-5\over 2}\over 1-4t}$$
Expanding in geometric series, we get
$$H(t) = \sum_{n=0}^\infty {11\over 2} 2^n t^n +  \sum_{n=0}^\infty {-5\over 2} 4^n t^n$$
Collecting powers of $t$, we see
$$H(t) = \sum_{n=0}^\infty \left({11\over 2} 2^n - {5\over 2} 4^n\right)t^n,$$
so 
$$h_n = {11\over 2} 2^n - {5\over 2} 4^n.$$
\bigskip 
\noindent
VI.  
\item{A)} (5)  {\it Define:} the {\it rook polynomial\/} of a rectangular
board $B$ with each square shaded or unshaded.

\answer The rook polynomial is
$$R(B,t) = \sum_{k=0}^{\min(m,n)} r_k(B) t^k,$$
where $r_k(B)$ is the number of placing $k$ non-attacking rooks
on the unshaded squares in $B$.

\bigskip
\item{B)} (5)  Explain why the coefficient of $t^6$ in 
the rook polynomial of any $5\times 7$ board $B$ must be zero.

\answer By the Pigeonhole Principle, if we had $6$ rooks on $B$,
then two of them would have to be in the same row.  That means
they are attacking.  Hence $r_6(B) = 0$ (and the same is true for
$r_k(B)$ for all $k \ge 6$).  

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

\answer $R(B,t) = 1 + 8t + 20t^2 + 16t^3 + 4t^4$.  This can
be derived in many different ways.  Probably the most economical
is to note that in computing $R(B,t)$, we can permute the 
rows and columns of $B$ any way we like.  The reason is that 
permuting rows and columns does not affect whether rooks can attack
each other or not.  If we apply this observation here, interchanging
rows 2 and 3, then columns 2 and 3 yields a board $B'$ with
$2\times 2$ blocks of unshaded squares in the upper right and lower left.
Hence by the product rule $R(B,t) = (1 + 4t + 2t^2)^2$, which 
gives the above when we expand(!)
\bigskip
\noindent
VII.
\item{A)} (10)  State Hall's ``marriage'' theorem.

\answer Let ${\cal A} = (A_1,\ldots,A_n)$ be a family of 
sets.  Then an SDR for the family exists if and only if 
``marriage condition'' is 
satisfied: for
all $I \subset \{1,\ldots,n\}$, 
$$\left|\bigcup_{i\in I} A_i\right| \ge |I|.$$

\bigskip
\item{B)} (15)  Use Hall's theorem to show that if $G = (X,E,Y)$
is a bipartite graph with $|X| = |Y| = n$, in which 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$.) 

\answer  By the condition that all vertices of $G$ have degree $d$,
the matrix described in the hint is an $n\times n$ (0,1)-matrix
with row and column sums all equal to $d$.  So, this is a restatement 
of the problem we did before
about writing $(0,1)$-matrices with constant row and column sum
$d$ as sums of $d$ permutation matrices. 

\bigskip
\item{} Recall, the proof goes as follows.  For each $i$, $1 \le i \le n$, 
let $A_i = \{j : m_{ij} \ne 0\}$, or what is the same, $A_i$
is the set of vertices $y_j$ in $Y$ such that there is an edge
from vertex $x_i$ to $y_j$.  We claim that the family 
${\cal A} = (A_1,\ldots,A_n)$ satisfies the ``marriage condition'':
$|\cup_{i\in I} A_i| \ge |I|$ for all $I \subset \{1,\ldots,n\}$. 
We argue by contradiction.  If not, then for some $I$, the 
entries in the rows of $M$ indexed by $I$ have sum $d|I|$, but
the nonzero entries occur in some number $k < |I|$ columns.  This is
a contradiction since {\it all of} the entries in $k$ columns of $M$
sum to $d k$, so this would say $d|I| \le d k$, but $k < |I|$, which
is absurd.  Hence the marriage condition is satisfied for the 
family ${\cal A}$.  This shows that there is an SDR.  In matrix
terms this means that there is a permutation matrix $P$ such that
$M = P + M'$ where $M'$ is another $(0,1)$-matrix with rows and 
columns summing to $d - 1$.  Hence we are done by induction {\it on d}.
In the base case, $d = 1$, and $M = P$ is a permutation matrix.  

\bigskip
\item{} Now note that the 1's in one of the permutation matrices adding
up to $M$ correspond to a matching from $X$ to $Y$ in the graph.
Hence we have partitioned the edges in $G$ into $d$ disjoint
matchings.

\bigskip
\noindent
VIII. 
\item{A)} (15) State and prove Burnside's Theorem for group 
actions.

\answer See class notes.

\bigskip
\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?

\answer The number is the number of orbits for the action of the
symmetry group
$$G = D_3 = \{I,\rho,\rho^2,\tau_1,\tau_2,\tau_3\}$$
on the set $X$ of colorings of the vertices.  We
have 
$$n = {1\over |D_3|} \sum_{g\in D_3} |{\rm Fix}(g)| = {1\over 6} (p^3 + 2p + 3p^2).$$
\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 7\} \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$.

\answer This follows immediately from the basic form of the 
Pigeonhole Principle (``pigeonholes'' $=$ the 7 different 
vertical lines, ``pigeons'' $=$ the 8 points).

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

\answer This follows immediately from the strong form of the 
Pigeonhole Principle (``pigeonholes'' $=$ the 7 different 
vertical lines, ``pigeons'' $=$ the 15 points).  Since $15 = 2\cdot 7 + 1$,
some pigeonhole must get at least 3 pigeons.

\bigskip
\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?

\answer No.  There are too many vertices of odd degree (note
that all $4\cdot 5 = 20$ of the edge vertices other than the 
4 corners have degree $3$).  Recall that Euler trails exist
only when the number of odd degree vertices is 0 or 2.
\bye



