c7.tex.bak

Concrete_Mathematics_2nd_Ed_TeX_Source_Code

% Chapter 7 of Concrete Mathematics
% (c) Addison-Wesley, all rights reserved.
\input gkpmac
\refin bib
\pageno=321
\refin chap2
\refin chap4
\refin chap5
\refin chap6

\beginchapter 7 Generating Functions
\pageno=321

THE MOST POWERFUL WAY to deal with sequences of numbers, as far as anybody
knows, is to manipulate infinite series that ``generate'' those sequences.
We've learned a lot of sequences and we've seen a few generating functions;
now we're ready to explore generating functions in depth, and to see how
remarkably useful they are.

\beginsection 7.1 Domino Theory and Change

"!Dimers and Dimes, \string\see Dominoes and Change"
"!Dominoes"
Generating functions are important enough, and for many of us new enough,
to justify a relaxed approach as we begin to look at them more closely.
So let's start this chapter with some fun and games as we try to develop our
intuitions about generating functions. We will study two applications
of the ideas, one involving dominoes and the other involving coins.

\unitlength=3pt
\def\domi{\beginpicture(0,2)(0,0) % identity
	\put(0,0){\line(0,1){2}}
	\endpicture}
\def\domI{\beginpicture(0,2)(0,0) % identity when isolated
	\put(0,-.1){\line(0,1){2.2}}
	\endpicture}
\def\domv{\beginpicture(1,2)(0,0) % vertical without left edge
	\put(1,0){\line(0,1){2}}
	\put(0,0){\line(1,0){1}}
	\put(0,2){\line(1,0){1}}
	\endpicture}
\def\domhh{\beginpicture(2,2)(0,0) % two horizontals without left edge
	\put(2,0){\line(0,1){2}}
	\put(0,0){\line(1,0){2}}
	\put(0,1){\line(1,0){2}}
	\put(0,2){\line(1,0){2}}
	\endpicture}
\def\Domh{\beginpicture(3,1)(-.5,0) % horizontal, stand-alone
	\put(2,0){\line(0,1){1}}
	\put(0,0){\line(0,1){1}}
	\put(0,0){\line(1,0){2}}
	\put(0,1){\line(1,0){2}}
	\endpicture}
\def\Domv{\beginpicture(2,2)(-.5,0) % vertical, stand-alone
	\put(0,0){\line(0,1){2}}
	\put(1,0){\line(0,1){2}}
	\put(0,0){\line(1,0){1}}
	\put(0,2){\line(1,0){1}}
	\endpicture}

How many ways $T_n$ are there to completely cover a $2\times n$
rectangle with $2\times1$ dominoes? We assume that the dominoes are
identical (either because they're face down, or
because someone has rendered them indistinguishable,
say by painting them all red);
thus only their orientations\dash---vertical or horizontal\dash---matter,
and we can imagine that we're working with domino-shaped tiles.
For example, there are three tilings of a $2 \times 3$ rectangle, namely
\domi\domv\domv\domv\kern1pt, \domi\domv\domhh\kern1pt, and~\domi\domhh\domv
\kern1pt; so $T_3 = 3$.

To find a closed form for general~$T_n$
\g\noindent\llap{``}Let me count the ways.''\par\hfill\dash---E.\thinspace B. "Browning"\g
we do our usual first thing,
look at small cases.
When $n=1$ there's obviously just one tiling,~\domi\domv\kern1pt;
and when $n=2$ there are two,
\domi\domv\domv~and~\domi\domhh\kern1pt.

How about when $n=0$;
how many tilings of a $2 \times 0$ rectangle are there?
It's not immediately clear what this question means, but we've seen
similar situations before: There is one permutation of zero objects
"!empty case" "!null case" "!basis of induction" "!thinking small" "!small cases"
(namely the empty permutation), so $0!=1$. There is one way to choose
zero things from $n$~things (namely to choose nothing), so ${n\choose0}
=1$. There is one way to partition the empty set into zero nonempty subsets,
but there are no such ways to partition a nonempty set; so ${n\brace0}=
\[n=0]$. By such reasoning we can conclude that there's just one way
to tile a $2\times0$ rectangle with dominoes, namely to use no dominoes;
therefore $T_0=1$. (This spoils the simple pattern $T_n=n$ that holds
when $n=1$, $2$, and~$3$; but that pattern was probably doomed anyway,
since $T_0$ wants to be~$1$ according to the logic of the situation.)
A proper understanding of the null case turns out to be useful whenever
we want to solve an enumeration problem.

Let's look at one more small case, $n=4$.
There are two possibilities for tiling the left edge of the rectangle\dash---%
we put either a vertical domino or two horizontal dominoes there.
If we choose a vertical one, the partial solution is
\domi\domv\beginpicture(3,2)(0,0)
 \put(0,0){\line(1,0){3}}
 \put(0,2){\line(1,0){3}}
 \put(3,0){\line(0,1){2}}\endpicture\
and the remaining $2\times3$ rectangle can be covered in $T_3$~ways.
If we choose two horizontals, the partial solution
\domi\domhh\beginpicture(2,2)(0,0)
 \put(0,0){\line(1,0){2}}
 \put(0,2){\line(1,0){2}}
 \put(2,0){\line(0,1){2}}\endpicture\
can be completed in $T_2$~ways.
Thus $T_4=T_3+T_2=5$. (The five tilings are
\domi\domv\domv\domv\domv\kern1pt,
\domi\domv\domv\domhh\kern1pt,
\domi\domv\domhh\domv\kern1pt,
\domi\domhh\domv\domv\kern1pt, and~%
\domi\domhh\domhh\kern1pt.)

We now know the first five values of~$T_n$:
\begindisplay \let\preamble=\tablepreamble
n&&0&1&2&3&4\cr
\noalign{\hrule}
T_n&&1&1&2&3&5\cr
\enddisplay
These look suspiciously like the "Fibonacci numbers",
and it's not hard to see why:
The reasoning we used to establish
$T_4 = T_3 + T_2$ easily generalizes to
$T_n = T_{n-1} + T_{n-2}$, for $n \geq 2$.
Thus we have the same recurrence here
as for the Fibonacci numbers,
except that the initial values $T_0 = 1$ and $T_1 = 1$
are a little different.
But these initial values are the consecutive Fibonacci numbers $F_1$~and~$F_2$,
so the $T$'s are just Fibonacci numbers
shifted up one place:
\begindisplay
 T_n
   = F_{n+1} \,, \qquad\hbox{for $n \geq 0$}.
\enddisplay
(We consider this to be a closed form for $T_n$,
because the Fibonacci numbers are important
enough to be considered ``known.\qback'' Also, $F_n$ itself has a
closed form \equ(6.|fib-sol|) in terms of algebraic operations.)
Notice that this equation confirms the wisdom of setting $T_0=1$.

But what does all this have to do with generating functions? Well, we're about
to get to that\dash---there's another way to figure out what $T_n$ is. This new
way is based on a bold idea.
\g To boldly go\par where no tiling has gone before.\g
 Let's consider the ``sum'' of all possible
$2\times n$ tilings, for all $n\ge0$, and call it~$T$:
\begindisplay
T	= \domI+
 \domi\domv+\domi\domv\domv + \domi\domhh
 + \domi\domv\domv\domv + \domi\domv\domhh + \domi\domhh\domv
 + \cdots\,.
\eqno\eqref|t-sum|
\enddisplay
(The first term `$\,\domI\,$' on the right
stands for the null tiling of a $2\times0$ rectangle.)
This sum~$T$ represents lots of information.
It's useful because it lets us prove things about $T$ as a whole
rather than forcing us to prove them (by induction)
about its individual terms.

The terms of this sum
stand for tilings, which are combinatorial objects. We won't be fussy
about what's considered legal when infinitely many tilings are added
together; everything can be made rigorous, but our goal right now is to
expand our consciousness beyond conventional algebraic formulas.

We've added the patterns together, and we can also multiply them\dash---%
by juxtaposition.
For example, we can multiply the tilings
\kern1pt\domi\domv\kern1pt\ and \kern1pt\domi\domhh\kern1pt\
to get the new tiling~\domi\domv\domhh\kern1pt.
But notice that multiplication is not "commutative";
that is, the order of multiplication counts:
\kern1pt\domi\domv\domhh\kern1pt\ is different from
\kern1pt\domi\domhh\domv\kern1pt.

Using this notion of multiplication
it's not hard to see that
the null tiling plays a special role\dash---%
it is the multiplicative identity.
For instance,
$\domI\times\domi\domhh=\domi\domhh\times\domI=\domi\domhh$\kern1pt.

Now we can use domino arithmetic to manipulate the infinite sum~$T$:
\begindisplay
T&=\domI+\domi\domv+\domi\domv\domv + \domi\domhh
 + \domi\domv\domv\domv + \domi\domv\domhh + \domi\domhh\domv
 + \cdots\cr
&=\domI+
 \domi\domv\,(\,\domI+\domi\domv+\domi\domv\domv + \domi\domhh+\cdots\,)+
 \domi\domhh\,(\,\domI+\domi\domv+\domi\domv\domv + \domi\domhh+\cdots\,)\cr
&=\domI+
 \domi\domv\,T+ \domi\domhh\,T\,.\eqno\cr
\enddisplay
Every valid tiling occurs
exactly once in each right side,
so what we've done is reasonable
even though we're ignoring the cautions in Chapter~2 about ``absolute
convergence.\qback''
\g I have a gut feeling that these sums
must converge, as long as the dominoes are small~enough.\g
The bottom line of this equation tells us that everything in~$T$
is either the null tiling,
or is a vertical tile followed by something else in~$T$,
or is two horizontal tiles followed by something else in~$T$.

So now let's try to solve the equation for $T$. Replacing the $T$ on the left
by $\domI\,T$ and subtracting
the last two terms on the right
from both sides of the equation, we get
\begindisplay
 (\,\domI-\domi\domv-\domi\domhh\,)T=\domI\,\,.
\eqno
\enddisplay
For a consistency check, here's an expanded version:
\begindisplay\def\preamble{&\strut$\hfil\,{}##{}\,\hfil$&$\hfil##\hfil$}
&\domI&+&\domi\domv&+&\domi\domv\domv&+&\domi\domhh&+&
 \domi\domv\domv\domv&+&\domi\domv\domhh&+&\domi\domhh\domv&+&
\cdots\cr
-&\domi\domv&-&\domi\domv\domv&-&\domi\domv\domv\domv&-&\domi\domv\domhh&-&
 \domi\domv\domv\domv\domv&-&\domi\domv\domv\domhh&-&\domi\domv\domhh\domv&-&
 \cdots\cr
-&\domi\domhh&-&\domi\domhh\domv&-&\domi\domhh\domv\domv&-&\domi\domhh\domhh&-&
 \domi\domhh\domv\domv\domv&-&\domi\domhh\domv\domhh&-&\domi\domhh\domhh\domv&-&
 \cdots\cr
\noalign{\kern2pt\hrule\kern2pt}
&\domI\cr
\enddisplay
Every term in the top row, except the first,
is cancelled by a term in either the second or third row,
so our equation is correct.

So far it's been fairly easy to make combinatorial sense
of the equations we've been working with.
Now, however, to get a compact expression for~$T$
we cross a combinatorial divide.
With a leap of algebraic faith
we divide both sides of equation \thiseq\ by
$\,\domI-\domi\domv-\domi\domhh\,$
to get
\begindisplay
 T
	= {\hbox{\domI}\over\domI-\domi\domv-\domi\domhh}\,.
\eqno\eqref|t-fraction|
\enddisplay
(Multiplication isn't commutative, so
we're on the verge of "cheating",
by not distinguishing between left and right division. In
our application it doesn't matter, because $\,\domI\,$ commutes with
everything. But let's not be picky, unless our wild ideas lead to
paradoxes.)

The next step is to expand this fraction as a power series,
using the rule
\begindisplay
 {1\over 1-z}
	= 1 + z + z^2 + z^3 + \cdots \,.
\enddisplay
The null tiling $\,\domI\,$,
which is the multiplicative identity for our combinatorial arithmetic,
plays the part of~$1$, the usual multiplicative identity;
and $\domi\domv+\domi\domhh$ plays~$z$.
So we get the expansion
\begindisplay
{\hbox{\domI}\over\domI-\domi\domv-\domi\domhh}
&=\domI+(\,\domi\domv+\domi\domhh\,)+
 (\,\domi\domv+\domi\domhh\,)^2+
 (\,\domi\domv+\domi\domhh\,)^3+\cdots\cr
&=\domI+(\,\domi\domv+\domi\domhh\,)+
 (\,\domi\domv\domv+\domi\domv\domhh+\domi\domhh\domv+\domi\domhh\domhh\,)\cr
&\qquad+(\,\domi\domv\domv\domv+\domi\domv\domv\domhh
 +\domi\domv\domhh\domv+\domi\domv\domhh\domhh
 +\domi\domhh\domv\domv+\domi\domhh\domv\domhh
 +\domi\domhh\domhh\domv+\domi\domhh\domhh\domhh\,)+\cdots\,.\cr
\enddisplay
This is $T$, but the tilings are arranged in a different order than
we had before. Every tiling appears exactly once in this sum;
for example, $\domi\domv\domhh\domhh\domv\domv\domhh\domv$
appears in the expansion of $(\,\domi\domv+\domi\domhh\,)^7$.

We can get useful information from this infinite sum by compressing it
down, ignoring details that are not of interest. For example, we
can imagine that the patterns become unglued and that the individual dominoes
commute with each other; then a term like
$\domi\domv\domhh\domhh\domv\domv\domhh\domv$ becomes $\Domv^4\Domh^6$,
because it contains four verticals and six horizontals. Collecting
like terms gives us the series
\begindisplay
 T = \domI+\Domv+\Domv^2+\Domh^2+\Domv^3+2\Domv\Domh^2+\Domv^4+3\Domv^2\Domh^2
 +\Domh^4+\cdots\,.
\enddisplay
The $2\Domv\Domh^2$ here represents
the two terms of the old expansion,
\domi\domv\domhh\ and~\domi\domhh\domv\kern1pt, that
have one vertical and two horizontal dominoes;
similarly $3\Domv^2\Domh^2$
represents the three terms
\domi\domv\domv\domhh\kern1pt, \domi\domv\domhh\domv\kern1pt, and 
\domi\domhh\domv\domv\kern1pt.
We're essentially treating \Domv\ and~\Domh\ as ordinary (commutative)
variables.

We can find a closed form for the coefficients in the commutative version
of~$T$ by using the binomial theorem:
\begindisplay
{\hbox{\domI}\over\domI-(\Domv+\Domh^2)}
&=\domI+(\Domv+\Domh^2) +(\Domv+\Domh^2)^2 +(\Domv+\Domh^2)^3+\cdots\cr
&=\sum_{k\ge0}(\Domv+\Domh^2)^k\cr
&=\sum_{j,k\ge0}{k\choose j}\Domv^j\Domh^{2k-2j}\cr
&=\sum_{j,m\ge0}{j+m\choose j}\Domv^j\Domh^{2m}\,.\eqno\cr
\enddisplay
(The last step replaces $k-j$ by $m$; this is legal because we have
\smash{\hbox{${k\choose j}=0$}}
when $0\le k<j$.) We conclude that $j+m\choose j$ is the number of ways