\documentclass[11pt]{book}
\usepackage{fancyheadings}
\usepackage{amssymb}
\usepackage{latexsym}
\usepackage{graphicx, pstcol, pst-plot}
\usepackage{pstricks, pst-node}
\usepackage{hyperref}
\newcommand{\ds}{\displaystyle}
\newcommand{\testname}{Homework \#4}
\newcommand{\testdate}{\today}
%		Problem
\newcounter{problemnumber}
\newcommand{\Problem}{\stepcounter{problemnumber}
       \item[\fbox{\parbox{.25in}{\hfil\theproblemnumber\hfil}}]}
\newcommand{\ProblemStar}{\stepcounter{problemnumber}
       \item[\fbox{\parbox{.25in}{$\star$\hfil\theproblemnumber\hfil}}]}
\newcommand{\Points}[1]{(#1 points) \ }
\newcommand{\Solution}[1]{\medskip\noindent{\bf Solution:}  (#1\%) }
%		Examheader
\newcommand{\Examheader}{\setcounter{problemnumber}{0}
\centerline{\Large\bf \testname}
}

\newcommand{\Circle}{%
\pscircle[linecolor=gray,linewidth=\psxunit](50,50){50\psxunit}
\cnode*(93.3,75){4\psxunit}{A}
\cnode*(50,100){4\psxunit}{B}
\cnode*(6.70,75){4\psxunit}{C}
\cnode*(6.70,25){4\psxunit}{D}
\cnode*(50,0){4\psxunit}{E}
\cnode*(93.3,25){4\psxunit}{F}
}

%		Formatting Parameters
\setlength{\parindent}{0pt}
\pretolerance=4000
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{9in}
\setlength{\textwidth}{7in}
\setlength{\headheight}{26pt}
\setlength{\headsep}{2pt}
\setlength{\headrulewidth}{0pt}
\setlength{\oddsidemargin}{-0.25in}
\setlength{\evensidemargin}{-0.25in}
\lhead{\bf Math 454 Summer 2005}
%\rhead{\bf Name: \rule{2in}{.2pt}}
\rhead{Due Tuesday 8/2/05}
\cfoot{}
\pagestyle{fancy}
%
%
\begin{document}
\thispagestyle{fancy}
\Examheader

\bigskip

First some review problems:

\begin{enumerate}

\Problem Determine the number of solutions of the equation $x_1+x_2+x_3+x_4=14$ in nonnegative integers not exceeding $8$.

\Problem Determine a general formula for the number of permutations of the set $\{1,2,3,\dots,n\}$ in which exactly $k$ integers are in their natural positions.  For example, in the permutation $1436527$ the integers $1$, $5$, and $7$ occur in their natural positions.

\Problem Let $D_n$ denote the number of derangements of $\{1,2,3,\dots,n\}$.  We proved in class that
$$
D_n=n!\left(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\cdots\pm\frac{1}{n!}\right).
$$
Use this to establish recurrence relation $D_n=(n-1)(D_{n-2}+D_{n-1})$ (for $n\ge 3)$.

\ProblemStar Give a combinatorial proof of this recurrence relation.

\Problem We proved in class that the $n$th Fibonacci number, $f_n$, is given by the formula
$$
f_n=\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^n-\frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^n.
$$
Prove that $f_n$ is actually the nearest integer to 
$$
\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^n.
$$

\Problem Solve the recurrence relation given by
\begin{eqnarray*}
a_n&=&2a_{n-1}+{n\choose 2}\ \ \mbox{for $n\ge 1$},\\
a_0&=&0.
\end{eqnarray*}

\Problem Solve the recurrence relation
$$
a_n=8a_{n-1}-16a_{n-2},
$$
(for $n\ge 2$) with $a_0=-1$ and $a_1=0$.

\Problem Solve the recurrence relation given by
\begin{eqnarray*}
a_n&=&(n+2)a_{n-1}\ \ \mbox{for $n\ge 1$},\\
a_0&=&2.
\end{eqnarray*}

\Problem Determine a recurrence relation for the number, $a_n$, of ternary strings (i.e., strings made up of $0$'s, $1$'s, and $2$'s) of length $n$ that contain neither two consecutive $0$'s nor two consecutive $1$'s.  Then use this recurrence relation to find a formula for $a_n$.

\Problem Fix $2n$ equally spaced points on a circle.  Show that the number of ways to join these points in pairs so that the resulting $n$ line segments do not intersect equals the $n^{\rm th}$ Catalan number.  For example, here are the $5$ ways to do this when $n=3$:

$$
\begin{array}{ccccccccc}
\psset{xunit=0.006in, yunit=0.006in}
\begin{pspicture}(0,0)(100,100)
\Circle
\ncline{A}{B}
\ncline{C}{F}
\ncline{D}{E}
\end{pspicture}
&
\hfil
&
\psset{xunit=0.006in, yunit=0.006in}
\begin{pspicture}(0,0)(100,100)
\Circle
\ncline{A}{D}
\ncline{B}{C}
\ncline{F}{E}
\end{pspicture}
&
\hfil
&
\psset{xunit=0.006in, yunit=0.006in}
\begin{pspicture}(0,0)(100,100)
\Circle
\ncline{B}{E}
\ncline{C}{D}
\ncline{A}{F}
\end{pspicture}
&
\hfil
&
\psset{xunit=0.006in, yunit=0.006in}
\begin{pspicture}(0,0)(100,100)
\Circle
\ncline{A}{B}
\ncline{C}{D}
\ncline{F}{E}
\end{pspicture}
&
\hfil
&
\psset{xunit=0.006in, yunit=0.006in}
\begin{pspicture}(0,0)(100,100)
\Circle
\ncline{A}{F}
\ncline{B}{C}
\ncline{D}{E}
\end{pspicture}
\end{array}
$$

\Problem Show that the number of permutations of $\{1,2,3,\dots,n\}$ that do not have an $acb$-pattern is the $n^{\rm th}$ Catalan number\footnote{A permutation $\pi$ has an $acb$-pattern if there are indices $1\le i<j<k$ for which $\pi(i)<\pi(k)<\pi(j)$, i.e., their values read small, large, medium.}.

\Problem Determine the generating function for the number, $a_n$, of bags contain $n$ total apples, oranges, bananas, and pears in which:
\begin{enumerate}
\item the number of apples is even,
\item there are at most two oranges,
\item the number of bananas is divisible by $3$,
\item there cannot be any pears if there are bananas, but otherwise there can be any number of pears.
\end{enumerate}

\Problem Invent a combinatorial problem that gives the following generating function
$$
(1+x+x^2)\cdot\left(\frac{1}{1-x^2}\right)\cdot\left(\frac{1}{1-x^3}\right).
$$

\Problem Complete the following $3\times 7$ Latin rectangle
$$
\left[\begin{array}{ccccccc}
0&1&2&3&4&5&6\\
2&3&0&6&5&4&1\\
1&4&6&0&2&3&5
\end{array}
\right].
$$

\Problem How many $2\times n$ Latin rectangles have first row equal to
$$
\left[\begin{array}{ccccc}
0&1&2&\cdots&n-1\\
\end{array}\right]?
$$

\end{enumerate}




\end{document}