History of combinatorics

The history of combinatorics is an area of study within the history of mathematics. Its focus ranges from antiquity to modern times.

Earliest records

The earliest known connection to combinatorics comes from the Rhind papyrus, problem 79, for the implementation of a geometric series.

A Jain text, the Bhagabati Sutra, had the first mention of a combinatorics problem; it asked how many ways one could take six tastes one, two, or three tastes at a time. The Bhagabati Sutra was written around 300 BC, and was the first book to mention the choose function.^[1] The next ideas of Combinatorics came from Pingala, who was interested in prosody. Specifically, he wanted to know how many ways a six-syllable meter could be made from short and long notes. He wrote this problem in the Chanda sutra (also Chandahsutra) in the second century BC.^[2][3] In addition, he also found the number of meters that had n long notes and k short notes, which is equivalent to finding the binomial coefficients.

The ideas of the Bhagabati were generalised by the Indian mathematician Mahavira in 850 AD, and Pingala's work on prosody was expanded by Bhaskara^[1][4] and Hemacandra in 1100 AD. Bhaskara was the first known person to find the generalised choice function, although Brahmagupta may have known earlier.^[5] Hemacandra asked how many meters existed of a certain length if a long note was considered to be twice as long as a short note, which is equivalent to finding the Fibonacci numbers.^[2]

The ancient Chinese book of divination, I Ching, is about what different hexagrams mean, and to do this one needs to know how many possible hexagrams there were. Since each hexagram is a permutation with repetitions of six lines, where each line can be one of two states, solid or dashed, combinatorics yields the result that there are 2 ⁶ = 64 hexagrams. A monk also may have counted the number of configurations to a game similar to Go around 700 AD.^[6] Although China had relatively few advancements in enumerative combinatorics, they solved a combinatorial design problem, the normal magic square of order three, around 100 AD, in the Lo Shu Square.^[5][7]

In Greece, Plutarch wrote that Xenocrates discovered the number of different syllables possible in the Greek language. This, however, is unlikely because this is one of the few mentions of Combinatorics in Greece. The number they found, 1.002 × 10 ¹² also seems too round to be more than a guess.^[6][8]

Magic squares remained an interest of China, and they began to generalise their original 3×3 square between 900 and 1300 AD. China corresponded with the Middle East about this problem in the 13th century.^[5] The Middle East also learned about binomial coefficients from Indian work, and found the connection to polynomial expansion.^[9]

Abū Bakr ibn Muḥammad ibn al Ḥusayn Al-Karaji (c.953-1029) wrote on the binomial theorem and Pascal's triangle. In a now lost work known only from subsequent quotation by al-Samaw'al, Al-Karaji introduced the idea of argument by mathematical induction.

The philosopher and astronomer Rabbi Abraham ibn Ezra (c. 1140) counted the permutations with repetitions in vocalization of Divine Name.^[10] He also established the symmetry of binomial coefficients, while a closed formula was obtained later by the talmudist and mathematician Levi ben Gerson (better known as Gersonides), in 1321.^[11] The arithmetical triangle— a graphical diagram showing relationships among the binomial coefficients— was presented by mathematicians in treatises dating as far back as the 10th century, and would eventually become known as Pascal's triangle. Later, in Medieval England, campanology provided examples of what is now known as Hamiltonian cycles in certain Cayley graphs on permutations.^[12]

Combinatorics in the West

Combinatorics came to Europe in the 13th century through two mathematicians, Leonardo Fibonacci and Jordanus de Nemore. Fibonacci's Liber Abaci introduced many of the Arabian and Indian ideas to Europe, including that of the Fibonacci numbers.^[13][14] Jordanus was the first person to arrange the binomial coefficients in a triangle, as he did in proposition 70 of De Arithmetica. This was also done in the Middle East in 1265, and China around 1300.^[5] Today, this triangle is known as Pascal's triangle.

Pascal's contribution to the triangle that bears his name comes from his work on formal proofs about it, in addition to his connection between it and probability.^[5] Together with Leibniz and his ideas about partitions in the 17th century,^[15] they are considered the founders of modern combinatorics.^[16]

Both Pascal and Leibniz understood that algebra and combinatorics corresponded (binomial expansion was equivalent to the choice function). This was expanded by De Moivre, who found the expansion of a multinomial.^[17] De Moivre also found the formula for derangements using the principle of inclusion-exclusion, a method different from Nikolaus Bernoulli, who had found them previously.^[5] He managed to approximate the binomial coefficients and factorial. Finally, he found a closed form for the Fibonacci numbers by inventing generating functions.^[18][19]

In the 18th century, Euler worked on problems of combinatorics. In addition to working on several problems of probability which is linked to combinatorics, he worked on the knights tour, Graeco-Latin square, Eulerian numbers, and others. He also invented graph theory by solving the Seven Bridges of Königsberg problem, which also led to the formation of topology. Finally, he broke ground with partitions by the use of generating functions.^[20]

Notes

References

• N.L. Biggs, The roots of combinatorics, Historia Mathematica 6 (1979), 109-136.
• Katz, Victor J. (1998). A History of Mathematics: An Introduction, 2nd Edition. Addison-Wesley Education Publishers. ISBN 0-321-01618-1.
• O'Connor, John J. and Robertson, Edmund F. (1999–2004). MacTutor History of Mathematics archive. St Andrews University.
• Rashed, R. (1994). The development of Arabic mathematics: between arithmetic and algebra. London.
• Wilson, R. and Watkins, J. (2013). Combinatorics: Ancient & Modern. Oxford.