\magnification=\magstep1
\centerline{Mathematics 357 -- Combinatorics}
\centerline{Selected Solutions -- Problem Set 5}
\centerline{March 21, 2005}
\bigskip
\noindent
Chapter 6/31.  Let $p_1,\ldots, p_k$ be all of the primes dividing
$n$, and let 
$$S_i = \{\ell : 1 \le \ell \le n, p_i | \ell\}$$
for each $i = 1, \ldots, k$.  We want to count the set of $\ell$
in the range $1 \le \ell \le n$ such that $\gcd(\ell,n) = 1$.
This is equivalent to saying that none of the $p_i$ divide $\ell$.
Hence, our goal is to count $\overline{S_1} \cap \cdots \cap \overline{S_k}$. 
By the Inclusion-Exclusion Principle,
$$\eqalign{
|\overline{S_1} \cap \cdots \cap \overline{S_k}|
&= n - \sum_{I \subseteq \{1,\ldots,n\}} (-1)^{|I|-1} \left|\bigcap_{i\in I} S_i\right|\cr
&= n - \sum_i |S_i| + \sum_{i,j} |S_i \cap S_j| - \sum_{i,j,k} |S_i \cap S_j\cap S_k|
   + \cdots \cr
&= n - \sum_i {n \over p_i} + \sum_{i,j} {n\over p_ip_j} - 
\sum_{i,j,k} {n\over p_ip_jp_k} + \cdots \cr}\leqno(1)$$
(The last line follows since as always the number of integers in the 
range $1 \le \ell \le N$ such that $q$ divides $\ell$ is 
$\lfloor {N\over q}\rfloor$.  Since all the primes $p_i$ actually
divide $n$ in our case, we do not need the $\lfloor, \rfloor$.)
We claim that the last line here is equal to the product 
$$n\prod_{i=1}^k \left(1 - {1\over p_i}\right) = n 
\left(1 - {1\over p_1}\right)\cdot\left(1 - {1\over p_2}\right)\cdot \cdots \cdot
\left(1 - {1\over p_k}\right).$$ 
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 - {n \over p_1} = n\left(1 - {1\over p_1}\right)$$
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 ${1\over 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\left(1 - {1\over p_{m+1}}\right)\cdot \left(1 - \sum_{i\ne m+1} {1\over p_i} 
+ \sum_{i,j\ne m+1} {1\over p_ip_j} - \cdots\right)$$
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\prod_{i=1}^{m+1} \left(1 - {1\over p_i}\right)$$
which concludes the proof.
\bigskip
\noindent
Chapter 6/32. (Refer to the {\it second} corrected version of the problem!)
\bigskip
\noindent
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 + {1\choose 1} t + \cdots $$
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 \le 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
$$\eqalign{
R(B_{k+1},t) &= R(B_k,t) + tR(B_{k-1},t)\cr
&= 1 + {k\choose 1} t + {k-1\choose 2}t^2 + {k-2\choose 3} t^3 + \cdots \cr
&\qquad +t\left(1 + {k-1\choose 1} t + {k-2\choose 2}t^2 + {k-3\choose 3} t^3 + \cdots\right)\cr
&= 1 + \left({k\choose 1} + {k\choose 0}\right)t +\left({k-1\choose 2} + {k-1\choose 1}\right)t^2\cr
&\qquad + \cdots + \left({k-\ell+1\choose \ell} + {k - \ell + 1\choose \ell - 1}\right)t^\ell + \cdots}$$
By the Pascal's Triangle identity ${n\choose k} + {n \choose k-1} = {n + 1 \choose k}$,
this last sum equals:
$$1 + {k+1\choose 1} t + {k \choose 2} t^2 + \cdots + {k + 2 - \ell\choose \ell} t^\ell + \cdots $$
and this is what we wanted to show.
\bigskip
\noindent
B)  Now consider the complement of the $n\times 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,
$$\eqalign{
R(\overline{B},t) &= R(B_{2n-1},t) + tR(B_{2n-3},t)\cr
&= 1 + {2n - 1\choose 1} t + \cdots + {2n - \ell\choose \ell} t^\ell + \cdots \cr
&\qquad 
+ t\left(1 + {2n-3\choose 1} t + \cdots + {2n - 2 - \ell\choose \ell} t^\ell + \cdots \right)\cr}$$
Collecting like powers of $t$, the coefficient of $t^\ell$ is
$$
\eqalign{
{2n - \ell \choose \ell} + {2n - \ell - 1\choose \ell - 1}
&= {(2n-\ell)!\over  \ell! (2n - 2\ell)!} + {(2n - \ell - 1)! \over (\ell-1)!(2n-2\ell)!}\cr
&= {(2n-\ell)! \over \ell! (2n - 2\ell)!} \cdot \left( 1 + {\ell\over 2n - \ell}\right)\cr
&={2n - \ell \choose \ell} {2n\over 2n - \ell}\cr}$$
as claimed.
\bigskip
\noindent
C)  To finish and compute the number of ways of placing $n$ non-attacking
rooks on the $n\times 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) = \sum_{\ell=0}^n (-1)^{\ell} (n-\ell)! r_\ell(\overline{B})
= \sum_{\ell=0}^n (-1)^\ell (n-\ell)! {2n\over 2n-\ell} {2n - \ell \choose \ell}$$
\bigskip
\noindent
Chapter 7/1c.  By examining the alternating sums
$$a_n = f_0 - f_1 + f_2 + \cdots + (-1)^n f_n$$
we see that for $n\ge 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
$$\eqalign{
a_{k+1} &= f_0 - f_1 + f_2 + \cdots + (-1)^k f_k + (-1)^{k+1} f_{k+1}\cr
&= a_k + (-1)^{k+1} f_{k+1}\cr
&= (-1)^k f_{k-1} - 1 + (-1)^{k+1} f_{k+1}\ {\rm (by\ induction\ hypothesis)}\cr
&= (-1)^{k+1}(f_{k+1}-f_{k-1}) - 1\cr
&= (-1)^{k+1}f_k - 1\cr}$$
(at the last step we used the Fibonacci recurrence
$f_{k+1} = f_k + f_{k-1}$).
\bigskip
\noindent
Chapter 7/8.  Consider any $1\times n$ board colored with no two
adjacent red squares.  If the $n$th square is blue, then the first
$n-1$ squares can be any $1\times (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 \times (n-2)$ boards.  Every $1\times n$ board
falls into one of these cases, and we never get the same
$1\times 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 = {1 \pm \sqrt{5}\over 2}$, and the general
solution is 
$$h_n = c_1 \left({1 + \sqrt{5}\over 2}\right)^n + c_2 \left({1 - \sqrt{5}\over 2}\right)^n$$
Solving for $c_1$ and $c_2$ from the initial conditions, we get
$$c_1 = {5 + 3\sqrt{5}\over 10}, \qquad c_2 = {5 - 3\sqrt{5}\over 10}$$
\end
