\magnification=\magstep1
\nopagenumbers
\centerline{Mathematics 357 -- Combinatorics}
\centerline{Final Examination -- May 12, 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 200 points, but
you have the possibility of accumulating up to 220 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 first
kind, $s(n,k)$, in terms of permutations? 
\item{B)} (10) Give a combinatorial proof that $\sum_{k=1}^n s(n,k) = n!$.
\item{C)} (15)  State and prove the recurrence relation for the $s(n,k)$. 
Use the recurrence to determine the Stirling number $s(7,2)$.
\bigskip
\noindent
II.  The Vandermonde convolution identity for binomial coefficients says
that for all positive integers $m,n,k$, 
$${n + m\choose k} = \sum_{i=0}^k {n \choose i} {m \choose k - i}.$$  
\item{A)} (15)  Give an algebraic proof of this identity.
\item{B)} (15)  Give a combinatorial proof of the identity.
\bigskip
\noindent
III. Let
$X=\{a,b,c,d\}$ and $Y = \{1,2,3,4,5,6,7\}$.
\item{A)} (10) How many different functions $f : X \to Y$ are there?
\item{B)} (10) How many of these functions are {\it injective} (one-to-one)?
\item{C)}  (10) How many of the functions in part A
satisfy $f(a) = 2$ or $f(b) = 5$?
\bigskip
\noindent
IV.  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$ cakes, one cake 
each in 10 different flavors, to 3 different bakery outlet stores, with no restrictions on 
the numbers that go to any one store?
\item{B)}  (5) How many ways are there if the cakes from part A go to the stores
and each store gets at least one cake?
\item{C)}  (5) What changes in part A if the cakes are 10 identical 
chocolate cakes (yum!)?
\item{D)}  (5) What changes in part B if the cakes are as in part C?
\bigskip
\noindent
V.  Explain how you would solve each of the following problems by 
means of generating functions.  Give a closed formula for the generating
function, and indicate what you do to determine the number asked for.
\item{A)}  (15)  Determine the number of ways to ``break" (that is, make change for) a $\$10$ bill
if you have unlimited supplies of $\$5$ bills, $\$1$ bills, quarters
and dimes. 
\item{B)}  (15)  Determine the number of triples $(a_1,a_2,a_3)$ 
of non-negative integers such that 
$$\eqalign{4 a_1 + 3 a_2 + a_3 &= 108,\ {\rm or\ (that\ is\ really\ or,\ not\ and)}\cr
           a_1 + 5a_2 + 3a_3 &= 98.\cr}$$

\noindent
VI.  You have unlimited supplies of $1\times 1$ tiles in $2$ different colors and
$1 \times 2$ tiles in $3$ additional different colors (different from the colors
of the $1\times 1$ tiles). For each non-negative integer $n$, let $R_n$ be the number of 
different $1 \times n$ designs you can make.
\medskip
\item{A)} (10)  Explain why $R_n$ satisfies the recurrence $R_n = 2R_{n-1} + 3R_{n-2}$
for all $n \ge 3$ and $R_1 = 2$, $R_2 = 7$.  
\item{B)} (20) Solve the recurrence with the initial conditions
in part A using any applicable method.
(Note:  You can do this part even if you were not able to see how to derive
the recurrence given in part A!)
\bigskip
\noindent
VII.  
\item{A)} (20) State and prove Burnside's Lemma for finite groups $G$
acting on finite sets $X$.
\item{B)}  (10) A circular pizza is divided into 6 equal slices (sectors of the 
circle), each of which
can have exactly one of 4 different toppings (pepperoni, anchovies, mushrooms, 
or onions).  Two topped pizzas are to be considered {\it the same} if there is 
some {\it rotation} of the pizza about its center that takes one to the other.
(Don't flip the pizza across a line through the center because that would spill
all of the toppings!)
How many {\it different} topped pizzas are there, up to rotations?
\bigskip
\noindent
VIII.  ({\bf Extra Credit} -- from the final project talks!)  
\item{A)} (5)  What is an $n\times n$ {\it Latin square}?  What does it
mean for two $n\times n$ Latin squares to be {\it orthogonal}?
\item{B)} (5) Consider the $5\times 5$ matrices
$$L = \pmatrix{ 1 & 2 & 5 & 4 & 3\cr
                2 & 5 & 4 & 3 & 1\cr
                5 & 4 & 3 & 1 & 2\cr
                4 & 3 & 1 & 2 & 5\cr
                3 & 1 & 2 & 5 & 4\cr}
\qquad {\rm and} \qquad  L' = 
\pmatrix{ 2 & 3 & 4 & 1 & 0\cr
          0 & 2 & 3 & 4 & 1\cr
          1 & 0 & 2 & 3 & 4\cr
          4 & 1 & 0 & 2 & 3\cr
          3 & 4 & 1 & 0 & 2\cr}$$
Show that the matrix $L + 5L'$ is a $5\times 5$ {\it magic square}.
\item{C)} (10) Show that if  
$$L = \pmatrix{ a & b & c & d & e\cr
                b & c & d & e & a\cr
                c & d & e & a & b\cr
                d & e & a & b & c\cr
                e & a & b & c & d\cr}
\qquad {\rm and} \qquad  L' = 
\pmatrix{ E & D & C & B & A\cr
          A & E & D & C & B\cr
          B & A & E & D & C\cr
          C & B & A & E & D\cr
          D & C & B & A & E\cr}$$
are any Latin square matrices with $a + b + c + d + e = 5e$ and $A + B + C + D + E = 5E$, 
and $\{a,b,c,d,e\} = \{1,2,3,4,5\}$, $\{A,B,C,D,E\} = \{0,1,2,3,4\}$, then 
$L + 5L'$ is a magic square.   
\bigskip
\centerline{\it Congratulations to graduating seniors!}
\centerline{\it Everyone have a great summer}
\centerline{\it I hope you have found Combinatorics interesting and fun!}
\bye 

