az(n) = 2 2 n(n+1) ,

proving equation (24).

49

Figure 6: The hexagonal board H(2, 3, 3)

8 Tilings and plane partitions.

We have discussed several examples of unexpected connections between seem-

ingly unrelated mathematical problems. This is one of the features of math-

ematics that makes it so appealing to its practitioners. In this section we

discuss another such connection, this time between tilings and plane parti-

tions. Other surprising connections will be treated in later sections.

The tiling problem we will be considering is very similar to the problem

of tiling an m — n chessboard with dominos. Instead of a chessboard (whose

shape is a rectangle), we will be tiling a hexagon. Replacing the squares of

the chessboard will be equilateral triangles of unit length which ¬ll up the

hexagon, yielding a “hexagonal board.” Let H(r, s, t) denote the hexagonal

board whose opposite sides are parallel and whose side lengths (in clockwise

order) are r, s, t, r, s, t. Thus opposite sides of the hexagon have equal length

just like opposite sides of a rectangle have equal length. Figure 6 shows the

hexagonal board H(2, 3, 3) with its 42 equilateral triangles. In general, the

hexagonal board H(r, s, t) has 2(rs + rt + st) equilateral triangles.

50

Instead of tiling with dominos (which consist of two adjacent squares), we

will be tiling with pieces which consist of two adjacent equilateral triangles.

We will call these pieces simply rhombi, although they are really only special

kinds of rhombi. Thus the number of rhombi in a tiling of H(r, s, t) is rs +

rt + st. The rhombi can have three possible orientations (compared with the

two orientations of a rectangle):

Here is a typical tiling of H(2, 3, 3)

LW

RW

RW

F

F

This picture gives the impression of looking into the corner of an r — s — t

box in which cubes are stacked. The brain will alternate between di¬erent

interpretations of this cube stacking. To be de¬nite, we have labelled by F

the ¬‚oor, by LW the left wall, and by RW the right wall. Shading the rhombi

according to their orientation heightens the impression of a cube stacking,

particularly if the page is rotated slightly counterclockwise:

51

Regarding the ¬‚oor as a 3 — 2 parallelogram ¬lled with six rhombi, we can

encode the cube stacking by a 3 — 2 array of numbers which tell the number

of cubes stacked above each ¬‚oor rhombus:

3

2

2

0

2

0

Rotate this diagram 45—¦ counterclockwise, erase the rhombi, and “straighten

out,” giving the following array of numbers:

322 .

200

This array is nothing more than a plane partition whose number of rows

is at most r, whose number of columns is at most s, and whose largest

part is at most t (where we began with the hexagonal board H(r, s, t))! This

52

correspondence between rhombic tilings of H(r, s, t) and plane partitions with

at most r rows, at most s columns, and with largest part at most t is a

bijection. In other words, given the rhombic tiling, there is a unique way to

interpret it as a stacking of cubes (once we agree on what is the ¬‚oor, left

wall, and right wall), which we can encode as a plane partition of the desired

type. Conversely, given such a plane partition, we can draw it as a stacking

of cubes which in turn can be interpreted as a rhombic tiling.

An immediate corollary of the amazing correspondence between rhombic

tilings and plane partitions is an explicit formula for the number N (r, s, t)

of rhombic tilings of H(r, s, t). For this number is just the number of plane

partitions with at most r rows, at most s columns, and with largest part at

most t. If we set x = 1 in the left-hand side of MacMahon™s formula (14)

then it follows that we just get N (r, s, t). If we set x = 1 in the right-hand

side then we get the meaningless expression 0/0. However, if we write

[i] = 1 ’ xi = (1 ’ x)(1 + x + · · · + xi’1 ),

then the factors of 1 ’ x cancel out from the numerator and denominator

of the right-hand side of (14). Therefore substituting x = 1 is equivalent to

replacing [i] by the integer i, so we get the astonishing formula

N (r, s, t) =

(1 + t)(2 + t)2 · · · (r + t)r (r + 1 + t)r · · · (s + t)r (s + 1 + t)r’1 (s + 2 + t)r’2 · · · (r + s ’ 1 + t)

.

1 · 22 · 33 · · · rr (r + 1)r · · · sr (s + 1)r’1 (s + 2)r’2 · · · (r + s ’ 1)

9 Combinatorics and Topology

On ¬rst acquaintance combinatorics may seem to have a somewhat di¬erent

“¬‚avor” than the mainstream areas of mathematics, due mainly to what

mathematicians call “discreteness.” Nevertheless, combinatorics is fortunate

to have many beautiful and fruitful links with older and more established

areas, such as algebra, geometry, probability and topology. We will now

move on to discuss one such connection, perhaps the most surprising one,

namely that with topology. First, however, let us say a few words about

what mathematicians mean by discreteness.

53

In mathematics the words “continuous” and “discrete” have technical

meanings that are quite opposite. Typical examples of continuous objects are

curves and surfaces in 3-space (or, suitably generalized, in higher-dimensional

spaces). A characteristic property is that each point on such an object is

surrounded by some “neighborhood” of other points, containing points that

are in a suitable sense “near” to it. The area within mathematics that deals

with the study of continuity is called topology. The characteristic property

of discrete objects, on the other hand, is that each point is “isolated” ”

there is no concept of points being “near.” Combinatorics is the area that

deals with discreteness in its purest form, particularly in the study of ¬nite

structures of various kinds.

Several fascinating connections between the continuous and the discrete

are known in mathematics ” in algebra, geometry and analysis. A quite

recent development of this kind, the one we want to talk about here, is that

ideas and results from topology can be put to use to solve certain combi-

natorial problems. We will soon exemplify this with two problems coming

from computer science. However, ¬rst we will discuss in greater detail the

connection between topology and combinatorics that will be used.

Let us take as our example of a topological space the torus, a 2-dimensional

surface that is well known in ordinary life in the form of an inner-tube, or as

the surface of a doughnut (see Figure 7).

a

b

Figure 7: The torus

There is a way to “encode” a space such as the torus into a ¬nite set sys-

tem, called a triangulation. It works as follows. Draw (curvilinear) triangles

on the torus so that each edge of a triangle is also the edge of some other

54

triangle, and the 2 endpoints of each edge are not the pair of endpoints of

any other edge. The triangles should cover the torus so that each point on

the torus is in exactly one of the triangles, or possibly in an edge where two

triangles meet or at a corner where several triangles meet. We can think

of this as cutting the rubber surface of an inner tube into small triangular

pieces. Figure 8 shows one way to do this using 14 triangles. In this ¬gure

the torus is cut up and ¬‚attened out ” to get back the original torus one

has to roll this ¬‚attened version up and glue together the two sides marked

1-2-3-1, and then wrap around the cylinder obtained and glue together the

two end-circles marked 1-4-5-1. Note that the two circles 1-2-3-1 and 1-4-5-1

in Figure 8 correspond to the circles marked a and b that are drawn with

dashed lines on the torus in Figure 7.

1 2 3 1

5 5

6 7

4 4

1 2 3 1

Figure 8: A triangulated torus

Having thus cut the torus apart we now have a collection of 14 triangles.

The corners in Figure 8 where triangles come together are called vertices,

and we can represent each triangle by its 3 vertices. Thus each one of our 14

triangles is replaced by a 3-element subset of {1,2,3,4,5,6,7}. For instance,

{1,2,4} and {3,4,6} denote two of the triangles. The full list of all 14 triangles

is

124 126 135 137 147 156 234

(25)

235 257 267 346 367 456 457

55

A family of subsets of a ¬nite set which is closed under taking subsets

(i.e., if A is a set in the family and B is obtained by removing some elements

from A then also B is in the family) is called a simplicial complex . Thus,

our fourteen 3-element sets and all their subsets form a simplicial complex.

An important fact is that just knowing the simplicial complex ” a ¬nite

set system ” we can fully reconstruct the torus! Namely, knowing the 14

triples we can manufacture 14 triangles with vertices marked in corresponding

fashion and then glue these triangles together according to the blueprint of

Figure 8 (using the vertex labels) to obtain the torus. To imagine this you

should think of the triangles as being ¬‚exible (e.g., made of rubber sheet) so

that there are no physical obstructions to their being bent and glued together.

Also, the torus obtained may be di¬erent in size or shape from the original

one (smaller, larger, deformed), but these di¬erences are irrelevant from the

point of view of topology.

To sum up the discussion: The simplicial complex coming from a trian-

gulation is a complete encoding of the torus as a topological object. Every

property of the torus that topology can have anything to say about is also a

property of this ¬nite set system!

Why would topologists want to use such an encoding? The main rea-

son is that they are interested in computing certain so called invariants of

topological spaces, such as the “Betti numbers” which we will soon comment

on. The spaces they consider (such as the torus) are geometric objects with

in¬nitely many points, on which it is usually hard to perform concrete com-

putations. An associated simplicial complex, on the other hand, is a ¬nite

object which is easily adapted to computation (except possibly for size rea-

sons). Topological invariants depend only on the space in question, but their

computation may depend on choosing a triangulation or other “combinato-

rial decomposition”. The part of topology that develops this connection is

known as combinatorial topology. It was initiated by the great French math-

ematician Jules Henri Poincar´ (1854“1912) in the last years of the 1800™s

e

and greatly developed in the ¬rst half of this century. Eventually the subject

took on a more and more algebraic ¬‚avor and in the 1940™s the area changed

name to algebraic topology.

The Betti numbers of a space are topological invariants that can be said

56

to measure the number of “independent holes” of various dimensions. It is

impossible to give the full technical de¬nition within the framework of this

article. Let it su¬ce to say that the de¬nition depends on certain algebraic

constructions and to give some examples. If T is a d-dimensional topological

space then there are d + 1 Betti numbers

β0 (T ), β1 (T ), ..., βd (T ),

which are nonnegative integers. Once we have a triangulation of a topological

space the computation of Betti numbers is a matter of some very simple (in

principle) linear algebra.

For instance, the d-dimensional sphere has Betti numbers (0, ..., 0, 1), re-