\magnification = \magstep1
\centerline{Mathematics 190 -- Advanced Topics: Combinatorics}
\centerline{Final Examination}
\centerline{May 6, 1996}
\bigskip
\noindent
{\bf Directions}
\bigskip
This exam consists of problems I - VIII and {\it either IX or IX'}.
If you submit solutions for both IX and IX', 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
I.  (20)  Using a ``choice'' argument (or otherwise)
show that for all $n \ge 1$, 
$${n \choose 1} + 2{n\choose 2} + \cdots + n{n \choose n} = n 2^{n-1}$$
(Hint: One way is to consider choosing a committee with a chairperson, 
making the choice in two different ways.)
\bigskip
\noindent
II. 
\item{A)} (10) State {\it Cayley's Theorem\/} on trees.
\item{B)} (10) How many different trees with vertex set $\{1,2,3,4,5,6\}$
and structure:
\vglue 0.75truein
\item{} are there?
\bigskip
\noindent
III.  
\item{A)} (5) {\it Define\/}:  Latin rectangle, Latin square.
\item{B)} (10)  State the transversal form of Hall's ``marriage'' theorem.
\item{C)} (10)  Using Hall's theorem, show that if $k < n$, 
every $k \times n$ Latin rectangle with entries in $\{1,2, \cdots, n\}$
can be extended in at least one way to an $n\times n$ Latin square.
\bigskip
\noindent
IV.  (20)  Two hundred folding chairs are to be divided into four
lots and placed in conference rooms A, B, C, D of a convention center.
Each room is to receive {\it at least 20\/} chairs, and the number
of chairs in each room is to be {\it a multiple of 20\/}.  How
many different ways are there to allot the chairs to the four rooms?
(Hint: One approach uses generating functions.)
\bigskip
\noindent
V.  A sequence $c_n$ is defined by the recurrence
$$c_n = 3c_{n-1} - 2c_{n-2}$$
and the initial terms $c_0 = 1, c_1 = 2$.
\item{A)} (10)  Express the 
{\it generating function\/} of the sequence as a rational function
of $x$. 
\item{B)} (10)  Derive a general formula for the term $c_n$
as a function of $n$.  
\bigskip 
\noindent
VI.
\item{A)} (10) {\it Define:\/} the (vertex) {\it chromatic
polynomial\/} of a graph $G = (V,E)$.
\item{B)} (15) Show by induction on $n$ that the graph $G$ shown below:
\vglue 1.0truein
with $2n$ vertices, has chromatic polynomial
$$p_G(\ell) = \ell(\ell - 1)(\ell^2 - 3\ell + 3)^{n-1}$$
\item{} (Hint:  consider the possible colorings of the vertices of the last
edge on the right, taking into account the coloring of the rest of the 
graph.  NOTE: this is {\it not\/} a case where the recurrence 
relation will help you very much!)
\bigskip
\noindent
VII.  
\item{A)} (10)  {\it Define:} the {\it rook polynomial\/} of a rectangular
board $B$ with each square colored either black or white.
\item{B)} (15)  Using rook polynomials, determine the number of 
orderings $a,b,c,d,e$ of the set $\{1,2,3,4,5\}$ such that
$$\eqalign{a &\notin \{2,3,5\}\cr
           b &\notin \{1,2,5\}\cr
           c &\notin \{1,4,5\}\cr
           d &\notin \{2,3,4\}\cr
           e &\notin \{1,3,4,5\}\cr}$$
\bigskip
\noindent
VIII. 
\item{A)} (10)  State {\it Landau's Theorem\/} on tournaments.
\item{B)} (10) In a tournament of $n$ players, how many different
sets of results are there so that no two players have the same score?
\bigskip
\noindent
Do either problem IX or problem IX' below.
\bigskip
\noindent
IX.  A {\it derangement\/} of $A_n = \{1,2,\ldots, n\}$ is a permutation
$f : A_n \to A_n$ such that $f(i) \ne i$ for all $i \in A_n$.
\item{A)} (10) Show that the {\it number\/} of derangements of $A_n$, 
which we will call $D_n$, satisfies the recurrence relation:
$$D_n = (n-1)(D_{n-1} + D_{n-2})$$
\item{B)}  (15)  Using part A and induction on $n$ show that
$$D_n = n!\left(1 - {1\over 1!} + {1\over 2!} - {1 \over 3!} + \cdots
+ (-1)^n {1\over n!}\right)$$
\bigskip
\noindent
IX'.  
\item{A)} (10)  Show that if a $b\times v$ $(0,1)$-matrix $M$ is 
the incidence matrix of a $(v,b,r,k,\lambda)$-design then
$M^tM = (r-\lambda)I + \lambda J$, where $I$ is 
the $v \times v$ identity matrix, and $J$ is the $v\times v$
matrix all of whose entries are 1's.
\item{B)} (5) Let $G = (V,E)$ be a graph.  An incidence matrix 
for $G$ is obtained by first fixing some particular orderings of the 
edge and vertex sets, then forming the $|E| \times |V|$ $(0,1)$-matrix
$M$ with 
$$M_{ij} = \cases{1 & if vertex $j$ is one of the endpoints of edge $i$\cr
                  0 & otherwise\cr}$$
What is the incidence matrix of the following graph:
\vglue 1.0truein
\item{C)}  (10) Show that the incidence matrix of a graph $G$ 
with $v$ vertices gives the incidence
matrix for a design if and only if $G = K_v$ is the
{\it complete graph\/} on $v$ vertices.

 \bigskip
\centerline{\it Have a productive, safe, and enjoyable summer!}
\bye