. 8
( 14 .)


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

proving equation (24).

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.

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)






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:

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:




Rotate this diagram 45—¦ counterclockwise, erase the rhombi, and “straighten
out,” giving the following array of numbers:

322 .

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

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.

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).



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

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

124 126 135 137 147 156 234
235 257 267 346 367 456 457

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
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

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-


. 8
( 14 .)