Mathematics 357 – Combinatorics Selected Solutions – Problem Set 4 March 7, 2005

Chapter 6/13. We want to count the number of permutations of {1, 2, …, 9} in which at least one odd number is fixed. So, let

S_{1} = permutations where 1 is fixed
S_{3} = permutations where 3 is fixed
⋮
S_{9} = permutations where 9 is fixed

We want |S_{1} ∪ S_{3} ∪ ⋯ ∪ S_{9}|. By the “union form” of the Inclusion-Exclusion Principle,

|S_{1} ∪ S_{3} ∪ ⋯ ∪ S_{9}| = ∑_{I⊆{1,3,5,7,9}}(−1)^{|I|−1} |⋂_{i∈I} S_{i}|

When |I| = 1, we have 8! permutations fixing exactly one element, and 5 odd numbers. When |I| = 2, we have 7! permutations fixing exactly one pair of elements, and \binom{5}{2} pairs, and so on. So the final number is

|S_{1} ∪ S_{3} ∪ ⋯ ∪ S_{9}| = 5 · 8! − \binom{5}{2} · 7! + \binom{5}{3} · 6! − \binom{5}{4} · 5! + \binom{5}{5} · 4!

16. The problem asks for a combinatorial proof of the identity

n! = D_{n} + \binom{n}{1}D_{n−1} + ⋯ + \binom{n}{n − 1}D_{1} + \binom{n}{n}D_{0} = ∑_{k=0}^{n} \binom{n}{k}D_{n−k}.

The left side, n!, counts the collection of all permutations of X = {1, 2, 3, …, n}. The right side gives the result of counting this same collection of permutations by using the following partition. Namely, for each k, 0 ≤ k ≤ n, let P_{k} be the collection of permutations which leave exactly k elements fixed (i.e. “in their natural positions”). Then P_{0} is the set of derangements and |P_{0}| = D_{n}. P_{1} is the collection of permutations with exactly one fixed point. That fixed point can be any one of the n elements of X, and elements of P_{1} must “move” all the other n − 1 elements of X. Hence for each ℓ ∈ X, we have a collection of permutations in one-to-one correspondence with the derangements of X − {ℓ}. Hence |P_{1}| = \binom{n}{1}D_{n−1}. Similarly, for each k, |P_{k}| = \binom{n}{k}D_{n−k}, since there are \binom{n}{k} ways to select the k fixed points in X, and each permutation in P_{k} must act as a derangement of the other n − k elements of X. The P_{k} are disjoint, so by the Addition Rule, we have

n! = ∑_{i=0}^{k} |P_{k}| = ∑_{k=0}^{n} \binom{n}{k}D_{n−k}.

19. The problem asks to show that

D_{n} = (n − 1)(D_{n−2} + D_{n−1})

using the result of Theorem 6.3.1 (that is, the formula:

(6.3.1)  D_{k} = k! (1 − \frac{1}{1!} + \frac{1}{2!} + ⋯ + \frac{(−1)^{k}}{k!} )

for all k ≥ 1.) The simplest way to show this is just to rearrange the sum algebraically, using the simple observation that (n − 1)! + (n − 2)! = (n − 1 + 1)(n − 2)! = n(n − 2)!. Starting from the sum on the right, substituting from 6.3.1, and noting that the sums for D_{n−2} and D_{n−1} contain many common terms, we get

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

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

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

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

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

= D_{n}

(from 6.3.1). This is what we wanted to show.

Comment: Note that it is not necessary to set this up as a proof by induction. In fact many people said they were doing an induction proof and then presented something like the above. If you’re not actually using an induction hypothesis, then it isn’t a proof by induction, and you shouldn’t say it is!!

20. This one is very simple if you do do a proof by induction. The goal is to prove the formula from (6.3.1) for all n ≥ 2 using the relation D_{n} = nD_{n−1}+(−1)^{n}. We have D_{1} = 0 so D_{2} = 2D_{1} + (−1)^{2} = 1. The formula in (6.3.1) also gives D_{2} = 1. So we have our base case for the induction. Now assume that (6.3.1) is true for n = k:

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

By assumption and the induction hypothesis we have

D_{k+1} = (k + 1)D_{k} + (−1)^{k+1}

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

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

and that’s what we wanted to show!

24 c) The given board can be split into two smaller blocks since the top three rows don’t have excluded positions (X’s) in the same columns as rows 4 and 5. The rook polynomial of the complementary board is

R(\overline{B}, t) = (1 + 5t + 6t^{2} + t^{3})(1 + 3t + t^{2}) = 1 + 8t + 22t^{2} + 24t^{3} + 9t^{4} + t^{5}

and from the coefficients in this polynomial:

\{ \begin{matrix}r_{1}(\overline{B}) = 5 \\ r_{2}(\overline{B}) = 22 \\ r_{3}(\overline{B}) = 24 \\ r_{4}(\overline{B}) = 9 \\ r_{5}(\overline{B}) = 1 \end{matrix}

By 6.4.1, the number of ways of placing 6 non-attacking rooks on the un-X’ed squares in the given board B is:

r_{6}(B) = 6! − 8 · 5! + 22 · 4! − 24 · 3! + 9 · 2! − 1 · 1!