\magnification=\magstep1
\centerline{MATH 357 -- Combinatorics}
\centerline{Review Sheet for Exam 2}
\centerline{March 30, 2017}
\bigskip
\noindent
{\it General Information and Groundrules}
\bigskip
The second midterm exam in Combinatorics this semester will be given (as announced
in the course syllabus) in class on Friday, April 7.  This will be a closed-book, 
individual exam.  You may use a basic calculator if you like.
\bigskip
\noindent
{\it What might be covered}
\bigskip
The new material on this exam will be the topics we have studied since Exam 1
(the material from problem sets 4,5,6,7).  In Beeler, this covers Chapters 4 (Distribution
Problems), Chapter 5 (Generating Functions) and Chapter 6 (Recurrences).  We
did not really discuss \S\S 4.4 or 6.4, so nothing from them will be included. 
\bigskip
\noindent
{\it Important Note:}  Many of the techniques in Chapter 4 rely on things done earlier.
So facts about binomial or multinomial coefficients, permutations, etc. may also 
enter into the questions on this exam.
\bigskip
\noindent
Specifically the new topics are:
\bigskip
\item{1)} 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{2)}  Algebraic techniques for factoring polynomials in the form
$$(1 - c_1 x)(1 - c_2 x)\cdots (1 - c_k x)$$
and the relation of $c_i$ to the roots of the polynomial
\item{3)}  Geometric series expansions; consequences obtained by 
substitution, differentiation, etc.
\item{4)}  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.  That's what questions IV and V below mean(!)
\item{5)}  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{6)}  Generating functions and recurrences
\item{7)}  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.
\bigskip
\noindent
{\it Some review/practice 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 and some of the ways I am asking things here would 
not be appropriate for an exam question.  This list is also quite a bit longer than the actual exam
will be.  
\bigskip
\noindent
I.  Find the number of distributions of 5 balls into 3 urns in each of the 
following cases.  For all parts of the question, 
\bigskip
\itemitem{(i)} give the number of distributions as a case of the formulas from Table 4.6, then
\itemitem{(ii)} evaluate the number to a single integer using recurrences, etc., then
\itemitem{(iii)} describe what the distributions you are counting actually mean (e.g. by listing
what those distributions actually do to the balls).  Note: it will be tedious to 
list every possible case for some of these -- you can stop when you are tired if
the pattern is clear; the point of the question is to make
sure you really understand what the number from item ii means(!)
\bigskip
\item{A)} Both the balls and the urns are labeled
\item{B)} Same as 1, but no urn is empty
\item{C)} The balls are labeled, but the urns are not labeled
\item{D)} Same as 3, but no urn is empty
\item{E)} The urns are labeled, but the balls are not labeled
\item{F)} Same as 4, but no urn is empty
\bigskip
\noindent
II.  Give a combinatorial proof of the recurrence
$$S(n,k) = \sum_{i=1}^n S(n-i,k-1) k^{i-1}.$$
(Hint:  Think about the way the ``one-step'' recurrence from Theorem 4.3.8 is proved, but
``keep going.'')
\bigskip
\noindent
III.  How many different ways are there to distribute 20 boiled eggs (say all 
from jumbo white-shell eggs with no flaws, no cracks, ... ) to 10 children?
How many if every child gets at least one egg?  How many if the eggs have been decorated for 
Easter with 20 different colors or patterns?  
\bigskip
\noindent
IV.  Give a ``generating function recipe'' (see point 4 in the list of topics covered
if you don't know what this means) for counting the number of unordered 12-letter words 
from the alphabet ${V,W,X,Y,Z}$ that satisfy all of the following:
\item{(i)}  If $V$ is used, then it is used exactly 3 times
\item{(ii)}  $W$ is used an even number of times (possibly $0$ times)
\item{(iii)}  $X$ is used at least 4 times
\item{(iv)}  $Y$ appears no more than 2 times
\item{(v)}  $Z$ appears {\it the same} number of times that $Y$ does.  (You'll need to 
think about this one; it's not exactly like anything we did before but you 
should see what to do if you think about it the right way(!))
\bigskip
\noindent
V.  Give a ``generating function recipe'' (see point 4 in the list of topics covered
if you don't know what this means) for finding the number of vectors $(x_1,x_2,x_3,x_4)$
of non-negative integers that satisfy:
$$\eqalign{
3x_1 + 4x_2 + 5x_3 + 2x_4 &= 20\cr
2x_1 + 2x_2 + 3x_3 + 3x_4 &= 18\cr}$$
What would change if the second $=$ was replaced by $\le$?
\bigskip
\noindent
VI.  Using any appropriate method, determine the number of derangements of $[7]$
(that is, the number $D_7$).  What fraction of the elements of $S_7$ are derangements?
\bigskip
\noindent
VII.  Recurrences.
\item{A)}  Show directly (i.e. without solving the recurrence) that $R_n = 6^n$
satisfies $R_n = 7 R_{n-1} - 6R_{n-2}$, and $R_0 = 1$, $R_1 = 6$.  
\item{B)}  Solve the following homogeneous recurrence using the generating function method:
$$R_n = 7 R_{n-1} - 12 R_{n-2}$$
with initial conditions $R_0 = 1$ and $R_1 = 0$.  
\item{C)}  What would the general solution of a homogeneous recurrence with
characteristic polynomial 
$$(1 - 4x)^4 (1 - 5x)^3 (1 - 6x)$$
look like?
\item{D)}   Solve the following inhomogeneous recurrence using our ``shortcut''
method and undetermined coefficients:
$$R_n = 7 R_{n-1} - 12 R_{n-2} + n^2$$
with initial conditions $R_0 = 1$ and $R_1 = 0$.  (Note:  The associated homogeneous
recurrence is the same as the one in part B.)
\item{E)}   Solve the following inhomogeneous recurrence using our ``shortcut''
method and undetermined coefficients:
$$R_n = 7 R_{n-1} - 12 R_{n-2} + 4^n$$
with initial conditions $R_0 = 1$ and $R_1 = 0$.  (Note:  The associated homogeneous
recurrence is the same as the one in part B.)
\bye
