Mathematics 357 – Combinatorics Midterm Exam 2 April 15, 2005

Directions

Do the following problems I-V in the blue exam booklet. There are 100 regular points and 10 Extra Credit points.

I. A) (10) Define: a derangement of X = {1, 2, …, n}. A) (15) Show that the number of derangements of X, D_{n}, satisfies

D_{n} = n! (1 − \frac{1}{1!} + \frac{1}{2!} − \frac{1}{3!} + ⋯ + (−1)^{n} \frac{1}{n!}) .

II. A) (10) Define: the rook polynomial of a rectangular board B with each square shaded

or unshaded. B) (15) Using rook polynomials, determine the number of permutations abcde of the set

{1, 2, 3, 4, 5} such that a ∉ {2, 3}, b ∉ {1, 2}, c ∉ {5}, d ∉ {4}, e ∉ {4, 5}.

III. A sequence c_{n} is defined by the recurrence h_{n} = 3h_{n−1}−2h_{n−2} and the initial conditions h_{0} = 1, h_{1} = 3. A) (10) Derive a general formula for the term h_{n} as a function of n. B) (10) Check your work in A by using the generating function method to solve the

recurrence.

IV. A) (10) Give a precise statement of Hall’s “Marriage” Theorem. B) (10) A number n of musicians are participating in a competition. Each has been

assigned d different pieces of music to prepare, and no single piece has been assigned to more than d different musicians. Is it possible to compile a concert program on which each musician will perform, and on which no piece will be performed twice? Prove your assertion.

V. (10) Show that in any graph G = (V, E), there are an even number of vertices of odd degree (possibly 0 of them).

Extra Credit (10) A “triominoe” is a 1 × 3 rectangle:

For each positive integer n, let t_{n} be the number of ways of arranging n triominoes in a 3 × n tray with no overlapping. For instance, t_{3} = 2, since we have the following two arrangements

Find a recurrence relation of order 3 for the t_{n} sequence. (Don’t try to solve it.)