\documentclass[11pt,twoside]{article}
\usepackage{latex-macros/course}

\begin{document}
\inclassproblems{13, Mon.}


%F96 H25-pquiz2

%fall97 prob 10

% Stolen from Brualdi, p. 246


\begin{problem}
\bparts \ppart Let $p_k$ be the number of ways to make change of $k$ cents
with indistinguishable pennies.  Give a generating function
for $p_k$.  \solution{
\[\frac{1}{1-x}.\]
}

\ppart Let $n_k$ be the number of ways to make change of $k$ cents with
indistinguishable nickels.  Give a generating function
for $n_k$.

\solution{
\[
\frac{1}{1-x^5}.
\]
}

\ppart Let $s_k$ be the number of ways to make change of $k$ cents with
indistinguishable pennies or nickels.  Give a generating function for
$s_k$.

\solution{
\[
\frac{1}{1-x}\cdot \frac{1}{1-x^5}.
\]
}

\ppart Give a generating function for the number of ways to make change
of $k$ cents with at least $3$ nickels and an odd number of pennies.

\solution{
\[
\left( \frac{x^{15}}{1-x^5}\right) \left( \frac{x}{1-x^2} \right).
\]
}

\eparts


\end{problem}


\begin{problem}
We're making up gift baskets of four kinds of fruit: apples, oranges,
peaches, and pears.  Various constraints on forming fruit baskets are
given below.  In each case, determine a closed form for the generating
function for the number of possible sets of $n$ pieces of fruit.

\bparts
\ppart Each kind of fruit occurs an odd number of times.

\solution{GF for odd number of apples is $x+x^3+x^5\cdots =
x(1+x^2+x^4+\cdots) =
x/(1-x^2)$.  Same for oranges, peaches and pears.  The number of ways to
choose an odd number of all fours kinds of fruit is therefore
$(x/(1-x^2))^4$.}

\ppart The number of apples is a multiple of 3, of oranges is a multiple
of 5, of peaches is congruent to $ 2 \pmod{5}$, and of pears is between 5
and 8.

\solution{GF for apples is $1/(1-x^3)$, oranges is $1/(1-x^5)$, peaches is
$x^2/(1-x^5)$, and pears is $x^5+x^6+x^7+x^8w$.  The generating function
for the number of sets of $n$ pieces of fruit meeting these specifications
is the product of these four generating functions, namely
\[
\frac{1\cdot 1 \cdot x^2(x^5+x^6+x^7+x^8)}{(1-x^3)(1-x^5)(1-x^5)} =
\frac{x^7+x^8+x^9+x^{10}}{(1-x^3)(1-x^5)^2}.
\]}

\ppart There are no apples and at most one peach.  In this case, use the
generating function to write a closed form for the number of sets of $n$
pieces of fruit meeting these specifications.

\solution{GF for apples is the constant function 1, for peaches is $1+x$,
and for oranges and pears is $1/(1-x)$.  The generating function
for the number of sets of $n$ pieces of fruit meeting these
specifications is the product of these four generating functions, namely
\[
\frac{1\cdot(1+x)}{(1-x)^2} = \frac{1}{(1-x)^2} + \frac{x}{(1-x)^2}.
\]
But
\[
\frac{1}{(1-x)^2} = \frac{d}{dx}\paren{\frac{1}{1-x}}
\]
and differentiating the terms of $1/(1-x)$ yields
\[
\frac{1}{(1-x)^2} = 1 + 2x + 3x^2 + 4x^3 + \cdots,
\]
so the coefficient of $x^n$ in $1/(1-x)^2$ is $n+1$ and in $x/(1-x)^2$ is
$n$, so the coefficient in their sum is $2n+1$.  That is, there are $2n+1$
ways to make up baskets of $n$ pieces of fruit.

This is independently obvious from reasoning by cases: if we pick no
peaches, there can be $k=0$ to $n$ oranges with $n-k$ pears making up the
rest of the basket; so there are $n+1n$ baskets of $n$ pieces of fruit with
no peaches.

Otherwise, there is one peach, and there can be $k=0$ to $n-1$ oranges
with $(n-1)-k$ pears making up the rest of the basket; so there are $n$
baskets of $n$ pieces of fruit with one peach.}

\eparts

\end{problem}

\iffalse  GIVEN OUT, BUT NONE GOT FAR WITH THIS, SO REUSE FOR WEDNESDAY.

\instatements{\newpage}
\begin{problem}

\bparts 

\ppart Let $S(x) \eqdef \sum_{k=1}^{\infty} k^2x^k$.  Verify that
\begin{equation}\label{Sx}
S(x) =\frac{x(1+x)}{(1-x)^3}.
\end{equation}

\hint Consider $\frac{d}{dx} \paren{1 + x + x^2 + x^3 + x^4 + \cdots}$.

\solution{
\begin{eqnarray*}
\frac{d}{dx} \paren{1 + x + x^2 + x^3 + x^4 + \cdots}
	& = & \frac{d}{dx}  \paren{\frac{1}{1-x}} \\
1 + 2x + 3x^2 + 4x^3 + \cdots & = & \frac{1}{(1-x)^2} \\
x + 2x^2 + 3x^3 + 4x^4 + \cdots & = & \frac{x}{(1-x)^2} \\
\frac{d}{dx} \paren{x + 2x^2 + 3x^3 + 4x^4 + \cdots} & = & \frac{d}{dx}
	\paren{\frac{x}{(1-x)^2}} \\
1 + 2^2x + 3^2x^2 + 4^2x^3 + \cdots & = &  x \cdot \frac{2}{(1-x)^3} +
	\frac{1}{(1-x)^2} \\
       &=&  \frac{2x}{(1-x)^3} +
	\frac{1-x}{(1-x)^3} \\
      &=& \frac{1+x}{(1-x)^3}\\
x + 2^2x^2 + 3^2x^3 + 4^2x^4 + \cdots & = &  \frac{x(1+x)}{(1-x)^3}
\end{eqnarray*}
So
\[
S(x) = \frac{x(1+x)}{(1-x)^3}.
\]
}

\ppart Explain why $S(x)/(1-x)$ is the generating function for the sum of
squares.  That is, the coefficient of $x^n$ in the series for $S(x)/(1-x)$
is $\sum_{k=1}^n k^2$.

\solution{
\[
\paren{\sum_{n=0}^{\infty} a_n x^n}\paren{\sum_{n=0}^{\infty} x^n}
= \sum_{n=0}^{\infty} \paren{\sum_{k=0}^{n} a_k} x^n
\]
as a special case of the convolution formula for the product of series.
So in particular for $S(x)$ with $a_k = k^2$, 
\[
\frac{S(x)}{1-x} = S(x)\paren{\sum_{n=0}^{\infty} x^n}, 
\] 
so the coefficient in of $x^n$ is the sum of the first $n$ squares.
}

\ppart Explain why $1/(1-x)^m$ is the generating function for the number
of sets of $n$ elements, chosen \emph{with repetition} from a set of $m$
elements.  Use this observation to write a closed form for the coefficient
of $x^n$ in the series for this generating function.

\solution{
There can be any number of repetitions of the first element, so the
generating function for the number of ways to pick the first element is
$1+x+x^2+\cdots = 1/(1-x)$.  The generating function for the number of
ways to pick all $m$ elements is the product of these individual
generating functions.  

The coefficient of $x^n$ in this product is the number of sets of $n$
elements chosen with repetition from the set of $m$ elements.  But we know
this is $\binom{m+n-1}{n}$.  That is,
\[
\frac{1}{(1-x)^k}= \sum_{n=0}^{\infty} \binom{m+n-1}{n} x^n.
\]}

\ppart  Use the previous parts to prove that
\[
\sum_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}{6}.
\]

\solution{We have from equation~\eqref{Sx} that
\begin{equation}\label{S4}
\frac{S(x)}{1-x} = \frac{x(1+x)}{(1-x)^4}.
\end{equation}

Applying the previous part with $m=4$ we get that the coefficient of $x^n$
in $1/(1-x)^4$ is $\binom{n+3}{n}= \frac{(n+1)(n+2)(n+3)}{3!}$.

But by~\eqref{S4},
\[
\frac{S(x)}{1-x} = \frac{x(1+x)}{(1-x)^4}= \frac{x}{(1-x)^4} +
\frac{x^2}{(1-x)^4},
\]
so the coefficient of $x^n$ is the sum of the $(n-1)$st and $(n-2)$nd
coefficients of $(1-x)^4$, namely,
\[
\frac{n(n+1)(n+2)}{3!}+\frac{(n-1)n(n+1)}{3!}= \frac{n(n+1)(2n+1)}{6}.
\]
}

\eparts

\end{problem}
\fi


\iffalse


%F96 H32-Quiz2sol Prob 8
\begin{problem}
In the following problem, you can leave your answers in closed form, that is,
you do not have to write down the coefficients of the generating
functions explicitly.

\bparts

\ppart Give a generating function for the number of ways to compose a bag of
chocolate donuts, which contains at least $3$ donuts.
\solution{$$G(x) = \frac{x^3}{1-x}$$}

\ppart Give a generating function for the number of ways to compose a bag of
glazed donuts, which contains at most $4$ donuts.
\solution{$$G(x) = \frac{1-x^5}{1-x}$$}

\ppart Give a generating function for the number of ways to compose a bag of
coconut donuts, which contains exactly $2$ donuts.
\solution{$$G(x) = x^2$$}

\ppart Give a generating function for the number of ways to compose a bag of
plain donuts, where the number of donuts in the bag is a multiple of $4$.
\solution{$$G(x) = \frac{1}{1-x^4}$$\\}

\ppart Give a generating function for the number of ways to compose a
bag of donuts where the donuts are of $4$ kinds (chocolate, glazed,
coconut and plain) and all the following conditions hold:
\begin{itemize}
\item at least $3$ are chocolate donuts.
\item at most $4$ donuts are glazed.
\item there are $2$ coconut donuts.
\item the number of plain donuts is a multiple of $4$.
\end{itemize}

\solution{$$ G(x) = \frac{x^3}{1-x} \frac{1-x^5}{1-x}x^2 \frac{1}{1-x^4} =
  \frac{x^5(1+x^2+x^3+x^4)}{(1-x)(1-x^4)}$$}

\eparts

\end{problem}
\fi


\end{document}
