Please consider the following problems:
- How many possible sudoku puzzles are there?
- Do 37 Londoners exist with the same number of hairs on their head?
- In a lottery where 6 balls are selected from 49, how often do two winning balls have consecutive numbers?
- In how many ways can we give change for £1 using only 10p, 20p, and 50p pieces?
- Is there a systematic way of escaping from a maze?
- How many ways are there of rearranging the letters in the word “ABRACADABRA”?
- Can we construct a floor tiling from squares and regular hexagons?
- In a random group of 23 people, what is the chance that two have the same birthday?
- In chess, can a knight visit all the 64 squares of an 8 × 8 chessboard by knight’s moves and return to its starting point?
- If a number of letters are put at random into envelopes, what is the chance that no letter ends up in the right envelope?
What do you notice about these problems?
First of all, unlike many mathematical problems that involve much abstract and technical language, they’re all easy to understand – even though some of them turn out to be frustratingly difficult to solve. This is one of the main delights of the subject.
Secondly, although these problems may appear diverse and unrelated, they mainly involve selecting, arranging, and counting objects of various types. In particular, many of them have the forms. Does such-and-such exist? If so, how can we construct it, and how many of them are there? And which one is the ‘best’?
The subject of combinatorial analysis or combinatorics (pronounced com-bin-a-tor-ics) is concerned with such questions. We may loosely describe it as the branch of mathematics concerned with selecting, arranging, constructing, classifying, and counting or listing things.
To clarify our ideas, let’s see how various sources define combinatorics.
Oxford Dictionaries describe it briefly as:
“The branch of mathematics dealing with combinations of objects belonging to a finite set in accordance with certain constraints, such as those of graph theory.”
While the Collins dictionary present it as:
“the branch of mathematics concerned with the theory of enumeration, or combinations and permutations, in order to solve problems about the possibility of constructing arrangements of objects which satisfy specified conditions.”
Wikipedia introduces a new idea, that combinatorics is:
“a branch of mathematics concerning the study of finite or countable discrete structures.”
So the subject involves finite sets or discrete elements that proceed in separate steps (such as the numbers 1, 2, 3 …), rather than continuous systems such as the totality of numbers (including π, √2, etc.) or ideas of gradual change such as are found in the calculus. The Encyclopaedia Britannica extends this distinction by defining combinatorics as:
“the field of mathematics concerned with problems of selection, arrangement, and operation within a finite or discrete system … One of the basic problems of combinatorics is to determine the number of possible configurations (e.g., graphs, designs, arrays) of a given type.”
Finally, Wolfram Research’s MathWorld presents it slightly differently as:
“the branch of mathematics studying the enumeration, combination, and permutation of sets of elements and the mathematical relations that characterize their properties,”
“Mathematicians sometimes use the term ‘combinatorics’ to refer to a larger subset of discrete mathematics that includes graph theory. In that case, what is commonly called combinatorics is then referred to as ‘enumeration’.”
The subject of combinatorics can be dated back some 3000 years to ancient China and India. For many years, especially in the Middle Ages and the Renaissance, it consisted mainly of problems involving the permutations and combinations of certain objects. Indeed, one of the earliest works to introduce the word ‘combinatorial’ was a Dissertation on the combinatorial art by the 20-year-old Gottfried Wilhelm Leibniz in 1666. This work discussed permutations and combinations, even claiming on the front cover to ‘prove the existence of God with complete mathematical certainty’.
Over the succeeding centuries the range of combinatorial activity broadened greatly. Many new types of problem came under its umbrella, while combinatorial techniques were gradually developed for solving them. In particular, combinatorics now includes a wide range of topics, such as the geometry of tilings and polyhedra, the theory of graphs, magic squares and Latin squares, block designs and finite projective planes, and partitions of numbers.
Much of combinatorics originated in recreational pastimes, as illustrated by such well-known puzzles such as the Königsberg bridges problem, the four-colour map problem, the Tower of Hanoi, the birthday paradox, and Fibonacci’s ‘rabbits’ problem. But in recent years the subject has developed in depth and variety and has increasingly become a part of mainstream mathematics. Prestigious mathematical awards such as the Fields Medal and the Abel Prize have been given for ground-breaking contributions to the subject, while a number of spectacular combinatorial advances have been reported in the national and international media.
Undoubtedly part of the reason for the subject’s recent importance has arisen from the growth of computer science and the increasing use of algorithmic methods for solving real-world practical problems. These have led to combinatorial applications in a wide range of subject areas, both within and outside mathematics, including network analysis, coding theory, probability, virology, experimental design, scheduling, and operations research.
Featured image credit: ‘Sudoku’ by Gellinger. CC0 public domain via Pixabay.