catenary 65

shows that the Catalan numbers can also be expressed in

terms of

BINOMIAL COEFFICIENT

s:

Thus the Catalan numbers can be found in P

ASCAL

’s

TRIANGLE

as the middle entry of every alternate row

divided by one more than the row number, regarding

the apex of the triangle as row zero.

One can show that the Catalan numbers satisfy the

relationship:

C0= 1

Cn= C0Cn–1 + C1Cn–2 + … + Cn–1C0

The Catalan numbers appear as the solution to a sur-

prising number of different mathematical problems. We

list here just a few examples.

1. Euler’s Polygon Division Problem: How

many ways are there to divide an (n+ 2)-

sided polygon into ntriangles using nonin-

tersecting diagonals of the polygon?

A three-sided polygon, that is, a triangle, is already

appropriately subdivided. There is one solution to the

problem, namely, do nothing. A square can be subdi-

vided into two triangles two different ways. One can

check that a pentagon can be so subdivided five differ-

ent ways. In general the solution to this puzzle is the

nth Catalan number.

2. Laddered Exponents: How many ways can

one interpret a laddered exponent?

For example, 32has only one interpretation: it means

3 ×3 = 9. The expression 23

4

, however, can be inter-

preted two ways: (23)

4

= 4096 or 2(3

4

)=

2417851639229258349412352. In general, a lad-

dered exponent with (n+ 1) terms can be interpreted

Cndifferent ways. (This problem is equivalent to

Catalan’s original parentheses puzzle.)

3. Handshakes across a Table: In how many

different ways can npairs of people sitting

at a circular table shake hands simultane-

ously? No pair of handshakes may cross.

Two people sitting at a table can shake hands only one

way. Four people can accomplish the feat in only two

ways. (Diagonal handshakes cross.) In general, npairs of

people can shake hands Cndifferent ways, for one can

interpret two hands shaking as a pair of parentheses.

4. Stair Climbing: Starting at the base of a

flight of stairs, in how many ways can one

take nsteps up and nsteps down, in any

order? (You will necessarily return to the

base of the steps on completion of the walk.)

There is one way to take two steps: one step up followed

by one step down, and two ways to take four steps: two

up, two down, or one up, one down, repeated twice. In

general there are Cnways to accomplish this task.

(Thinking of a left parenthesis as an “up step” and a

right parenthesis as a “down step,” we can see that this

puzzle too is equivalent to Catalan’s original problem.)

5. Summation Problem: Select nnumbers from

the set {1,2,3,…,2n} so that their sum is a

multiple of n+ 1. Can this be done? If so, in

how many different ways?

Consider the case n= 3, for example. There are five ways

to select three numbers from the set {1, 2, 3, 4, 5, 6} with

sum divisible by four: 1 + 2 + 5 = 8; 1 + 3 + 4 = 8; 1 + 5

+ 6 = 12; 2 + 4 + 6 = 12; 3 + 4 + 5 = 12. In general, these

puzzles can always be solved, and there are Cnways to

do them.

See also C

ATALAN CONJECTURE

.

catenary The shape of the curve formed by a uniform

flexible cable hanging freely between two points, such as

an electric cable between two telegraph poles, is called a

catenary. G

ALILEO

G

ALILEI

(1564–1642) thought this

curve to be a

PARABOLA

, but German scholar Joachim

Jungius (1587–1657) later proved that this could not be

the case. Jacques Bernoulli (1654–1705) of the famous