Anders Bj¨rner1

o

Matematiska Institutionen

Kungl. Tekniska H¨gskolan

o

S-100 44 Stockholm

SWEDEN

Richard P. Stanley2

Department of Mathematics

Massachusetts Institute of Technology

Cambridge, MA 02139

U.S.A.

September 13, 2004

1 Introduction.

A recent newcomer to the the center stage of modern mathematics is the

area called combinatorics. Although combinatorial mathematics has been

pursued since time immemorial, and at a reasonable scienti¬c level at least

since Leonhard Euler (1707“1783), the subject has come into its own only in

1

Partially supported by the Mathematical Sciences Research Institute (Berkeley, CA).

2

Partially supported by NSF grant #DMS-9500714.

1

the last few decades. The reasons for the spectacular growth of combinatorics

come both from within mathematics itself and from the outside.

Beginning with the outside in¬‚uences, it can be said that the recent de-

velopment of combinatorics is somewhat of a cinderella story. It used to be

looked down on by “mainstream” mathematicians as being somehow less re-

spectable than other areas, in spite of many services rendered to both pure

and applied mathematics. Then along came the prince of computer science

with its many mathematical problems and needs ” and it was combinatorics

that best ¬tted the glass slipper held out.

The developments within mathematics that have contributed to the cur-

rent strong standing of combinatorics are more di¬cult to pinpoint. One

is that, after an era where the fashion in mathematics was to seek general-

ity and abstraction, there is now much appreciation of and emphasis on the

concrete and “hard” problems. Another is that it has been gradually more

and more realized that combinatorics has all sorts of deep connections with

the mainstream areas of mathematics, such as (to name the most important

ones) algebra, geometry, probability and topology.

Our aim with this article is to give the reader some answers to the ques-

tions “What is combinatorics, and what is it good for?” We will do that not

by attempting any kind of general survey, but by describing a few selected

problems and results in some detail. We want to bring you both some ex-

amples of problems from “pure” combinatorics, some examples illustrating

its interactions with other parts of mathematics, and a few glimpses of its

use for computer science. Fortunately, the problems and results of combina-

torics are usually quite easy to state and explain, even to the layman. Its

accessibility is one of its many appealing aspects. For instance, most popular

mathematical puzzles and games, such as Rubik™s cube and jigsaw puzzles,

are essentially problems in combinatorics.

To achieve our stated purpose it has been necessary to concentrate on

a few topics, leaving many of the specialities within combinatorics without

mention. The choice will naturally re¬‚ect our own interests. The suggestions

for further reading point to some more general accounts that can help remedy

this shortcoming.

2

With some simpli¬cation, combinatorics can be said to be the mathe-

matics of the ¬nite. One of the most basic properties of a ¬nite collection of

objects is its number of elements. For instance, take words formed from the

letters a, b and c, using each letter exactly once. There are six such words:

abc, acb, bac, bca, cab, cba.

Now, say that we have n distinct letters. How many words can be formed?

The answer is n · (n ’ 1) · (n ’ 2) · · · 3 · 2 · 1, because the ¬rst letter can

be chosen in n ways, then the second one in n ’ 1 ways (since the letter

already chosen as the ¬rst letter is no longer available), the third one in n ’ 2

ways, and so on. Furthermore, the total number must be the product of the

number of individual choices.

The number of words that can be formed with n letters is an example

of an enumerative problem. Enumeration is one of the most basic and im-

portant aspects of combinatorics. In many branches of mathematics and its

applications you need to know the number of ways of doing something. One

of the classical problems of enumerative combinatorics is to count partitions

of various kinds, meaning the number of ways to break an object into smaller

objects of the same kind. The study of partition enumeration was begun by

Euler and is very active to this day. We will exposit some parts of this theory.

All along the way there are interesting connections with algebra, but these

are unfortunately too sophisticated to go into details here. We also illustrate

(in Section 11) the relevance of partitions to applied problems.

Another, more recent, topic within enumeration is to count the number

of tilings. These are partitions of a geometric region into smaller regions

of some speci¬ed kinds. We will give some glimpses of recent progress in

this area. The mathematical roots are in this case mainly from statistical

mechanics.

Combinatorics is used in many ways in computer science, for instance for

the construction and analysis of various algorithms. (Remark: algorithms are

the logically structured systems of commands that instruct computers how

to perform prescribed tasks.) Of this young but already huge and rapidly

growing area we will give here but the smallest glimpse, namely a couple of

3

examples from complexity theory. This is the part of theoretical computer

science that concerns itself with questions about computer calculations of

the type “How hard is it?”, “How much time will it take?” Proving that

you cannot do better than what presently known methods allow is often

the hardest part, and the part where the most mathematics is needed. Our

examples are of this kind.

To illustrate the surprising connections that exist between combinatorics

and seemingly unrelated parts of mathematics we have chosen the links with

topology. This is an area which on ¬rst acquaintance seems far removed

from combinatorics, having to do with very general in¬nite spaces. Never-

theless, the tools of algebraic topology have proven to be of use for solving

some problems from combinatorics and theoretical computer science. Again,

the theme of enumeration in its various forms pervades some of this border

territory.

Our ¬nal topic is a glimpse of progress made in the combinatorial study of

convex polytopes. In three dimensions these are the decorative solid bodies

with ¬‚at polygon sides (such as pyramids, cubes and geodesic domes) that

have charmed and intrigued mathematicians and laymen alike since antiquity.

In higher dimensions they can be perceived only via mathematical tools, but

they are just as beautiful and fascinating. Of this huge subject we discuss

the question of laws governing the numbers of faces of various dimensions on

the boundary of a polytope.

To understand this article should for the most part require hardly any

knowledge of mathematics beyond high-school algebra. Only some details in

the boxes and in the last few sections (having to do with topology) are a bit

more demanding.

2 Partitions.

A fundamental concept in combinatorics is that of a partition. In general,

a partition of an object is a way of breaking it up into smaller objects. We

will be concerned here with partitions of positive integers (positive whole

4

numbers). Later on we will encounter also other kinds of partitions. The

subject of partitions has a long history going back to Gottfried Wilhelm

von Leibniz (1646“1716) and Euler, and has been found to have unexpected

connections with a number of other subjects. A partition of a positive integer

n is a way of writing n as a sum of positive integers, ignoring the order of the

summands. For instance, 3 + 4 + 2 + 1 + 1 + 4 represents a partition of 15,

and 4 + 4 + 3 + 2 + 1 + 1 represents the same partition. A partition is allowed

to have only one part (summand), so that 5 is a partition of 5. There are in

fact seven partitions of 5, given by

5

4+1

3+2

3+1+1

2+2+1

2+1+1+1

1 + 1 + 1 + 1 + 1.

We denote the number of partitions of n by p(n), so for instance p(5) = 7.

By convention we set p(0) = 1, and similarly for related partition functions

discussed below. The problem of evaluating p(n) has a long history. There

is no simple formula in general for p(n), but there are remarkable and quite

sophisticated methods to compute p(n) for “reasonable” values of n. For

instance, as long ago as 1938 Derrick Henry Lehmer (1905“1991) computed

p(14, 031) (a number with 127 digits!), and nowadays a computer would

have no trouble computing p(1012 ), a number with 1,113,996 digits. It is

also possible to codify all the numbers p(n) into a single object known as a

generating function. A generating function (in the variable x) is an expression

of the form

F (x) = a0 + a1 x + a2 x2 + a3 x3 + · · · ,

where the coe¬cients a0 , a1 , . . . are numbers. (We call an the coe¬cient of

xn , and call a0 the constant term. The notation x0 next to a0 is suppressed.)

The generating function F (x) di¬ers from a polynomial in x in that it can

have in¬nitely many terms. We regard x as a formal symbol, and do not

think of it as standing for some unknown quantity. Thus the generating

function F (x) is just a way to represent the sequence a0 , a1 , . . ..

It is natural to ask what advantage is gained in representing a sequence in

such a way. The answer is that generating functions can be manipulated in

5

various ways that often are useful for combinatorial problems. For instance,

letting G(x) = b0 + b1 x + b2 x2 + · · ·, we can add F (x) and G(x) by the rule

F (x) + G(x) = (a0 + b0 ) + (a1 + b1 )x + (a2 + b2 )x2 + · · · .

In other words, we simply add the coe¬cients, just as we would expect from

the ordinary rules of algebra. Similarly we can form the product F (x)G(x)

using the ordinary rules of algebra, in particular the law of exponents xi xj =

xi+j . To perform this multiplication, we pick a term ai xi from F (x) and a

term bj xj from G(x) and multiply them to get ai bj xi+j . We then add together

all such terms. For instance, the term in the product involving x4 will be

a0 · b4 x4 + a1 x · b3 x3 + a2 x2 · b2 x2 + a3 x3 · b1 x + a4 x4 · b0

= (a0 b4 + a1 b3 + a2 b2 + a3 b1 + a4 b0 )x4 .

In general, the coe¬cient of xn in F (x)G(x) will be

a0 bn + a1 bn’1 + a2 bn’2 + · · · + an’1 b1 + an b0 .

Consider for instance the product of F (x) = 1 + x + x2 + x3 + · · · with

G(x) = 1 ’ x. The constant term is just a0 b0 = 1 · 1 = 1. If n > 1 then the

coe¬cient of xn is an b0 + an’1 b1 = 1 ’ 1 = 0 (since bi = 0 for i > 1, so we

have only two nonzero terms). Hence

(1 + x + x2 + x3 + · · ·)(1 ’ x) = 1.

For this reason we write

1

= 1 + x + x2 + x3 + · · · .

1’x

Some readers will recognize this formula as the sum of an in¬nite geometric

series, though here the formula is “formal,” that is, x is regarded as just a

symbol and there is no question of convergence. Similarly, for any k ≥ 1 we

get

1

= 1 + xk + x2k + x3k + · · · . (1)

k

1’x

Now let P (x) denote the (in¬nite) product

1 1 1

P (x) = · · ···.

1 ’ x 1 ’ x2 1 ’ x3

6

We may also write this product as

1

P (x) = . (2)

(1 ’ x)(1 ’ x2 )(1 ’ x3 ) · · ·

Can any sense be made of this product? According to our previous discussion,

we can rewrite the right-hand side of equation (2) as

P (x) = (1 + x + x2 + · · ·)(1 + x2 + x4 + · · ·)(1 + x3 + x6 + · · ·) · · · .

To expand this product as a sum of individual terms, we must pick a term

xm1 from the ¬rst factor, a term x2m2 from the second, a term x3m3 from

the third, etc., multiply together all these terms, and then add all such

products together. In order not to obtain an in¬nite (and therefore mean-

ingless) exponent of x, it is necessary to stipulate that when we pick the

terms xm1 , x2m2 , x3m3 , . . ., only ¬nitely many of these term are not equal to

1. (Equivalently, only ¬nitely many of the mi are not equal to 0.) We then

obtain a single term xm1 +2m2 +3m3 +··· , where the exponent m1 +2m2 +3m3 +· · ·

is ¬nite. The coe¬cient of xn in P (x) will then be the number of ways to write

n in the form m1 + 2m2 + 3m3 + · · · for nonnegative integers m1 , m2 , m3 , . . ..

But writing n in this form is the same as writing n as a sum of m1 1™s, m2

2™s, m3 3™s, etc. Such a way of writing n is just a partition of n. For instance,

the partition 5 + 5 + 5 + 4 + 2 + 2 + 2 + 2 + 1 + 1 + 1 of 30 corresponds to

choosing m1 = 3, m2 = 4, m4 = 1, m5 = 3, and all other mi = 0. It follows

that the coe¬cient of xn in P (x) is just p(n), the number of partitions of n,

so we obtain the famous formula of Euler

1

p(0) + p(1)x + p(2)x2 + · · · = . (3)