\magnification=\magstep1
\centerline{Mathematics 357 -- Combinatorics}
\centerline{Review Sheet for Midterm Exam 2}
\centerline{April 8, 2005}
\bigskip
\noindent
{\it General Information}
\bigskip
As announced in the course syllabus and on the 
course homepage, the second midterm exam will be given
in class on Friday, April 15.  The exam will cover
the material we have studied since the first exam, 
through the material on general graphs from the start
of Chapter 11 from classes April 6 and 8. (This 
includes sections from Chapters 
6,7,9,11 in the text -- see detailed list of topics you are 
responsible for below).  {\it Important Note:} Much of this
material makes use of the basic counting techniques we learned
earlier.  So there may be parts of questions that
deal with material from the first exam too(!)  {\it Be prepared.}

This will be an individual, closed-book, 
closed-notes exam.  No collaboration of any kind will be permitted
during the exam period.  You {\it may} bring a calculator
if you want one; however, answers written terms of powers, 
factorials, binomial coefficients, etc.  can always be 
left in that form, so a calculator should be of truly 
minimal value for your work on the exam.  My advice: 
leave it home!

If there is interest, I would be happy to run a late
afternoon or evening review session next week to help
you prepare.  Wednesday evening after the $\pi\mu\epsilon$
induction and majors' dinner will be OK if that's
a good time for you.

\bigskip
\noindent
{\it Topics to be Covered}
\bigskip
\item{1)}  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{2)}  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{3)}  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{5)}  Chapter 11:  Terminology and basic concepts for
graphs and multigraphs (section 11.1 only on this exam).

\bigskip
\noindent
{\it Proofs to know}
\bigskip
\item{$\bullet$}  The proof of the formula 
$$D_n = n!\left(1 - {1\over 1!} + {1 \over 2!} + \cdots + {(-1)^n\over n!}\right)$$
for the derangement number $D_n$.  (See Theorem 6.3.1 in the text
and the class notes.)
\item{$\bullet$}  The proof of Hall's ``Marriage'' Theorem 
(as we did it in class, not the book's approach).  

\bigskip
\noindent
{\it Some Good Practice Problems}
\bigskip
\item{$\bullet$} Chapter 6/2, 8, 11, 14, questions like 24 (Suggestion:
make up your own $5\times 5$ or $6\times 6$ boards to practice and 
also compute the rook polynomials in addition to finding the 
number of placements of $n$ non-attacking rooks on the unshaded squares
via Theorem 6.4.1.), 26
\item{$\bullet$} Chapter 7/3, 5, 9, 14, 24, 27, 28, 29, 30 d,e, 34, 36 
\item{$\bullet$} Chapter 9/9, 12, 16, 27
\item{$\bullet$} Chapter 11/3,4,5,6,8
\bigskip
\noindent
Warning:  The above problems cover the ideas you will need to
understand in order to do the exam problems, but the exam
problems may be organized and formatted differently, may
draw on different types of examples, etc.  Be prepared!
\bye