\magnification=\magstep1
\nopagenumbers
\centerline{Mathematics 357 -- Combinatorics}
\centerline{Solutions for Final Examination -- May 12, 2017}
\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{} {\it Solution:}  $s(n,k)$ is the number of permutations of $[n]$
with cycle index $k$ (that is, the number of permutations such that in 
the disjoint cycle decomposition, there are $k$ disjoint cycles).  
\item{B)} (10) Give a combinatorial proof that $\sum_{k=1}^n s(n,k) = n!$.
\item{} {\it Solution:}  The right side is the total number of permutations of $[n]$.
Each permutation of $[n]$ has a unique disjoint cycle decomposition, hence, it
has a cycle index somewhere between $1$ and $n$.  The set of permutations
with cycle index $k$ and the set of permutations with cycle index $k'$ are
disjoint if $k \ne k'$ by the uniqueness.  Hence by the Addition Principle, 
the number of permutations of $[n]$ is also given by $\sum_{k=1}^n s(n,k)$.
That is, 
$$\sum_{k=1}^n s(n,k) = |S_n| = 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)$.
\item{} {\it Solution:}  The recurrence is 
$$s(n+1,k) = n \cdot s(n,k) + s(n,k-1).$$
To prove this, we begin by writing the set of permutations of $[n+1]$
with $k$ disjoint cycles as $A \cup B$ where $A$ is the set
of permutations $\pi$ with $\pi(n+1) \ne n+1$ (and $k$ disjoint cycles), 
and $B$ is the set of permutations with $\pi(n+1) = n+1$ (and $k$ disjoint cycles).  
Since $A \cap B = \emptyset$, by the Addition Principle, 
$$s(n+1,k) = |A| + |B|.$$
But clearly $|B|$ is the same as the number of permutations of $[n]$ with 
$k - 1$ disjoint cycles since any permutation in $B$ contains $(n+1)$ as one
of its cycles, but the rest is arbitrary.  Hence $|B| = s(n,k-1)$. On the other hand if 
On the other hand, if $\pi(n+1) \ne n+1$, then we can take any permutation
of $[n]$ with $k$ disjoint cycles and insert $n+1$ anywhere in any one of 
the cycles except at the end to get elements of $B$.  There are $n$ ways to 
do this.  So $|A| = n\cdot s(n,k)$ by the Multiplication Principle.  

The last part:  
$$\eqalign{s(7,2) &= 6\cdot s(6,2) + s(6,1)\cr
                  &= 6\cdot (5\cdot s(5,2) + s(5,1)) + s(6,1)\cr
                  &= 6\cdot (5\cdot (4\cdot s(4,2) + s(4,1)) + s(5,1)) + s(6,1)\cr
                  &= 6\cdot (5\cdot (4 \cdot 11 + 6) + 24) + 120\cr
                  &= 1764.\cr}$$ 
(Note:  I used the facts that $s(4,2) = 11$ and $s(n,1) = (n-1)!$ for all $n$ here.
The first comes from the fact that there are 3 $(ab)(cd)$'s and 8 $(abc)(d)$'s in $S_4$.
The permutations counted by $s(n,1)$ are the $n$-cycles in $S_n$.  You can always
start the cycle from $1$ but then there are $(n-1)!$ ways to continue.) 
\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{} {\it Solution:}  The best way to prove this algebraically is to use the Binomial
Theorem.  The binomial coefficient ${m + n\choose k}$ is equal to the coefficient of $x^k$
in the binomial expansion of $(1 + x)^{m+n}$.  Since 
$$(1 + x)^{m+n} = (1 + x)^m \cdot (1 + x)^n,$$ 
the $x^k$ terms come from products $x^i \cdot x^{k - i}$.  The coefficient of $x^i$ in 
the first factor in the last displayed equation is ${m \choose i}$ and the coefficient
of $x^{k-i}$ in the second factor is ${n \choose k - i}$.  Summing over $i$, we get
$${m + n\choose k} = \sum_{i=0}^k {m \choose i}{n \choose k - i}$$
as desired. 
\item{B)} (15)  Give a combinatorial proof of the identity.
\item{} {\it Solution:}  Consider the process of choosing a committee of $k$ people
out of a pool containing $m$ women and $n$ men.  If we do the selection without
considering gender, there are ${m + n\choose k}$ possible choices.  If, on the other
hand, we consider the breakdown of the committee members by gender, there are 
${m \choose i}$ ways to choose $i$ of the women, ${n \choose k - i}$ ways to 
choose $k - i$ of the men, and hence ${m \choose i}{n \choose k - i}$
committees with exactly $i$ women and $k - i$ men (Multiplication Principle).
Summing over $i$ (using the Addition Principle) we get the desired 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{} {\it Solution:}  By the Multiplication Principle, there are $7\cdot 7\cdot 7 \cdot 7 = 7^4$
such functions ($7$ choices for $f(a)$, $7$ choices for $f(b)$, ... ).  
\item{B)} (10) How many of these functions are {\it injective} (one-to-one)?
\item{} {\it Solution:}  There are $7$ choices for $f(a)$, but then $6$ for $f(b)$ since $f(b) \ne f(a)$, 
then $5$ choices for $f(c) \ne f(a),f(b)$ and $4$ choices for $f(d) \ne f(a),f(b),f(c)$.  The total number is 
$P(7,4) = 7\cdot 6\cdot 5\cdot 4$ by the Multiplication Principle.  
\item{C)}  (10) How many of the functions in part A
satisfy $f(a) = 2$ or $f(b) = 5$?
\item{} {\it Solution:}  There are $7^3$ functions with $f(a) = 2$, $7^3$ functions with
$f(b) = 5$ and $7^2$ with both $f(a) = 2$ and $f(b) = 5$.  Hence by the Inclusion-Exclusion
Principle, this number is $7^3 + 7^3 - 7^2 = 2\cdot 7^3 - 7^2$.
\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{} {\it Solution:} The cakes (the ``balls'') can be considered as labeled by their flavors
and the stores (the ``urns'') are also labeled by their addresses.  Hence the 
number of distributions is $3^{10}$.  
\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{} {\it Solution:}  The number is $3!\cdot S(10,3).$
\item{C)}  (5) What changes in part A if the cakes are 10 identical 
chocolate cakes (yum!)?
\item{} {\it Solution:}  The cakes are now indistinguishable (unlabeled), but the
stores are still labeled.  So the 
number of distributions is ${10 + 3 - 1 \choose 3 - 1} = {12 \choose 2}$
by the ``dividers'' or ``stars and bars'' method.
\item{D)}  (5) What changes in part B if the cakes are as in part C?
\item{} {\it Solution:}  The number is ${10 - 1\choose 3 - 1} = {9\choose 2}$.
(Recall, one way to think about this is that we distribute one cake to 
each store first, then count the number of ways to distribute the remaining
$7$ cakes to the $3$ stores 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{} {\it Solution:}  To avoid having to consider fractional amounts of dollars,
let us convert all the money to cents.  Then a $\$10$ bill consists of $1000$
cents, a $\$5$ bill consists of $500$ cents,
a $\$1$ bill is $100$ cents, a quarter is $25$ cents and a dime is $10$ cents.  
We want the coefficient of $x^{1000}$ in the generating function
$${1\over 1 - x^{500}}\cdot {1 \over 1 - x^{100}} \cdot {1 \over 1 - x^{25}} \cdot {1 \over 1 - x^{10}}.$$
(Also correct would be to write the geometric series expansions of the factors above
and truncate to include only terms with $x^n$ for $n \le 1000$.) 
\item{B)}  (15)  Determine the number of triples $(a_1,a_2,a_3)$ 
of non-negative integers such that 
$$4 a_1 + 3 a_2 + a_3 = 108$$
{\it or}
$$a_1 + 5a_2 + 3a_3 = 98.$$
\item{} {\it Solution:}  Because of the ``or'' here we need to use the Inclusion-Exclusion
Principle as follows.  The number $A$ of solutions of the first equation is the 
coefficient of $x^{108}$ in ${1\over 1 - x^4}\cdot {1 \over 1 - x^3}\cdot {1 \over 1 - x}$.
Similarly, the number $B$ of solutions of the second equation is 
the coefficient of $x^{98}$ in ${1\over 1 - x}\cdot {1 \over 1 - x^5}\cdot {1 \over 1 - x^3}$.
We also need the number $C$ of solutions of the two equations simultaneously, which is the 
coefficient of $u^{108} v^{98}$ in the expansion of 
$${1\over 1 - u^4 v}\cdot {1 \over 1 - u^3 v^5} \cdot {1 \over 1 - u v^3}.$$
The final answer would be $A + B - C$.  
\bigskip
\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{} {\it Solution:}  The number $R_1 = 2$ since you can only use
the two different colors of $1\times 1$ tiles in that case.  A $1 \times 2$
design can be made with any $2$ of the $1\times 1$ tiles.  There are 4 different designs
possible.  (For instance, if the colors are red and green, you can have
(red,red) or (red,green) or (green,red) or (green,green).)  You can
also use any one of the $1 \times 2$ tiles, giving three more types.  This 
gives $R_2 = 4 + 3 = 7$.  Now consider a general $1 \times n$ pattern.
If the first tile on the left is $1\times 1$, then there are $2$ choices
for the color and the remaining pattern can be any one of the $1 \times (n - 1)$
patterns. So there are $2R_{n-1}$ of those.  On the other hand, if the first
tile on the left is a $1 \times 2$, it can be any one of the $3$ different
colors of those tiles, and the remainder is a $1 \times (n - 2)$ pattern.
hence there are $3R_{n-2}$ of these.  By the Addition Principle,
$$R_n = 2 R_{n-1} + 3R_{n-2}.$$
\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!)
\item{} {\it Solution:} The generating function for the $R_n$ sequence
satisfies:
$$(1 - 2x - 3x^2)R(x) = 1.$$
So 
$$R(x) = {1 \over (1 + x)( 1 - 3x)} = {1/4\over 1 + x} + {3/4 \over 1 - 3x}$$
and hence
$$R_n = {1\over 4}\cdot (-1)^n + {3\over 4}\cdot 3^n.$$
Alternatively, the characteristic polynomial is 
$$1 - 2 x - 3x^2 = (1 + x)(1 - 3x)$$
Hence the general solution of the recurrence is 
$$R_n = A\cdot (-1)^n + B\cdot 3^n.$$
From the initial conditions
$$\eqalign{2 &= -A + 3B\cr
           7 &=  A + 9B\cr}$$
So $12B = 9$ and $B = {3\over 4}$.  Then $A = {1\over 4}$ and 
$$R_n = {1\over 4}\cdot (-1)^n + {3\over 4}\cdot 3^n.$$

\bigskip
\noindent
VII.  
\item{A)} (20) State and prove Burnside's Lemma for finite groups $G$
acting on finite sets $X$.
\item{} {\it Solution:}  The statement is:  Let a finite group $G$ act on 
a finite set $X$.  Then the number of orbits is given by 
$$|\{{\rm orbits}\}| = {1\over |G|} \sum_{g \in G} |{\rm Inv}(g)|,$$
where ${\rm Inv}(g)$ is the set of elements of $X$ fixed by $g$ (the ``invariants'' of 
$g$).  For the proof, consider the $|X| \times |G|$ matrix $M = (m_{xg})$, with
rows indexed by the $x \in X$ and columns indexed by the $g \in G$, where 
$$m_{xg} = \cases{1 & if $g(x) = x$\cr 0 & if not\cr}.$$
The sum of the entries in the row corresponding to $x \in X$ is the number of
elements in ${\rm st}(x)$, the stabilizer of $x$, defined as 
$${\rm st}(x) = \{g \in G\mid g(x) = x\}.$$
On the other hand the sum of the entries in the column corresponding to 
$g \in G$ is $|{\rm Inv}(g)|$.  If we add all of the entries in the matrix
row-wise, then column-wise, the totals are the same, which shows
$$\sum_{g\in G} |{\rm Inv}(g)| = \sum_{x \in X} |{\rm st}(x)|.\leqno(1)$$
Now we explained in class that for each $x \in X$, there is a
relation 
$$|{\rm st}(x)|\cdot |o(x)| = |G|,$$
where $o(x) = \{g(x) \mid g \in G\}$ is the {\it orbit} of $x$.  Hence, substituting into (1)
and rearranging, we get
$${1\over |G|} \sum_{g \in G} |{\rm Inv}(g)| = \sum_{x\in X} {1\over |o(x)|}.$$
But the orbits form a partition of the set $X$ and if $x$ is in an orbit consisting
of $m$ elements, then there are $m$ terms of $1/m$ in the sum on the right side of the
last displayed equation.  Hence 
$${1\over |G|} \sum_{g \in G} |{\rm Inv}(g)| = \sum_{x\in X} {1\over |o(x)|} = 
|\{{\rm orbits}\}|.$$

\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 off of it!)
How many {\it different} topped pizzas are there, up to rotations?
\item{} {\it Solution:}  Let $\rho$ represent the $\pi/3$ counterclockwise
rotation around the center of the pizza.  Then $G = \{e,\rho,\rho^2,\rho^3,\rho^4,\rho^5\}$
acts on $X = $ the collections of toppings.  We have $|X| = 4^6 = 4096$.  Then
$$\eqalign{
|{\rm Inv}(e)| &= 4096\cr
|{\rm Inv}(\rho)| &= 4\cr
|{\rm Inv}(\rho^2)| &= 4^2 = 16\cr
|{\rm Inv}(\rho^3)| &= 4^3 = 64\cr
|{\rm Inv}(\rho^4)| &= 4^2 = 16\cr
{\rm Inv}(\rho^5)| &= 4.\cr}$$
(because every pizza is invariant under $e$, the only pizzas invariant under 
$\rho$ and $\rho^5$ are ones with all six slices having the same topping, 
the pizzas invariant under $\rho^2$ and $\rho^4$ are those where every other
slice around the pizza has the same topping -- two
toppings alternate, and the pizzas that are invariant under $\rho^3$ are the ones
where every third slice around the pizza has the same topping.)
Hence by Burnside's Lemma, the number of orbits for this action, which is the 
same as the number of different topped pizzas up to rotations is
$${1\over 6}(4096 + 4 + 16 + 64 + 16 + 4) = 700.$$

\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{} {\it Solution:}  An $n\times n$ Latin square is an $n\times n$ array
of $n$ different symbols where each symbol appears exactly once in each row
and each column (see $L$ and $L'$ in part B).  Two $n\times n$ Latin squares
are mutually orthogonal if, when they are overlaid, every possible pair of 
symbols from the two sets appears exactly once.  For instance $L$ and $L'$
are mutually orthogonal $5\times 5$ Latin squares in part B since every 
pair $(k,\ell)$ with $1 \le k\le 5$ and $0 \le \ell \le 4$ appears
once when we overlay the two arrays:
$$L\times L' = \pmatrix{ (1,2) & (2,3) & (5,4) & (4,1) & (3,0)\cr
                         (2,0) & (5,2) & (3,4) & (4,3) & (1,1)\cr
                         (5,1) & (4,0) & (3,2) & (1,3) & (2,4)\cr
                         (4,4) & (3,1) & (1,0) & (2,2) & (5,3)\cr
                         (3,3) & (1,4) & (2,1) & (5,0) & (4,2)\cr}$$
\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{} {\it Solution:}  To be a magic square, each row, each column, and
the two diagonals of the matrix have to add to the same total and 
the entries in the matrix have to be distinct.  Here the entries are 
$$L+5L' = \pmatrix{ 11 & 17 & 25 & 9 & 3\cr
                    2 & 15 & 19 & 23 & 6\cr
                    10 & 4 & 13 & 16 & 22\cr
                    24 & 8 & 1 & 12 & 20\cr
                    18 & 21 & 7 & 5 & 14\cr}$$
and the rows, columns and diagonals of this matrix add up to $65$ (it's magic!)
\item{C)} (10) (This is a special case of a pattern noticed by L. Euler
in his 1776 paper on magic squares that Hope and Margot mentioned in
their talk.)  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.   
\item{} {\it Solution:}  The row and column sums of the matrix $L + 5L'$ are 
all $(a + b + c + d + e) + 5(A + B + C + D + E)$.  The main diagonal in $L + 5L'$ sums to 
$$(a + b + c + d + e) + 25E = (a + b + c + d + e) + 5(A + B + C + D + E).$$
Similarly the second diagonal sums to 
$$5e + 5(A + B + C + D + E) = (a + b + c + d + e) + 5(A + B + C + D + E).$$
Finally, the numbers $x + 5y$ with $x \in \{1,2,3,4,5\}$ and $y \in \{0,1,2,3,4\}$
give each number between $1$ and $25$ exactly one time each.  Hence the entries in the 
matrix $L + 5L'$ are all distinct, and all the properties to be a magic square 
are satisfied.  
\bye 

