c7.tex.bak

Concrete_Mathematics_2nd_Ed_TeX_Source_Code

	\endpicture\kern1pt}
\def\nullp{\copy\bnullp}
\def\nulln{\copy\bnulln}
\def\nulld{\copy\bnulld}
\def\nullq{\copy\bnullq}
\def\nullh{\copy\bnullh}
\def\penny{\copy\bpenny}
\def\nickel{\copy\bnickel}
\def\dime{\copy\bdime}
\def\quarter{\copy\bquarter}
\def\halfdollar{\copy\bhalfdollar}

\smallskip
How many ways are there to pay 50~cents?
We assume that the payment must be made with
pennies \penny, nickels \nickel, dimes \dime, quarters
\quarter, and half-dollars \halfdollar.
\g Ah yes, I remember when we had half-dollars.\g
George "P\'olya" [|polya-pictures|] popularized this
problem by showing that it can be solved with generating functions in
an instructive way.

Let's set up infinite sums that represent all possible ways to give change,
just as we tackled the domino problems by working with infinite sums
that represent all possible domino patterns. It's simplest to start
by working with fewer varieties of coins, so let's suppose first that
we have nothing but pennies. The sum of all ways to leave some number
of pennies (but just pennies) in change can be written
\begindisplay
P&=\nullp+\penny+\penny\penny+\penny\penny\penny+\penny\penny\penny\penny
   +\cdots\cr
 &=\nullp+\penny+\penny^2+\penny^3+\penny^4+\cdots\,.\cr
\enddisplay
The first term stands for the way to leave no pennies,
the second term stands for one penny,
then two pennies, three pennies, and so on.
Now if we're allowed to use both pennies and nickels, the sum of all possible
ways is
\begindisplay
N&=P+\nickel\,P+\nickel\nickel\,P+\nickel\nickel\nickel\,P
 +\nickel\nickel\nickel\nickel\,P+\cdots\cr
 &=(\nulln+\nickel+\nickel^2+\nickel^3+\nickel^4+\cdots\,)\,P\,,\cr
\enddisplay
since each payment has a certain number of nickels chosen from the first
factor and a certain number of pennies chosen from~$P$. (Notice that
$N$ is {\it not\/} the sum $\nullp+\penny+\nickel+(\penny+\nickel)^2+
(\penny+\nickel)^3+\cdots\,$, because such a sum includes many types of
payment more than once. For example, the term $(\penny+\nickel)^2=
\penny\penny+\penny\nickel+\nickel\penny+\nickel\nickel$ treats \penny\nickel\
and \nickel\penny\ as if they were different, but we want to list each
set of coins only once without respect to order.)

Similarly, if dimes are permitted as well, we get the infinite sum
\begindisplay
D&=(\nulld+\dime+\dime^2+\dime^3+\dime^4+\cdots\,)\,N\,,\cr
\enddisplay
which includes terms like $\dime^3\nickel^3\penny^5=
\dime\dime\dime\nickel\nickel\nickel\penny\penny\penny\penny\penny$
when it is expanded in full. Each of these terms is a different way to make change.
Adding quarters and then half-dollars to the realm of possibilities
\g Coins of the realm.\g
gives
\begindisplay
Q&=(\nullq+\quarter+\quarter^2+\quarter^3+\quarter^4+\cdots\,)\,D\,;\cr
C&=(\nullh+\halfdollar+\halfdollar^2+\halfdollar^3+\halfdollar^4+\cdots\,)\,Q\,.
\enddisplay
Our problem is to find the number of
terms in $C$ worth exactly 50\rlap/c.

A simple trick solves this problem nicely: We can replace \penny\ by~$z$,
\nickel\ by~$z^5$, \dime\ by~$z^{10}$, \quarter\ by~$z^{25}$, and
\halfdollar\ by~$z^{50}$. Then each term is replaced by~$z^n$, where $n$~is
the monetary value of the original term. For example, the term
\halfdollar\dime\nickel\nickel\penny\ becomes $z^{50+10+5+5+1}=z^{71}$.
The four ways of paying 13~cents, namely $\dime\penny^3$, $\nickel\penny^8$,
$\nickel^2\penny^3$, and $\penny^{13}$, each reduce to~$z^{13}$; hence the
coefficient of~$z^{13}$ will be~$4$ after the $z$-substitutions are made.

Let $P_n$, $N_n$, $D_n$, $Q_n$, and $C_n$ be
the numbers of ways to pay $n$ cents when we're allowed to use coins that
are worth at most $1$, $5$, $10$, $25$, and~$50$ cents, respectively.
Our analysis tells us that these
are the coefficients of~$z^n$ in the respective power series
\begindisplay
P&=1+z+z^2+z^3+z^4+\cdots\,,\cr
N&=(1+z^5+z^{10}+z^{15}+z^{20}+\cdots\,)@P\,,\cr
D&=(1+z^{10}+z^{20}+z^{30}+z^{40}+\cdots\,)@N\,,\cr
Q&=(1+z^{25}+z^{50}+z^{75}+z^{100}+\cdots\,)@D\,,\cr
C&=(1+z^{50}+z^{100}+z^{150}+z^{200}+\cdots\,)@Q\,.\cr
\enddisplay
Obviously $P_n=1$ for all $n\ge0$.
\g How many pennies are there, really?\par
If\/ $n$ is greater than, say, $10^{10}$,
I~bet that\/ $P_n=0$ in the ``real world.\qback''\g
And a little thought proves that we have $N_n=\lfloor n/5\rfloor+1$:
To make $n$~cents out of pennies and nickels, we must choose either
$0$~or $1$ or \dots\ or~$\lfloor n/5\rfloor$ nickels, after which
there's only one way to supply the requisite number of pennies.
Thus $P_n$ and $N_n$ are simple; but the values of $D_n$, $Q_n$, and
$C_n$ are increasingly more complicated.

One way to deal with these formulas is to realize that
$1+z^m+z^{2m}+\cdots$ is just $1/(1-z^m)$. Thus we can write
\begindisplay
P&=1/(1-z)\,,\cr
N&=P/(1-z^5)\,,\cr
D&=N/(1-z^{10})\,,\cr
Q&=D/(1-z^{25})\,,\cr
C&=Q/(1-z^{50})\,.\cr
\enddisplay
Multiplying by the denominators, we have
\begindisplay
(1-z)\,P&=1\,,\cr
(1-z^5)\,N&=P\,,\cr
(1-z^{10})\,D&=N\,,\cr
(1-z^{25})\,Q&=D\,,\cr
(1-z^{50})\,C&=Q\,.\cr
\enddisplay
Now we can equate coefficients of $z^n$ in these equations, getting
recurrence relations from which the desired coefficients
can quickly be computed:
\begindisplay
P_n&=P_{n-1}+\[n=0]\,,\cr
N_n&=N_{n-5}+P_n\,,\cr
D_n&=D_{n-10}+N_n\,,\cr
Q_n&=Q_{n-25}+D_n\,,\cr
C_n&=C_{n-50}+Q_n\,.\cr
\enddisplay
For example, the coefficient of $z^n$ in $D=(1-z^{25})Q$ is equal to
$Q_n-Q_{n-25}$;
so we must have $Q_n-Q_{n-25}=D_n$, as claimed.

We could unfold these recurrences and find, for example, that
$Q_n=D_n+D_{n-25}+D_{n-50}+D_{n-75}+\cdots\,$, stopping when the subscripts
get negative. But the non-iterated form is convenient because each
coefficient is computed with just one addition, as in Pascal's triangle.

Let's use the recurrences to find $C_{50}$. First, $C_{50}=C_0+Q_{50}$;
so we want to know $Q_{50}$. Then $Q_{50}=Q_{25}+D_{50}$, and
$Q_{25}=Q_0+D_{25}$; so we also want to know $D_{50}$ and~$D_{25}$.
These $D_n$ depend in turn on $D_{40}$, $D_{30}$, $D_{20}$, $D_{15}$,
$D_{10}$,~$D_5$, and on $N_{50}$,~$N_{45}$, \dots,~$N_5$. A simple calculation
therefore suffices to determine all the necessary coefficients:
\begindisplay \let\preamble=\tablepreamble \offinterlineskip
n&&0&5&10&15&20&25&30&35&40&45&50\cr
\omit&height2pt\cr
\noalign{\hrule}
\omit&height2pt\cr
P_n&&1&1&1&1&1&1&1&1&1&1&1\cr
N_n&&1&2&3&4&5&6&7&8&9&10&11\cr
D_n&&1&2&4&6&9&12&16&&25&&36\cr
Q_n&&1&&&&&13&&&&&49\cr
C_n&&1&&&&&&&&&&50\cr
\enddisplay
The final value in the table gives us our answer, $C_{50}$: There are
exactly 50~ways to leave a 50-cent tip.
\g(Not counting the option of charging the tip to a credit card.)\g

How about a closed form for $C_n$? Multiplying the equations together
gives us the compact expression
\begindisplay
C={1\over1-z}\,{1\over1-z^5}\,{1\over1-z^{10}}\,{1\over1-z^{25}}\,
 {1\over1-z^{50}}\,,
\eqno\eqref|change-gf|
\enddisplay
but it's not obvious how to get from here to the coefficient of $z^n$.
Fortunately there is a way; we'll return to this problem later in the
chapter.

More elegant formulas arise if we consider the problem of giving change
when we live in a land that mints
 coins of every positive integer denomination
(\penny,
\kern1pt\beginpicture(25,18)(-12.5,0)
	\put(0,9){\circle{25}}
	\put(0,9){\makebox(0,0){\tiny 2}}
	\endpicture\kern1pt,
\kern1pt\beginpicture(28,18)(-14,0)
	\put(0,9){\circle{28}}
	\put(0,9){\makebox(0,0){\tiny 3}}
	\endpicture\kern1pt, \dots~)
instead of just the five we allowed before.
The corresponding generating function is
an infinite product of fractions,
\begindisplay
{1\over (1 - z) (1 - z^2) (1 - z^3) \ldots}\,,
\enddisplay
and the coefficient of $z^n$ when these factors are fully
multiplied out is called $p(n)$, the number of {\it"partitions"\/} of~$n$.
A partition of~$n$ is a representation of~$n$ as a sum of positive integers,
disregarding order. For example, there are seven different partitions of~$5$,
namely
\begindisplay \tightplus \let\displaythick=\normalthick
5=4+1=3+2=3+1+1=2+2+1=2+1+1+1=1+1+1+1+1\,;
\enddisplay
hence $p(5)=7$. (Also
$p(2)=2$, $p(3)=3$, $p(4)=5$, and $p(6)=11$; it begins to look as if
$p(n)$ is always a prime number. But $p(7)=15$, spoiling the pattern.)
 There is no closed form
for $p(n)$, but the theory of partitions is a fascinating branch of
mathematics in which many remarkable discoveries have been made.
For example, "Ramanujan" proved that $p(5n+4)\=0$ \tmod5,
$p(7n+5)\=0$ \tmod7, and $p(11n+6)\=0$ \tmod{11},
by making ingenious transformations of generating functions
(see "Andrews"~[|andrews-partitions|, Chapter~10]).

\beginsection 7.2 Basic Maneuvers

Now let's look more closely
at some of the techniques that make
power series powerful.

First a few words about terminology and notation.
Our generic generating function has the form
\begindisplay
G(z)
	= g_0 + g_1 z + g_2 z^2 + \cdots
	= \sum_{n \geq 0} g_n z^n \,,
\eqno\eqref|gf-ord|
\enddisplay
and we say that $G(z)$, or $G$ for short,
is the generating function for the sequence
$\<g_0,g_1,g_2,\ldots\,\>$,
which we also call~$\<g_n\>$.
The coefficient $g_n$ of $z^n$ in~$G(z)$ is often
denoted $[z^n]\,G(z)$, as in Section~5.4.

The sum in \thiseq\ runs over all $n\geq0$, but we often
find it more convenient
to extend the sum over all integers~$n$.
We can do this by simply regarding
$g_{-1} = g_{-2} = \cdots = 0$.
In such cases we might still talk about
the sequence $\<g_0,g_1,g_2,\ldots\,\>$,
as if the $g_n$'s didn't exist for negative~$n$.

Two kinds of ``"closed forms"'' come up when we work with generating functions.
We might have a "closed form" for $G(z)$, expressed in terms of~$z$;
or we might have a closed form for $g_n$, expressed in terms of~$n$.
For example, the generating function for "Fibonacci numbers" has the
closed form $z/(1-z-z^2)$; the Fibonacci numbers themselves have the
closed form $(\phi^n-\phihat^n)/\!\sqrt5$. The context will explain what
kind of closed form is meant.

Now a few words about perspective.
"!philosophy"
The generating function~$G(z)$ appears to be two different entities,
depending on how we view it.
Sometimes it is a function of a complex variable~$z$,
satisfying all the standard properties proved in calculus books.
And sometimes it is simply a "formal power series",
\g If physicists can get away with viewing light
sometimes as a wave and sometimes as a particle,
mathematicians should be able to view generating functions in
two different ways.\g
with $z$~acting as a placeholder. In the previous section, for example,
we used the second interpretation;
we saw several examples in which $z$ was substituted for some
feature of a combinatorial object in a ``sum''
of such objects. The coefficient of~$z^n$ was then the
number of combinatorial objects having $n$ occurrences of that feature.

When we view $G(z)$ as a function of a complex variable,
its "convergence" becomes an issue.
We said in Chapter~2 that the infinite series $\sum_{n\ge0}g_nz^n$
converges (absolutely) if and only if there's a bounding constant $A$
such that the finite sums $\sum_{0\le n\le N}\vert g_nz^n\vert$ never
exceed~$A$, for any~$N$. Therefore it's easy to see that if $\sum_{n\ge0}
g_nz^n$ converges for some value $z=z_0$, it also converges for all $z$
with $\vert z\vert<\vert z_0\vert$. Furthermore, we must have
$\lim_{n\to\infty}\vert g_nz_0^n\vert=0@$; hence, in the
notation of Chapter~9, $g_n=O\bigl(\vert1/z_0\vert^n
\bigr)$ if there is convergence at~$z_0$. And conversely if $g_n=O(M^n)$,
the series $\sum_{n\ge0}g_nz^n$ converges for all $\vert z\vert<1/M$.
These are the basic facts about convergence of power series.

But for our purposes convergence is usually a red herring, unless we're
trying to study the asymptotic behavior of the coefficients.
Nearly every operation we perform on generating functions can be
justified rigorously as an operation on formal power series, and such
operations are legal even when the series don't converge.
(The relevant theory can be found, for example, in "Bell"~[|bell-gf|],
"Niven"~[|niven-gf|], and "Henrici"~[|henrici|, Chapter~1].)

Furthermore, even if we throw all caution to the winds
\g Even if we remove the tags from our mattresses.\g
 and derive formulas
without any rigorous justification, we generally can take the
results of our derivation and prove them by induction. For example,
the generating function for the Fibonacci numbers converges only when
$\vert z\vert<1/\phi\approx0.618$, but we didn't need to know that
when we proved the formula $F_n=(\phi^n-\phihat^n)/\!\sqrt5$. The latter
formula, once discovered, can be verified directly, if we don't
trust the theory of formal power series. Therefore we'll
ignore questions of convergence in this chapter; it's more a hindrance than
a help.

So much for perspective.
Next we look at our main tools
for reshaping generating functions\dash---%
adding, shifting, changing variables,
differentiating, integrating, and multiplying.
In what follows we assume that, unless stated otherwise,
$F(z)$ and $G(z)$ are the generating functions for
the sequences $\<f_n\>$ and $\<g_n\>$.
We also assume that the $f_n$'s and $g_n$'s
are zero for negative~$n$,
since this saves us some bickering with the limits of summation.

It's pretty obvious what happens when we add
constant multiples of $F$~and~$G$ together:
\begindisplay \advance\belowdisplayskip-3pt
\alpha F(z) + \beta G(z)
&= \alpha \sum_n f_n z^n \;+\; \beta \sum_n g_n z^n\cr
&= \sum_n \,(\alpha f_n + \beta g_n)\, z^n \,.
\eqno
\enddisplay
This gives us the generating function for the sequence
$\<\alpha f_n + \beta g_n\>$.