Mathematics 357 – Combinatorics Solutions – Midterm Exam 2 April 15, 2005

I. A) A derangement is a permutation that has no fixed points (that is, a permutation of {1, 2, …, n} that leaves none of the integers 1, 2, …, n in their “natural positions”).

B) Let A_{i} be the set of permutations that do fix i (or leave i in its natural position). Then for all I ⊂ {1, 2, …, n}, |∩_{i∈I}A_{i}| = (n − |I|)! since these permutations fix the i ∈ I and permute the other n − |I| integers in all possible ways. There are \binom{n}{k} different ways to choose I with |I| = k for each k. Hence by the Inclusion-Exclusion Principle,

D_{n} = n! + ∑_{I}(−1)^{|I|} |∩_{i∈I}A_{i}|

= n! + ∑_{k=1}^{n}(−1)^{k}\binom{n}{k}(n − k)!

= n! + ∑_{k=1}^{n}(−1)^{k} \frac{n!}{k!(n − k)!}(n − k)!

= n! + ∑_{k=1}^{n}(−1)^{k} \frac{n!}{k!}

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

which is what we had to show.

II. A) The rook polynomial R(B, t) of B is the generating function for the sequence r_{k}(B) = number of ways to place k non-attacking rooks on the unshaded squares in B. That is:

R(B, t) = ∑_{k} r_{k}(B)t^{k}.

B) The given forbidden positions for the permutations correspond to the shaded squares in B below. We are looking for the number of ways to place 5 non-attacking rooks on B. We also show the complementary board \overline{B}, since we will compute r_{5}(B) by using the formula in Theorem 6.4.1 in the text. Note that \overline{B} splits into two row- and column-disjoint sub-boards B_{1} and B_{2}:

Hence by the product rule

R(\overline{B}, t) = R(B_{1}, t)R(B_{2}, t) = (1 + 4t + 3t^{2})(1 + 4t + 3t^{2}) = 1 + 8t + 22t^{2} + 24t^{3} + 9t^{4} and then the number of ways to place 5 non-attacking on B is r_{5}(B) = 5! − r_{1}(\overline{B}) · 4! + r_{2}(\overline{B}) · 3! − r_{3}(\overline{B}) · 2! + r_{4}(\overline{B}) · 1! = 5! − 8 · 4! + 22 · 3! − 24 · 2! + 9 · 1!

III. A) The characteristic polynomial is

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

so the roots are q = 1, 2 and

h_{n} = c_{1} + c_{2} · 2^{n}

for some c_{1} and c_{2}. From the initial conditions,

\begin{aligned}c_{1} + c_{2} & = 1 \\ c_{1} + 2c_{2} & = 3 \end{aligned}

so c_{1} = −1 and c_{2} = 2. B) The generating function is

H(t) = \frac{1}{1 − 3t + 2t^{2}} = \frac{1}{(1 − t)(1 − 2t)}.

Decomposing in partial fractions,

H(t) = \frac{A}{1 − t} + \frac{B}{1 − 2t},

which implies

1 = A(1 − 2t) + B(1 − t).

Setting t = 1, we get A = −1; with t = 1/2, we get B = 2. Therefore, expanding in geometric series, we have

\begin{matrix}H(t) = ∑_{n=0}^{∞} h_{n}t^{n} = \frac{1}{1 − t} + \frac{2}{1 − 2t} \\ = ∑_{n=0}^{∞} (1 + 2 · 2^{n}) t^{n} \end{matrix}

This checks that h_{n} = 1 + 2 · 2^{n}. IV. A) Hall’s theorem states that the family of sets A = (A_{1}, …, A_{n}) has an SDR if and only if the “marriage condition” is satisfied: for all subsets I ⊆ {1, 2, …, n},

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

B) Label the musicians {1, 2, …, n} and let A_{i} be the set of pieces assigned to musician i. Then a concert as described, in which all n musicians play different pieces from the ones they are assigned, is the same as an SDR for the family A = (A_{1}, …, A_{n}). Hall’s Theorem says that we can find such an SDR if and only if the marriage condition is satisfied. But here, since each musician is assigned exactly d different pieces, if we pick any subset of them (corresponding to some I ⊆ {1, 2, …, n}) and have them list their pieces, we will have exactly d · |I| pieces in the list (with duplicates). On the other hand, since no piece is assigned to more than d different musicians, there must be at least \frac{d·|I|}{d} distinct pieces of music. In other words, for all I,

|⋃_{i∈I} A_{i}| ≥ \frac{d · |I|}{d} = |I|.

This says the marriage condition is satisfied, so such a concert can be given in all cases(!)

V. The sum of the degrees of all the vertices in the graph G = (V, E) is

∑_{v∈V} deg(v) = 2|E|

since each edge has two different endpoints. This implies that the number of vertices of odd degree has to be even (since otherwise the sum on the left above would be odd!)

Extra Credit

The recurrence is t_{n} = t_{n−1} + t_{n−3}, since every arrangement in the 3 × n tray either begins with one vertical triominoe or 3 stacked horizontal triominoes. (We can use the Addition Rule rather than Inclusion-Exclusion because there cannot be any arrangements of both types).