\magnification=\magstep1
\nopagenumbers
\centerline{Mathematics 357 -- Combinatorics}
\centerline{Midterm Examination 2 -- April 7, 2017}
\bigskip
\noindent
{\it Directions}
\bigskip
Do any combination of parts of the following problems in the 
blue exam book.  (The exam will be scored out of 100 points, but
you have the possibility of accumulating up to 110 points if you do all the 
parts.)
Explain your reasoning fully and do not place any work on the exam sheet.  
{\it Relax, and read each question carefully before starting to work!}
\bigskip
\noindent
I.  
\item{A)} (5)  What is the definition of the Stirling number of the second
kind, $S(n,k)$, in terms of distribution problems? 
\item{B)} (15)  State and prove the recurrence relation for the $S(n,k)$. 
\item{C)} (5)  Determine the Stirling number $S(6,2)$.
\bigskip
\noindent
II.  For all parts of this question, express the number of distributions
in terms of partition numbers, Stirling numbers, binomial coefficients, etc.
{\it You do not need to evaluate any of these to a single number.}
\item{A)}  (5) How many ways are there to distribute $10$ identical unmarked 
pads of paper into $4$ piles, with no restrictions on the sizes of the piles?
\item{B)}  (5) How many ways are there if the piles of pads are supposed
to go to 4 numbered tables and at least one pad goes to each table?
\item{C)}  (5) How many ways are there if the pads have 10 different colors
of paper but we're back in the situation of part A
(i.e. just 4 piles, not the 4 numbered tables)?
\item{D)}  (5) What changes in part C) if every table gets at least one pad?
\bigskip
\noindent
III.  (15) 100 pencils are divided into four
lots of sizes $x_1,x_2,x_3,x_4$, {\it each a multiple of 5}, and placed in 4 classrooms.  
Room 1 receives {\it at least $20$\/} pencils, room 2 receives {\it no more than $40$} pencils,
room 3 receives {\it between $15$ and $25$} pencils, and room 4 receives a number of pencils
that is a {\it multiple of $10$}.  How many different vectors $(x_1,x_2,x_3,x_4)$ of numbers
of pencils satisfy these conditions?  Set up an appropriate {\it generating
function} and explain how you would use it to answer this question.
\bigskip
\noindent
IV. (15) For each $n \ge 1$, let $T_n$ be the number of ways of
arranging $n$ ``triominoes'' (like dominoes, but $3\times 1$) in a $3\times n$ tray with no overlapping.
Find a recurrence relation of order 3 for the $T_n$ sequence and the initial values $T_1,T_2$.
({\it Don't try to solve the recurrence.})
\bigskip
\noindent
V.  
\item{A)} (20) A sequence $R_n$ is defined by the recurrence
$R_n = 6R_{n-1} - 8R_{n-2}$. Express the 
{\it generating function\/} of the sequence $R_n$ as a rational function
of $x$ if the initial terms are $R_0 = 3, R_1 = 1$ and use it to derive a 
formula for $R_n$ as a function of $n$.  (Partial credit 10 for solution by the 
``shortcut'' method.)
\item{B)} (15) Now suppose we wanted to solve 
$R_n = 6R_{n-1} - 8R_{n-2} + 2^n$.
What would be the appropriate ``good guess'' for the particular solution?  See
table from Beeler on back. Determine the solution of this recurrence with the 
initial conditions $R_0 = 1$, $R_1 = 1$.  
\bye

