\documentclass{article}
\usepackage{amssymb,graphics}

\def\mod#1{\ ({\rm mod\ }#1)}

\begin{document}
\begin{center}
{\Large
MATH 2113/CSCI 2113, Discrete Structures II

Winter 2008

Toby Kenney

\large Homework Sheet 5

Due: Wednesday 13th February: 1:30 PM}
\end{center}

\begin{list}{}{}

\subsection*{Compulsory questions}

\item[1] Let $a_n$ be defined recursively by 
$a_n=\sum_{i=1}^n \frac{a_{n-i}(-1)^{i-1}}{i!}$ for $n\geqslant 1$, and $a_0=1$.

(a) Find the generating function for $a_n$.

(b) Find a general formula for $a_n$.

\item[2] (a) Find a recurrence relation for the number of ways to tile a 
$3\times n$ chessboard with $3\times 1$ blocks.

(b) Find a recurrence relation for the number of ways to tile a $3\times n$ 
chessboard with $3\times 1$ and $3\times 2$ blocks.

\item[3] We have a sequence of $n$ tiles that we want to paint with 4 colours: red, 
green, blue and yellow, in such a way that no two adjacent tiles are the same colour, 
and no two adjacent pairs of tile have the same colours - so for example RGBGB would 
not be a valid colouring, since the sequence GB is repeated.

(a) Find a recurrence relation for the number of valid colourings.

(b) Solve your recurrence relation to get an explicit formula.

\item[4] Define the sequence $a_n$ recursively by $a_0=0$ and $a_{n+1}=2a_n+(n+1)^2$ 
for $n\geqslant 0$.

(a) Find the generating function for $a_n$.

(b) Expand the generating function as a partial fraction.

(c) Use this to find the $a_n$.

\end{list}

\end{document}
