\documentstyle[12pt,amssymb,amstex,twoside]{article}
\input{macros-course}

\begin{document}

\pset{8}{April 7, 1998}{April 14, 1998}

\bigskip

\begin{problems}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 
{\bf [11 points]}
A donut shop carries just four flavors of donuts: glazed, chocolate,
Boston creme, and strawberry. How many ways can we choose a box of 12
donuts so that we have at least one of each flavor?

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 
{\bf [10 points]}
How many eleven-letter strings can be formed by permuting the letters
in ABRACADABRA?

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 
{\bf [24 points]}

Compute the (ordinary) generating function for each of the
following sequences.

\bparts
\ppart
$\displaystyle \ang{1,1,1,1,1,\ldots}$
\ppart
$\displaystyle \ang{1,1,1,1,0,0,0,0,0,\ldots}$
\ppart
$\displaystyle \ang{0,0,1,1,1,1,1,\ldots }$
\ppart
$\displaystyle \ang{0,0,0,0,1,1,1,1,1,\ldots }$
\ppart
$\displaystyle \ang{0,0,0,1,1,2,1,1,1,1,1\ldots }$
%\ppart
%$\displaystyle \ang{0,0,0,1,2,3,4,5,6,7,8,9\ldots }$
\ppart
$\displaystyle \ang{1,0,0,0,1,0,0,0,1,0,0,0,1,\ldots}$
\ppart
$\displaystyle \ang{1,4,9,16,25,\ldots}$
\ppart
$\displaystyle \ang{2,6,12,20,30,42,56,\ldots}$
\ppart
$\displaystyle \ang{a_k} = \ang{k^2(k+2)}$
\ppart
$\displaystyle \ang{a_k}=\ang{3^k+5^k+7^k}$
\ppart
$\displaystyle \ang{a_k}=\ang{1/k!}$
%\ppart
%$\displaystyle \ang{a_k}=\ang{n\choose k} ~~~~\mbox{for fixed $n$}$
\ppart
$\displaystyle \ang{a_k}=\ang{\sum_{i=0}^k {1\over i!}}$
%\ppart
%$\displaystyle \ang{1,1/2,1/3,1/4,\ldots}$
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
{\bf [15 points]}

Find partial fraction decompositions for the following functions.

%\begin{multicols}{3}
\bparts

\ppart
$\displaystyle \frac{8x}{ 4x^2 -1}$

\ppart
$\displaystyle \frac{x^4 - x^3 - 6x^2 + 6x + 7}{x^2 + 3x + 2}$

\ppart
$\displaystyle \frac{x-5}{x^3 + x^2 - x - 1}$

\eparts
%\end{multicols}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 
{\bf [20 points]}

Use generating functions to solve the recurrence
\[
a_n = \left\{ \begin{array}{ll}
       2^n & \mbox{if $n<3$} \\
       2a_{n-2}+a_{n-3} & \mbox{if $n\geq 3$}
               \end{array}
      \right.
\]
Use induction to check your answer.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\problem 
%
%A communication channel protocol uses sequences of length $n$
%to encode packets, where each sequence is composed of letters in the
%set $\set{a,b,c}$ with the restriction that no two $a$'s can occur
%consecutively.  Use generating functions to determine how many of the
%$3^n$ possible $n$-digit sequences are legal packets.  Also, give a simple
%and tight ($\Theta$) asymptotic bound for your answer.  (\hint Set up
%recurrences for the number of $n$-digit sequences that end with $a$
%and for the number that end with $b$ or~$c$.)  
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 	% Stolen from Brualdi, p. 246
{\bf [20 points]}

Let $S$ be the multiset $\set{\infty\cdot a_1,\infty\cdot
a_2, \infty\cdot a_3,\infty\cdot a_4, \infty\cdot a_5}$.  
For each of the following problem parts, 
determine the generating function for the sequence
$\ang{g_0,g_1,\ldots}$, where $g_r$ is the number of $r$-combinations
of $S$ with the specified added restriction.
\bparts
\ppart Each $a_k$ occurs an even number of times.
\ppart Each $a_k$ occurs a multiple of 5 times.
\ppart The element $a_1$ does not occur, and $a_2, a_3$ occurs at most once.
\ppart The element $a_1$ occurs 2, 5, or 8 times, and the element $a_2$
occurs 4, 7, or 10 times.
\ppart Each $a_k$ occurs at least 15 times.
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{problems}

\end{document}
