chap7.tex

Concrete_Mathematics_2nd_Ed_TeX_Source_Code

to tile a $2\times(j+2m)$ rectangle with $j$ vertical dominoes and $2m$
horizontal dominoes. For example, we recently looked at the $2\times10$ tiling
$\domi\domv\domhh\domhh\domv\domv\domhh\domv$\kern1pt,
which involves
four verticals and six horizontals; there are ${4+3\choose4}=35$ such
tilings in all, so one of the terms in the commutative version of~$T$
is $35@\Domv^4\Domh^6$.

We can suppress even more detail by ignoring the orientation of the dominoes.
Suppose we don't care about the horizontal/vertical breakdown; we only want
to know about the total number of $2\times n$ tilings. (This, in fact,
is the number~$T_n$ we started out trying to discover.)
We can collect the necessary information by simply substituting a
single quantity, $z$, for \Domv\ and~\Domh.
\g Now I'm dis\-oriented.\g
And we might as well also replace \kern1pt\domI\kern1pt\ by~$1$, getting
\begindisplay
T={1\over 1-z-z^2}\,.
\eqno
\enddisplay
This is the generating function \equ(6.|fib-gf|) for Fibonacci numbers,
except for a missing factor of~$z$ in the numerator; so we conclude
that the coefficient of $z^n$ in~$T$ is $F_{n+1}$.

The compact representations $\,\domI\,/(\,\domI-\domi\domv-\domi\domhh\,)$,
$\,\domI\,/(\,\domI-\Domv-\Domh^2)$, and $1/(1-z-z^2)$ that we have deduced
for~$T$ are called {\it"generating functions"}, because they generate
the coefficients of interest.

Incidentally, our derivation implies that the number of $2\times n$
domino tilings with exactly $m$ pairs of horizontal dominoes is
${n-m\choose m}$. (This follows because there are $j=n-2m$ vertical
dominoes, hence there are
\begindisplay 
{j+m\choose j}={j+m\choose m}={n-m\choose m}
\enddisplay % done for page break later
ways to do the tiling according to our formula.) We observed in Chapter~6 that
$n-m\choose m$ is the
number of "Morse code" sequences of length~$n$ that contain $m$~dashes;
in fact, it's easy to see that $2\times n$ domino tilings correspond
directly to Morse code sequences. (The tiling
$\,\domi\domv\domhh\domhh\domv\domv\domhh\domv\,$ corresponds to
\def\mdot{\beginpicture(1.5,2)(-.75,-1)\put(0,0){\disk{.7}}\endpicture}%
\def\mdash{\beginpicture(2.5,2)(-.5,-1)
 \put(0,0){\thicklines\line(1,0){1.5}}\endpicture}%
`$\mdot\mdash\mdash\mdot\mdot\mdash\mdot$'.)
Thus domino tilings are closely related to the continuant polynomials
we studied in Chapter~6. It's a small world. "!cliches"

We have solved the $T_n$ problem in two ways. The first way, guessing the
answer and proving it by induction, was easier; the second way, using
infinite sums of domino patterns and distilling out the coefficients
of interest, was fancier. But did we use the second method only because
it was amusing to play with dominoes as if they were algebraic variables?
No; the real reason for introducing the second way
was that the infinite-sum approach is a lot more powerful.
The second method applies to many more problems, because it doesn't require us
to make magic guesses.

\def\tomv#1#2#3{\beginpicture(0,2.7)(0,.5) % vertical segments (top-down)
 \if1#1\put(0,2){\line(0,1){1}}\fi
 \if0#2\else\put(0,1){\line(0,1){#2}}\fi
 \if0#3\else\put(0,0){\line(0,1){#3}}\fi \endpicture}
\def\tomh#1#2#3#4{\beginpicture(1,2)(0,.5) % horizontal segments (top-down)
 \if0#1\else\put(0,3){\line(1,0){#1}}\fi
 \if0#2\else\put(0,2){\line(1,0){#2}}\fi
 \if0#3\else\put(0,1){\line(1,0){#3}}\fi
 \if0#4\else\put(0,0){\line(1,0){#4}}\fi \endpicture}

Let's generalize up a notch, to a problem where guesswork
will be beyond us. How many ways $U_n$ are there to tile a
$3\times n$ rectangle with dominoes?

 The first few cases of this problem
tell us a little: The null tiling gives $U_0=1$. There is no valid
tiling when $n=1$, since a $2\times1$ domino doesn't fill a $3\times1$
rectangle, and since there isn't room for two. The next case, $n=2$, can
easily be done by hand; there are three tilings,
\tomv003\tomh2022\tomv020\tomh0000\tomv003\kern1pt,
\tomv003\tomh2202\tomv002\tomh0000\tomv003\kern1pt,
and
\tomv003\tomh2222\tomh0000\tomv003\kern1pt,
so $U_2=3$.
(Come to think of it we already knew this,
because the previous problem told us that $T_3 = 3$;
the number of ways to tile a $3 \times 2$ rectangle
is the same as the number to tile a~$2 \times 3$.)
When~$n=3$, as when~$n=1$, there are no tilings.
We can convince ourselves of this either
by making a quick exhaustive search or
by looking at the problem from a higher level:
The area of a $3 \times 3$ rectangle is odd,
so we can't possibly tile it with dominoes whose area is even.
(The same argument obviously applies to any odd~$n$.)
Finally, when $n=4$ there seem to be about a dozen tilings;
it's difficult to be sure about the exact number without spending a lot of time
to guarantee that the list is complete.

\begingroup \advance\medmuskip 3mu
So let's try the infinite-sum approach that worked last time:
\begindisplay
U=\tomv003
+\tomv003\tomh2022\tomv020\tomh0000\tomv003
+\tomv003\tomh2202\tomv002\tomh0000\tomv003
+\tomv003\tomh2222\tomh0000\tomv003
+\tomv003\tomh2022\tomv020\tomh0000\tomv003\tomh2022\tomv020\tomh0000\tomv003
+\tomv003\tomh2022\tomv020\tomh0000\tomv003\tomh2202\tomv002\tomh0000\tomv003
+\tomv003\tomh2022\tomv020\tomh0000\tomv003\tomh2222\tomh0000\tomv003
+\tomv003\tomh4044\tomv020\tomh0200\tomv001\tomh0000\tomv020\tomh0000\tomv003
+\tomv003\tomh2202\tomv002\tomh0000\tomv003\tomh2022\tomv020\tomh0000\tomv003
+\cdots\,.
\eqno
\enddisplay
Every non-null tiling begins with either
\tomv003\tomh1022\tomv020\tomh0000\tomv001\
or \tomv003\tomh2201\tomv002\tomh0000\tomv100
or \tomv003\tomh2222\tomh0000\tomv003\kern1pt;
but unfortunately the first two of these three possibilities don't
simply factor out and leave us with $U$ again. The sum of all terms in~$U$ that
begin with \tomv003\tomh1022\tomv020\tomh0000\tomv001\
can, however, be written as $\tomv003\tomh1022\tomv020\tomh0000\tomv001\,V$, where
\begindisplay
V=\tomv020\tomh1010\tomv020
+\tomv020\tomh3030\tomv003\tomh0002\tomv020\tomh0000\tomv003
+\tomv020\tomh3010\tomv003\tomh0202\tomv002\tomh0000\tomv003
+\tomv020\tomh3030\tomv003\tomh0202\tomh0000\tomv003
+\tomv020\tomh3230\tomv001\tomh0002\tomv020\tomh0000\tomv003 +\cdots
\enddisplay
is the sum of all domino tilings of a mutilated $3\times n$ rectangle that
has its lower left corner missing. Similarly, the terms of~$U$ that
begin with \tomv003\tomh2201\tomv002\tomh0000\tomv100\ can be written
$\tomv003\tomh2201\tomv002\tomh0000\tomv100\,\Lambda$, where
\begindisplay
\Lambda=\tomv002\tomh0101\tomv002
+\tomv002\tomh0303\tomv003\tomh2000\tomv002\tomh0000\tomv003
+\tomv002\tomh0103\tomv003\tomh2020\tomv020\tomh0000\tomv003
+\tomv002\tomh0303\tomv003\tomh2020\tomh0000\tomv003
+\tomv002\tomh0323\tomv100\tomh2000\tomv002\tomh0000\tomv003 +\cdots
\enddisplay
consists of all rectangular tilings lacking their upper left corner. The
series $\Lambda$ is a mirror image of $V$. These factorizations allow us to write
\begindisplay
U=\tomv003\,
+\tomv003\tomh1022\tomv020\tomh0000\tomv001\,V
+\tomv003\tomh2201\tomv002\tomh0000\tomv100\,\Lambda
+\tomv003\tomh2222\tomh0000\tomv003\,U\,.
\enddisplay
And we can factor $V$ and $\Lambda$ as well, because such tilings
can begin in only two ways:
\begindisplay
V&=\tomv020\tomh1010\tomv020\,U+
 \tomv020\tomh2230\tomv001\tomh0002\tomv020\tomh0000\tomv001\,V\,,\cr
\Lambda&=\tomv002\tomh0101\tomv002\,U+
 \tomv002\tomh0322\tomv100\tomh2000\tomv002\tomh0000\tomv100\,\Lambda\,.\cr
\enddisplay
Now we have three equations in three unknowns ($U$, $V$, and $\Lambda$). We can
solve them by first solving for $V$ and~$\Lambda$ in terms of~$U$, then
plugging the results into the equation for $U$:
\begindisplay \openup4pt
V&=(\,\tomv003-
 \tomv020\tomh2230\tomv001\tomh0002\tomv020\tomh0000\tomv001\,)^{-1}
  \,\tomv020\tomh1010\tomv020\,U\,,\qquad
\Lambda=(\,\tomv003-
 \tomv002\tomh0322\tomv100\tomh2000\tomv002\tomh0000\tomv100\,)^{-1}
  \,\tomv002\tomh0101\tomv002\,U\,;\cr
U&=\tomv003\,+\,
 \tomv003\tomh1022\tomv020\tomh0000\tomv001\,
(\,\tomv003-
 \tomv020\tomh2230\tomv001\tomh0002\tomv020\tomh0000\tomv001\,)^{-1}
  \,\tomv020\tomh1010\tomv020\,U\,+\,
 \tomv003\tomh2201\tomv002\tomh0000\tomv100\,
(\,\tomv003-
 \tomv002\tomh0322\tomv100\tomh2000\tomv002\tomh0000\tomv100\,)^{-1}
  \,\tomv002\tomh0101\tomv002\,U\,+\,
\tomv003\tomh2222\tomh0000\tomv003\,U\,.
\enddisplay
And the final equation can be solved for $U$, giving the compact formula
\begindisplay
U={\hbox{\tomv003}\over\, \tomv003
\,-\,\tomv003\tomh1022\tomv020\tomh0000\tomv001\,
(\,\tomv003-
 \tomv020\tomh2230\tomv001\tomh0002\tomv020\tomh0000\tomv001\,)^{-1}
  \,\tomv020\tomh1010\tomv020\,
\,-\,\tomv003\tomh2201\tomv002\tomh0000\tomv100\,
(\,\tomv003-
 \tomv002\tomh0322\tomv100\tomh2000\tomv002\tomh0000\tomv100\,)^{-1}
  \,\tomv002\tomh0101\tomv002
\,-\,\tomv003\tomh2222\tomh0000\tomv003}\,.
\eqno
\enddisplay\endgroup % end of the special \medmuskip
This expression defines the infinite sum $U$,
\g I learned in another class about ``regular expressions.\qback'' If
I'm not mistaken, we can write\smallskip
\unitlength=2pt
$U=(
\tomv003\tomh1022\tomv020\tomh0000\tomv001\,\,
 \tomv020\tomh2230\tomv001\tomh0002\tomv020\tomh0000\tomv001^{\ast}
  \,\tomv020\tomh1010\tomv020$\par
\hfill${}+\tomv003\tomh2201\tomv002\tomh0000\tomv100\,\,
 \tomv002\tomh0322\tomv100\tomh2000\tomv002\tomh0000\tomv100\,^{\ast}
  \,\tomv002\tomh0101\tomv002
+\tomv003\tomh2222\tomh0000\tomv003\,)^{\ast}$\par\smallskip
in the language of regular expressions; so there must be some
connection between regular expressions and generating functions.\g
just as \eq(|t-fraction|) defines $T$.

The next step is to go commutative. Everything simplifies beautifully
when we detach all the dominoes and use only powers of $\Domv$ and~$\Domh$:
\begindisplay \openup5pt
U&={1\over
1-\Domv^2\Domh(1-\Domh^3)^{-1}
     -\Domv^2\Domh(1-\Domh^3)^{-1}-\Domh^3}\cr
&={1-\Domh^3\over
 (\,1-\Domh^3)^2-2\Domv^2\Domh}\cr
&={(1-\Domh^3)^{-1}\over
 1-2\Domv^2\Domh(1-\Domh^3)^{-2}}\cr
&={1\over1-\Domh^3}
 +{2\Domv^2\Domh\over(1-\Domh^3)^3}
 +{4\Domv^4\Domh^2\over(1-\Domh^3)^5}
 +{8\Domv^6\Domh^3\over(1-\Domh^3)^7}+\cdots\cr
&=\sum_{k\ge0}{2^k\Domv^{2k}\Domh^k\over(1-\Domh^3)^{2k+1}}\cr
&=\sum_{k,m\ge0}{m+2k\choose m}2^k\Domv^{2k}\Domh^{k+3m}\,.\cr
\enddisplay
(This derivation deserves careful scrutiny.
The last step uses the formula $(1-w)^{-2k-1}=\sum_m{m+2k\choose m}w^m$,
identity \equ(5.|neg-binomial1|).)
Let's take a good look at the bottom line to see what it tells us. First, it says
that every $3\times n$ tiling uses an even number of vertical dominoes. Moreover,
if there are $2k$ verticals, there must be at least $k$ horizontals, and the
total number of horizontals must be $k+3m$ for some $m\ge0$. Finally, the
number of possible tilings with $2k$ verticals and $k+3m$ horizontals is
exactly ${m+2k\choose m}2^k$.

We now are able to analyze the $3\times4$ tilings that left us doubtful
when we began looking at the $3\times n$ problem. When $n=4$ the total
area is~$12$, so we need six dominoes altogether. There are $2k$ verticals
and $k+3m$ horizontals,
 for some $k$ and~$m$; hence $2k+k+3m=6$. In other
words, $k+m=2$. If we use no verticals, then $k=0$ and $m=2$;
the number of possibilities is
${2+0\choose2}2^0=1$. (This accounts for the tiling
$\tomv003\tomh4444\tomh0000\tomv003\tomh0000\tomh0000\tomv003\,$.)
If we use two verticals, then $k=1$ and $m=1$; there are
${1+2@\choose1}2^1=6$ such tilings. And if we use four verticals, then
$k=2$ and $m=0$; there are ${0+4\choose0}2^2=4$ such tilings, making a
total of\/ $U_4=11$. In general if $n$ is even, this reasoning shows that
$k+m=\half n$, hence
${m+2k\choose m}={n/2+k\choose n/2-k}$ and the total
 number of $3\times n$ tilings is
\begindisplay
U_n=\sum_k{n/2+k\choose n/2-k}2^k=\sum_m{n-m\choose m}2^{n/2-m}\,.
\eqno\eqref|u-sum|
\enddisplay

As before, we can also substitute $z$ for both \Domv\ and~\Domh, getting
a generating function that doesn't discriminate between dominoes of
particular persuasions. The result is
\begindisplay
U={1\over 1-z^3(1-z^3)^{-1}-z^3(1-z^3)^{-1}-z^3}={1-z^3\over 1-4z^3+z^6}\,.
\eqno\eqref|u-with-cubes|
\enddisplay
If we expand this quotient into a power series, we get
\begindisplay
U=1+U_2\,z^3+U_4\,z^6+U_6\,z^9+U_8\,z^{12}+\cdots\,,
\enddisplay
a generating function for the numbers $U_n$. (There's a curious mismatch
between subscripts and exponents in this formula, but it is easily explained.
The coefficient of~$z^9$, for example, is $U_6$, which counts the tilings
of a $3\times6$ rectangle. This is what we want, because every
such tiling contains nine~dominoes.)

We could proceed to analyze \thiseq\ and get a closed form for the coefficients,
but it's better to save that for later in the chapter after we've gotten
more experience. So let's divest ourselves of dominoes for the moment
%\g Nuns do it out of habit.\g % too risqu\'e
and proceed to the next advertised problem, ``"change".\qback''

\newdimen\coinmm \coinmm=.33333pt
\unitlength=\coinmm
\let\tiny=\mathsubsubtext % 5pt
\newbox\bnullp \newbox\bnulln \newbox\bnulld \newbox\bnullq \newbox\bnullh
\setbox\bnullp=\hbox{\kern1pt\beginpicture(14,18)(-7,0)
	\put(0,9){\makebox(0,0){\lower.2ex\hbox{$\not\mskip4mu$}%
		\tiny 1}}\endpicture\kern1pt}
%\setbox\bnullt=\hbox{\kern1pt\beginpicture(14,18)(-7,0)
%	\put(0,9){\makebox(0,0){\lower.2ex\hbox{$\not\mskip4mu$}%
%		\tiny 2}}\endpicture\kern1pt}
\setbox\bnulln=\hbox{\kern1pt\beginpicture(14,18)(-7,0)
	\put(0,9){\makebox(0,0){\lower.2ex\hbox{$\not\mskip4mu$}%
		\tiny 5}}\endpicture\kern1pt}
\setbox\bnulld=\hbox{\kern1pt\beginpicture(16,18)(-8,0)
	\put(0,9){\makebox(0,0){\lower.2ex\hbox{$\not\mskip1.5mu$}%
		\tiny 1$\mskip-1mu$0}}\endpicture\kern1pt}
\setbox\bnullq=\hbox{\kern1pt\beginpicture(16,18)(-8,0)
	\put(0,9){\makebox(0,0){\lower.2ex\hbox{$\not\mskip1.5mu$}%
		\tiny 2$\mskip-1mu$5}}\endpicture\kern1pt}
\setbox\bnullh=\hbox{\kern1pt\beginpicture(16,18)(-8,0)
	\put(0,9){\makebox(0,0){\lower.2ex\hbox{$\not\mskip1.5mu$}%
		\tiny 5$\mskip-1mu$0}}\endpicture\kern1pt}
% Note, I've added 3mm to all Oren's measurements, for more clearance
\newbox\bpenny \newbox\bnickel \newbox\bdime \newbox\bquarter \newbox\bhalfdollar
\setbox\bpenny=\hbox{\kern1pt\beginpicture(22,18)(-11,0)
	\put(0,9){\circle{22}}
	\put(0,9){\makebox(0,0){\kern.5pt\tiny 1}}
	\endpicture\kern1pt}
\setbox\bnickel=\hbox{\kern1pt\beginpicture(24.2,18)(-12.1,0)
	\put(0,9){\circle{24.2}}
	\put(0,9){\makebox(0,0){\tiny 5}}
	\endpicture\kern1pt}
\setbox\bdime=\hbox{\kern1pt\beginpicture(20.9,18)(-10.45,0)
	\put(0,9){\circle{20.9}}
	\put(0,9){\makebox(0,0){\tiny 1$\mskip-1.5mu$0}}
	\endpicture\kern1pt}
\setbox\bquarter=\hbox{\kern1pt\beginpicture(27.3,18)(-13.65,0)
	\put(0,9){\circle{27.3}}
	\put(0,9){\makebox(0,0){\tiny 2$\mskip-1mu$5}}
	\endpicture\kern1pt}
\setbox\bhalfdollar=\hbox{\kern1pt\beginpicture(33.6,18)(-16.8,0)
	\put(0,9){\circle{33.6}}