### Combinatorics: Ancient and Modern

01Jan15

Happy new year! As a way of celebrating (?) or making up for procrastinating (more likely), I have finished a long-overdue book review for The Mathematical Intelligencer. The book is called Combinatorics: Ancient & Modern.

This book, a collection of 16 chapters by different authors, spans the history of combinatorics from the dawn of civilization to present day. It is a cohesive book: it does not suffer the typical problem of compilations where the tone is inconsistent from chapter to chapter. Rather, it is consistently easy to read, well-illustrated, and it strikes a good balance between technical information and historical details.

The book’s organization is flexible, which helps each chapter speak through. The first third of the book deals with mathematics organized by culture and place of origin. This is followed by several chapters organized by time period and then chapters on particular topics within combinatorics (e.g., partitions).

I was amazed at the sheer diversity in applications of combinatorics throughout its early history. People studied ways to choose, arrange and combine Chinese syllables for divination, syllables in Indian, Latin and Greek poetry, pronunciation of Arabic words, Hebrew letters for seating charts, note sequences in songs, voicings of parts to singers, tastes of medicine, dice outcomes for gambling, virtues & vices, splitting inheritance, partitions of incense smells, humors in medicine, rhythm patterns, and chemical combinations; this is in addition to more well-known applications of combinatorics like supernatural protection (magic squares) and sheep farming (mutually orthogonal latin squares).

Two of the early applications I found particularly interesting. One from Jewish culture was the enumeration of words of a given length, with the motivation being that everything God made has a name, and therefore counting the number of names gives a bound on how many things God made. Another is in the introductory chapter. In 1615, Bauhuis wrote a poem which, in 1617, Puteanus tried to permute in all possible ways subject to certain pronunciation constraints. Through the years Leibniz, Prestis, Wallis, Jacob Bernoulli and the Mathematical Gazette all tried to determine the correct number of possibilities; Knuth reports that Bernoulli, who used a careful exhaustive backtracking algorithm, was the only one who was correct. Quoting Bernoulli,

Even the wisest and most prudent people often suffer from what Logicians call insufficient enumeration of cases.

Other algorithmic ideas are sprinkled throughout the book. The history of Indian combinatorics includes the ideas of binary encoding, repeated squaring, and error-correction (memorizing Vedas both backwards and forwards). In the middle of the book, after a wonderful visual proof of the pentagonal number theorem, it is shown that the theorem is not just a neat fact, but also leads to a faster way to compute the partition numbers. And towards the end of the book, we find that computer-based proofs were necessary to solve several longstanding open problems: the 4-color theorem posed in 1852 by De Morgan/Hamilton and solved in 1976 by Appel and Haken; the existence of a resolvable 15-point Steiner triple system, posed in 1850 by Sylvester and solved affirmatively in 1971 by Dennison; and the existence of a 10-point projective plane, open since Veblen’s early work in 1904 and resolved negatively by Lam in 1988. (Though, computers did not solve the longest-standing open problem in the book, Parker’s construction in 1959 of order-10 orthogonal latin squares, conjectured by Euler in 1782 not to exist.)

Another theme that recurs as the book works its way through the annals of history is mis-attribution. For example, “Pascal’s Triangle” was written about by other authors in North Africa and Europe hundreds of years before him, and in Asia over a thousand years before that. Chapter 7 hypothesizes that Pascal learned it from Mersenne, who may have learned it from Cardano and Tartaglia. However, Pascal did publicize it well, writing the first full book on the topic. And having died three years before its publication, he was not in the best position to correct the subsequent assumption (made in writing by de Montimort) that he was the originator.

The middle ages brought other new ideas. One, the study of gambling and probability, mentioned several times in the middle part of the book. Two, the frontispiece, the decorative front page of a book. Throughout, Combinatorics: Ancient & Modern has high quality illustrations, scans and diagrams, and the many frontispieces reproduced in the book are no exception. I particularly like page 140, showing a wonderfully busy scene including an angel carrying an icosahedron (the table of contents) from Caramuel’s 1670 Old and New Two-Headed Mathematics, and page 290, with at least a dozen fonts adorning Nicholson’s 1818 Essays on the Combinatorial Analysis.

The last third of the book is largely comprised of histories/surveys of individual topics in modern combinatorics: partitions, designs, algebraic combinatorics, extremal combinatorics, and graphs. Chapter 12, on enumeration and algebraic combinatorics, included an intriguing story and equally intriguing mathematics. J.~Howard Redfield trained originally as a civil engineer and linguist, but did pioneering outsider work in 1927 on using group theory in enumerative combinatorics. There is a brief explanation of his methods, illustrated by the problem of counting arrangements of 4 white and 4 black balls at the corners of a cube, modulo rotations. It is very interesting and leaves me wanting a slightly more detailed explanation: I have never seen the number 7 obtained in such a mysterious way!

Chapter 13, on combinatorial set theory and extremal combinatorics, presents a very nice history while also being thought-provoking. For example, it discussed Schur’s precursor work to Ramsey theory, and how Schur used it to give a nicer proof of Dickson’s result that Fermat’s Last Theorem does not hold if you take the integers modulo a prime. The only fault that I could draw with the book is that it would be nice to include more proofs: Schur’s theorem and its corollary, for instance, have beautiful short proofs but they are not given. Regardless, this chapter (like the rest) surveys history nicely, ranging from a 1662 textbook use of the pigeonhole principle to show that two people in Paris have the same number of hairs on their head, and continuing its discussion to the work of Erdős and his collaborators.

Overall, I recommend the book for anyone with interests in mathematics, culture, or history. The authors do a good job of presenting the mathematics in an authentic way while not assuming the reader has any specific background, and the variety of topics means there are a lot of opportunities to engage your interests. The book is a light read, though still mathematical, and can inspire further discovery. For me, the presentation of each culture separately was very novel and opened my eyes up to new ways of motivating combinatorics: it may be that for future assignments, rather than asking students about arranging cities in a tour or selecting outfits from a given set of clothing, that I will ask them to permute the words of a poem.

Advertisements

#### 2 Responses to “Combinatorics: Ancient and Modern”

1. I think you are too used to tex – the para starting with % stayed in the text.
Btw, I even have a paper with a sentence starting with % – the typographer thought it was an error that it didn’t show and put a \ in front of the %…

• Thanks! The good news is, when the robots take over, I’ve figured out a way we can still send secret messages to one another.

• ## Subscription

Instead of using RSS, enter an email address to get new post notifications:

• I'm a lecturer in computer science, originally from Canada, who also loves math.

Want to learn Python? Click here!

This blog has some topics which might interest your stomach.

A great metaphor by Claire Mathieu

• Advertisements