Mathematics 357 – Combinatorics Selected Solutions – Problem Set 5 March 21, 2005

Chapter 6/31. Let p_{1}, …, p_{k} be all of the primes dividing n, and let

S_{i} = {ℓ : 1 ≤ ℓ ≤ n, p_{i}|ℓ}

for each i = 1, …, k. We want to count the set of ℓ in the range 1 ≤ ℓ ≤ n such that gcd(ℓ, n) = 1. This is equivalent to saying that none of the p_{i} divide ℓ. Hence, our goal is to count \overline{S_{1}} ∩ ⋯ ∩ \overline{S_{k}}. By the Inclusion-Exclusion Principle,

(1)  \begin{aligned}|\overline{S_{1}} ∩ ⋯ ∩ \overline{S_{k}}| & = n − ∑_{I⊆\{1,...,n\}}(−1)^{|I|−1} |⋂_{i∈I} S_{i}| \\ & = n − ∑_{i} |S_{i}| + ∑_{i,j} |S_{i} ∩ S_{j}| − ∑_{i,j,k} |S_{i} ∩ S_{j} ∩ S_{k}| + ⋯ \\ & = n − ∑_{i} \frac{n}{p_{i}} + ∑_{i,j} \frac{n}{p_{i}p_{j}} − ∑_{i,j,k} \frac{n}{p_{i}p_{j}p_{k}} + ⋯ \end{aligned}

(The last line follows since as always the number of integers in the range 1 ≤ ℓ ≤ N such that q divides ℓ is ⌊\frac{N}{q} ⌋. Since all the primes p_{i} actually divide n in our case, we do not need the ⌊, ⌋.) We claim that the last line here is equal to the product

n ∏_{i=1}^{k} (1 − \frac{1}{p_{i}} ) = n (1 − \frac{1}{p_{1}} ) · (1 − \frac{1}{p_{2}} ) · · · · · (1 − \frac{1}{p_{k}} ) .

Here’s a formal proof of that fact, by induction on the number of factors (same as the number of distinct primes dividing n). The base case is k = 1. In that case the sum in the last line of (1) is just

n − \frac{n}{p_{1}} = n (1 − \frac{1}{p_{1}} )

and we have the desired result. Now assume the formula works whenever there are k = m distinct primes, and consider the expansion in (1) with k = m+1 distinct primes. Regroup the terms in (1) into two sums: those not containing p_{m+1}, and those that do contain p_{m+1}. By the way (1) is constructed when we do this and factor out \frac{1}{p_{m+1}} from the terms that do contain that prime, what is left is the same as the other group of terms. In other words, we get

n (1 − \frac{1}{p_{m+1}} ) · (1 − ∑_{i≠m+1} \frac{1}{p_{i}} + ∑_{i,j≠m+1} \frac{1}{p_{i}p_{j}} − ⋯)

The last factor here has the same form as (1) but only involves m primes. So by induction, it factors similarly, and we get

n ∏_{i=1}^{m+1} (1 − \frac{1}{p_{i}} )

which concludes the proof.

Chapter 6/32. (Refer to the second corrected version of the problem!)

A) We show this by induction on m, the number of unshaded squares in the “staircase”. The base case m = 1 is a single unshaded square. This has rook polynomial:

R(B_{1}, t) = 1 + t = 1 + \binom{1}{1}t + ⋯

since all the other terms in the general form are zero when m = 1. Now assume that the formula works for all B_{m} with m ≤ k, and consider the staircase board with m = k + 1 squares. Let s be the last unshaded square in the staircase. If we shade that in, we get B_{k}. If we delete the row and column containing the last square, we get B_{k−1}. Hence by the expansion formula, and our induction hypothesis

R(B_{k+1}, t) = R(B_{k}, t) + tR(B_{k−1}, t)

= 1 + \binom{k}{1}t + \binom{k − 1}{2}t^{2} + \binom{k − 2}{3}t^{3} + ⋯

+ t (1 + \binom{k − 1}{1}t + \binom{k − 2}{2}t^{2} + \binom{k − 3}{3}t^{3} + ⋯)

= 1 + (\binom{k}{1} + \binom{k}{0}) t + (\binom{k − 1}{2} + \binom{k − 1}{1}) t^{2}

+ ⋯ + (\binom{k − ℓ + 1}{ℓ} + \binom{k − ℓ + 1}{ℓ − 1}) t^{ℓ} + ⋯

By the Pascal’s Triangle identity \binom{n}{k} + \binom{n}{k−1} = \binom{n+1}{k}, this last sum equals:

1 + \binom{k + 1}{1}t + \binom{k}{2}t^{2} + ⋯ + \binom{k + 2 − ℓ}{ℓ}t^{ℓ} + ⋯

and this is what we wanted to show.

B) Now consider the complement of the n×n board given in the problem in the book. This is the staircase B_{2n−1} together with the single unshaded square in the lower left corner. If we shade in that single square, we get B_{2n−1}. If we delete the row and column containing that, we get a “transposed” B_{2n−3} staircase. The transposition does not change the rook polynomial because the placements of rooks on the transposed board are in one-to-one correspondence with the rook placements on B_{2n−3}. Hence by the expansion rule again, and part A,

R(\overline{B}, t) = R(B_{2n−1}, t) + tR(B_{2n−3}, t)

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

+ t (1 + \binom{2n − 3}{1}t + ⋯ + \binom{2n − 2 − ℓ}{ℓ}t^{ℓ} + ⋯)

Collecting like powers of t, the coefficient of t^{ℓ} is

\binom{2n − ℓ}{ℓ} + \binom{2n − ℓ − 1}{ℓ − 1} = \frac{(2n − ℓ)!}{ℓ!(2n − 2ℓ)!} + \frac{(2n − ℓ − 1)!}{(ℓ − 1)!(2n − 2ℓ)!}

= \frac{(2n − ℓ)!}{ℓ!(2n − 2ℓ)!} · (1 + \frac{ℓ}{2n − ℓ})

= \binom{2n − ℓ}{ℓ}\frac{2n}{2n − ℓ}

as claimed.

C) To finish and compute the number of ways of placing n non-attacking rooks on the n × n board B as in the problem in the book, we use Theorem 6.4.1 (which comes from Inclusion-Exclusion). That number is

r_{n}(B) = ∑_{ℓ=0}^{n}(−1)^{ℓ}(n − ℓ)!r_{ℓ}(\overline{B}) = ∑_{ℓ=0}^{n}(−1)^{ℓ}(n − ℓ)!\frac{2n}{2n − ℓ}\binom{2n − ℓ}{ℓ}

Chapter 7/1c. By examining the alternating sums

a_{n} = f_{0} − f_{1} + f_{2} + ⋯ + (−1)^{n}f_{n}

we see that for n ≥ 1, a_{n} is always one less than f_{n−1} if n is even and one less than −f_{n−1} if n is odd. In other words, we conjecture

a_{n} = (−1)^{n}f_{n−1} − 1.

To prove this by induction, we first consider the base case n = 1. a_{1} = f_{0}−f_{1} = 0−1 = −1. But also, (−1)^{1}f_{0} − 1 = 0 − 1 = −1. So the base case is established. Now assume that a_{k} = (−1)^{k}f_{k−1} − 1 and consider a_{k+1}. We have

a_{k+1} = f_{0} − f_{1} + f_{2} + ⋯ + (−1)^{k}f_{k} + (−1)^{k+1}f_{k+1}
= a_{k} + (−1)^{k+1}f_{k+1}
= (−1)^{k}f_{k−1} − 1 + (−1)^{k+1}f_{k+1} (by induction hypothesis)
= (−1)^{k+1}(f_{k+1} − f_{k−1}) − 1
= (−1)^{k+1}f_{k} − 1

(at the last step we used the Fibonacci recurrence f_{k+1} = f_{k} + f_{k−1}).

Chapter 7/8. Consider any 1 × n board colored with no two adjacent red squares. If the nth square is blue, then the first n − 1 squares can be any 1 × (n − 1) board colored according to our restriction. If the last square is red, then the preceding square must be blue, and then the first n − 2 squares form any one of the allowable 1 × (n − 2) boards. Every 1 × n board falls into one of these cases, and we never get the same 1 × n board twice since the last two squares are not the same. Hence h_{n} = h_{n−1} + h_{n−2}. The initial conditions are h_{0} = 1 (convention – “the empty coloring”), and h_{1} = 2. The characteristic polynomial of the recurrence is q^{2} − q − 1 = 0, so q = \frac{1±\sqrt{5}}{2}, and the general solution is

h_{n} = c_{1} (\frac{1 + \sqrt{5}}{2})^{n} + c_{2} (\frac{1 − \sqrt{5}}{2})^{n}

Solving for c_{1} and c_{2} from the initial conditions, we get

c_{1} = \frac{5 + 3\sqrt{5}}{10}, c_{2} = \frac{5 − 3\sqrt{5}}{10}