\include{preamble}
\setcounter{try}{25}
\renewcommand{\thefootnote}{\fnsymbol{footnote}}
\title{}
\author{Zajj Daugherty}
\date{\today}
\usepackage{multicol}
\begin{document}
\begin{flushright}
SOLUTIONS\\
Homework 6\\
Due 3/20/19
\end{flushright}
%-----------------% HANDOUT 10 %-----------------%
\begin{try}~
\begin{enumerate}[(a)]
\item Consider strings of length 10 consisting of 1's, 2's, and/or 3's.
\begin{enumerate}[(i)]
\item How many of these are there (with no additional restrictions)?
\Ans{$3^{10}$ (three choices for each digit)}
\item How many of these are there that contain exactly three 1's, two 2's, and five 3's?
\begin{ans}
We're counting the anagrams of $1112233333$:
$$\frac{10!}{3!2!5!} = \binom{10}{3}\binom{10-3}{2}\binom{10-3-5}{5}.$$
\end{ans}
\end{enumerate}
\item How many anagrams are there of MISSISSIPPI?
\begin{ans}
There are 4 S's, 4 I's, 2 P's, and 1 M, therefore, there are
$$\frac{11!}{4!4!2!1!} = \binom{11}{4}\binom{11-4}{4}\binom{11-4-4}{2}\binom{11-4-4-2}{1}$$
anagrams.
\end{ans}
\item Suppose you've got eight varieties of doughnuts to choose from at a doughnuts shop.
\begin{enumerate}[(i)]
\item How many ways can you select 6 doughnuts?
\begin{ans}
We're putting 6 indistinguishable objects (our choices) into 8 distinguishable boxes (the varieties of doughnuts):
$$\binom{6+(8-1)}{6}.$$
(This is a ``stars and bars'' problem.)
\end{ans}
\item How many ways can you select a dozen (12) doughnuts?
\begin{ans}
We're putting 12 indistinguishable objects (our choices) into 8 distinguishable boxes (the varieties of doughnuts):
$$\binom{12+(8-1)}{12}.$$
(This is a ``stars and bars'' problem.)
\end{ans}
\item How many ways can you select a dozen doughnuts with at least one of each kind?\\
{[Hint: if there's at least one of each kind, then how many choices are you really making?]}
\begin{ans}Since 8 choices have already been made, we're left with putting 4 indistinguishable objects (our choices) into 8 distinguishable boxes (the varieties of doughnuts):
$$\binom{4+8-1}{4}.$$
(This is still a ``stars and bars'' problem, but accounting for choices already determined.)
\end{ans}
\end{enumerate}
\item How many different combinations of pennies, nickels, dimes, quarters, and half dollars can a jar contain if it has 20 coins in it?
\begin{ans}We're putting 200 indistinguishable objects (instances of coins) into 5 distinguishable boxes (the varieties of coins):
$$\binom{20+5-1}{20}.$$
(This is a ``stars and bars'' problem.)
\end{ans}
\item Counting solutions.
\begin{enumerate}[(i)]
\item How many solutions are there to the equation
$x_1 + x_2 + x_3 = 10,$
where $x_1, x_2$, and $x_3$ are nonnegative integers?
\begin{ans}We're putting 10 indistinguishable objects (one unit at a time) into 3 distinguishable boxes (the value of the variables):
$$\binom{10+3-1}{10}.$$
(This is a ``stars and bars'' problem.)\end{ans}
\item How many solutions are there to the equation
$x_1 + x_2 + x_3 = 10,$
where $x_1, x_2$, and $x_3$ are strictly positive integers?\\
{[Hint: See problem (c)(iii)]}
\begin{ans}Since 3 ``units'' have already been assigned (one to $x_1$, one to $x_2$, and one to $x_3$), we're left with putting 7 indistinguishable objects (our units) into 3 distinguishable boxes (the variables):
$$\binom{7+3-1}{7}.$$
(This is still a ``stars and bars'' problem, but accounting for choices already determined.)
\end{ans}
\item How many solutions are there to the equation
$x_1 + x_2 + x_3 \leq 10,$
where $x_1, x_2$, and $x_3$ are nonnegative integers?\quad
{[}Hint: Use an extra variable $x_4$ such that $x_1 + x_2 + x_3 + x_4 = 10${]}
\begin{ans}
The nonnegative integer solutions to $x_1 + x_2 + x_3 \leq 10$ is the same as the nonnegative integer solutions to $x_1 + x_2 + x_3 + x_4 = 10$ (where $x_4 = 10 -(x_1 + x_2 + x_3)$). So, similarly to the previous part, there are
$$\binom{10+4-1}{10} \qquad \text{ solutions. }$$
(This is still a ``stars and bars'' problem.)
\end{ans}
\end{enumerate}
\end{enumerate}
\end{try}
\pagebreak
\begin{try}
~
\begin{enumerate}[(a)]
\item List the partitions of 6, both as box diagrams and as sequences.
\begin{ans}
\begin{align*}
\PART{6} & \qquad (6)\\
\PART{5,1} & \qquad (5,1)\\
\PART{4,2}& \qquad (4,2)\\
\PART{4,1,1}& \qquad (4,1,1)\\
\PART{3,3}& \qquad (3,3)\\
\PART{3,2,1}& \qquad (3,2,1)\\
\PART{3,1,1}& \qquad (3,1,1)\\
\PART{2,2,2}& \qquad (2,2,2)\\
\PART{2,2,1,1}& \qquad (2,2,1,1)\\
\PART{2,1,1,1,1}& \qquad (2,1,1,1,1)\\
\PART{1,1,1,1,1,1}& \qquad (1,1,1,1,1,1)
\end{align*}
\end{ans}
\item How many ways are there to distribute 6 identical cookies into 6 identical lunch boxes, possibly leaving some empty?
\begin{ans}
This is the number of partitions of 6 with at most 6 parts, of which there are 12 (see part (a)).
\end{ans}
\item How many ways are there to distribute 6 identical snack bars into 4 identical lunch boxes, possibly leaving some empty?
\begin{ans}
This is the number of partitions of 6 with at most 4 parts, of which there are 9 (see part (a)).
\end{ans}
\item How many ways are there to distribute 4 identical apples into 6 identical lunch boxes, possibly leaving some empty?
\begin{ans}
This is the number of partitions of 4 with at most 6 parts, which is the same as the number of partitions with at most 4 parts, of which there are 5:
$$\PART{4}, \quad \PART{3,1}, \quad \PART{2,2} \quad \PART{2,1,1}, \quad \text{ and } \quad \PART{1,1,1,1}.$$
\end{ans}
\end{enumerate}
\end{try}
\pagebreak
\begin{try}~
\begin{enumerate}[(a)]
\item Basic counting:
\begin{enumerate}[(a)]
\item[(i)] How many ways are there to distribute 5 distinguishable objects into 3 distinguishable boxes, possibly leaving some empty?
\Ans{$3^5$}
\medskip
\item[(ii)] How many ways are there to distribute 5 indistinguishable objects into 3 distinguishable boxes, possibly leaving some empty?
\Ans{$\binom{5+3-1}{5}$}
\medskip
\item[(iii)] How many ways are there to distribute 5 distinguishable objects into 3 indistinguishable boxes, possibly leaving some empty?
\begin{ans}
There are
$$S(5,3) + S(5,2) + S(5,1)$$
ways, where $S(n,j)$ is the Stirling number of the second kind.
To compute this number explicitly, you can either use the formula
$$S(n,j) = \frac{1}{j!} \sum_{\ell=0}^{j-1} (-1)^\ell \binom{j}{\ell}(j - \ell)^n;$$
or you can count directly by cases as follows.
\smallskip
\noindent \underline{$ S(5,1) = 1$}: There is one way to put all 5 things into one box.
\smallskip
\noindent \underline{$ S(5,2) = 5+\binom{5}{2} = 15$}: If we split 5 things into two boxes then that split either looks like
$$\{a,b,c,d\}, \{e\} \qquad \text{ or } \qquad \{a,b,c\}, \{d,e\}.$$
In the first case, there are 5 ways to do this (5 ways to choose $e$); in the second case, there are $\binom{5}{2} = 10$ ways to choose $d$ and $e$.
\smallskip
\noindent \underline{$ S(5,3) = \binom{5}{2} + \frac{1}{2} \binom{5}{2} \binom{3}{2} = 25$}: If we split 5 things into three boxes then that split either looks like
$$\{a,b,c\}, \{d\}, \{e\} \qquad \text{ or } \qquad \{a,b\}, \{c,d\}, \{e\}.$$
In the first case, there are $\binom{5}{2}$ to choose $d$ and $e$ (the order doesn't matter since the boxes are indistinguishable--all we care about is that $d$ and $e$ get their own box, and the rest have to share a box). In the second case, there are $\frac{1}{2} \binom{5}{2} \binom{3}{2}$ ways--pick $a$ and $b$, then pick $c$ and $d$, and then divide by the permutations of the first two sets (again since I can't tell the difference between the boxes).
\smallskip
So
$$S(5,3) + S(5,2) + S(5,1) = 25 + 15 + 1.$$
\end{ans}
\item[(iv)] How many ways are there to distribute 5 indistinguishable objects into 3 indistinguishable boxes, possibly leaving some empty?
\begin{ans}
The ways to do this are in bijection with integer partitions of 5 with at most 3 parts, so there are
$$p_3(5) = \left|\left\{ \PART{5}, \PART{4,1}, \PART{3,2}, \PART{3,1,1}, \PART{2,2,2} \right\}\right| = 5$$
ways
\end{ans}
\pagebreak
\item[(v)] How many ways are there to distribute 6 distinguishable objects into 4 indistinguishable boxes, possibly leaving some empty?
\begin{ans}
$$S(6,4) + S(6,3) + S(6,2) + S(6,1)$$
\end{ans}
\item[(vi)] How many ways are there to distribute 6 distinguishable objects into 4 indistinguishable boxes so that each of the boxes contains at least one object?
\Ans{$S(6,4)$}
\end{enumerate}
\bigskip
\item How many ways are there to pack 8 identical DVDs into 5 indistinguishable boxes? How many ways to do this task so that each box contains
at least one DVD?
\begin{ans}
In general,
$$S(8,5) + S(8,4)+ S(8,3)+ S(8,2) + S(8,1);$$
but only $S(8,5)$ if each box contains at least one DVD.
\end{ans}
\item How many ways are there to distribute 5 balls into 7 boxes if
\begin{enumerate}[(i)]
\item both the balls and boxes are labeled? \Ans{$7^5$}
\medskip
\item the balls are labeled, but the boxes are unlabeled?
\begin{ans}
There are
$$S(5,7) + S(5,6) + S(5,5) + S(5,4) + S(5,3) + S(5,2) + S(5,1) = 0 + 0 + 1 + S(5,4) + S(5,3) + S(5,2) + S(5,1)$$
ways.
Note that $S(5,7) = S(5,6) = 0$ since there is no way to leave no box empty when there are more boxes than balls.
\end{ans}
\item the balls are unlabeled, but the boxes are labeled? \Ans{$\binom{5+7-1}{5}$}
\item both the balls and boxes are unlabeled?
\begin{ans}
$$p_7(5) = \left|\left\{\PART{5}, \PART{4,1}, \PART{3,2}, \PART{3,1,1}, \PART{2,2,2}, \PART{2,2,1,1}, \PART{2,1,1,1,1}, \PART{1,1,1,1,1,1}\right\}\right|$$
\end{ans}
\end{enumerate}
\item Repeat parts (i)--(iv) of part (c), adding the condition that each bucket can have at \emph{most} one ball in it.
\begin{enumerate}[(i)]
\item both the balls and boxes are labeled:
\begin{ans}
There are $7*6*5*4*3$ ways (pick 5 boxes from 7 in order without replacement).
\end{ans}
\pagebreak
\item the balls are labeled, but the boxes are unlabeled:
\begin{ans}
Each ball has to go into a separate box, but we can't tell the difference between the buckets. So there's one way.
\end{ans}
\item the balls are unlabeled, but the boxes are labeled:
\begin{ans}
Each ball has to go into a separate box, and we can't tell the difference between the balls, but we can tell which buckets have been filled. So there are $\binom{7}{5}$ ways.
\end{ans}
\item both the balls and boxes are unlabeled:
\begin{ans}
Each ball has to go into a separate box, and we can't tell the difference between the balls or the buckets. So there's one way.
\end{ans}
\end{enumerate}
\end{enumerate}
\end{try}
%--------- Handout 11 ---------------%
\begin{try}
Draw a tree-diagram that tells you how many ways to form the following results, and count the possible outcomes.
\begin{enumerate}[(a)]
\item Strings of 1's and 0's of length-four with three consecutive 0's.
\begin{ans}
$$
\begin{tikzpicture}[yscale=-1]
\node[bV] (e) at (0,0) {};
\node[bV](0) at (-1,1) {};
\node[bV](1) at (1,1) {};
\node[bV](00) at (-1,2) {};
\node[bV](000) at (-1,3) {};
\node[bV](0000) at (-1.5,4) {};
\node[bV](0001) at (-.5,4) {};
\node[bV](10) at (1,2) {};
\node[bV](100) at (1,3) {};
\node[bV](1000) at (1,4) {};
\draw (e) to node[above left] {$0$} (0);
\draw (e) to node[above right] {$1$} (1);
\draw (0) to node[left] {$0$} (00);
\draw (00) to node[left] {$0$} (000);
\draw (000) to node[above left] {$0$} (0000);
\draw (000) to node[above right] {$1$} (0001);
\draw (1) to node[above right] {$0$} (10) to node[above right] {$0$} (100)
to node[above right] {$0$} (1000) ;
\foreach \x in {0000, 0001, 1000}{\node[right, rotate=-90] at (\x) {$\x$};}
\end{tikzpicture}$$
\end{ans}
\pagebreak
\item Subsets of the set $\{3,7,9,11,24\}$ whose elements sum to less than 28.
\begin{ans}
$$
\begin{tikzpicture}
\node[bV] (r) at (0,0){};
\node[bV] (1) at (-4,-1){};
\node[bV] (0) at (6,-1){};
\node[bV] (10) at (-4,-2){};
\node[bV] (01) at (3,-2){};
\node[bV] (00) at (9,-2){};
\node[bV] (100) at (-4,-3){};
\node[bV] (011) at (1.5,-3){};
\node[bV] (010) at (4.5,-3){};
\node[bV] (001) at (7.5,-3){};
\node[bV] (000) at (10.5,-3){};
\node[bV] (1000) at (-4,-4){};
\node[bV] (0111) at (.75,-4){};
\node[bV] (0110) at (2.25,-4){};
\node[bV] (0101) at (3.75,-4){};
\node[bV] (0100) at (5.25,-4){};
\node[bV] (0011) at (6.75,-4){};
\node[bV] (0010) at (8.25,-4){};
\node[bV] (0001) at (9.75,-4){};
\node[bV] (0000) at (11.25,-4){};
\node[bV] (10001) at (-5,-5.5){};
\node[bV] (10000) at (-3,-5.5){};
\node[bV] (01110) at (.75,-5.5){};
\node[bV] (01101) at (1.9,-5.5){};
\node[bV] (01100) at (2.6,-5.5){};
\node[bV] (01011) at (3.4,-5.5){};
\node[bV] (01010) at (4.1,-5.5){};
\node[bV] (01001) at (4.9,-5.5){};
\node[bV] (01000) at (5.6,-5.5){};
\node[bV] (00111) at (6.4,-5.5){};
\node[bV] (00110) at (7.1,-5.5){};
\node[bV] (00101) at (7.9,-5.5){};
\node[bV] (00100) at (8.6,-5.5){};
\node[bV] (00011) at (9.4,-5.5){};
\node[bV] (00010) at (10.1,-5.5){};
\node[bV] (00001) at (10.9,-5.5){};
\node[bV] (00000) at (11.6,-5.5){};
\draw (r) to node[sloped, above] {24 in} (1);
\draw (1) to node[right] {11 out} (10);
\draw (10) to node[right] {9 out} (100);
\draw (100) to node[right] {7 out} (1000);
%
\draw (r) to node[sloped, above] {24 out} (0);
\draw (0) to node[sloped, above] {11 in} (01);
\draw (0) to node[sloped, above] {11 out} (00);
\draw (01) to node[sloped, above] {9 in} (011);
\draw (01) to node[sloped, above] {9 out} (010);
\draw (00) to node[sloped, above] {9 in} (001);
\draw (00) to node[sloped, above] {9 out} (000);
\foreach \x in {011,010,001,000}
{\draw (\x) to node[sloped, above] {7 in} (\x1);
\draw (\x) to node[sloped, above] {7 out} (\x0);}
\foreach \x in {1000,0110,0101,0100,0011,0010,0001,0000}
{\draw (\x) to node[sloped, above] {3 in} (\x1);
\draw (\x) to node[sloped, above] {3 out} (\x0);}
\draw (0111) to node[sloped, above] {3 out} (01110);
\node[right, rotate=-90] at (10001) {$\{24, 3\}$};
\node[right, rotate=-90] at (10000) {$\{24\}$};
\node[right, rotate=-90] at (01110) {$\{11, 9, 7\}$};
\node[right, rotate=-90] at (01101) {$\{11,9,3\}$};
\node[right, rotate=-90] at (01011) {$\{11,7,3\}$};
\node[right, rotate=-90] at (01100) {$\{11,9\}$};
\node[right, rotate=-90] at (01010) {$\{11,7\}$};
\node[right, rotate=-90] at (01001) {$\{11,3\}$};
\node[right, rotate=-90] at (01000) {$\{11\}$};
\node[right, rotate=-90] at (00111) {$\{9,7,3\}$};
\node[right, rotate=-90] at (00110) {$\{9,7\}$};
\node[right, rotate=-90] at (00101) {$\{9,3\}$};
\node[right, rotate=-90] at (00100) {$\{9\}$};
\node[right, rotate=-90] at (00011) {$\{7,3\}$};
\node[right, rotate=-90] at (00001) {$\{3\}$};
\node[right, rotate=-90] at (00010) {$\{7\}$};
\node[right, rotate=-90] at (00000) {$\emptyset$};
\end{tikzpicture}$$
\end{ans}
\end{enumerate}
$\quad$\hfill\emph{To check your answers: (a) 3; (b) 17.}
\end{try}
\begin{try}~
\begin{enumerate}[(a)]
\item Permutations.
\begin{enumerate}[(i)]
\item Find a recurrence relation and initial conditions for the number of permutations of a set with $n$ elements.
\begin{ans}
For each permutation of $n-1$, insert an $n$. There are $n$ ways to do this (insert at the beginning, after the first term, after the second term, \dots, after the $n-1$ term):
$$a_n = na_{n-1}.$$
This needs one initial condition. There is one permutation of one thing, so
$$a_1 = 1.$$
\end{ans}
\item Check your recurrence relation by iteratively calculating the first 5 terms of your sequence, and using the known closed formula for counting permutations.
\begin{ans}
We know that there are $n!$ permutations of $n$ elements.
\begin{align*}
a_2 &= 2a_1 = 2*1 = 2!& \checkmark\\
a_3 &= 3a_2 = 3*2*1 = 3!& \checkmark\\
a_4 &= 4a_3 = 4*3*2*1 = 4!& \checkmark\\
a_5 &= 5a_4 = 5*4*3*2*1 = 5!& \checkmark
\end{align*}
\end{ans}
\end{enumerate}
\pagebreak
\item Bit strings.
\begin{enumerate}[(i)]
\item Find a recurrence relation and initial conditions for the number of bit strings of length $n$ that contain a pair of consecutive $0$s.
\begin{ans}
For every good bit string (a bit string containing at least one pair of consecutive 0's) or length $n$, removing the last bit leave either a good or a bad bit string of length $n-1$. For those that leave a good bit sting, either the last digit is a 1 or a 0, so there are
$$a_{n-1}*2 \qquad \text{ of these.}$$
For those that leave a bad bit string, this means that the $n-1$ bit has to be a 0 and the $n-2$ bit has to be a 1. The rest of the bits are free. Thus there are
$$\text{(total $n-3$ strings) $-$ (number of good $n-3$ strings)} = 2^{n-3} - a_{n-3} \qquad \text{ of these.}$$
So
$$a_n = 2 a_{n-1} + 2^{n-3} - a_{n-3.}$$
This requires three initial conditions. There are no good bit strings of length 1; there is 1 good string of length 2 ($00$), and there are three good strings of length 3 ($000$, $100$, and $001$). So
$$a_1 = 0, \quad a_2 = 1, \quad a_3 = 3.$$
\end{ans}
\item Check your answer for $n=4$ by iteratively using your recurrence relation, and then by listing the possibilities.
\begin{ans}
Decision tree:
$$\begin{tikzpicture}
\node[bV] (root) at (0,0){};
\node[bV] (0) at (-4,-1){};
\node[bV] (1) at (4,-1){};
\node[bV] (00) at (-6,-2){};
\node[bV] (01) at (-2,-2){};
\node[bV] (10) at (2,-2){};
\node[bV] (11) at (6,-2){};
\node[bV] (000) at (-7,-3){};
\node[bV] (001) at (-5,-3){};
\node[bV] (010) at (-2,-3){};
\node[bV] (100) at (2,-3){};
\node[bV] (110) at (6,-3){};
\node[bV] (0000) at (-7.5,-4){};
\node[bV] (0001) at (-6.5,-4){};
\node[bV] (0010) at (-5.5,-4){};
\node[bV] (0011) at (-4.5,-4){};
\node[bV] (0100) at (-2,-4){};
\node[bV] (1000) at (1.5,-4){};
\node[bV] (1001) at (2.5,-4){};
\node[bV] (1100) at (6,-4){};
\foreach \x in {0,1,00,000,001,100}{\draw (\x) to node[above left]{\tiny 0} (\x0);}
\foreach \x in {0,1,00,000,001,100}{\draw (\x) to node[above right]{\tiny 1} (\x1);}
\draw (root) to node[above left]{\tiny 0} (0);
\draw (root) to node[above right]{\tiny 1} (1);
\draw (01) to node[left]{\tiny 0} (010);
\draw (010) to node[left]{\tiny 0} (0100);
\draw (10) to node[left]{\tiny 0} (100);
\draw (110) to node[left]{\tiny 0} (1100);
\draw (11) to node[left]{\tiny 0} (110);
\end{tikzpicture}$$
This shows that there are 8 good 4-strings. Alternatively,
$$a_4 = 2a_3 + 2^1 - a_1 = 2*3 + 2 - 0 = 8 \qquad \checkmark$$
\end{ans}
\end{enumerate}
\pagebreak
\item Climbing stairs.
\begin{enumerate}[(i)]
\item
Find a recurrence relation and initial conditions for the number of ways to climb $n$ stairs if the person climbing the stairs can take one stair or two stairs at a time.
\begin{ans}
Consider the last step taken. This is either two stairs or one. If it's two, there are $a_{n-2}$ ways to lead up to this; if it's one, there are $a_{n-1}$ ways to lead up to this. So
$$a_n = a_{n-1} + a_{n-2}.$$
If there's only one stair, there's one way to climb it. If there are two stairs, the person can take them one at a time, or both at once. So
$$a_1 = 1 \qquad \text{ and } \qquad a_2 = 2.$$
\end{ans}
\item Check your answer for $n=4$ by iteratively using your recurrence relation, and by counting the number of these sequences by hand using a decision tree.
\begin{ans}
$$\begin{tikzpicture}
\node[bV] (root) at (0,0){};
\node[bV] (2) at (-4,-1){};
\node[bV] (1) at (4,-1){};
\node[bV] (22) at (-6,-2){};
\node[bV] (21) at (-2,-2){};
\node[bV] (12) at (2,-2){};
\node[bV] (11) at (6,-2){};
\node[bV] (211) at (-2,-3){};
\node[bV] (121) at (2,-3){};
\node[bV] (112) at (4,-3){};
\node[bV] (111) at (8,-3){};
\node[bV] (1111) at (8,-4){};
\foreach \x in {2,1,11}{\draw (\x) to node[above left]{\tiny 2} (\x2);}
\foreach \x in {2,1,11}{\draw (\x) to node[above right]{\tiny 1} (\x1);}
\draw (root) to node[above left]{\tiny 2} (2);
\draw (root) to node[above right]{\tiny 1} (1);
\foreach \x in {21,12,111}{\draw (\x) to node[left]{\tiny 1} (\x1);}
\end{tikzpicture}$$
This shows that there are 5 ways to climb 4 stairs. Alternatively,
\begin{align*}
a_3 &= a_2 + a_1 = 2+1 = 3\\
a_4&= a_3 + a_2 = 3+ 1 = 5 & \checkmark
\end{align*}
\end{ans}
\item Calculate the number of ways to climb 8 stairs in this way.
\begin{ans}
Continuing from before:
\begin{align*}
a_5 &= a_4 + a_3 = 5+3 = 8\
a_6 &= a_5 + a_4 = 8+5 = 13\\
a_7 &= a_6 + a_5 = 13+8 = 21\\
a_8 &= a_7 + a_6 = 21+13 = 34.
\end{align*}
\end{ans}
\end{enumerate}
\pagebreak
\item Tiling boards.
\begin{enumerate}[(i)]
\item Find a recurrence relation and initial conditions for the number of ways to completely cover a $2 \times n$ checkerboard with $1 \times 2$ dominoes. For example, if $n=3$, one solution is
$$
\begin{tikzpicture}[scale=.8]
\node at (1.5,2.5) {$2 \times 3$ checkerboard:};
\foreach \x/\y in {0/0, 1/1, 2/0}{
\filldraw[black!60] (\x,\y) rectangle (\x+1,\y+1);
}
\foreach \x in {0,1,2,3}{\draw (\x,0) to (\x,2);}
\foreach \x in {0,1,2}{\draw (0,\x) to (3,\x);}
\end{tikzpicture}
\qquad\qquad
\begin{tikzpicture}[scale=.8]
\node at (1.5,2.5) {covered with 3 dominoes:};
\foreach \x/\y in {0/0, 1/1, 2/0}{
\filldraw[black!60] (\x,\y) rectangle (\x+1,\y+1);
}
\foreach \x in {0,1,2,3}{\draw (\x,0) to (\x,2);}
\foreach \x in {0,1,2}{\draw (0,\x) to (3,\x);}
\draw[fill=black!20] (.1,.1) rectangle (.9,1.9);
\draw[fill=black!20] (1.1,.1) rectangle (2.9,.9);
\draw[fill=black!20] (1.1,1.1) rectangle (2.9,1.9);\end{tikzpicture}
\qquad\qquad
\begin{tikzpicture}[scale=.8]
\node at (1.5,2.5) {shorthand for same solution:};
%\foreach \x/\y in {0/0, 1/1, 2/0}{
%\filldraw[black!60] (\x,\y) rectangle (\x+1,\y+1);
%}
\foreach \x in {0,1,2,3}{\draw (\x,0) to (\x,2);}
\foreach \x in {0,1,2}{\draw (0,\x) to (3,\x);}
\draw[line width=5pt] (.5,.5) rectangle (.5,1.5);
\draw[line width=5pt] (1.5,.5) rectangle (2.5,.5);
\draw[line width=5pt] (1.5,1.5) rectangle (2.5,1.5);\end{tikzpicture}
$$
{[}Hint: Consider separately the coverings where the position in the top right corner of the checkerboard is covered by a domino positioned horizontally and where it is covered by a domino positioned vertically.{]}
\begin{ans}
If the top right corner is covered by a vertical domino, then the remainder of the board is a tiling of a $2 \times (n-1)$ board, of which there are $a_{n-1}$ ways. If the top right corner is covered by a horizontal domino, then the bottom right corner is tiled by a horizontal domino. The rest of the board is a $2 \times (n-2)$ board, of which there are $a_{n-2}$ ways to do this. So
$$a_n = a_{n-1} + a_{n-2}.$$
There's one way to tile a $2 \times 1$ board, and two ways to tile a $2 \times 2$ board, so
$$a_1 = 1 \qquad \text{ and } \qquad a_2 = 2.$$
\end{ans}
\item Check your answer for $n=4 $ by iteratively using your recurrence relation, and by counting the number of these sequences by hand.
\begin{ans}
The $2 \times 4$ tilings:
$$\begin{tikzpicture}[scale=.5]
\foreach \x in {0,1,2,3,4}{\draw (\x,0) to (\x,2);}
\foreach \x in {0,1,2}{\draw (0,\x) to (4,\x);}
\draw[line width=5pt] (.5,.5) rectangle (.5,1.5);
\draw[line width=5pt] (1.5,.5) rectangle (1.5,1.5);
\draw[line width=5pt] (2.5,.5) rectangle (2.5,1.5);
\draw[line width=5pt] (3.5,.5) rectangle (3.5,1.5);\end{tikzpicture}
\quad
\begin{tikzpicture}[scale=.5]
\foreach \x in {0,1,2,3,4}{\draw (\x,0) to (\x,2);}
\foreach \x in {0,1,2}{\draw (0,\x) to (4,\x);}
\draw[line width=5pt] (.5,.5) rectangle (.5,1.5);
\draw[line width=5pt] (1.5,.5) rectangle (1.5,1.5);
\draw[line width=5pt] (2.5,.5) rectangle (3.5,.5);
\draw[line width=5pt] (2.5,1.5) rectangle (3.5,1.5);\end{tikzpicture}
\quad
\begin{tikzpicture}[scale=.5]
\foreach \x in {0,1,2,3,4}{\draw (\x,0) to (\x,2);}
\foreach \x in {0,1,2}{\draw (0,\x) to (4,\x);}
\draw[line width=5pt] (.5,.5) rectangle (.5,1.5);
\draw[line width=5pt] (1.5,.5) rectangle (2.5,.5);
\draw[line width=5pt] (1.5,1.5) rectangle (2.5,1.5);
\draw[line width=5pt] (3.5,.5) rectangle (3.5,1.5);\end{tikzpicture}
\quad
\begin{tikzpicture}[scale=.5]
\foreach \x in {0,1,2,3,4}{\draw (\x,0) to (\x,2);}
\foreach \x in {0,1,2}{\draw (0,\x) to (4,\x);}
\draw[line width=5pt] (2.5,.5) rectangle (2.5,1.5);
\draw[line width=5pt] (3.5,.5) rectangle (3.5,1.5);
\draw[line width=5pt] (.5,.5) rectangle (1.5,.5);
\draw[line width=5pt] (.5,1.5) rectangle (1.5,1.5);\end{tikzpicture}
\quad
\begin{tikzpicture}[scale=.5]
\foreach \x in {0,1,2,3,4}{\draw (\x,0) to (\x,2);}
\foreach \x in {0,1,2}{\draw (0,\x) to (4,\x);}
\draw[line width=5pt] (2.5,.5) rectangle (3.5,.5);
\draw[line width=5pt] (2.5,1.5) rectangle (3.5,1.5);
\draw[line width=5pt] (.5,.5) rectangle (1.5,.5);
\draw[line width=5pt] (.5,1.5) rectangle (1.5,1.5);\end{tikzpicture}
$$
Alternatively,
$$a_3= 2+1 = 3, \quad \text{ so } \quad a_4 = 3+2 = 5. \qquad \checkmark$$
\end{ans}
\item How many ways are there to completely cover a $2 \times 6$ checkerboard with $1 \times 2$ dominoes?
\begin{ans}
Continuing from above,
$$a_5= 5+3 = 8, \quad \text{ so } \quad a_6 = 8+5 = 13.$$
\end{ans}
\end{enumerate}
\pagebreak
\item Increasing sequences
\begin{enumerate}[(i)]
\item Find a recurrence relation for the number of strictly increasing sequences of positive integers that have $1$ as their first term and $n$ as their last term, where $n$ is a positive integer. That is, sequences $a_1$, $a_2$, \dots, $a_k$, where $a_1=1$, $a_k=n$, and $a_j