\magnification=\magstep1
\centerline{Mathematics 357 -- Combinatorics}
\centerline{Selected Solutions -- Problem Set 4}
\centerline{March 7, 2005}
\bigskip
\noindent
Chapter 6/13.  We want to count the number of permutations 
of $\{1,2,\ldots,9\}$ in which at least one odd number is 
fixed.  So, let
$$\cases{
S_1 = &permutations where 1 is fixed\cr
S_3 = &permutations where 3 is fixed\cr
\vdots & \cr
S_9 = &permutations where 9 is fixed \cr}$$
We want $|S_1 \cup S_3 \cup \cdots \cup S_9|$.  By 
the ``union form'' of the Inclusion-Exclusion 
Principle, 
$$|S_1 \cup S_3 \cup \cdots \cup S_9|
=\sum_{I \subseteq \{1,3,5,7,9\}} (-1)^{|I|-1} \left| \bigcap_{i\in I} S_i\right|$$
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 ${5\choose 2}$ pairs, and so on.
So the final number is 
$$|S_1 \cup S_3 \cup \cdots \cup S_9| = 5\cdot 8! - {5\choose 2} \cdot 7!
+{5\choose 3}\cdot 6! - {5\choose 4}\cdot 5! + {5\choose 5}\cdot 4!$$
\bigskip
\noindent
16.  The problem asks for a combinatorial proof of the identity
$$n! = D_n + {n \choose 1} D_{n-1} + \cdots + {n\choose n-1} D_1 + {n\choose n}D_0
=\sum_{k=0}^n {n\choose k}D_{n-k}.$$
The left side, $n!$, counts the collection of all permutations of 
$X = \{1,2,3,\ldots,n\}$.  The right side gives the result of counting
this same collection of permutations by using the following partition.
Namely, for each $k$, $0 \le k \le n$,
let $P_k$ be the collection of permutations which leave {\it 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 $\ell \in X$, we have a collection of permutations
in one-to-one correspondence with the derangements of $X - \{\ell\}$.
Hence $|P_1| = {n\choose 1}D_{n-1}$.  Similarly, for each $k$,
$|P_k| = {n\choose k}D_{n-k}$, since there are ${n \choose 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! = \sum_{i=0}^k |P_k| = \sum_{k=0}^n {n\choose k} D_{n-k}.$$
\bigskip
\noindent
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:
$$D_k = k!\left(1 - {1\over 1!} + {1\over 2!} + \cdots + {(-1)^k\over k!}\right)
\leqno(6.3.1)$$
for all $k \ge 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
$$\eqalign{
(n-1)(D_{n-2} + D_{n-1}) &= (n-1)\left(
(n-2)!\left(1 - {1\over 1!} + \cdots + {(-1)^{n-2}\over (n-2)!}\right)\right{}\cr
&\qquad
\left{}+(n-1)!\left(1 - {1\over 1!} + \cdots + {(-1)^{n-1}\over (n-1)!}\right)\right)\cr
&=(n-1)\left(n(n-2)!
\left(1 - {1\over 1!} + \cdots + {(-1)^{n-2}\over (n-2)!}\right) 
+ (-1)^{n-1}\right)\cr
&=n!\left(1 - {1\over 1!} + \cdots + {(-1)^{n-2}\over (n-2)!}\right) 
+ n (-1)^{n-1} + (-1)^n\cr
&= n!\left(1 - {1\over 1!} + \cdots + {(-1)^{n-2}\over (n-2)!} 
+ {(-1)^{n-1}\over (n-1)!} + {(-1)^n\over n!}\right)\cr
&=D_n\cr
}$$
(from 6.3.1).  This is what we wanted to show.
\bigskip
\noindent
Comment:  Note that it is {\it 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!!
\bigskip
\noindent
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\ge 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!\left(1 - {1\over 1!} + {1\over 2!} + \cdots + {(-1)^k\over k!}\right).$$
By assumption and the induction hypothesis we have 
$$\eqalign{D_{k+1} &= (k+1) D_k + (-1)^{k+1}\cr
&= (k+1)k!\left(1 - {1\over 1!} + {1\over 2!} + \cdots + {(-1)^k\over k!}\right)
+(-1)^{k+1}\cr
&=(k+1)!\left(1 - {1\over 1!} + {1\over 2!} + \cdots + {(-1)^k\over k!} + {(-1)^{k+1}\over (k+1)!}\right)
}$$
and that's what we wanted to show!
\bigskip
\noindent
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 + 24 t^3 + 9t^4 + t^5$$
and from the coefficients in this polynomial:
$$\cases{
r_1(\overline{B}) = 5\cr
r_2(\overline{B}) = 22\cr
r_3(\overline{B}) = 24\cr
r_4(\overline{B}) = 9\cr
r_5(\overline{B}) = 1\cr}$$
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\cdot 5! + 22\cdot 4! - 24\cdot 3! + 9\cdot 2! - 1 \cdot 1!$$ 
\bye