\documentclass[10pt]{article} % 
\usepackage{fullpage}
\usepackage{graphicx}
\usepackage{graphics}
\usepackage{psfrag}
\usepackage{amsmath,amssymb}
%\input{preface}

\setlength{\textwidth}{6.5in}
\setlength{\textheight}{9in}


\date{Spring 2016}


\begin{document} 
\begin{center}
{\bf Math 432 -- Combinatorics\\
Homework 3}\\
Due:  Feb 12  11:58pm, 2016.
\end{center}

Work the following problems. Show all your work. Four points each if not otherwise specified.\\



\begin{enumerate}



\item (6 points) Let $a_n$ be the number of $n$-tuples $(a_1, a_2, \ldots, a_n)$ with $a_i\in [4]$ that have at least one $1$ and have no $2$ appearing before the first 1.  
\begin{itemize}
\item Obtain and solve a recurrence for $a_n$. 
\item Give a direct counting argument (without using summations) to prove the resulting simple formula.  
\end{itemize}

\item Solve the following recurrence relation using characteristic equation method.
 
 $h_n=4h_{n-1}+8h_{n-2}+3n$, $(n\ge 3)$, with $h_1=h_2=1$.

\item Solve the following recurrence relation using generating function method:

 $a_n=5a_{n-1}-6a_{n-2}+2^n$ for $n\ge 3$,  with $a_1=a_2=1$. 
 
 \item (6 points) Let $a_n$ be the number of words of length $n$ on the alphabet $\{0, 1, 2\}$ such that $1$ and $2$ are never adjacent. 
 \begin{itemize}
 \item Obtain a recurrence relation for $a_n$.
 \item Solve for $a_n$ using both the characteristic equation method and the generating function method. 
 \end{itemize}
 
\item (6 points) Let $a_{n,k}$ denote the number of ways to partition $n$ people in a row into $k$ groups so that no two consecutive people are in the same group.  
\begin{itemize}
\item  Obtain a recurrence relation for $a_{n,k}$.   
\item Let $A_k(x)=\sum_{n=0}^{\infty} a_{n,k}x^n$.  Use the generating function method to express $F_k(x)$ as a ratio of polynomials. 
\end{itemize}



\end{enumerate}

\end{document}


