The Art and Craft of Problem Solving

218 CHAPTER 6 COMBINATORICS

which you can check by carefully drawing all the possibilities.

Before we rest, let's look at the 7-gon case. The triangulations are partitioned by

the five cases below:

000'0'0

,II. • " I

:'.,.

... .... :,:

�

I , • • • •

,

. ,

,..

�

�

"

"

..

,/

\,

,:.'

�

....

....

......
..... :
...
..

.. ... :: �

....

...

The first picture yields t 6 triangulations and the second yields t5, but the third picture

gives rise to t 4. t 4 triangulations, since we are free to choose any triangulation in each

of the two quadrilaterals on either side of the dotted triangle. The general situation is

that each picture dissects the 7-gon into three polygons, one of which is the specified

triangle with fixed base, and the other two mayor may not involve choices. The other

two polygons may include a "degenerate" 2-gon (for example, the first and last pic­

tures) or a triangle, and in both cases this provides no new choices. But otherwise, we

will be free to choose and will need to multiply to count the total number of triangula­

tions for each picture. If we include the "degenerate" case and define t2 to equal 1, we

have the more consistent equation

and in general,

tn = t2 tn-l +t3 tn-2 + ... + tn-lt 2 = � tutv,

u+v=n+l

(11)

where the indices of summation are all pairs u, v that add up to n + 1; we need no

further restrictions as long as we accept the sensible convention that tu = 0 for all

u � 1.

Now that we have a recurrence plus boundary values, we have "solved" the prob­

lem, at least in a computational sense, since we can calculate as many values of tn as

we would like. _

Here is a table of the first few values.

The sequence 1,1,2,5, 14, ... is known as the Catalan numbers (according to some

conventions, the index starts at zero, so if Cr denotes the rth Catalan number, then

tr = Cr-2). Recurrence formulas such as (11) may seem rather complicated, but they

are really straightforward applications of standard counting ideas (partitioning and

simple encoding). Algebraically, the sum should remind you of the rule for mUltiplying

polynomials (see page 16 4), which in turn should remind you of generating functions

(Section 4.3).

Example 6.4.3 Use generating functions to find a formula for Cn.