

\bparts

\ppart Let $D_n$ be the number of different collections of $n$ dogs
that can accompany Miss McGillicuddy.  Give a closed-form generating
function $d(x)$ for the sequence:
%
\[
\seq{D_0,\ D_1,\ D_2,\ D_3,\ \ldots}
\]

\solution[\vspace{1.5in}]{
\begin{align*}
s(x) & = x^3 + x^4 + x^5
\end{align*}
}

\ppart Let $S_n$ be the number of different collections of $n$
songbirds that can accompany her.  Give a closed-form generating
function $s(x)$ for the sequence:
%
\[
\seq{S_0,\ S_1,\ S_2,\ S_3,\ \ldots}
\]

\solution[\vspace{1.5in}]{
\begin{align*}
d(x) & = x^2 + x^4 + x^6 + x^8 + \ldots \\
     & = \frac{x^2}{1 - x^2}
\end{align*}
}

\ppart Let $A_n$ be the number of different collections of $n$
alligatorsthat can accompany her.  Give a closed-form generating
function $a(x)$ for the sequence:
%
\[
\seq{A_0,\ A_1,\ A_2,\ A_3,\ \ldots}
\]

\solution[\newpage]{
\begin{align*}
g(x) & = 1 + x
\end{align*}
}

\ppart 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\iffalse
\newpage

\begin{problem}[10 points]
A committee consists of a chair and vice-chair and possibly additional
members.  Give a combinatorial proof of the following identity by
describing two different ways to count the number of committees that can
be formed from a population of $n$ possible committee members.
\[
n(n-1) 2^{n-2} = \sum_{k=1}^n k(k-1) \binom{n}{k}.
\]

\solution[\vspace{3in}]{
Counting Method 1: Represent a committee by a triple consisting of the
chair, the vice-chair, and the set of other committee members.  There are
\begin{equation}\label{nn1}
n(n-1)2^{n-2}
\end{equation}
such triples.

Counting Method 2: Represent a committee of size $k$ by a triple
consisting of the the set of $k$ committee members, the chair, and the
vice-chair.  There are $\binom{n}{k}k(k-1)$ such triples, so the total
number of committees (of all sizes) is
\begin{equation}\label{sk1}
\sum_{k=1}^n k(k-1)\binom{n}{k}.
\end{equation}

Since both Methods count the number of committees, the
expressions~\eqref{nn1} and~\eqref{sk1} must be equal.
}

\end{problem}
\fi


In how many different ways can the squares of a
$4 \times 4$ grid be colored so that exactly four are red, four are
green, four are blue, and four are yellow?  Here is one example of
such a coloring.
%
\begin{center}
\begin{picture}(80,80)
\multiput(0,0)(20,0){5}{\line(0,1){80}}
\multiput(0,0)(0,20){5}{\line(1,0){80}}
{\Large
\put(10,10){\makebox(0,0){B}}
\put(10,30){\makebox(0,0){B}}
\put(10,50){\makebox(0,0){Y}}
\put(10,70){\makebox(0,0){R}}
\put(30,10){\makebox(0,0){G}}
\put(30,30){\makebox(0,0){R}}
\put(30,50){\makebox(0,0){B}}
\put(30,70){\makebox(0,0){B}}
\put(50,10){\makebox(0,0){Y}}
\put(50,30){\makebox(0,0){R}}
\put(50,50){\makebox(0,0){G}}
\put(50,70){\makebox(0,0){Y}}
\put(70,10){\makebox(0,0){Y}}
\put(70,30){\makebox(0,0){G}}
\put(70,50){\makebox(0,0){G}}
\put(70,70){\makebox(0,0){R}}
}
\end{picture}
\end{center}

\solution{There is a bijection from colored grids to sequences with 4
R's, 4 G's, 4 B's, and 4 Y's.  By the Bookkeeper Rule, the number of
such sequences is:
%
\[
\frac{16!}{4!\ 4!\ 4!\ 4!}
\]
%
By the Bijection Rule, this is also the number of colored grids.}

\iffalse
\ppart A shelf holds 17 books in a row.  How many ways are there to
choose 4 books so that there are at least two books between every pair
of chosen books?

\solution[\vspace{3in}]{There exists a bijection from 11-bit sequences
with exactly four 1's to valid book selections.  Map each zero to a
non-chosen book, each of the first three 1's to a chosen book followed
by two non-chosen books, and the last 1 to a chosen book.  For example,
the 11-bit sequence:
%
\[
(0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1)
\]
%
maps to the book selection:
%
\[
\underbrace{n}_{0}\
\underbrace{n}_{0}\ 
\underbrace{c\ n\ n}_{1}\
\underbrace{n}_{0}\
\underbrace{c\ n\ n}_{1}\
\underbrace{c\ n\ n}_{1}\
\underbrace{n}_{0}\ 
\underbrace{n}_{0}\ 
\underbrace{n}_{0}\ 
\underbrace{n}_{0}\ 
\underbrace{c}_{1}
\]
%
where $c$ denotes a chosen book and $n$ denotes a non-chosen book.
Therefore, the number of valid book selections is $\binom{11}{4}$.}
\fi

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\iffalse
\newpage

\begin{problem}[10 points]
Use integration to find lower and upper bounds for the summation:
%
\[
\sum_{k=1}^n k^{3/5}
\]
%
(Your bounds must be asymptotically equal, but you do \underline{not}
need to prove that they are.)
\end{problem}

\solution{

\begin{center}
\unitlength=0.5in
\begin{picture}(9,4.5)(0,-0.5)
% \put(0,-0.5){\framebox(9,4.5){}} % bounding box

\put(0,0){\vector(1,0){9}}
\put(0,0){\vector(0,1){4}}

\qbezier(0.000000,1.000000)(0.419875,1.251925)(1.000000,1.515717)
\qbezier(1.000000,1.515717)(1.452845,1.721632)(2.000000,1.933182)
\qbezier(2.000000,1.933182)(2.466491,2.113544)(3.000000,2.297397)
\qbezier(3.000000,2.297397)(3.473992,2.460739)(4.000000,2.626528)
\qbezier(4.000000,2.626528)(4.478743,2.777420)(5.000000,2.930156)
\qbezier(5.000000,2.930156)(5.482024,3.071397)(6.000000,3.214096)
\qbezier(6.000000,3.214096)(6.484427,3.347552)(7.000000,3.482202)
\qbezier(7.000000,3.482202)(7.486262,3.609197)(8.000000,3.737193)
\put(0.000000,0){\framebox(1.0,1.000000){}}
\put(1.000000,0){\framebox(1.0,1.515717){}}
\put(2.000000,0){\framebox(1.0,1.933182){}}
\put(3.000000,0){\framebox(1.0,2.297397){}}
%\put(4.000000,0){\framebox(1.0,2.626528){}}
%\put(5.000000,0){\framebox(1.0,2.930156){}}
%\put(6.000000,0){\framebox(1.0,3.214096){}}
\put(7.000000,0){\framebox(1.0,3.482202){}}

\put(0.65,0.25){\makebox(0,0){$1^{3/5}$}}
\put(1.5,0.5){\makebox(0,0){$2^{3/5}$}}
\put(2.5,0.75){\makebox(0,0){$3^{3/5}$}}
\put(3.5,0.75){\makebox(0,0){$4^{3/5}$}}
\put(7.5,0.75){\makebox(0,0){$n^{3/5}$}}

\put(1,-0.25){\makebox(0,0){1}}
\put(2,-0.25){\makebox(0,0){2}}
\put(3,-0.25){\makebox(0,0){3}}
\put(4,-0.25){\makebox(0,0){4}}
\put(8,-0.25){\makebox(0,0){$n$}}

\put(5, 3.5){\makebox(0,0){$y = (x+1)^{3/5}$}}
\put(6, 2.5){\makebox(0,0){$y = x^{3/5}$}}

\qbezier(0.000000,0.000000)(0.0,0.4)(1.000000,1.000000)
\qbezier(1.000000,1.000000)(1.419875,1.251925)(2.000000,1.515717)
\qbezier(2.000000,1.515717)(2.452845,1.721632)(3.000000,1.933182)
\qbezier(3.000000,1.933182)(3.466491,2.113544)(4.000000,2.297397)
\qbezier(4.000000,2.297397)(4.473992,2.460739)(5.000000,2.626528)
\qbezier(5.000000,2.626528)(5.478743,2.777420)(6.000000,2.930156)
\qbezier(6.000000,2.930156)(6.482024,3.071397)(7.000000,3.214096)
\qbezier(7.000000,3.214096)(7.484427,3.347552)(8.000000,3.482202)
\end{picture}
\end{center}

\noindent We'll use the bounds:
%
\[
\int_0^n x^{3/5}\ dx \leq \sum_{k=1}^n k^{3/5} \leq \int_0^n (x+1)^{3/5}\ dx 
\]
%
For the lower bound, we get:
%
\[
\int_0^n x^{3/5}\ dx
    = \frac{5}{8} x^{8/5}\ \Bigr|_{x=0}^n \\
    = \frac{5}{8} n^{8/5}
\]
%
For the upper bound, we get:
%
\[
\int_0^n (x+1)^{3/5}\ dx
    = \int_1^{n+1} x^{3/5}\ dx \\
    = \frac{5}{8} x^{8/5}\ \Bigr|_{x=1}^{n+1} \\
    = \frac{5}{8} (n+1)^{8/5} - \frac{5}{8}
\]
}
\fi


\iffalse
\bparts

\ppart Give a closed-form generating function for the sequence:
%
\[
\seq{T_0,\ T_1,\ T_2,\ T_3,\ \ldots}
\]

\solution{
\[
\frac{x^2}{1 - x^2} \cdot (x^3 + x^4 + x^5) \cdot (1 + x)
\]
}

\ppart Give a closed-form expression for $T_{100}$.  Justify your
answer in terms of the generating function.

\solution{
Simplifying the expression above gives:
%
\begin{align*}
(x^5 + x^6 + x^7) \cdot \frac{1}{1 - x}
    & = (x^5 + x^6 + x^7) (1 + x + x^2 + x^3 + \ldots) \\
    & = 
\left(
\begin{array}{cccccccccccc}
x^5 & + & x^6 & + & x^7 & + & x^8 & + & \ldots \\
    & + & x^6 & + & x^7 & + & x^8 & + & \ldots \\
    &   &     & + & x^7 & + & x^8 & + & \ldots \\
\end{array} \right) \\
    & = x^5 + 2 x^6 + 3 x^7 + 3 x^8 + 3 x^9 + 3 x^{10} + \ldots
\end{align*}
%
Thus, we have:
%
\[
T_n =
\begin{cases}
0 & \text{for $n < 5$} \\
1 & \text{for $n = 5$} \\
2 & \text{for $n = 6$} \\
3 & \text{for $n \geq 7$}
\end{cases}
\]
%
And in particular, $T_{100} = 3$.
}

\eparts
\fi