Mathematics 357 – Combinatorics Solutions for Final Examination – May 12, 2017

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

permutations? 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).

B) (10) Give a combinatorial proof that ∑_{k=1}^{n} s(n, k) = n!.

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 ≠ k′ by the uniqueness. Hence by the Addition Principle, the number of permutations of [n] is also given by ∑_{k=1}^{n} s(n, k). That is,

∑_{k=1}^{n} s(n, k) = |S_{n}| = 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). Solution: The recurrence is

s(n + 1, k) = n · 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 ∪ B where A is the set of permutations π with π(n + 1) ≠ n + 1 (and k disjoint cycles), and B is the set of permutations with π(n+1) = n+1 (and k disjoint cycles). Since A ∩ B = ∅, 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 π(n + 1) ≠ 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 · s(n, k) by the Multiplication Principle. The last part:

s(7, 2) = 6 · s(6, 2) + s(6, 1)
= 6 · (5 · s(5, 2) + s(5, 1)) + s(6, 1)
= 6 · (5 · (4 · s(4, 2) + s(4, 1)) + s(5, 1)) + s(6, 1)
= 6 · (5 · (4 · 11 + 6) + 24) + 120
= 1764.

(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.)

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.

Solution: The best way to prove this algebraically is to use the Binomial Theorem. The binomial coefficient \binom{m+n}{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} · (1 + x)^{n},

the x^{k} terms come from products x^{i} · x^{k−i}. The coefficient of x^{i} in the first factor in the last displayed equation is \binom{m}{i} and the coefficient of x^{k−i} in the second factor is \binom{n}{k−i}. Summing over i, we get

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

as desired. B) (15) Give a combinatorial proof of the identity.

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 \binom{m+n}{k} possible choices. If, on the other hand, we consider the breakdown of the committee members by gender, there are \binom{m}{i} ways to choose i of the women, \binom{n}{k−i} ways to choose k − i of the men, and hence \binom{m}{i}\binom{n}{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.

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?

Solution: By the Multiplication Principle, there are 7 · 7 · 7 · 7 = 7^{4} such functions (7 choices for f(a), 7 choices for f(b), ... ).

B) (10) How many of these functions are injective (one-to-one)? Solution: There are 7 choices for f(a), but then 6 for f(b) since f(b) ≠ f(a), then 5 choices for f(c) ≠ f(a), f(b) and 4 choices for f(d) ≠ f(a), f(b), f(c). The total number is P (7, 4) = 7 · 6 · 5 · 4 by the Multiplication Principle.

C) (10) How many of the functions in part A satisfy f(a) = 2 or f(b) = 5? 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 · 7^{3} − 7^{2}.

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? 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}.

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? Solution: The number is 3! · S(10, 3).

C) (5) What changes in part A if the cakes are 10 identical chocolate cakes (yum!)? Solution: The cakes are now indistinguishable (unlabeled), but the stores are still labeled. So the number of distributions is \binom{10+3−1}{3−1} = \binom{12}{2} by the “dividers” or “stars and bars” method.

D) (5) What changes in part B if the cakes are as in part C?

Solution: The number is \binom{10−1}{3−1} = \binom{9}{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.)

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, $1bills, quarters and dimes. 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

\frac{1}{1 − x^{500}} · \frac{1}{1 − x^{100}} · \frac{1}{1 − x^{25}} · \frac{1}{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 ≤ 1000.)

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

a_{1} + 5a_{2} + 3a_{3} = 98.

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 \frac{1}{1−x^{4}} · \frac{1}{1−x^{3}} · \frac{1}{1−x}. Similarly, the number B of solutions of the second equation is the coefficient of x^{98} in \frac{1}{1−x} · \frac{1}{1−x^{5}} · \frac{1}{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

\frac{1}{1 − u^{4}v} · \frac{1}{1 − u^{3}v^{5}} · \frac{1}{1 − uv^{3}} .

The final answer would be A + B − C.

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. Solution: The number R_{1} = 2 since you can only use the two different colors of 1 × 1 tiles in that case. A 1 × 2 design can be made with any 2 of the 1 × 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 × 2 tiles, giving three more types. This gives R_{2} = 4 + 3 = 7. Now consider a general 1 × n pattern. If the first tile on the left is 1 × 1, then there are 2 choices for the color and the remaining pattern can be any one of the 1 × (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 × 2, it can be any one of the 3 different colors of those tiles, and the remainder is a 1 × (n − 2) pattern. hence there are 3R_{n−2} of these. By the Addition Principle,

R_{n} = 2R_{n−1} + 3R_{n−2}.

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!) Solution: The generating function for the R_{n} sequence satisfies:

(1 − 2x − 3x^{2})R(x) = 1.

So

R(x) = \frac{1}{(1 + x)(1 − 3x)} = \frac{1/4}{1 + x} + \frac{3/4}{1 − 3x}

and hence

R_{n} = \frac{1}{4} · (−1)^{n} + \frac{3}{4} · 3^{n}.

Alternatively, the characteristic polynomial is

1 − 2x − 3x^{2} = (1 + x)(1 − 3x)

Hence the general solution of the recurrence is

R_{n} = A · (−1)^{n} + B · 3^{n}.

From the initial conditions

\begin{aligned}2 & = −A + 3B \\ 7 & = A + 9B \end{aligned}

So 12B = 9 and B = \frac{3}{4}. Then A = \frac{1}{4} and

R_{n} = \frac{1}{4} · (−1)^{n} + \frac{3}{4} · 3^{n}.

VII. A) (20) State and prove Burnside’s Lemma for finite groups G acting on finite sets X.

Solution: The statement is: Let a finite group G act on a finite set X. Then the number of orbits is given by

|\{orbits\}| = \frac{1}{|G|} ∑_{g∈G} |Inv(g)|,

where Inv(g) is the set of elements of X fixed by g (the “invariants” of g). For the proof, consider the |X| × |G| matrix M = (m_{xg}), with rows indexed by the x ∈ X and columns indexed by the g ∈ G, where

m_{xg} = \{ \begin{matrix}1 & if g(x) = x \\ 0 & if not \end{matrix} .

The sum of the entries in the row corresponding to x ∈ X is the number of elements in st(x), the stabilizer of x, defined as

st(x) = {g ∈ G | g(x) = x}.

On the other hand the sum of the entries in the column corresponding to g ∈ G is |Inv(g)|. If we add all of the entries in the matrix row-wise, then column-wise, the totals are the same, which shows

(1)  ∑_{g∈G} |Inv(g)| = ∑_{x∈X} |st(x)|.

Now we explained in class that for each x ∈ X, there is a relation

|st(x)| · |o(x)| = |G|,

where o(x) = {g(x) | g ∈ G} is the orbit of x. Hence, substituting into (1) and rearranging, we get

\frac{1}{|G|} ∑_{g∈G} |Inv(g)| = ∑_{x∈X} \frac{1}{|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

\frac{1}{|G|} ∑_{g∈G} |Inv(g)| = ∑_{x∈X} \frac{1}{|o(x)|} = |\{orbits\}|.

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 off of it!) How many different topped pizzas are there, up to rotations? Solution: Let ρ represent the π/3 counterclockwise rotation around the center of the pizza. Then G = {e, ρ, ρ^{2}, ρ^{3}, ρ^{4}, ρ^{5}} acts on X = the collections of toppings. We have |X| = 4^{6} = 4096. Then

|Inv(e)| = 4096
|Inv(ρ)| = 4
|Inv(ρ^{2})| = 4^{2} = 16
|Inv(ρ^{3})| = 4^{3} = 64
|Inv(ρ^{4})| = 4^{2} = 16
Inv(ρ^{5})| = 4.

(because every pizza is invariant under e, the only pizzas invariant under ρ and ρ^{5} are ones with all six slices having the same topping, the pizzas invariant under ρ^{2} and ρ^{4} are those where every other slice around the pizza has the same topping – two toppings alternate, and the pizzas that are invariant under ρ^{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

\frac{1}{6}(4096 + 4 + 16 + 64 + 16 + 4) = 700.

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. Solution: An n × n Latin square is an n × 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 × 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 × 5 Latin squares in part B since every pair (k, ℓ) with 1 ≤ k ≤ 5 and 0 ≤ ℓ ≤ 4 appears once when we overlay the two arrays:

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

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. 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′ = ( \begin{matrix}11 & 17 & 25 & 9 & 3 \\ 2 & 15 & 19 & 23 & 6 \\ 10 & 4 & 13 & 16 & 22 \\ 24 & 8 & 1 & 12 & 20 \\ 18 & 21 & 7 & 5 & 14 \end{matrix} )

and the rows, columns and diagonals of this matrix add up to 65 (it’s magic!) 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 = ( \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. 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 ∈ {1, 2, 3, 4, 5} and y ∈ {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.