Mathematics 357 – Combinatorics Final Examination – May 12, 2017

Directions

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. Relax, and read each question carefully before starting to work!

I. A) (5) What is the definition of the Stirling number of the first kind, s(n, k), in terms of

permutations? B) (10) Give a combinatorial proof that ∑_{k=1}^{n} s(n, k) = n!. C) (15) State and prove the recurrence relation for the s(n, k). Use the recurrence to

determine the Stirling number s(7, 2).

II. The Vandermonde convolution identity for binomial coefficients says that for all positive integers m, n, k,

\binom{n + m}{k} = ∑_{i=0}^{k} \binom{n}{i}\binom{m}{k − i}.

A) (15) Give an algebraic proof of this identity. B) (15) Give a combinatorial proof of the identity.

III. Let X = {a, b, c, d} and Y = {1, 2, 3, 4, 5, 6, 7}. A) (10) How many different functions f : X → Y are there? B) (10) How many of these functions are injective (one-to-one)? C) (10) How many of the functions in part A satisfy f(a) = 2 or f(b) = 5?

IV. For all parts of this question, express the number of distributions in terms of partition numbers, Stirling numbers, binomial coefficients, etc. You do not need to evaluate any of these to a single number. 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?

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? C) (5) What changes in part A if the cakes are 10 identical chocolate cakes (yum!)? D) (5) What changes in part B if the cakes are as in part C?

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.

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. B) (15) Determine the number of triples (a_{1}, a_{2}, a_{3}) of non-negative integers such that

4a_{1} + 3a_{2} + a_{3} = 108, or (that is really or, not and)
a_{1} + 5a_{2} + 3a_{3} = 98.

VI. You have unlimited supplies of 1 × 1 tiles in 2 different colors and 1 × 2 tiles in 3 additional different colors (different from the colors of the 1 × 1 tiles). For each nonnegative integer n, let R_{n} be the number of different 1 × n designs you can make.

A) (10) Explain why R_{n} satisfies the recurrence R_{n} = 2R_{n−1} + 3R_{n−2} for all n ≥ 3 and

R_{1} = 2, R_{2} = 7. 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!)

VII. A) (20) State and prove Burnside’s Lemma for finite groups G acting on finite sets X. 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 the same if there is some 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 different topped pizzas are there, up to rotations?

VIII. (Extra Credit – from the final project talks!) A) (5) What is an n × n Latin square? What does it mean for two n × n Latin squares

to be orthogonal? B) (5) Consider the 5 × 5 matrices

L = ( \begin{matrix}1 & 2 & 5 & 4 & 3 \\ 2 & 5 & 4 & 3 & 1 \\ 5 & 4 & 3 & 1 & 2 \\ 4 & 3 & 1 & 2 & 5 \\ 3 & 1 & 2 & 5 & 4 \end{matrix} )  and  L′ = ( \begin{matrix}2 & 3 & 4 & 1 & 0 \\ 0 & 2 & 3 & 4 & 1 \\ 1 & 0 & 2 & 3 & 4 \\ 4 & 1 & 0 & 2 & 3 \\ 3 & 4 & 1 & 0 & 2 \end{matrix} )

Show that the matrix L + 5L′ is a 5 × 5 magic square. C) (10) Show that if

L = ( \begin{matrix}a & b & c & d & e \\ b & c & d & e & a \\ c & d & e & a & b \\ d & e & a & b & c \\ e & a & b & c & d \end{matrix} )  and  L′ = ( \begin{matrix}E & D & C & B & A \\ A & E & D & C & B \\ B & A & E & D & C \\ C & B & A & E & D \\ D & C & B & A & E \end{matrix} )

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.

Congratulations to graduating seniors! Everyone have a great summer I hope you have found Combinatorics interesting and fun!