\magnification=\magstep1
\centerline{Mathematics 357 -- Combinatorics}
\centerline{Solutions -- Midterm Exam 2}
\centerline{April 15, 2005}
\bigskip
\noindent
I.  A)  A derangement is a permutation that has no fixed points
(that is, a permutation of $\{1,2,\ldots, n\}$ that leaves
none of the integers $1,2,\ldots,n$ in their ``natural positions'').
\bigskip
\noindent
B)  Let $A_i$ be the set of permutations that do fix $i$ (or leave
$i$ in its natural position).  Then for all $I \subset \{1,2,\ldots,n\}$,
$\left|\cap_{i\in I}A_i \right| = (n - |I|)!$  since these permutations
fix the $i\in I$ and permute the other $n - |I|$ integers in all possible
ways.  There are ${n \choose k}$ different ways to choose $I$ with $|I| = k$
for each $k$.  Hence by the Inclusion-Exclusion Principle,
$$\eqalign{D_n &=
n! + \sum_{I} (-1)^{|I|} \left|\cap_{i\in I}A_i \right|\cr
&= n! + \sum_{k=1}^n (-1)^k {n\choose k} (n-k)!\cr
&= n! + \sum_{k=1}^n (-1)^k {n!\over k! (n-k)!} (n-k)!\cr
&= n! + \sum_{k=1}^n (-1)^k {n!\over k!}\cr
&= n!\left(1 - 1 + {1\over 2!} + {1\over 3!}+ \cdots + {(-1)^n\over n!}\right)\cr}$$
which is what we had to show.
\bigskip
\noindent
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) = \sum_k r_k(B) t^k.$$
\bigskip
\noindent
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$:
\vglue 1.0truein
\noindent
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})\cdot 4! + r_2(\overline{B})\cdot 3! -
r_3(\overline{B})\cdot 2! +
r_4(\overline{B})\cdot 1!  = 5! - 8\cdot 4! + 22\cdot 3! - 24\cdot 2! + 9\cdot 1!$$
\bigskip
\noindent
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 \cdot 2^n$$
for some $c_1$ and $c_2$.  From the initial conditions,
$$\eqalign{c_1 + c_2 &= 1\cr 
           c_1 + 2c_2 &=3\cr}$$
so $c_1 = -1$ and $c_2 = 2$.  
\bigskip
\noindent
B)  The generating function is 
$$H(t) = {1\over 1 - 3t + 2t^2} = {1\over (1 - t)(1 - 2t)}.$$
Decomposing in partial fractions,
$$H(t) = {A\over 1-t} + {B \over 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
$$\eqalign{H(t) = \sum_{n=0}^\infty h_n t^n = {1\over 1-t} + {2\over 1 - 2t}\cr
= \sum_{n=0}^\infty \left(1 + 2\cdot 2^n\right)t^n\cr}$$
This checks that $h_n = 1 + 2\cdot 2^n$.
\bigskip
\noindent
IV.  A)  Hall's theorem states that the family of sets 
${\cal A} = (A_1,\ldots, A_n)$ has an SDR if and only if the ``marriage
condition'' is satisfied:  {\it for
all subsets $I \subseteq \{1,2,\ldots,n\}$}, 
$$\left|\bigcup_{i\in I} A_i\right| \ge |I|.$$
\bigskip
\noindent
B)  Label the musicians $\{1,2,\ldots,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, {\it is the same as an SDR for the family
${\cal A} = (A_1,\ldots, 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 \subseteq \{1,2,\ldots, n\}$) and 
have them list their pieces, we
will have exactly $d \cdot |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 
${d \cdot |I|\over d}$ distinct pieces of music.  In other words,
for all $I$,
$$\left|\bigcup_{i\in I} A_i\right| \ge {d\cdot |I|\over d} = |I|.$$
This says the marriage condition is satisfied, so such a concert
can be given in all cases(!)
\bigskip
\noindent
V.  The sum of the degrees of all the vertices in the graph $G = (V,E)$
is
$$\sum_{v\in 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!)
\bigskip
\noindent
{\it Extra Credit}
\bigskip
The recurrence is $t_n = t_{n-1} + t_{n-3}$, since 
every arrangement in the $3\times 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).
\bye