The Mathematics that Counts

10 October 2013   The Mathematics that Counts   Professor Robin Wilson     Good evening – and welcome to the launch of Combinatorics: Ancient and Modern, our recent book on the history of combinatorics. The purpose of today is to tell you what the subject is about, and how it arose historically, and I’ll include many fascinating examples from the book.   So first: What is combinatorics? Although the term means different things to different people, roughly speaking it’s the branch of mathematics that’s concerned with selecting, arranging, and listing or counting collections of objects – usually finite collections. Included here are permutations and combinations of the objects in a set, recreational problems from graph theory (such as the Königsberg bridges problem and the four-color problem), and magic squares and latin squares, including the sudoku puzzles that thousands try to solve on their way to work, unaware that they’re doing combinatorics.  The chapters of our book were written by distinguished combinatorialists and historians of mathematics from around the world. The Ancient half of the book presents the multicultural origins of the subject, and following a wide-ranging overview by the distinguished American computer scientist Donald Knuth, we feature the early combinatorial concerns of people from China, India, the Islamic world, and the Jewish scholarly community, before we move forward to look at combinatorics in Renaissance Europe.   By way of contrast, the Modern part is arranged thematically, rather than chronologically, and includes such areas as graph theory, block designs and latin squares: you’ll see some of these topics in the second part of this talk. Our book concludes with a personal view of contemporary topics by the distinguished combinatorialist Peter Cameron.   PART I Our journey starts in China, with the well-known I Ching (The Book of Change). Each of its 64 chapters is symbolized by a ‘hexagram’ formed from six horizontal lines, either solid (yang) or dashed (yin). With six lines and two choices for each line, the total number of hexagrams is 26 = 64. These are ordered selections with repetition – the order of the lines in each hexagram matters, and yins and yangs can appear more than once in the hexagrams. Note the arrangement of hexagrams here: each one appears next to its ‘yin-yang complement’.   By way of contrast, we next consider ordered selections without repetition – called permutations. Here’s a statue of the four-handed Indian god Vishnu holding a discus, conch, lotus, and mace. How many arrangements are possible? His first hand can hold any of the four objects, his second can hold any of the remaining three, and so on, so the number of possible permutations is         4 × 3 × 2 × 1 = 24, or ‘4-factorial’.    A similar ancient problem concerns the ten-handed god Sambhu:    How many are the variations of form of this god by the exchange of his ten attributes held in his ten hands: the rope, the elephant’s hook, the serpent, the tabor, the skull, the trident, the bedstead (of all things!), the dagger, the arrow and the bow?    The answer is 10!: over three million ways!  A musical example was given by the French Minimite friar Marin Mersenne. In his Harmonicorum Libri (Book of Harmonic Principles) of 1636 he displayed all the 4! = 24 permutations of four musical notes, and then proceeded to write out all the 6! = 720 possible ‘songs’ with 6 notes.    Another example is a medieval commentary on a sacred Jewish text, the Sefer Yetsirah (Book of Creation), which we’ll meet again later. This shows the 5! = 120 permutations of five Hebrew symbols.     Throughout the centuries many writers have been interested in the combinatorics of poetic meter. Such concerns featured in ancient India, and in 1617 Erycius Puteanus, a Flemish professor, took a famous 8-word Latin hexameter line in praise of the Virgin Mary:  Tot tibi sunt dotes, Virgo, quot sidera caelo. Although there are 8! = 40,320 permutations of these eight words, each permutation was required to fit the basic hexameter pattern:  dum-diddy, dum-dum, dum-dum, dum-dum, dum-diddy, dum-dum.   For example: Tot-tibi   sunt do-   tes Vir-   go quot   si-dera   cae-lo . . . Sunt-caelo   tot Vir-   go ti-   bi, quot   si-dera   do-tes.   Puteanus then wrote out 1022 of these permutations: he chose this number because there were 1022 visible stars in Ptolemy’s star catalogue.   In the early part of the last millennium a number of writers formulated specific rules for the number of permutations. Here’s an example from 1321 by Levi ben Gerson, a Jewish Scholar who lived in the south of France and who introduced the idea of mathematical induction. There was then no algebraic notation, so he had to present his rules in words:   If the number of permutations of a given number of different elements is equal to a given number, then the number of permutations of a set of different elements containing one more number equals the product of the former number of permutations and the given next number. This was one of his simpler results and asserts that (n + 1)! = (n + 1) × n!   A different type of combinatorial problem involves combinations. Like permutations, these selections don’t allow repetition, but now the objects can appear in any order.    In the 6th century BC a celebrated Sanskrit medical treatise of Susruta noted that medicines can be sweet, sour, salty, pungent, bitter, or astringent, and he listed all the combinations of these when taken one, two, three, four, five or six at a time. The numbers of these are shown here – you’ll meet them again later.   Many early problems on combinations originated in India. For example, around 300 BC the Jainas studied various combinations of five senses, and of men, women and eunuchs (giving rise, no doubt, to a eunuch solution!) But as the numbers become larger, it was no longer possible to list every combination explicitly. In a voluminous 6th-century work, Varahamihira found a way of counting the ways of counting the number of ways of selecting four from a collection of sixteen ingredients, obtaining the correct answer, 1820.     Many examples arose from religious concerns. The Sefer Yetsirah (seen earlier) asserted that God had created the world and named everything in it, using just the 22 letters of the Hebrew alphabet.    God drew them, combined them, weighed them, interchanged them, and through them produced the whole creation and everything that is destined to be created.    But how many things can be named with just two letters? According to the unknown author, God combined the aleph (the first letter) with all the other letters in succession, and all the other letters again with aleph (giving both orderings); he then repeated this with the second letter bet, and so on. The total number of pairs is then 22 × 21, and thus, since the ordering doesn’t matter, we need just half of this number, which is 231.    The author then went on to count permutations of letters, going up to 11! since the longest word in the Bible contained just 11 different Hebrew letters.    Also in a religious context, the Catalan mystic Ramon Llull asserted that all knowledge can be discovered by combining the attributes of God in all possible ways. On the left we see nine of these divine attributes – bonitas (goodness), potestas (power), sapientia (wisdom), and so on – and on the right is his bipartite graph linking these attributes in pairs. (He even introduced movable concentric wheels labelled with these attributes helping us to compare them more easily.) As we shall see, Llull’s influence over later centuries was profound, with such followers as Marin Mersenne, Athanasius Kircher, and even Gottfried Wilhelm Leibniz in his early years.   Different authors liked to express their formulas in different ways, depending on the purpose. In 1658 the Dutch mathematician Frans van Schooten listed the combinations of the letters a, b, c, d like this, adding one new letter in each row. He then observed that by replacing these letters by 2, 3, 5 and 7 we obtain the divisors of the number 210. As with permutations, the early part of the last millennium saw formulas for the number of combinations of objects selected from a given set. Here’s such a formula, from Bhaskara II’s 12th-century work Lilavati, rewritten in modern notation.     If we wish to display numbers of combinations, we often use the ‘arithmetical triangle’, usually referred to as Pascal’s triangle. In this pattern the rows count combinations of objects – for example, the row beginning 1, 6, 15 counts Susruta’s combinations of six tastes, seen earlier. Note that each number (other than the 1s) is the sum of the two numbers above it, and so the triangle can easily be extended as far as one wishes.    The arithmetical triangle also gives the coefficients arising from the binomial theorem: for example, when we expand (1 + x)3, we get  1 + 3x + 3x2 + 1x3, giving the row 1, 3, 3, 1.   But ‘Pascal’s triangle’ predated Blaise Pascal by many centuries.    The oldest ‘arithmetical triangles’ (as we should more properly call them) are from the Islamic world. Here on the left is the earliest known example, due to al-Karaji from around the year 1007, with another one by Ibn Munim from around 1200, which is easier for us to read since its numerals are closer to the Hindu-Arabic numerals we use today.   A well-known arithmetical triangle is this Chinese one, dating from 1303, from Zhu Shijie’s ‘Jade Mirror of Four Elements’. Interestingly, it contains an error in the penultimate row, where the number 34 should be 35.     The two strands, binomial coefficients and combinations, had come together by the 16th century, and shortly afterwards several arithmetical triangles appeared. Here’s one by Cardano, the writer on cubic equations, dating from 1570 . . .     … and here’s an earlier one from Tartaglia, his bitter rival in the struggle to solve cubic equations.    A truly impressive arithmetical triangle appeared in Marin Mersenne’s music book, mentioned earlier. Concerned with combinations of musical notes, he extended the table to selecting 12 notes from 36. As seen in the bottom right-hand corner, there are over a billion of them.    Mersenne also calculated every factorial up to 64!, a 90-digit number, but unfortunately many of his later values were incorrect.      Pascal’s original triangle is shown here – it appeared in a posthumous work on the arithmetical triangle which was published in 1665. Here Pascal gave the first ‘modern’ treatment of the subject, clearly describing (with proofs) the various ways in which the triangle can arise, and putting it on a proper theoretical basis. It was probably De Montmort who attributed the triangle to Pascal, in his Essay Analysing Games of Chance, which we see again later.    Just as Pascal gave the first modern discussion of the arithmetical triangle, so also the word ‘combinatorical’ seems to date from this period. In 1666 the 20-year-old Leibniz wrote his Dissertation on the Combinatorial Art, mainly on permutations and combinations, and greatly influenced by the teachings of Llull. It was a somewhat insubstantial work, even though its title page promised to ‘Demonstrate the existence of God with complete mathematical certainty’. Combinatorics is indeed a powerful subject!    More attractive was the title page of Athanasius Kircher’s Ars Magna Sciendi (The Great Art of Knowledge), with the subtitle Sive Combinatoria. Strongly influenced by Llull, it featured much of religious significance, including the eye of God and a displayed list of divine attributes. Heavily based on Mersenne’s writings, Kircher’s work presented combinatorial problems in a religious context.   Pascal’s treatise on the arithmetical triangle also included an analysis of dice games – a popular topic at the time. Here we see all the unordered patterns of three dice, from a 13th-century manuscript called De Vetula.   Pierre De Montmort’s 1708 Essay Analysing Games of Chance continued this theme and included this splendid illustration of a card game.   And such discussions also appeared in Abraham De Moivre’s 1718 Doctrine of Chances, ‘A Method of Calculating the Probability of Events in Play’.   De Moivre’s book, incidentally, presented a discussion of the derangement problem:  If we permute six letters, what’s the probability that none of them ends up in its initial position?  This problem is frequently couched in more popular terms:   If six letters are randomly placed into six addressed envelopes, what’s the probability that no letter ends up in its correct envelope?    To solve this, De Moivre introduced the so-called ‘method of inclusion-exclusion’, obtaining the answer 265/720, which is remarkably close to 1/e. Indeed, it turns out that the number of derangements of n symbols (permutations in which no symbol is left fixed) is always the integer closest to n!/e.     Probability was indeed a thriving preoccupation at this time, and in his posthumous work Ars Conjectandi (The Art of Conjecturing), published 300 years ago this year, Jakob Bernoulli presented his celebrated ‘law of large numbers’.    This work also introduced the so-called Bernoulli numbers of number theory, although the first eleven of them had actually been studied a century earlier by Johann Faulharber. If you add together the first n squares, or the first n cubes, or fourth powers, etc., you obtain these formulas (where integral signs correspond to our sigmas). The coefficients of n that appear on the right are the Bernoulli numbers – though one of them is incorrect. In the penultimate line, −1/12 should be −3/20.  PART II We now move to Part II of this talk, where we present a selection of topics from more ‘modern’ combinatorics. Several of these were initiated by the 18th-century mathematician Leonhard Euler.       Perhaps Euler’s best-known combinatorial achievement was to solve the Königsberg bridges problem. The medieval city of Königsberg consisted of four land areas (one of them an island), linked by seven bridges. The problem was to find a walk that crosses each bridge exactly once.     Euler’s first innovation was to realize that this is a topological problem – that is, a geometry problem that involves no ‘metrical’ ideas such as distance and angle. He then realized that the answer depends on whether the numbers of bridges emerging from the land areas are even or odd, and produced the following rules:   If the number of bridges is even for all areas, then the journey is possible, starting from any area.  If the number of bridges is odd for exactly two areas, then the journey is possible, starting in one area and ending in the other. If the number of bridges is odd for more than two areas, then such a journey is impossible – so the Königsberg problem has no solution because here the numbers of bridges are 5 for A, 3 for B, 3 for C, and 3 for D – all odd numbers. Note that Euler did not draw the graph diagram that we now use to solve the bridges problem.    A problem that only gradually emerged as related to this one was that of drawing a given diagram without lifting one’s pen from the paper or repeating any line. For example, this diagram can be so drawn: since the only points with an odd number of emerging lines are those at the two ends, a drawing can be made, starting at one end and ending at the other. Incidentally, Listing was the first to coin the word ‘topology’ (in a letter to his schoolteacher) and was also the first to invent the Möbius strip, six months before Möbius did.   Another type of route-tracing problem was the Icosian game, devised by the Irish mathematician William Rowan Hamilton in connection with his invention of quaternions. Here the aim is to visit all twenty vertices of a dodecahedron exactly once and return to our starting point: we can obtain a solution by visiting the places in alphabetical order. The vertices were meant to represent places (such as B for Brussels, C for Canton, up to Z for Zanzibar), and a solution corresponded to A Voyage Around the World.  Yet another recreation was the knight’s tour problem, in which a knight follows a succession of knight’s moves in such a way as to visit every square of the chessboard and return to its starting point, as shown here. Although this problem was many centuries old, Euler was the first to analyze it mathematically.    Incidentally, this knight’s tour is particularly interesting.  If you number the squares 1, 2, 3, as you go, up to 64, the pattern of numbers that you get has the property that every row and column has the same sun: 260. The diagonals don’t work, so it’s a semi-magic square.   Euler was also responsible for introducing the ‘polyhedron formula’. If a polyhedron, such as a cube, has F faces, V vertices (or corners), and E edges, then    F + V = E + 2; for example, a cube has 6 faces, 8 vertices, and 12 edges, and 6 + 8 = 12 + 2. Here, in a 1750 letter from Euler to Christian Goldbach, is the first appearance of the formula, in the form H + S = A + 2: H = hedrae (faces), S = solid angles (vertices), and A = acies (edges). Surprisingly, Euler was the first to introduce the concept of an ‘edge’, which had never featured in earlier polyhedron studies, by the ancient Greeks and the astronomer Kepler, for example.    A counting problem from the 1850s involved trees and chemical molecules. The theory of chemical valency had just emerged, and the question arose as to how many molecules have a given chemical formula, such as C4H10 for the two shown here with four carbon atoms and ten hydrogen ones. Such molecules take the form of ‘trees’ which are diagrams without any cycles in them, such as these trees with six vertices.    Successful attempts to count trees and molecules were made by the English mathematician Arthur Cayley, and also by his friend James Joseph Sylvester. Here are Sylvester’s chemical trees, in an 1878 article based on his inaugural lecture as the first Professor of Mathematics at the newly founded Johns Hopkins University in Baltimore. It was at this time that Sylvester introduced the word graph, in the sense of graph theory.   A different type of combinatorial problem, also from the mid-19th century, concerns block designs – systematic arrangements of objects into blocks – with later applications to agricultural experiments, and the planting of fields with several types of grain to be compared.    The original problem, a recreational one, was devised by the Lancashire clergyman Thomas Kirkman, and appeared in the 1850 edition of the Lady’s and Gentleman’s Diary, designed for ‘students in mathematics’ and all ‘persons engaged in that delightful pursuit’.   Kirkman’s problem, which came to be known as the ‘schoolgirls problem’, was this.    Fifteen young ladies in a school walk out three abreast for seven days in succession: it is required to arrange them daily, so that no two shall walk twice abreast.    A solution, shown here, was presented in the following year: notice that if you select any two schoolgirls, such as 6 and 11, they appear together just once – in this case, on Friday.    A very ancient problem involves magic squares. According to legend, Emperor Yu was standing on the banks of the river Lo, a tributary of the Yellow River, when a sacred turtle emerged from the river with the numbers 1 to 9 on its back. This square arrangement, called the Lo-shu, has the ‘magic’ property that the sum of the numbers in any row, any column, or either of the two main diagonals, is the same, 15.  Over the centuries this arrangement came to acquire great religious and mystic significance, and many complicated magic squares were constructed.    Later, several Chinese mathematicians created interesting magic squares. On the right is an example by Yang Hui, who published the Chinese arithmetical triangle you saw earlier. His magic square of size 9 splits up into nine smaller squares of size 3, each of which is itself a magic square.     Magic squares appear all over the place. Here’s an Arabic one of size 6, found in Xian in modern China.    Leonhard Euler was also interested in magic squares, and showed how to construct them from ‘latin squares’. A latin square is a square array of symbols arranged so that every symbol appears just once in each row and each column. Here are latin squares of sizes 3, 4, and 5, taken from various sources.       More complicated are these two latin squares of size 7. The one on the left is from an Arabic text by al-Buni, while on the right is a window at Gonville and Caius College, Cambridge, commemorating the statistician R. A. Fisher, a pioneer in the use of combinatorial designs in agricultural experiments.   A sudoku puzzle concerns the completion of a partially filled latin square of size 9 in which each of the nine main blocks of size 3 must contain all the numbers from 1 to 9. Such puzzles are said to date from the late 1970s, but sudoku designs were used years earlier in the design of agricultural experiments. Here’s an even earlier puzzle from the 1890s, in which the challenge is to fill in each empty square with the numbers from 1 to 9, so as to yield a latin square. Pleasingly, the published solution, described as a ‘diabolical magic square’, turns out to be a sudoku design.   An important concept is that of a pair of orthogonal latin squares. A 17th-century challenge, due to Bachet de Méziriac and known as the card puzzle, asks us to arrange the 16 court cards in a square array so that the four suits (diamonds, hearts, spades, and clubs) form a latin square, as do the four values (Ace, King, Queen, and Jack). Such pairs of latin squares are called orthogonal: each possible pairing of a suit and a value occurs just once in the pattern.   It was Euler who coined the term latin square.  In a 1782 paper written in French (instead of his usual Latin) he investigated their properties and presented methods for constructing them. He also posed his ‘36 officers’ problem:   Arrange thirty-six officers, of six different ranks and from six different regiments, in a square array so that each row and column includes officers of all six ranks and all six regiments.   He was thus asking for a pair of 6 × 6 orthogonal latin squares.  Euler couldn’t solve this problem and believed it to be impossible. He knew how to construct pairs of orthogonal latin squares of most sizes, but conjectured that they cannot exist for latin squares of sizes 6 (the officers’ problem), 10, 14, 18, and so on, increasing by 4 each time.    Euler was indeed correct that there’s no pair of orthogonal latin squares of side 6 (a fact not proved until 1900), but was spectacularly wrong about the rest. In 1959 three combinatorialists, Bose and Shrikhande from India, and Parker from the US, later called ‘Euler’s spoilers’, surprised the world by proving that pairs of orthogonal latin squares exist for ALL of these other sizes, a result that even made the front page of the New York Times.    The subject of square patterns can be truly amazing – here’s one of my favourite examples, designed by Benjamin Franklin. In this pattern of size 16 the numbers in every row and every column have the same sum, 2056, while every half-row and every half-column adds up to exactly half this sum, 1028. Moreover, if you cut a 4 × 4 hole in a piece of cardboard and lay it anywhere over this pattern, the sixteen numbers that show through also add up to 2056.  Finally, if from any diagram on the right you select any colour, then the sixteen numbers in the V-shape of that colour add up to 2056. Let me make some concluding remarks. For many years mathematicians did not take combinatorial mathematics seriously. But things have changed. Combinatorial arguments are now used throughout mathematics, in algebra, in topology, and in a wide range of applications, while most universities regularly teach combinatorial topics as part of their mathematics and computer science curricula.    The growth of the subject has been greatly helped by major figures such as Paul Erdős, who travelled the world working with people on combinatorial problems of great interest and difficulty, while recent Presidents of the American Mathematical Society have included George Andrews (one of our authors) and Ron Graham (who wrote the Foreword).  When the 1998 film Good Will Hunting featured a famous MIT mathematician who had apparently won a Fields Medal for a combinatorial problem – an exercise on trees, shown here, that I’ve sometimes set to students as a homework problem – many mathematicians found that unbelievable.    But ten years later life followed art when Fields Medals were awarded to Tim Gowers  and Richard Borcherds for their work, much of which was in combinatorics – and just last year, the Abel Prize for a lifetime’s contributions to mathematics was awarded to a combinatorialist, the Hungarian Endre Szemerédi. The mathematical world is at last taking note. Finally, this hasn’t been the first launch of our book. Last month my co-editor John Watkins and I held another one in Colorado, with a magnificent cake featuring the cover of our book. But don’t be misled – combinatorics can be a very difficult subject – it’s certainly not a piece of cake!  

    © Professor Robin Wilson 2013