Mathematics 357 – Combinatorics Final Examination May 12, 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? 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?

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?

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}

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 pos-

sible exams are there? 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? 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.

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?

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. B) (15) Derive a general formula for the term h_{n} as a function of n.

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

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

be zero. 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.

VII. A) (10) State Hall’s “marriage” theorem. B) (15) Use Hall’s theorem to show that if G = (X, E, Y) is a bipartite graph, in which

|X| = |Y | and 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.)

VIII. A) (15) State and prove Burnside’s Theorem for group actions. 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?

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

L = {(i, j) : 0 ≤ i ≤ 6, 0 ≤ j ≤ 6} ⊂ 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. 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. 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?

Have a productive, safe, and enjoyable summer!