\magnification=\magstep1
\overfullrule=0pt
\centerline{MATH 357 -- Combinatorics}
\centerline{Solutions for Review Problems for Final Exam}
\centerline{May 1, 2017}
\bigskip
\noindent
1.3.13.  Let $H$ be the set of guests who have a hamburger and let $D$
be the set who have a hot dog.  The given information is $|H| = 25$, $|D| = 18$, 
and $|H\cap D| = 10$. Since it is given that everyone had either a hamburger
or a hot dog, the set of guests is $H \cup D$ and by the Inclusion-Exclusion
Principle, 
$$|H\cup D| = |H| + |D| - |H\cap D| = 25 + 18 - 10 = 33.$$

\noindent
1.4.8.  If $\sigma,\tau$ are both bijections of $X$, then consider $\sigma\circ\tau$.
If $(\sigma\circ\tau)(x) = (\sigma\circ\tau)(x')$, the $\sigma(\tau(x)) = \sigma(\tau(x'))$.
Since $\sigma$ is injective (one-to-one), this implies $\tau(x) = \tau(x')$.  But
then $x = x'$ since $\tau$ is also injective.  This shows $\sigma\circ\tau$ is injective.
Now, let $x \in X$ be arbitrary.  Since $\sigma$ is surjective (onto), there is some $y \in X$
such that $\sigma(y) = x$.  But $\tau$ is also surjective, so there is some $z \in X$
such that $y = \tau(z)$.  Substituting this into the previous equation gives
$\sigma(\tau(z)) = (\sigma\circ\tau)(z) = x$.
Since $x$ was arbitrary, this shows $\sigma\circ\tau$ is surjective as well, hence bijective.
\bigskip
\noindent
1.5.7.  (This problem is very like Example 1.5.3 in the text.)  Let $a_1,\ldots,a_{32}$ be
the number of math problems done after day 1, day 2, ..., day 32.  We have
$a_{32} \le {9\over 8}\cdot 32 = 36$.  Now consider the ``pigeons'' to be the 
numbers 
$$a_1,a_2,\ldots,a_{32}, a_1 + 27, a_2 + 27,\ldots,a_{32} + 27$$
and the ``pigeonholes'' to be the number values.  We have $32 + 32 = 64$ numbers
in the range $1$ to $36 + 27 = 63$.  Hence two of them must be the same, say 
$$a_i = a_j + 27.$$
The $a_i$ are strictly increasing with $i$, so we must have $i > j$ here, hence
$a_i - a_j = 27$ and this represents the number of problems done between day $j+1$
and day $i$, a consecutive string of days.  This is what we wanted to show.
\bigskip
\noindent
2.1.22.  Note: I'm assuming the whole password consists of 
8 characters.) (i) $26^6 \cdot 10^2$ ( (ii) $25 \cdot 26^5 \cdot 10^2$.  (iii)  $26^6 \cdot 99$ (iv)  $25\cdot 26^5 \cdot 99$.  
\bigskip
\noindent
2.2.9.  By the Inclusion-Exclusion Principle, the number is 
$$26^5 + 25^6 - 25^5$$
(the last term is the number of words that begin with $a$ and contain no $b$).
\bigskip
\noindent
2.3.9.  The number depends on whether $n$ is even or odd.  If $n$ is even there
are $n/2$ odds and $n/2$ evens in $[n]$.  To make a permutation with evens and 
odds alternating, we can either begin with and even or an odd.  The total number 
is $2\cdot (n/2)! (n/2)!$.  For instance, with $n = 4$, there are 8 such permutations.
In the ``one-row'' format (not cycle decomposition), they are:
$$(1234),(1432),(3214),(3412),(2143),(2341),(4123),(4321).$$
If $n$ is odd, then there are $(n+1)/2$ odds and $(n-1)/2$ evens in $[n]$.  To 
make one of the required permutations, we must start with an odd (i.e. 1 must map to an odd).
Otherwise, we ``run out'' of evens before odds.  There are $((n-1)/2)!((n+1)/2)!$ such
permutations.  For instance, with $n = 5$, there are 12 such permutations.  (Write them down
to make sure you understand!)
\bigskip
\noindent
2.4.8.  We use Corollary 2.4.2 and Inclusion-Exclusion.  There
are
$$\lfloor {10000\over 3}\rfloor = 476$$
numbers divisible by $21 = 3\cdot 7$, 
$$\lfloor {10000\over 33}\rfloor = 303$$
numbers divisible by $33 = 3\cdot 11$, and
$$\lfloor {10000\over 231}\rfloor = 43$$
numbers divisible by $231 = 3 \cdot 7\cdot 11$.  
Hence the number divisible by 21 or 33 is 
$$476 + 303 - 43 = 736.$$
\noindent
2.5.9.  Let $I,II,III,IV$ be the sets of elections where
conditions (i),(ii),(iii),(iv) respectively are satisfied.  Note that 
$|I| = P(19,3) = 19\cdot 18\cdot 17 = 5814$ (the other three positions are three other distinct people).
We also have $|II| = P(19,3) = 19 \cdot 18 \cdot 17 = 5814$, 
but $|I \cap II| = P(18,2) = 18\cdot 17 = 306$.
Then $|III| = 18\cdot 17\cdot 2 = 612$ and $|IV| = P(18,4) = 18\cdot 17\cdot 16\cdot 15 = 73440$.  
Now the set where at least one condition is satisfied is $I \cup II \cup III \cup IV$.
Note that $(I \cup II) \cap III = \emptyset$, $(I \cup II) \cap IV = \emptyset$, 
$III \cap IV = \emptyset$.  Hence by the Addition Principle, and Inclusion-Exclusion, we have
$$|(I \cup II)\cup III\cup IV| = |I\cup II| + |III| + |IV| = (5814 + 5814 - 306) + 612 + 73440 = 85347.$$
(There are $20 \cdot 19 \cdot 18 \cdot 17 = P(20,4) = 116280$ total different election outcomes.)
\bigskip
\noindent
2.7.15.  The number is
$$\left({P(25,8)\over 8}\right)\left({P(17,8)\over 8}\right)\left({P(9,6)\over 6}\right)$$
(The last three numbers go into the three 1-cycles and there is only one way that 
can happen.  You could also express the number of ways to pick them as
$${1\over 3!} P(3,1)P(2,1)P(1,1) = 1.$$
\noindent
3.1.15.  There are ${6\choose 3}$ ways to pick the digits that come from $\{2,3,5,9\}$.
Since repeated digits are allowed, there are $4^3$ ways to pick the digits themselves.
The locations of the other digits from $\{1,4,6,7\}$ are then determined and there are 
$4^3$ ways to pick them.  The number of security codes is ${6\choose 3} 4^3 \cdot 4^3 = 81920.$
\bigskip
\noindent
3.2.7.  There are $13$ denominations for the three cards and ${4\choose 3} = 4$ possibilities
for the suits.  Then there are $12$ possible denominations for the pair and ${4 \choose 2} = 6$
possibilities for the suits.  This gives 
$$13 \cdot 4 \cdot 12 \cdot 6 = 3744$$
possible full house hands.
\bigskip
\noindent
3.3.8.  We construct such a bijection inductively.  If $n = 1$, then the subsets of 
$[1]$ are $\emptyset$ (with an even cardinality $ = 0$) and $[1]$ with odd cardinality.
So clearly there are as many subsets of $[1]$ with even cardinality as with odd cardinality
in this base case and the bijection just maps $\emptyset$ to $[1]$. 
Now, assume we have such a bijection for subsets of $[k-1]$ and consider subsets of $[k]$.
Every such subset either contains $k$ or it does not.  If it does not then, it is a subset
of $[k-1]$ and there is a bijection between the number of such subsets with even cardinality
and those with odd cardinality by the induction hypothesis.  If the subset $A \subseteq [k]$ 
does contain $k$, then it has the form $A = A' \cup \{k\}$ for some $A' \subseteq [k-1]$.
Clearly $|A'|$ even $\Rightarrow |A|$ odd and vice versa.  By the induction hypothesis 
again, there is a bijection between subsets of $[k]$ containing $k$ with even cardinality
and those with odd cardinality.  This gives the required bijection for subsets of $[k]$
by patching the two bijections together (i.e. the one for subsets that do not contain $k$
and the bijection for those that do) and we are done by induction. 
\bigskip
\noindent
3.5.6.  This is slightly tricky but it also follows by the ``dividers'' method.  The 
trick is that you now need to think of the $k$ dominoes {\it as the dividers} and the 
$m - 2k$ unoccupied columns within the $m \times 1$ array as the {\it things between the 
dividers}.  This gives a total number of placements equal to 
$${(m - 2k) + k \choose k} = {m - k \choose k}.$$
\noindent
3.6.20.  Since the two Ns, the two Us and the two Os are indistinguishable, the 
number is
$${10 \choose 2,2,2,1,1,1,1} = {10!\over 2!2!2!}.$$
See Example 3.6.9.
\bigskip
\noindent
4.2.12.  This is slightly ambiguous, depending on whether you interpret 
$k$-tuple as meaning an ordered list or an unordered list.  If it is ordered, then 
this is the same as the number of ways to distribute $n$ unlabeled balls to 
$k$ labeled urns with no urn empty, or ${n - 1 \choose k - 1}$ (dividers). 
If the list is unordered, then think unlabeled urns, so the number
is $p(n,k)$ -- the number of partitions of $n$ into exactly $k$ positive parts.
(Also note, it's the $k$-tuples that are ``distinct'' -- this does not mean that
the numbers in the $k$-tuple are distinct.)
\bigskip
\noindent 
4.2.19.  The right side $k^n$ is the number of ways of distributing $k$ labeled balls
into $n$ labeled urns.  The left side counts the same thing, but breaking it down
into all the possible cases of how many balls go to each urn, and using the 
Addition Principle.  The term 
${n \choose \lambda_1,\ldots,\lambda_k}$ counts the number of ways to distribute
the $n$ labeled balls into the $k$ labeled urns where urn 1 gets $\lambda_1$ balls,
urn 2 gets $\lambda_2$ balls, etc.  That equals the $k^n$ since we are summing over
all collections of $(\lambda_1,\ldots,\lambda_k)$ where $\lambda_i \ge 0$ for
all $i$, and $\lambda_1 + \cdots + \lambda_k = n$. 
\bigskip
\noindent  
4.3.14.  The number is $p(11,5) = p(10,4) + p(6,5) = 9 + 1 = 10$.  They can be 
represented like this (this is equivalent to counting partitions):
$$\eqalign{&7+1+1+1+1, 6+2+1+1+1, 5+3+1+1+1, 5+2+2+1+1, 4+4+1+1+1,\cr
           &4+3+2+1+1, 4+2+2+2+1, 3+3+3+1+1, 3+3+2+2+1, 3+2+2+2+2\cr}$$
\noindent 
4.3.15.  (See Example 4.3.11 which is somewhat similar).  Distribute the unlabeled red
balls first.  Suppose that out of the $n_1$, $j_1$ go into the unlabeled red urns and the other
$n_1 - j_1$ of them go into the labeled white urns.  There are 
$$p(j_1,1) + \cdots + p(j_1,k_1) = \sum_{\ell=1}^{k_1} p(j_1,\ell)$$
ways to do the distribution to the red urns and then 
${n_1 - j_1 + k_2 - 1\choose k_2 - 1}$ ways to distribute the others to the white
urns.  We then multiply and sum over $j_1$ to get the total 
number of ways to distribute the red balls:
$$(1) \quad \sum_{j_1 = 1}^{n_1}\left( \sum_{\ell=1}^{k_1} p(j_1,\ell)\right)\cdot {n_1 - j_1 + k_2 - 1 \choose k_2 - 1}.$$
Now we do the labeled white balls.  Suppose $j_2$ of them go into the unlabeled red urns
and the other $n_2 - j_2$ go into the labeled white urns.  There are
$$S(j_2,1) + \cdots + S(j_2,k_2) = \sum_{m=1}^{k_2} S(j_2,m)$$
ways to do the distribution to the red urns, and $k_2^{n_2 - j_2}$ ways to the do 
the distribution to the white urns.  Then the total number of ways to distribute
the white balls is
$$(2) \quad \sum_{j_2=1}^{n_2} \left(\sum_{m=1}^{k_2} S(j_2,m)\right)\left(k_2^{n_2 - j_2}\right).$$
Finally, by the Multiplication Principle, the total number of ways to distribute is
the product of the sum in (1) times the sum in (2) -- too complicated to write out on one line(!)
\bigskip
\noindent
5.3.9 (just say how you would solve this
using a generating function).  This would be the coefficient of $x^{100}$ in the 
Taylor expansion of 
$${1\over 1 - x} \cdot {1\over 1 - x^5} \cdot {1 \over 1 - x^{10}} \cdot {1 \over 1 - x^{20}}\cdot 
{1 \over 1 - x^{50}} \cdot {1 \over 1 - x^{100}}.$$
\noindent
5.4.9 (same directions).  This would be the sum of the coefficients of all the terms
$u^i v^j$ with $3 \le i \le 11$ and $5 \le j \le 13$ in the expansion of 
$${1\over 1 - uv^2} \cdot {1 \over 1 - u^4 v^3}\cdot {1 \over 1 - u^5 v^5}\cdot {1 \over 1 - u^6 v^7}.$$ 
\noindent
6.1.20 (figure 6.2 is at the top of the page).
Note that there are $R_0 = 1$ squares in $s_0$, $R_1 = 6$ squares in $s_1$, and 
$R_2 = 26$ squares in $s_2$.  In going from $s_{n-1}$ to $s_n$ we place a copy of $s_{n-1}$
into each quadrant of the larger graph, and then we also add the large outside square 
and the small central square.  Therefore the total number of squares in $s_n$ is
4 times the number of squares in $s_{n-1}$, plus $2$:
$$R_n = 4R_{n-1} + 2$$
for all $n\ge 1$.  
\bigskip\noindent
6.3.10 (solve with a generating function and by the ``shortcut'' method).  
The generating function $R(x)$ satisfies
$$(1 - x - 6x^2)R(x) = R_0 + (R_1 - R_0)x = x$$
so 
$$R(x) = {x\over 1 - x - 6x^2}$$
Now, using partial fractions, we have
$$ = {x\over (1 - 3x)(1 + 2x)} = {1/5\over 1 - 3x} + {-1/5\over 1 + 2x}.$$
So expanding in geometric series, we see that 
$$R_n = {1\over 5} \cdot (3^n - (-2)^n).$$
The shortcut method gets us to the same place somewhat more quickly.  The characteristic
polynomial is $1 - x - 6x^2 = (1 - 3x)(1 + 2x)$ so the general solution is
$$R_n = A\cdot 3^n + B\cdot (-2)^n$$
for some $A,B$.  From $n=0$ we get $0 = A + B$ and from $n = 1$, we get $1 = 3A - 2B$.
Therefore $A = {1\over 5}$ and $B = {-1\over 5}$.
\bigskip
\noindent
6.5.27.  Because the characteristic polynomial is $1 - 8x + 16x^2 = (1 - 4x)^2$, we
need to take a particular solution of the form $C n^2 4^n$ using Table 6.1.  The solution
has the form $(A + Bn)4^n + Cn^2 4^n$ and we can solve for $A,B,C$ from the given initial values
$R_0 = 1$, $R_1 = 1$, $R_2 = 8 - 16 + 4^2 = 8$.  Answer:
$$R_n = 4^n\left(1 - {5n\over 4} + {n^2\over 2}\right).$$  
\noindent
7.1.16 (just say how you would solve it using generating functions).  We need to use 
generating functions and Inclusion-Exclusion for this since we are counting the number
of elements of a union of four sets.  Let $A,B,C,D$ be the sets of solutions of the
equation with each of the constraints separately.  Then 
$$\eqalign{
|A| &= {\rm coeff.\ of\ } x^{35} {\rm\ in\ } {1 + x + \cdots + x^{12} \over (1 - x)^3}\cr
|B| &= {\rm coeff.\ of\ } x^{35} {\rm\ in\ } {1 + x + \cdots + x^{10} \over (1 - x)^3}\cr
|C| &= {\rm coeff.\ of\ } x^{35} {\rm\ in\ } {1 + x + \cdots + x^{7} \over (1 - x)^3}\cr
|D| &= {\rm coeff.\ of\ } x^{35} {\rm\ in\ } {1 + x + \cdots + x^{4} \over (1 - x)^3}\cr}$$
$$\eqalign{
|A \cap B| &= {\rm coeff.\ of\ } x^{35} {\rm\ in\ } {(1 + x + \cdots + x^{12})(1 + \cdots + x^{10}) \over (1 - x)^2}\cr
|A \cap C| &= {\rm coeff.\ of\ } x^{35} {\rm\ in\ } {(1 + x + \cdots + x^{12})(1 + \cdots + x^{7}) \over (1 - x)^2}\cr
|A \cap D| &= {\rm coeff.\ of\ } x^{35} {\rm\ in\ } {(1 + x + \cdots + x^{12})(1 + \cdots + x^{4}) \over (1 - x)^2}\cr
|B \cap C| &= {\rm coeff.\ of\ } x^{35} {\rm\ in\ } {(1 + x + \cdots + x^{10})(1 + \cdots + x^{7}) \over (1 - x)^2}\cr
|B \cap D| &= {\rm coeff.\ of\ } x^{35} {\rm\ in\ } {(1 + x + \cdots + x^{10})(1 + \cdots + x^{4}) \over (1 - x)^2}\cr
|C \cap D| &= {\rm coeff.\ of\ } x^{35} {\rm\ in\ } {(1 + x + \cdots + x^{7})(1 + \cdots + x^{4}) \over (1 - x)^2}\cr}$$
$$\eqalign{
|A \cap B \cap C| &= {\rm coeff.\ of\ } x^{35} {\rm\ in\ } {(1 + \cdots + x^{12})(1 + \cdots + x^{10})(1 + \cdots + x^7) \over (1 - x)}\cr
|A \cap B \cap D| &= {\rm coeff.\ of\ } x^{35} {\rm\ in\ } {(1 + \cdots + x^{12})(1 + \cdots + x^{10})(1 + \cdots+x^4) \over (1 - x)}\cr
|A \cap C \cap D| &= {\rm coeff.\ of\ } x^{35} {\rm\ in\ } {(1 + \cdots + x^{12})(1 + \cdots + x^{7})(1 + \cdots +x^4) \over (1 - x)}\cr
|B \cap C \cap D| &= {\rm coeff.\ of\ } x^{35} {\rm\ in\ } {(1 + \cdots + x^{10})(1 + \cdots + x^{7})(1 + \cdots +x^7) \over (1 - x)}\cr
|A \cap B \cap C \cap D| &= {\rm coeff.\ of\ } x^{35} {\rm\ in\ } (1 + \cdots + x^{12})(1 + \cdots + x^{10})(1 + \cdots +x^7)( 1 + \cdots + x^4)\cr}$$
Then 
$$|A\cup B\cup C \cup D| = \sum_{I \subseteq [4], I \ne \emptyset} (-1)^{|I|+1} \left|\bigcap_{i\in I} A_i\right|.$$
\noindent
7.3.4.  Recall that we know $D_n = n! \sum_{m=0}^n {(-1)^m \over m!}$.  Hence
$$\lim_{n\to\infty} {D_n\over n!} = \lim_{n\to\infty} \sum_{m=0}^n {(-1)^m \over m!} = e^{-1}.$$
\noindent
8.3.20.  The $4\times 4$ grid with squares labeled by $[16]$ is our $X$.  The group acting
is $C_4 = \{e,\rho,\rho^2,\rho^3\}$ acting by rotations about the center point of 
the grid.  Let's label the squares $1,2,3,4$ left to right across the top row, 
then $5,6,7,8$ left to right across the second row, etc.  We see
$$\eqalign{{\rm Inv}(e) &= [16]\cr
           {\rm Inv}(\rho) &= \emptyset\cr
           {\rm Inv}(\rho^2) &= \emptyset\cr
           {\rm Inv}(\rho^3) &= \emptyset\cr}$$
By Burnside's Lemma, the number of orbits is equal to 
$${1\over |G|} \sum_{g \in G} |{\rm Inv}(g)| = {1\over 4}(16 + 0 + 0 + 0) = 4.$$
(The orbits are $\{1,4,13,16\}$ (the corners), $\{2,9,15,8\}$ and $\{3,5,14,12\}$ (interior points of
outside rows and columns), and $\{6,7,10,11\}$ the 4 points in the ``inside ring.'')
\bigskip
\noindent
8.5.12 (just say how you would solve it using the Polya Theorem).  We begin by computing the 
cycle index polynomial for this action of $C_4$ on $X$.  We have
$$\eqalign{{\rm cim}(e) &= x_1^{16}\cr
           {\rm cim}(\rho) &= x_4^4\cr
           {\rm cim}(\rho^2) &= x_2^8\cr
           {\rm cim}(\rho^3) &= x_4^2\cr}$$
Hence 
$$Z_{C_4}(x_1,x_2,x_4) = {1\over 4}(x_1^{16} + 2 x_4^2 + x_2^8).$$
Then by the Polya Theorem, the number of distinct two-colorings of the $4\times 4$ grid
using the first color 10 times and the second 6 times is equal to the coefficient of 
$c_1^{10} c_2^6$ in the expansion of 
$$Z_{C_4}(c_1 + c_2, c_1^2 + c_2^2, c_1^4 + c2^4).$$
(In case you are interested, this number is $2016$.)
\end                 
