. 1
( 14 .)



>>

A Combinatorial Miscellany

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)

. 1
( 14 .)



>>