\magnification=\magstep1
\centerline{MATH 357 -- Combinatorics}
\centerline{Review Sheet for Final Exam}
\centerline{May 1, 2017}
\bigskip
\noindent
{\it General Information and Groundrules}
\bigskip
The final exam in Combinatorics this semester (for those not doing a final
project) will be given at the announced time for MWF 11am classes -- Friday, May 12
at 11:30am in Swords 302.  This will be a closed-book, 
individual exam.  No use of phones, I-pods, tablets, or any other electronic devices
beyond a calculator will be allowed during the exam -- turn them off
and stow them in your backpack. 
\bigskip
\noindent
{\it What might be covered}
\bigskip
The exam will be comprehensive -- it will cover all of the material we have discussed
from Chapters 1 - 8 of Beeler.  I will write the exam so that it should take
about 100 minutes (twice the regular class hour) to complete if you are well-prepared
and work steadily.  However, you will have the full 150 minutes (11:30am - 2:00pm) to work on the exam
if you need the time.  In addition, there might be a question
dealing with material from some of the final project presentations.  The set-up
will be similar to the midterms; you will have the choice to omit some questions
and still earn 100 out of 100 points.  
\bigskip
\noindent
Specifically the topics are:
\bigskip
\item{1)} Mathematical sets, unions, intersections, functions, etc.
\item{2)} The Multiplication and Addition Principles
\item{3)} The Pigeonhole Principle (basic and generalized versions)
\item{4)} Permutations, cycle decompositions, counting permutations by cycle type or
cycle index, the Stirling numbers of the first kind (Know the proof of the recurrence
relation $s(n+1,k) = n s(n,k) + s(n, k-1)$.)
\item{5)} Legendre's theorem on divisiblity of $n!$ by a primes $p$.  
\item{6)} Numbers of permutations $P(n,k)$ and binomial coefficients ${n \choose k}$ and
the counting problems they solve.
\item{7)} Poker hands and related counting problems
\item{8)} Binomial coefficient identities -- know algebraic and combinatorial proofs of the 
``Vandermonde convolution identity'' 
identity (Theorem 3.4.4)
$${n + m\choose k} = \sum_{i=0}^k {n \choose i} {m \choose k - i}.$$  
\item{9)}  Multinomial coefficients.
\item{10)} The different categories of distribution problems and the counting
techniques needed for them.  This is basically the material appearing in Table 4.6 on page
109 of Beeler.  You should know the formulas in the first two columns there
and be able to analyze a problem to determine which one applies.  Note that this includes
\bigskip
\itemitem{a)} The ``stars and bars'' or dividers idea for the unlabeled balls, labeled
urns case
\itemitem{b)} Partitions of an integer into a fixed number of parts and
into any number of parts.  Know the recurrence relation for $p(n,k)$ and
its proof.  
\itemitem{c)}  The Stirling numbers of the second kind.  Know the recurrence
relation for $S(n,k)$ and its proof.  
\bigskip
\item{11)}  Single- and Multivariable generating function techniques for counting problems.  Note that
you won't have Maple to use on the exam, so I might ask questions about
how problems would be set up and what you would be looking for in the generating function without
asking for a single number answer.  There are some examples in the Review Problems below.
\item{12)}  Finding recurrence relations for sequences from counting problems.  Know 
in particular the recurrences $D_n = (n-1) D_{n-1} + (n-1) D_{n-2}$ and 
$D_n = n D_{n-1} + (-1)^n$ for the number
of derangements of $[n]$ and how they are proved.  
\item{13)}  Generating functions and recurrences.  
Solving constant-coefficient linear recurrences in the homogeneous
and inhomogeneous cases.  The relation between the generating function methods
and the ``shortcuts'' based on the characteristic polynomial of the recurrence.
If I ask you to solve an inhomogeneous recurrence, I would give you the Table 6.1 on p. 185
containing the ``good guesses'' for the particular solution.
\item{14)}  The general Inclusion-Exclusion Principle.  Know the statement, the proof by 
induction on the number of sets in the union, and how to apply it.
\item{15)}  Group actions, Burnside's Lemma -- Theorem 8.3.1 -- (know the statement and the proof), 
Burnside for Colorings, Polya's Enumeration Theorem -- 8.5.3 (know how to apply it; I wouldn't
ask for a proof here because we did not do one in detail).
\bigskip
\noindent
{\it How to Prepare}
\bigskip
Start by reviewing your class notes, problem sets, and exams.  Pay special attention to
anything you did not ``get'' before and be sure you understand the posted solutions and
how to attack similar problems.  Then, try some or all of the
following review problems.  I will post solutions for these about a week before the exam.   
\bigskip
\noindent
{\it Review Problems}
\bigskip
\noindent
{\it Disclaimer:}  These problems are {\it only} intended to give you an idea of the range
of topics and to help you review the concepts.  The actual exam questions
will not be exactly like these.  This list is also quite a bit longer than the actual exam
will be.  
\bigskip
\noindent
From Beeler:  1.3.13, 1.4.8, 1.5.7, 2.1.22, 2.2.9, 2.3.9, 2.4.8, 2.5.9, 2.7.15, 3.1.15, 3.2.7, 
3.3.8, 3.5.6, 3.6.20, 4.2.12, 4.2.19, 4.3.14, 4.3.15, 5.3.9 (just say how you would solve this
using a generating function), 5.4.9 (same directions), 6.1.20 (figure 6.2 is at the top of the page), 
6.3.10 (solve with a generating function and by the ``shortcut'' method), 6.5.27, 7.1.16 (just
say how you would solve it using generating functions), 7.3.4, 8.3.20, 8.5.12 (just say how you would
solve it using the Polya Theorem). 
\bye 
