Mathematics 357 – Combinatorics Final Examination Answers and Solutions May 13, 2005

Directions

This exam consists of problems I - VII and either VIII or VIII’. If you submit solutions for both VIII and VIII’, I will count one as extra credit. Do all your work in the blue exam booklet. There are 200 possible points. Good hunting!

I. n men and n women attend a wedding reception on a rainy day and check their coats and umbrellas. When the reception is over, they retrieve the umbrellas, but (gasp!) things have gotten mixed up at the coat check stand.

A) (5) In how many different ways is it possible for none of the people to get his or her own umbrella back?

Answer: The derangement number D_{2n}.

B) (10) In how many different ways is it possible for none of the men to get his own umbrella back and none of the women to get her own umbrella back, but for each man’s umbrella to go to another man, and each woman’s umbrella to go to another woman?

Answer: There are D_{n} possible assignments of men’s umbrellas to men other than their owners, and similarly for the women. Each combination of a derangement of the men’s umbrellas together with a derangement of the women’s umbrellas is possible. By the multiplication rule, the number here is D_{n} · D_{n} = D_{n}^{2}.

C) (10) In how many different ways is it possible for all of the men to get women’s umbrellas back, and all of the women to get men’s umbrellas back?

Answer: The men’s umbrellas can be returned to the women in n · (n − 1) ⋯ 2 · 1 = n! ways, and similarly for the women’s umbrellas. By the multiplication rule again, the number is n! · n! = (n!)^{2}.

II. (25) Using a combinatorial or algebraic proof, as you prefer, show that for all n ≥ 1,

\binom{n}{1} + 2\binom{n}{2} + ⋯ + n\binom{n}{n} = n2^{n−1}

Solution: (algebraic) By the binomial theorem,

∑_{k=0}^{n} \binom{n}{k}x^{k} = (1 + x)^{n}

Differentiate both sides with respect to x and substitute x = 1:

\begin{aligned}∑_{k=1}^{n} k\binom{n}{k}x^{k−1} & = n(1 + x)^{n−1} \\ ⇒ ∑_{k=1}^{n} k\binom{n}{k} & = n2^{n−1}, \end{aligned}

which is what we had to show.

Solution: (combinatorial) Consider counting the number of committees of sizes 1 ≤ k ≤ n with a chairperson, chosen from a pool of n people. We can count this number in two ways. First, consider choosing the committee from the pool and then choosing the chairperson from the membership. This gives the sum on the left hand side. Second, choose the chairperson first (n possibilities), then go through the n − 1 remaining people one at a time and decide whether each is on the committee or not. This gives n2^{n−1} different committees with chairperson.

III. A professor makes up a review sheet for an exam including 15 practice questions, subdivided into parts I,II,III, each with 5 questions. The actual exam will consist of exactly 8 of the 15 practice questions.

A) (5) Taking the ordering of the exam problems into account, how many different possible exams are there?

Answer: The number is the number of permutations of 15 things 8 at a time P (15, 8) = \frac{15!}{7!}.

B) (10) How many possible exams are there containing at least two questions from each part, if we ignore the order in which the problems are listed?

Answer: The correct way to make this count is to think of the different breakdowns of how many questions can come from each part of the review sheet. There are six possibilities: (4, 2, 2), (2, 4, 2), (2, 2, 4), (3, 3, 2), (3, 2, 3), (2, 3, 3). Hence the number of exams is:

3 · \binom{5}{4}\binom{5}{2}\binom{5}{2} + 3 · \binom{5}{3}\binom{5}{3}\binom{5}{2}

Note: The tempting answer \binom{5}{2}\binom{5}{2}\binom{5}{2}\binom{9}{2} is not correct because it multiple counts. You get the same collection of 8 questions multiple times because the same 4 questions from part I, for instance, could be broken down in different ways as coming from the fixed 2 from part I and questions from the remaining 9. Another common mistake here was to try to do this count using our formulas for multisets. That is not correct because it treats the exam questions as interchangeable. That is certainly not the case for the situation here.

C) (10) How many possible exams are there using between two and four questions from each of the three parts? Again, ignore the ordering of the questions on the exam.

Answer: Same as in part B.

IV. (25) Use an appropriate generating function to answer the following question: 180 pencils are divided into four lots of sizes n_{1}, n_{2}, n_{3}, n_{4} and placed in 4 different classrooms where students are taking a standardized exam. Each room receives at least 20 pencils, and the number of pencils for each room is to be a multiple of 20 . How many different vectors (n_{1}, n_{2}, n_{3}, n_{4}) of numbers of pencils satisfy these conditions?

Answer: The generating function for the number of ways to distribute the pencils is

(t^{20} + t^{40} + ⋯)^{4} = \frac{t^{80}}{(1 − t^{20})^{4}}

We want to determine the coefficient of t^{180} in the expanded form. To simplify, write u = t^{20}. Then we want the coefficient of u^{9} in \frac{u^{4}}{(1−u)^{4}} , or equivalently, the coefficient of u^{5} in \frac{1}{(1−u)^{4}} . By one of our standard series identities, we know:

\frac{1}{(1 − u)^{4}} = ∑_{k=0}^{∞} \binom{k + 3}{3}u^{k}

So the coefficient of u^{5} is \binom{8}{3} = 56.

V. A sequence h_{n} is defined by the recurrence

h_{n} = 6h_{n−1} − 8h_{n−2}

and the initial terms h_{0} = 3, h_{1} = 1. A) (10) Express the generating function of the sequence as a rational function of t.

Answer: The generating function is

H(t) = \frac{3 − 17t}{(1 − 2t)(1 − 4t)}

B) (15) Derive a general formula for the term h_{n} as a function of n.

Answer: Applying the partial fraction decomposition to our answer in part A, we find

H(t) = \frac{3 − 17t}{(1 − 2t)(1 − 4t)} = \frac{\frac{11}{2}}{1 − 2t} + \frac{\frac{−5}{2}}{1 − 4t}

Expanding in geometric series, we get

H(t) = ∑_{n=0}^{∞} \frac{11}{2}2^{n}t^{n} + ∑_{n=0}^{∞} \frac{−5}{2}4^{n}t^{n}

Collecting powers of t, we see

H(t) = ∑_{n=0}^{∞} (\frac{11}{2}2^{n} − \frac{5}{2}4^{n}) t^{n},

so

h_{n} = \frac{11}{2}2^{n} − \frac{5}{2}4^{n}.

VI. A) (5) Define: the rook polynomial of a rectangular board B with each square shaded or

unshaded.

Answer: The rook polynomial is

R(B, t) = ∑_{k=0}^{min(m,n)} r_{k}(B)t^{k},

where r_{k}(B) is the number of placing k non-attacking rooks on the unshaded squares in B.

B) (5) Explain why the coefficient of t^{6} in the rook polynomial of any 5×7 board B must be zero.

Answer: By the Pigeonhole Principle, if we had 6 rooks on B, then two of them would have to be in the same row. That means they are attacking. Hence r_{6}(B) = 0 (and the same is true for r_{k}(B) for all k ≥ 6).

C) (15) Determine the rook polynomial of a 4×4 board in which the shaded and unshaded squares alternate in each row and each column, starting from a shaded square in the upper left corner.

Answer: R(B, t) = 1 + 8t + 20t^{2} + 16t^{3} + 4t^{4}. This can be derived in many different ways. Probably the most economical is to note that in computing R(B, t), we can permute the rows and columns of B any way we like. The reason is that permuting rows and columns does not affect whether rooks can attack each other or not. If we apply this observation here, interchanging rows 2 and 3, then columns 2 and 3 yields a board B′ with 2 × 2 blocks of unshaded squares in the upper right and lower left.

Hence by the product rule R(B, t) = (1 + 4t + 2t^{2})^{2}, which gives the above when we expand(!)

VII. A) (10) State Hall’s “marriage” theorem.

Answer: Let A = (A_{1}, …, A_{n}) be a family of sets. Then an SDR for the family exists if and only if “marriage condition” is satisfied: for all I ⊂ {1, …, n},

|⋃_{i∈I} A_{i}| ≥ |I|.

B) (15) Use Hall’s theorem to show that if G = (X, E, Y) is a bipartite graph with |X| = |Y | = n, in which all vertices have degree d ≥ 1, then the edges of G can be partitioned into d disjoint matchings. (Hint: It may help to think of the (0, 1)−matrix M where m_{ij} = 1 if and only if there is an edge from x_{i} ∈ X to y_{j} ∈ Y.)

Answer: By the condition that all vertices of G have degree d, the matrix described in the hint is an n × n (0,1)-matrix with row and column sums all equal to d. So, this is a restatement of the problem we did before about writing (0, 1)-matrices with constant row and column sum d as sums of d permutation matrices.

Recall, the proof goes as follows. For each i, 1 ≤ i ≤ n, let A_{i} = {j : m_{ij} ≠ 0}, or what is the same, A_{i} is the set of vertices y_{j} in Y such that there is an edge from vertex x_{i} to y_{j}. We claim that the family A = (A_{1}, …, A_{n}) satisfies the “marriage condition”: | ∪_{i∈I} A_{i}| ≥ |I| for all I ⊂ {1, …, n}. We argue by contradiction. If not, then for some I, the entries in the rows of M indexed by I have sum d|I|, but the nonzero entries occur in some number k < |I| columns. This is a contradiction since all of the entries in k columns of M sum to dk, so this would say d|I| ≤ dk, but k < |I|, which is absurd. Hence the marriage condition is satisfied for the family A. This shows that there is an SDR. In matrix terms this means that there is a permutation matrix P such that M = P + M′ where M′ is another (0, 1)-matrix with rows and columns summing to d − 1. Hence we are done by induction on d. In the base case, d = 1, and M = P is a permutation matrix.

Now note that the 1’s in one of the permutation matrices adding up to M correspond to a matching from X to Y in the graph. Hence we have partitioned the edges in G into d disjoint matchings.

VIII. A) (15) State and prove Burnside’s Theorem for group actions.

Answer: See class notes.

B) (10) The corners of an equilateral triangle are colored with p different colors. How many different colorings are there, up to symmetries of the triangle?

Answer: The number is the number of orbits for the action of the symmetry group

G = D_{3} = {I, ρ, ρ^{2}, τ_{1}, τ_{2}, τ_{3}}

on the set X of colorings of the vertices. We have

n = \frac{1}{|D_{3}|} ∑_{g∈D_{3}} |Fix(g)| = \frac{1}{6}(p^{3} + 2p + 3p^{2}).

VIII’. Consider the rectangular 7 × 7 grid L of integer lattice points:

L = {(i, j) : 0 ≤ i ≤ 6, 0 ≤ j ≤ 7} ⊂ R^{2}.

A) (5) Show that if we have a subset S ⊂ L with |S| = 8, then there are two points in S on the same vertical line x = c.

Answer: This follows immediately from the basic form of the Pigeonhole Principle (“pigeonholes” = the 7 different vertical lines, “pigeons” = the 8 points).

B) (10) Show that if we have S ⊂ L with |S| = 15, then some three points in S lie on the same vertical line x = c.

Answer: This follows immediately from the strong form of the Pigeonhole Principle (“pigeonholes” = the 7 different vertical lines, “pigeons” = the 15 points). Since 15 = 2 · 7 + 1, some pigeonhole must get at least 3 pigeons.

C) (10) Consider the points in L and the vertical and horizontal line segments joining them as a graph. Does this graph have an Euler trail? Why or why not?

Answer: No. There are too many vertices of odd degree (note that all 4 · 5 = 20 of the edge vertices other than the 4 corners have degree 3). Recall that Euler trails exist only when the number of odd degree vertices is 0 or 2.