\documentclass[12pt]{article}
\usepackage{latex-macros/course}% !! Use the macros

\renewcommand{\coursecopyrightnames}
{\href{http://theory.csail.mit.edu/~meyer}{Prof.~Albert~R.~Meyer}}
\renewcommand{\coursecopyrightyear}{2005}

\renewcommand{\reading}{Counting Notes, II.\S 4--5; Notes on Generating Functions}

\newcommand{\rem}{\operatorname{\,rem\,}}

\begin{document}
\problemset{8}


\begin{problem}
Find the coefficients of

\bparts

\problempart $x^{10}$ in $(x+(1/x))^{100}$

\solution{
$x^{55}(1/x)^{45} = x^{10}$ so  the coefficient is
\[
\binom{100}{55}
\]
}

\ppart $x^k$ in $(x^2 - (1/x))^{n}$.

\solution{
$x^k$ must equal $(x^2)^j(1/x)^(n-j)$ for some $j$ where $0\leq j
\leq n$, in which case $j=(n+k)/3$.  In such a case the coefficient is
\[
\binom{n}{j}(-1)^{n-j} = \binom{n}{(n + k)/{3}}(-1)^{(2n - k)/3}.
\]
}

\eparts

\end{problem}


% F04, ps9, which was a complete revision of F97 Pset8, Prob 2

\begin{problem}
Suppose a generalized World Series between the Sox and the Cardinals
involved $2n+1$ games.  As usual, the generalized Series will stop as soon
as one team has won more than half the possible games.

\bparts

\ppart\label{exr} Suppose that when the Sox finally win the GSeries, the
Cards have managed to win \emph{exactly} $r$ games (so $r \le n$).  How
many possible win-loss patterns are possible for the Sox to win the GSeries
in this way?  Express your answer as a binomial coefficient.

\solution{
\begin{equation}\label{nrr}
\binom{n+r}{r}
\end{equation}

Stars and bars, or better ``S'''s and ``C'''s: we can represent a win-loss
pattern as a sequence of $r$ C's and $n+1$ S's, where an S in the $i$th
position indicates that the Sox won the $i$th game.  However, the sequence
must end with an $S$, so the number of such sequences is the same as the
number of sequences of $r$ C's and $n$ S's, namely~\eqref{nrr}.}

\ppart\label{mostr} How many possible win-loss patterns are possible for
the Sox to win the GSeries when the Cards win \emph{at most} $r$ games?
Express your answer as a binomial coefficient.

\solution{
\begin{equation}\label{nr1}
\binom{n+r+1}{r}
\end{equation}

We can represent a win-loss pattern as a sequence of $r$ C's and $n+1$ S's,
as in part~\eqref{exr}.  The number of C's which occur before the $n+1$st
(last) $S$ is the number of games the Cards won when the GSeries ends.}

\ppart\label{ss} Give a combinatorial proof that
\begin{equation}\label{sib}
\sum_{i=0}^r \binom{n+i}{i} = \binom{n+r+1}{r}.
\end{equation}

\solution{The righthand side of~\eqref{sib} is the number of patterns where
the Cards win at most $r$ games.  But they can at most $r$ by winning
exactly $i$ games, where $0 \leq i \leq r$.  So by part~\eqref{exr}, the
number of win-loss patterns is given by the expression of the lefthand side
of~\eqref{sib}.}

\ppart Verify equation~\eqref{sib} by induction using algebra.

\solution{By induction on $r$, taking~\eqref{sib} as $P(r)$.
\begin{proof}
\textbf{Base case ($r = 0$):}
\[
\binom{n}{0} = 1 = \binom{n+1}{0}.
\]

{\bf Inductive step:}
\begin{align*}
\sum_{i=0}^{r+1} \binom{n+i}{i} & = \binom{n+r+1}{r+1} + \sum_{i=0}^{r} \binom{n+i}{i}\\
& =  \binom{n+r+1}{r+1} + \binom{n+r+1}{r} & \text{(by Ind. Hyp.)}\\
& =  \binom{n+(r+1) + 1}{r+1} & \text{(Pascal's identity)},
\end{align*}
Which proves $P(r+1)$.
\end{proof}
}

\eparts

\end{problem}



\begin{problem}
\bparts \ppart\footnote{From Rosen, 5th ed., \S6.1,
Exercise 34.} Let $a_n$ be the number of length $n$ ternary strings
(strings of the digits 0, 1, and 2) that contain two consecutive digits
that are the same.  For example, $a_2=3$ since the only ternary strings of
length 2 with matching consecutive digits are \texttt{11}, \texttt{22},
and \texttt{33}.  Also, $a_0=a_1=0$, since in order to have consecutive
matching digits, a string must be of length at least two.

Find a recurrence formula for $a_n$.

\solution{
Call a ternary string with at least two consecutive matching digits a
\emph{good} string.  Let $a_n$ be the number of good strings of length
$n$.  Call the other $3^n-a_n$ strings of length $n$ the \emph{bad}
strings.

Now for $n \ge 2$, a good string of length $n$ consists of (1) a good
string of length $n-1$ followed by any digit, or else (2) a bad string of
length $n-1$ followed by a digit that matches the last symbol of the bad
string.  (Note that there is such a last symbol because $n-1 \ge 1$.)
There are $3a_{n-1}$ strings of type (1) and $3^{n-1}-a_{n-1}$ strings of
type (2), and these two types of strings are disjoint.  So
\[
a_n = 3a_{n-1}+3^{n-1}-a_{n-1} = 2a_{n-1} + 3^{n-1}.
\]
Also, a good string must have at least two digits, so $a_0=a_1=0$.
}

\ppart Show that
\[
\frac{-x}{1-2x} + \frac{x}{(1-3x)(1-2x)}
\]
is a closed form for the generating function of the sequence $a_0,a_1,\dots$

\solution{For $n \ge 1$, the coefficient of $x^n$ in the series expansion
of $2xA(x)$ is $2a_{n-1}$, and the coefficient of $x^n$ in
\[
x+3x^2+3^2x^3+\cdots+3^{n-1}x^n+\cdots =
x(1+3x+(3x)^2+\cdots+(3x)^{n-1}+\cdots) = \frac{x}{1-3x}
\]
is obviously $3^{n-1}$.  So in the series for $A(x) - 2xA(x) - x/(1-3x)$,
all the coefficients of $x^n$ for $n\ge 2$ are zero.  This leaves
\[
A(x) - 2xA(x) - \frac{x}{1-3x} = (a_0+a_1x)-2a_0x - x = -x.
\]
So
\begin{equation}\label{Ax}
A(x) = \frac{-x}{1-2x} + \frac{x}{(1-3x)(1-2x)} = \frac{3x^2}{(1-3x)(1-2x)}.
\end{equation}
}

\ppart Find real numbers $r$ and $s$ such that 
\[
\frac{1}{(1-2x)(1-3x)} = \frac{r}{1-2x} + \frac{s}{1-3x}.
\]

\solution{Expressing the righthand side of this equation as
\[
\frac{r(1-3x) + s(1-2x)}{(1-2x)(1-3x)},
\]
we need $r,s$ so the numerators of the left and righthand expressions are
equal, namely, so that
\[
1 = r(1-3x) + s(1-2x).
\]

So letting $x=1/2$, we conclude that $1=r(-1/2)$ so $r=-2$, and letting
$x=1/3$, we conclude that $1=s(1/3)$, so $s=3$.
}

\ppart Use the previous results to write a closed form for the $n$th term
in the sequence.

\solution{From equation~\eqref{Ax}, the generating function is
\[
3x^2\paren{\frac{1}{(1-2x)(1-3x)}} = 3x^2 \paren{\frac{-2}{1-2x} +
  \frac{3}{1-3x}}.
\]

So for $n \ge 2$, the coefficient of $x^n$ in the generating function is
$3\cdot(-2)$ times the coefficient of $x^{n-2}$ in $1/(1-2x)$, plus
$3\cdot 3$ times the coefficient of $x^{n-2}$ in $1/(1-3x)$.  Namely,
\[
a_n = (-3\cdot 2)2^{n-2} + 3^2 3^{n-2} = 3(3^{n-1} - 2^{n-1}).
\]
}

\eparts

\end{problem}


%Fall96, pset9, and later terms; Stolen from Brualdi, p. 246

\begin{problem}
Suppose there are four kinds of doughnuts: plain, chocolate, glazed, and
butterscotch.  Write generating functions for the number of ways to select
the flavors of $n$ doughnuts, subject to the following different
constraints.

\bparts
\ppart Each flavor occurs an odd number of times.

\solution{Generating function for picking chocolate doughnuts is
$x/(1-x^2)$, so for all 4 doughnuts it is
\[
\paren{\frac{x}{1-x^2}}^4.
\]
}

\ppart Each flavor occurs a multiple of 3 times.

\solution{
GF for chocolate is $1/(1-x^3)$ so
\[
\paren{\frac{1}{1-x^3}}^4
\]
for all 4 kinds.
}

\ppart There are no chocolate doughnuts and at most one glazed doughnut.

\solution{ GF for chocolate is $1$, for glazed $1+x$, for others
$1/(1-x)$, so for all 4 it is
\[
\frac{1+x}{(1-x)^2}
\]
}

\ppart There are 1, 3, or 11 chocolate doughnuts, and 2, 4, or 5 glazed.

\solution{
GF for chocolate is
$x+x^3+x^{11}$, for glazed $x^2+x^4+x^5$, and $1/(1-x)$ for the others, so
\[
\frac{(x+x^3+x^{11})(x^2+x^4+x^5)}{(1-x)^2}.
\]
for all.
}

\ppart Each flavor occurs at least 10 times.

\solution{GF for chocolate is $x^{10}/(1-x)$, so
\[
\frac{x^{40}}{(1-x)^4}
\]
for all 4.
}

\eparts

\end{problem}

\end{document}
