

\ppart Two baseball teams, the $A$'s and the $B$'s, play a series of
games again each other until one team wins a total of 4 games.  For
example, the sequence of winners might look like this:
%
\[
(A, B, A, B, A, A)
\]
%
How many such sequences are possible?

\solution{First, suppose that the $A$'s win the series.  Then the
$A$'s necessarily win the last game.  Thus, the remainder of the
tournament is described by a sequence containing 3 $A$'s and between 0
and 3 $B$'s.  The number of such sequences is:
%
\[
\binom{3}{0} + 
\binom{4}{1} + 
\binom{5}{2} + 
\binom{6}{3}
\]
%
There are an equal number of tournaments where $B$ wins overall, so
the total number of sequences is:
%
\[
2 \cdot \paren{
\binom{3}{0} + 
\binom{4}{1} + 
\binom{5}{2} + 
\binom{6}{3}}
\]
}


\ppart How many $n$-player single-elimination tournaments?  (Work from
root back to leaves!)

\ppart Seatings of students in 300 room exam with none next to each
other and specified number per row?


\newpage

\begin{problem}
Suppose that the function $g(x)$ generates the sequence
%
\[
\seq{t_0, t_1, t_2, \ldots}
\]
%
where:
%
\begin{align*}
t_1 & = 1 \\
t_n & = 2 t_{n-1} + 1 \quad (\text{for } n \geq 1)
\end{align*}
%
Write $g(x)$ in a closed form.

\solution{
We can rewrite the sequence using the equations:
%
\begin{align*}
g(x) & \longleftrightarrow \seq{1, 2 t_0 + 1, 2 t_1 + 1, 2 t_2 + 1, \ldots}
\end{align*}
%
We can also write a generating function for this sequence in terms of
$g(x)$ as follows:
%
\begin{align*}
\seq{t_0, t_1, t_2, \ldots} & \longleftrightarrow g(x) \\
\seq{0, t_0, t_1, t_2, \ldots} & \longleftrightarrow x g(x) \\
\seq{0, 2 t_0, 2 t_1, 2 t_2, \ldots} & \longleftrightarrow 2 x g(x) \\
\seq{1, 2 t_0 + 1, 2 t_1 + 1, 2 t_2 + 1, \ldots} & \longleftrightarrow 2 x g(x) + \frac{1}{1+x} \\
\end{align*}
%
Thus $g(x) = 2 x g(x) + \frac{1}{1+x}$.  Solving for $g(x)$ gives:
%
\[
g(x) = \frac{1}{(1+x)(1-2x)} = \frac{1}{1-x-2x^2}
\]
%
}

\end{problem}
