\magnification = \magstep1
\overfullrule=0pt
\centerline{Mathematics 357 -- Combinatorics}
\centerline{Information on Final Exam}
\centerline{April 26, 1996}
\bigskip
\noindent
{\it Background}
\bigskip
The final exam for Combinatorics
will be given as an in-class individual exam at our scheduled
time, 8:30 a.m. on Thursday, May 12.  The exam will be comprehensive,
covering all the material we have studied since the beginning of the 
semester.  I will write the exam to be twice the length of the 
in-class midterms.  However, you will have the full three-hour
period 8:30 - 11:30 a.m. to work on the exam if you need that much time.
The questions will be similar to those on midterms. I will include some 
questions asking for definitions of terms and statements of theorems, as 
well as some problems where you will need to apply the ideas to derive a 
result or prove an assertion.
\bigskip
\noindent
{\it Reading Week Schedule and Review Session}
\bigskip
I will be out of town (visiting Oberlin College as their mathematics department's
External Honors Examiner) from about 2:00 pm on Wednesday, May 4 through
the end of the day on Friday, May 6.  I may be able to check email,
but I'm not going to have much if any open time while I'm at Oberlin.  If there 
is interest, I would be happy to run a review session Monday May 9 or Tuesday
May 10 during the exam week. On Wednesday evening, I have another commitment off
campus so I will not be available.
 \bigskip
\noindent
{\it Topics to be Covered}
\bigskip
\item{1)}  Chapter 2:  The Pigeonhole Principle (basic and strong forms), 
applications.
\item{2)}  Chapters 3 and 4:  Basic counting principles, permutations and
combinations of sets, permutations and combinations of 
multisets.  Methods for generating combinations systematically.  (Note -- we
only discussed a portion of the material in Chapter 4, and
you're only responsible for the stuff from sections 3 and 4 that
we did cover.)
\item{3)}  Chapter 5:  Binomial coefficients, identities, algebraic
and combinatorial proofs, applications to counting problems.  (Omit the material
in sections 4 and 7 of this chapter.)
\item{4)}  Chapter 6:  Inclusion-Exclusion Principle in the ``union''
and ``complement of union'' forms.  Applications to counting
combinations with repetition, derangements, permutations with
forbidden positions (``rook placement'' problems).  Also know
how to compute and use rook polynomials for these counting
problems, including the product and expansion rules.  (Omit section 6.6.) 
\item{5)}  Chapter 7: Number sequences, recurrences, solving homogeneous
and nonhomogeneous linear recurrences with constant coefficients.
Generating functions, and the generating function technique for solving
recurrences.  (Omit section 7.7)
\item{6)}  Chapter 9:  Hall's ``Marriage Theorem'', matchings in 
bipartite graphs, applications.  (Note: you are only responsible
for the topics here we covered in class.  There's actually a lot more
in Chapter 9 than we looked at, and it's presented differently in 
some cases.  So my advice is:  {\it use the class notes!})
\item{7)}  Chapter 11:  Terminology and basic concepts for
graphs and multigraphs.  Euler trails.  Hamilton cycles.  Trees
and Cayley's Theorem.
\item{8)} Chapter 14:  Counting with symmetry, group actions, Burnside's
Theorem (know the statement, the proof, and how to apply it).  
\bigskip
\noindent
{\it Suggestion on How to Study}
\bigskip
Begin by reviewing the class notes, your graded problem sets and the solutions
 and the discussion write-ups from 
your group's work.  Look at the in-class midterm problems and try to 
work out solutions for those again, without refering to your previous
work.  Look over some of the problems from the text and try some
new ones that look interesting.  Also try the practice/review problems below.
\bigskip
\noindent
{\it Practice/Review Problems}
\bigskip
\noindent
{\it Also see review sheets for Exams 1 and 2}
\bigskip
\item{A)}  A golfer has 11 weeks to prepare for the Masters golf tournament.
He decides to play at least one round of 18 holes of golf each day, but so 
as not to tire himself, he will play no more than 12 rounds in any calendar week.
Show that there is a string of consecutive days in which he plays exactly 21
rounds.  (Hint: Pigeonhole.)
\item{B)}  How many distinct words of length $7$ can be formed from the alphabet
${0,1,2}$?  How many containing exactly 4 2's? How many with no more than 4 2's?
How many with equal numbers of 0's and 1's?
\item{C)}  How many distinct ``monomials'' $x_1^{a_1}x_2^{a_2} \cdots x_k^{a_k}$
are there of ``total degree'' $a_1 + \cdots + a_k = n$?  (Here the $x_i$ are commuting
variables and $a_i \ge 0$ are 
integers.)  How many monomials are there that are divisible by $x_1^3$ (assuming
the total degree is at least $3$)?
How many monomials are there which are divisible by $x_i$ 
for all $1 \le i \le k$? 
\item{D)} Let $n\ge r \ge m$ be natural numbers.
 Use a ``choice'' argument to prove the binomial coefficient identity:
$${n-m\choose r-m} = \sum_{k=0}^{m} (-1)^k {m\choose k}{n-k \choose r}$$
(Hint:  The left hand side is the number of ways to choose $r$ objects from 
a collection of $n$,
always including some particular subset of $m$ ``special'' objects in the $r$ --
for instance, committees with {\it ex officio\/} members.)
\item{E)}  Show that the number $D_n$ of derangements of $\{1,2,\ldots,n\}$
satisfies the recurrence $D_n = nD_{n-1} + (-1)^n$.  Deduce from this that
$D_n$ is even if and only if $n$ is odd.
\item{F)}  Use generating functions to show that the number of partitions
of any positive integer $n$ with {\it distinct parts} is the same as the
number of partitions of $n$ with {\it all odd parts}.
\item{G)}  Find (some formula for) the term $a_{50}$ in the sequence
with generating function
$$f(t) = {1 - t\over 1 - 2t + 3t^2} = a_0 + a_1 t + \cdots + a_{50} t^{50} + \cdots$$
\item{H)}  Fix some numbering of the vertices and edges of a graph $G = (V,E)$.
The {\it incidence matrix} of $G$ is the 
$|V| \times |E|$ (0,1)-matrix $M$ with $M_{ij}=1$ if vertex $i$ is one of the 
endpoints of edge $j$ and $M_{ij}=0$ if not.  Give a general statement (valid
for all graphs) describing the form of the $|V| \times |V|$
matrix $M M^t$ (for instance, what are the diagonal entries, what are the 
off-diagonal entries?)
\itemitem{1)}  Show that if $G$ is not a tree, the rows of the incidence matrix  
are linearly dependent mod 2.  (The converse also holds; can you prove it?)
\item{I)}    How many distinct
labeled trees of order 7 are there with degrees 
$$d_1 = 2, d_2 = 1, d_3 = 1, d_4 = 4, d_5 = 2, d_6 = 1, d_7 = 1?$$
What if we changed $d_3$ to $3$ and kept the other degrees the same?
State and prove Cayley's Theorem on trees.
\item{J)}  State and prove Burnside's Theorem.
\item{K)}  From the text: Chapter 14/10 and 22, 17, 18, 31
\bye  


