\documentclass[12pt,twoside]{article}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{graphics}
\input{macros-course}
\begin{document}
\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}

%\newcommand{\solution}[1]{}
%\pset{8}{November 3, 1998}{Start of class on November 10, 1998}

\newcommand{\solution}[1]{\bigskip #1}
\psol{8}{November 13, 1998}

\centerline{\bf Read sections 4.3, 4.4, and Appendix 3 in Rosen.}

\begin{problems}

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

\problem {\bf (15 points)} Solve the following counting problems.
Simplifying expressions is unnecessary.

\begin{problemparts}

\problempart Find the number of 5-card hands with consecutive values,
e. g. $8\clubsuit \ 9\heartsuit \ 10\diamondsuit \ J\diamondsuit \
Q\spadesuit$.  (Assume that the value of an ace is just above the
value of a king.)

\solution{There are 9 possible sequences of five consecutive values.
For each sequence, there are $4^5$ hands, since each value can be
represented by one of four different suits.  Therefore, there are a
total of $9 \cdot 4^5$ such hands.}

\problempart Find the number of 5-card hands with exactly three aces.

\solution{ We can choose the three aces in $\binom{4}{3}$ ways, and
we can choose the remaining two cards in $\binom{48}{2}$ ways.  Thus,
there are $\binom{4}{3} \binom{48}{2}$ such hands.}

\problempart Find the number of 5-card hands in which every suit
appears at most twice.

\solution{There are two cases.  Either one suit appears twice or else
two suits appear twice.  The number of hands in which one suit appears
twice is $\binom{13}{2} \cdot 13^3 \cdot 4$.  The number of hands in
which two suits appear twice is $\binom{13}{2}^2 \cdot 13 \cdot 12$.
Therefore, there are a total of

\[
\binom{13}{2} \cdot 13^3 \cdot 4 + \binom{13}{2}^2 \cdot 13 \cdot 12
\]

such hands.}

\problempart There are 15 sidewalk squares in front of the Lab for
Computer Science.  Suppose that Theory Pig can be thrown so that he
bounces on 0, 1, 2, or 3 distinct sidewalk squares.  How many
different throws are possible?

\solution{
\[
\binom{15}{0} + \binom{15}{1} + \binom{15}{2} + \binom{15}{3}
\]
}

\problempart In how many different ways can the numbers shown on a red
die, a green die, and a blue die total up to 15?  Assume that these
are ordinary, 6-sided dice.

\solution{We fall back on explicit enumeration.  Let $R$, $G$, and $B$
be the values shown on the three dice.

\begin{eqnarray*}
R = 1, B + G = 14 & \rightarrow & 0 \ \text{ways} \\
R = 2, B + G = 13 & \rightarrow & 0 \ \text{ways} \\
R = 3, B + G = 12 & \rightarrow & 1 \ \text{way} \\
R = 4, B + G = 11 & \rightarrow & 2 \ \text{ways} \\
R = 5, B + G = 10 & \rightarrow & 3 \ \text{ways} \\
R = 6, B + G = 9 & \rightarrow & 4 \ \text{ways} \\
\end{eqnarray*}

Thus there are 10 ways in total.
}

\problempart How many permutations are there of the letters
$MISSISSIPPI$?

\solution{
\begin{eqnarray*}
\frac{11!}{4! \ 4! \ 2!}	& = &	34650
\end{eqnarray*}
}

\problempart Find the number of squences of $k$ non-negative integers
with sum equal to $n$.  For example, if $k = 2$ and $n = 3$, then
there are four sequences: $0 + 3$, $1 + 2$, $2 + 1$, and $3 + 0$.

\solution{This is equal to the number of strings with $n$ stars and
$k-1$ bars.  The sizes of the $k$ groups of stars are the values of
the $k$ integers in the sequence.  Thus, there are

\[
\binom{n+k-1}{n}
\]

such sequences.
}

\problempart Find the number of squences of $k$ positive integers with
sum equal to $n$.  For example, if $k = 2$ and $n = 4$, then there are
three sequences: $1 + 3$, $2 + 2$, and $3 + 1$.

\solution{This is equal to the number of strings with $n-k$ stars and
$k-1$ bars.  Numbers in the sequence are one greater than the sizes of
the groups of stars.  Thus, there are

\[
\binom{n-1}{k-1}
\]

sequences.}

\end{problemparts}

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

\problem {\bf (10 points)} Solve the following counting problems.

\begin{problemparts}
\problempart Suppose that Theory Pig starts at position $(0, 0)$.  At
any time, he can step north (incrementing the first coordinate) or
step east (incrementing the second coordinate).  In how many different
ways can he reach position $(n, n)$, where $n$ is a non-negative
integer?

\solution{Theory Pig must take $2n$ steps in total.  Of these, he must
choose a subset of $N$ to be north steps.  This gives $\binom{2n}{n}$
different ways to reach $(n, n)$.}

\problempart How many different ways are there to list the numbers $1,
2, \ldots, 2n$ such that the even numbers appear in increasing order
and the odd numbers appear in decreasing order?

\solution{ There are $(2n)!$ ways to list the numbers $1, 2, \ldots,
n$.  We can define a $n!$-to-1 mapping that takes an arbitrary listing
to a listing in which the even numbers are sorted in increasing order
and the odd numbers remain as before.  Thus, by the quotient rule
there are $(2n)!/n!$ listings in which the even numbers appear in
increasing order.  Similarly, we can define an $n!$-to-1 mapping that
takes a listing in which the even numbers appear in increasing order
and the odd numbers are in an arbitrary order to a listing in which
the even numbers appear in increasing order (as before) and the odd
numbers appear in decreasing order.  Therefore, there are

\begin{eqnarray*}
\frac{(2n)!}{n! \ n!} & = & \binom{2n}{n}
\end{eqnarray*}

listings in which the even numbers are increasing and the odd numbers
are decreasing.
}

\problempart Describe a bijection that maps each one of Theory Pig's
paths to a listing of the numbers $1, 2, \ldots 2n$ with even numbers
increasing and odd numbers decreasing.

\solution{Each time Theory Pig take a step north, write down an even
number, starting with 2 and working up.  Each time Theory Pig takes a
step east, write an odd number, starting with $2n-1$ and working down.}

\end{problemparts}

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

\problem {\bf (20 points)} Suppose that every two people either know
one another or else are strangers.  How many people must there be in a
room to guarantee that there are either 6 people who all know each
other or 6 people who are all strangers to one another?

The solution to this problem is a number called $R(6, 6)$.  The
solution to the simpler problem involving groups of only 5 people is
called $R(5, 5)$.  Earlier in the course, we solved a still-simpler
version of this problem involving groups of just 3 people in about ten
minutes.  Finding $R(5, 5)$ and $R(6, 6)$ is a bit more tricky.  The
following is taken from a well-known text, {\em Ten Lectures on the
Probabilistic Method}, by Joel Spencer:

\begin{quotation}
Erdos [possibly the 20th century's top mathematician] asks us to
imagine an alien force, vastly more powerful than us, landing on Earth
and demanding the value of $R(5, 5)$ or they will destroy our planet.
In that case, he claims, we should marshall all our computers and all
our mathematicians and attempt to find the value.  But suppose,
instead, that they ask for $R(6, 6)$.  In that case, he believes, we
should attempt to destroy the aliens.
\end{quotation}

Given rumors that a new fleet is forming on Xoros 19, we had better
take a stab at $R(6, 6)$.  For now, however, we will only try to prove
that $R(6, 6) > 17$.

\begin{problemparts}
\problempart If there are $n$ people in a room, then how many
different pairs of people are there?

\solution{
\[
\binom{n}{2}
\]
}

\problempart A {\em configuration} of a group of people is a setting
of who-knows-who.  For example, there are two possible configurations
of a group of just two people: either they know each other or they are
strangers.  How many different configurations are possible in a room
with $n$ people?

\solution{Since every two people either know each other or are
strangers, the number of configurations is

\[
2^{\binom{n}{2}}.
\]
}

\problempart Suppose that there is a specific group of six people who
all know each other.  How many configurations are possible with this
restriction?

\solution{
\[
2^{\binom{n}{2} - \binom{6}{2}}
\]
}

\problempart In a set of $n$ people, how many different subsets of six
people are there?

\solution{
\[
\binom{n}{6}
\]
}

\problempart Use your answers to the preceding two parts to find an
upper bound on the number of configurations in which there exists some
group of six people who all know each other.

\solution{There are $\binom{n}{6}$ different sets of six people.  For
each set of six people, there are $2^{\binom{n}{2} - \binom{6}{2}}$
configurations in which these people all know each other.  Therefore,
there are at most

\[
\binom{n}{6} \cdot 2^{\binom{n}{2} - \binom{6}{2}}
\]

configurations in which some set of six people all know each other.
}

\problempart Give an upper bound on the number of configurations in
which there exist either six people who all know each other or six
people who are all strangers.

\solution{
There are at most

\[
\binom{n}{6} \cdot 2^{\binom{n}{2} - \binom{6}{2}}
\]

configurations in which some six people all know each other.  By the
same argument, there are at most this many configurations of six
people that are all strangers.  Therefore, there are at most

\[
2 \cdot \binom{n}{6} \cdot 2^{\binom{n}{2} - \binom{6}{2}}
\]

configurations in which some six people either all know each other or
are all strangers.}

\problempart Use your answers to parts (b) and (f) to prove that there
exists a configuration of $17$ people such that no set of six people
all know each other or are all strangers.  This implies that $R(6, 6)
> 17$.

\solution{
By part (a), there are

\[
2^{\binom{17}{2}}
\]

configurations of 17 people.  By part (f) there are at most

\[
2 \cdot \binom{17}{6} \cdot 2^{\binom{17}{2} - \binom{6}{2}}
\]

configurations in which some set of six people either all know each
other or are all strangers.  If the first quantity is greater than the
second, then there must exist a configuration of 17 people such that
there is no set of six people that all know each other or are all
strangers.  The second quantity divided by the first is

\begin{eqnarray}
2 \cdot \binom{17}{6} \cdot 2^{- \binom{6}{2}} & \approx & 0.75.
\end{eqnarray}

Therefore, the first quantity is greater than the second, as desired.

The best known bounds are $102 \leq R(6, 6) \leq 165$.
Asymptotically, the simple technique outlined above gives a lower
bound on $R(k, k)$ that is within a factor of 2 of the best known.}

\end{problemparts}

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

\problem {\bf (10 points)} Find generating functions for the following
sequences.

\begin{problemparts}

\problempart $< 0, 0, 1, 1, 1, 1, 1, \ldots >$

\solution{
\begin{eqnarray*}
x^2 + x^3 + x^4 + x^5 + x^6 + \ldots
	& = &	x^2 \cdot (1 + x + x^2 + x^3 + x^4 + \ldots) \\
	& = &	\frac{x^2}{1-x}
\end{eqnarray*}
}

\problempart $< 0, 2, 4, 6, 8, 10, \ldots >$

\solution{
\begin{eqnarray*}
0 + 2 x +  4 x^2 + 6 x^3 + 8 x^4 + \ldots
	& = &	2x \cdot (0 + 1 + 2 x + 3 x^2 + 4 x^3 \ldots) \\
	& = &   2x \cdot \frac{d}{dx} \ (1 + x + x^2 + x^3 + x^4 + \ldots) \\
	& = & 	2x \cdot \frac{d}{dx} \ \left(\frac{1}{1-x} \right)\\
	& = &	\frac{2x}{(1-x)^2}
\end{eqnarray*}
}

\problempart $< 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, \ldots >$

\solution{
\begin{eqnarray*}
1 + x^3 + x^6 + x^{9} + x^{12} + \dots	& = &	\frac{1}{1 - x^3}
\end{eqnarray*}
}

\problempart $< 2^0, 2^1, 2^2, 2^3, 2^4, 2^5, \ldots  >$

\solution{
\begin{eqnarray*}
\lefteqn{2^0 + 2^1 x + 2^2 x^2 + 2^3 x^3 + 2^4 x^4 + \ldots}
\hspace{1in} \\
	& = &	(2x)^0 + (2x)^1 + (2x)^2 + (2x)^3 + (2x)^4 + \ldots \\
	& = &	\frac{1}{1 - 2x}
\end{eqnarray*}
}

\problempart $< -1, 0, 1, -1, 0, 1, -1, 0, 1, -1, 0, 1, \ldots >$

\solution{
\begin{eqnarray*}
\lefteqn{-1 + x^2 - x^3 + x^5 - x^6 + x^8 - \ldots}
\hspace{1in} \\
	& = & (x^2 + x^5 + x^8 + \ldots) - (1 + x^3 + x^6 + \ldots) \\
	& = & x^2 (1 + x^3 + x^6 + \ldots) - (1 + x^3 + x^6 + \ldots) \\
	& = & (x^2 - 1) \cdot (1 + x^3 + x^6 + \ldots) \\
	& = & \frac{x^2 - 1}{1 - x^3}
\end{eqnarray*}
}

\end{problemparts}

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

\problem {\bf (10 points)} Suppose that $f(x)$ is the generating
function for the sequence $a_0, a_1, a_2, \ldots$.  Find generating
functions for the following sequences.

\begin{problemparts}
\problempart $< 0, 0, 0, a_0, a_1, a_2, \ldots >$

\solution{
\begin{eqnarray*}
a_0 x^3 + a_1 x^4 + a_2 x^5 + \ldots
	& = &	x^3 \cdot (a_0 + a_1 x + a_2 x^2 + \ldots) \\
	& = &	x^3 f(x)
\end{eqnarray*}
}

\problempart $< a_0, a_1 + 1, a_2 + 2, a_3 + 3, \ldots >$

\solution{
\begin{eqnarray*}
\lefteqn{a_0 + (a_1 + 1) x + (a_2 + 2) x^2 + (a_3 + 3) x^3 + \ldots}
\hspace{1in} \\
	& = &	(a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \ldots)
		+ (0 + 1 x + 2 x^2 + 3 x^3 + \ldots) \\
	& = &	f(x) + \frac{x}{(1 - x)^2}
\end{eqnarray*}
}

\problempart $< a_0, 0, a_1, 0, a_2, 0, a_3, 0, \ldots >$

\solution{
\begin{eqnarray*}
a_0 + a_1 x^2 + a_2 x^4 + a_3 x^6 + \ldots
	& = &	f(x^2)
\end{eqnarray*}
}

\problempart $< a_0, -a_1, a_2, -a_3, a_4, \ldots >$

\solution{
\begin{eqnarray*}
a_0 - a_1 x + a_2 x^2 - a_3 x^3 + a_4 x^4 - \ldots
	& = &	f(-x)
\end{eqnarray*}
}

\problempart $< a_0, 0, a_2, 0, a_4, 0, \ldots >$

\solution{
\begin{eqnarray*}
\lefteqn{a_0 + a_2 x^2 + a_4 x^4 + a^6 x^6 + \ldots}
\hspace{1in} \\
	& = &	\frac{1}{2} (
		(a_0 - a_1 x + a_2 x^2 - a_3 x^3 + \ldots) \\
	&   & \mbox{} + (a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \ldots)) \\
	& = &	\frac{1}{2}(f(-x) + f(x))
\end{eqnarray*}
}

\end{problemparts}

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

\problem {\bf (10 points)} For each of the following generating
functions, find a closed-form expression for the coefficient of $x^n$.

\begin{problemparts}
\problempart
\[
\frac{5 - 11x}{4x^2 - 5x + 1}
\]

\solution{We will use the partial fractions method.  The roots of the
denominator are $x = 1$ and $x = \frac{1}{4}$.  Therefore, we look for
a partial fractions expansion of the form

\begin{eqnarray*}
\frac{5 - 11x}{(1-x)(1-4x)}	& = &	\frac{A}{1 - x} + \frac{B}{1 - 4x}.
\end{eqnarray*}

Multiplying by the denominators gives:

\begin{eqnarray*}
5 - 11x	& = &	A (1 - 4x) + B (1 - x)
\end{eqnarray*}

Setting $x = 1$ gives $A = 2$, and setting $x = \frac{1}{4}$ gives $B
= 3$.  Therefore, we can rewrite the generation function as

\begin{eqnarray*}
\frac{5 - 11x}{4x^2 - 5x + 1}
	& = &	\frac{2}{1 - x} + \frac{3}{1 - 4x} \\
	& = &	2 (1 + x + x^2 + x^3 + \ldots) + \\
	&   &	3 (1 + 4x + 4^2 x^2 + 4^3 x^3 + \ldots)
\end{eqnarray*}

Therefore, the coefficient of $x^n$ is $3 \cdot 4^n + 2$.
}

\problempart
\[
\frac{2x}{(1-x)^3}
\]

\solution{ The partial fractions expansion of the above expression is
itself.  Therefore, we take successive derivatives.  One helpful
observation is that the sequence generated by this function is
equivalent to doubling and shifting the sequence generated by $f(x) =
1/(1-x)^3$.  Therefore, we only need to find the sequence
generated by $f(x)$, which involves easier derivatives.

\begin{eqnarray*}
f(x)	& = &	\frac{1}{(1-x)^3} \\
f'(x)	& = &	\frac{3}{(1-x)^4} \\
f''(x)	& = &	\frac{3 \cdot 4}{(1-x)^5} \\
f'''(x)	& = &	\frac{3 \cdot 4 \cdot 5}{(1-x)^6} \\
\\
\ldots & \ldots & \ldots \\
\\
f^{(n)}(x)	& = &	\frac{(n+2)!}{2} \cdot \frac{1}{(1-x)^{n+3}}
\end{eqnarray*}

The coefficient of $x^n$ in $f(x)$ is equal to $f^{(n)}(0)/n!$, which
is $(n+1)(n+2)/2$.  Therefore, the coefficient of $x^n$ in the
original generating function is $n(n+1)$.
}

\end{problemparts}

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

\problem {\bf (15 points)} In this problem, we use generating functions
to compute the number of $m$ bit strings with a multiple of three 1's.
For example, if $m = 4$, then there are five such strings:

\[
\begin{array}{ccccc}
0000 &\quad&	1110	&\quad&	1101 \\
1011 &\quad&	0111		\\
\end{array}
\]

\begin{problemparts}
\problempart Use summation notation and binomial coefficients to
describe the number of $m$-bit strings with a multiple of three 1's.

\solution{
\[
\sum_{i=0}^{\left\lfloor\frac{m}{3}\right\rfloor} \binom{m}{3i}
\]
}
\end{problemparts}

The following fact will be useful in evaluating this sum.  Let $z_1 =
1$, $z_2 = -\frac{1}{2} + \frac{\sqrt{3}}{2} i$, and $z_3 =
-\frac{1}{2} - \frac{\sqrt{3}}{2} i$.  The expression
$\frac{1}{3}(z_1^k + z_2^k + z_3^k)$ is then equal to 1 if $k$ is a
multiple of 3 and is equal to 0 otherwise.

\begin{problemparts}
\problempart Left $f(x)$ be a generating function for the series $<
a_0, a_1, a_2, \ldots >$.  Give a closed-form expression for the
following sum.

\[
\sum_{i=0}^{\infty} a_{3i}
\]

\solution{
\begin{eqnarray*}
\sum_{i=0}^{\infty} a_{3i}
	& = &	\sum_{k=0}^{\infty} a_k \cdot \frac{z_1^k+z_2^k+z_3^k}{3}\\
	& = &	\frac{1}{3} \cdot \left(
		\sum_{k=0}^{\infty} a_k z_1^k +
		\sum_{k=0}^{\infty} a_k z_2^k +
		\sum_{k=0}^{\infty} a_k z_3^k
		\right) \\
	& = &	\frac{f(z_1) + f(z_2) + f(z_3)}{3}
\end{eqnarray*}
}

\problempart Recall that $f(x) = (1 + x)^m$ is the generating function
for binomial coefficients; that is, for $0 \leq k \leq m$, the
coefficient of $x^k$ is $\binom{m}{k}$, and for $k > m$, the
coefficient of $x^k$ is zero.  Combine this fact and the two preceding
problem parts to obtain a closed-form expression for the number of
$m$-bit strings with a multiple of three 1's.

\solution{
\begin{eqnarray*}
\sum_{i=0}^{\left\lfloor\frac{m}{3}\right\rfloor} \binom{m}{3i}
	& = &	\frac{1}{3}((1 + z_1)^m + (1 + z_2)^m + (1 + z_3)^m) \\
	& = &	\frac{1}{3}\left(
		2^m +
		\left( \frac{1}{2} + \frac{\sqrt{3}}{2} i \right)^m +
		\left( \frac{1}{2} - \frac{\sqrt{3}}{2} i \right)^m
		\right)
\end{eqnarray*}
}

\problempart Use DeMoivre's formula, restated below, to eliminate
complex numbers from your solution.

\begin{eqnarray*}
(\cos \theta + i \sin \theta)^n & = & \cos(n \theta) + i \sin(n \theta)
\end{eqnarray*}

\solution{
\begin{eqnarray*}
\lefteqn{\frac{1}{3}\left(2^m +
		\left( \frac{1}{2} + \frac{\sqrt{3}}{2} i \right)^m +
		\left( \frac{1}{2} - \frac{\sqrt{3}}{2} i \right)^m
		\right)}
\hspace{1in} \\
	& = &	\frac{1}{3}\left(2^m +
		\left( \cos \frac{\pi}{3} + i \sin \frac{\pi}{3} \right)^m +
		\left( \cos \frac{\pi}{3} - i \sin \frac{\pi}{3} \right)^m
		\right) \\
	& = &	\frac{1}{3}\left(2^m +
		\cos \frac{m \pi}{3} + i \sin \frac{m \pi}{3} +
	   	\cos \frac{m \pi}{3} - i \sin \frac{m \pi}{3} \right) \\
	& = &	\frac{1}{3}\left(2^m + 2 \cos \frac{m \pi}{3} \right)
\end{eqnarray*}

For example, the number of 4-bit strings with a multiple of three ones
is equal to

\begin{eqnarray*}
\frac{1}{3}\left(2^4 + 2 \cos \frac{4 \pi}{3} \right)
	& = &	\frac{1}{3}\left(16 + 2 \cdot \left(-\frac{1}{2}\right)
		\right) \\
	& = &	5
\end{eqnarray*}
 }

\end{problemparts}

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

\problem {\bf (20 points)} A string of parentheses is called
``balanced'' if the number of ('s is equal to the number of )'s and
the number of )'s never exeeds the number of ('s as the string is read
from left to right.  For example, (()())((())) is a balanced string,
but ())( is not.  With three pairs of parentheses, five different
balanced strings can be formed.  These five strings are listed below.

\[
((())) \quad (()()) \quad (())() \quad ()(()) \quad ()()()
\]

In general, the number of balanced strings increases rapidly with the
number of pairs of parentheses.  Your diligent TA stayed up until
dawn, slaving away with a dull pencil stub, working out the following
table:\footnote{This is a lie; he cranked it out with a C program in
about six minutes.}

\bigskip

\centerline{
\begin{tabular}{ccc}
Pairs of Parentheses & \quad & Number of Balanced Strings \\
0 & & 1 \\
1 & & 1 \\
2 & & 2 \\
3 & & 5 \\
4 & & 14 \\
5 & & 42 \\
6 & & 132 \\
7 & & 429 \\
8 & & 1430 \\
9 & & 4862 \\
10 & & 16796 \\
11 & & 58786 \\
12 & & 208012
\end{tabular}
}

\bigskip

In an apparently unrelated calculation, your exhausted TA then used
his final drops of energy and the last nubbin of his pencil to
evaluate $500000 - 1000 \sqrt{249999}$ out to 72 decimal
places:\footnote{This is also a lie; he plugged the thing into Maple.}

\[
1.000001000002000005000014000042000132000429001430004862016796058786208012\ldots
\]

Compare the table to the irrational number.  The goal of this problem
is to explain the apparently miraculous correspondence.

\begin{problemparts}

\problempart Let $p_n$ be the number of balanced strings containing
$n$ pairs of parentheses.  Express $p_n$ with a recurrence equation
and sufficient base cases.

\solution{ Note that every balanced string with $n \geq 1$ pairs of
parentheses consists of a balanced string with $k$ pairs, all enclosed
in parentheses, followed by a balanced string with $n-k-1$ pairs:

\[
\text{string with $n$ pairs} = ( \ \text{string with $k$ pairs} \ ) \ 
	\text{string with $n-k-1$ pairs}
\]

This observation suggests the following recurrence equation:

\begin{eqnarray*}
p_0	& = &	1 \\
p_n	& = &	\sum_{k=0}^{n-1} p_k \cdot p_{n-k-1} \quad (n \geq 1)
\end{eqnarray*}
}

\problempart Let $P(x)$ be the generating function for the number of
balanced strings; that is,

\begin{eqnarray*}
P(x) & = & p_0 + p_1 x + p_2 x^2 + p_3 x^3 + \ldots.
\end{eqnarray*}

Using the recurrence relation as a guide, find a (non-trivial)
equation relating and $P(x)$ and the square of $P(x)$.

\solution{
The summation in the recurrence equation suggests

\begin{eqnarray*}
P(x) & = & x P(x)^2 + 1.
\end{eqnarray*}

We can verify this equation using the recurrence relation.

\begin{eqnarray*}
x P(x)^2 + 1
	& = &	x (p_0 + p_1 x + p_2 x^2 + p_3 x^3 + \ldots)^2 + 1 \\
	& = &	x (p_0^2 + (p_0 p_1 + p_1 p_ 0) x + (p_0 p_2 + p_1 p_1 + p_2 p_0) x^2 + \ldots) + 1 \\
	& = &	1 + p_0^2 x + (p_0 p_1 + p_1 p_ 0) x^2 + (p_0 p_2 + p_1 p_1 + p_2 p_0) x^3 + \ldots \\
	& = &	1 + p_1 x + p_2 x^2 + p_3 x^3 + \ldots \\
	& = &	P(x)
\end{eqnarray*}
}

\problempart Apply the quadratic formula to obtain a closed-form
expression for the generating function $P(x)$.

\solution{
Given that $P(x) = x P(x)^2 + 1$, the quadratic formula implies that

\begin{eqnarray*}
P(x)	& = & \frac{1 \pm \sqrt{1 - 4 x}}{2x}.
\end{eqnarray*}

If $x$ is small, then $P(x)$ should be about $p_0 = 1$.  Therefore,
the correct choice of sign is

\begin{eqnarray*}
P(x)	& = & \frac{1 - \sqrt{1 - 4 x}}{2x}.
\end{eqnarray*}
}

\problempart Show that $P(1/1000000) = 500000 - 1000 \sqrt{249999}$.

\solution{
\begin{eqnarray*}
P(1/1000000)
	& = &	\frac{1 - \sqrt{1 - \frac{4}{1000000}}}
		{\left(\frac{2}{1000000}\right)} \\
	& = &	500000 - 500000 \sqrt{\frac{249999}{250000}} \\
	& = &	500000 - 1000 \sqrt{249999}
\end{eqnarray*}
}

\problempart Explain why the digits of this irrational number encode
the number of balanced strings of parentheses.

\solution{Suppose that we symbolically carry out the substitution done
in the preceding problem part.

\begin{eqnarray*}
P(x)		& = &	p_0 + p_1 x + p_2 x^2 + p_3 x^3 + \ldots \\
P(10^{-6})	& = &	p_0 + p_1 10^{-6} + p_2 10^{-12}
				+ p_3 10^{-18} + \ldots
\end{eqnarray*}

Thus, $p_0$ appears in the units position, $p_1$ appears in the
millionths position, $p_2$ appears in the trillionths position, and so
forth.
}
\end{problemparts}

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

\end{problems} \end{document}
