History of combinatorics

History of combinatorics is a part of History of mathematics, dedicated to the history of combinatorics and its variations, from antiquity to modern times.

Earliest uses
The appearance of the Fibonacci number five in prosody. There is one way to arrange one beat, two for two, three for three, and five for four beats.

The earliest books about combinatorics are from India[1]. 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[2]. 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[3][4]. 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 [2][5] and Hemacandra in 1100 AD. Bhaskara was the first known person to find the generalised choice function, although Brahmagupta may have known earlier[6]. 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[3].

A hexagram

While India was the first nation to publish results on Combinatorics, there were discoveries by other nations on similar topics. The earliest known connection to Combinatorics comes from the Rhind papyrus, problem 79, for the implementation of a geometric series. The next milestone is held by the I Ching. The book is about what different hexagrams mean, and to do this they needed 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 6 = 64 hexagrams. A monk also may have counted the number of configurations to a game similar to Go around 700 AD[7]. Although China had relatively few advancements in enumerative combinatorics, they solved a combinatorial design problem, the magic square, around 100 AD[6].

In Greece, Plutarch wrote that the 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 12 also seems too round to be more than a guess[7][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[6]. The Middle East also learned about binomial coefficients from Indian work, and found the connection to polynomial expansion[9].

The philosopher and astronomer Rabbi Abraham ibn Ezra (c. 1140) 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.[10] 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.[11]

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[12][13]. 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[6]. 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[6]. Together with Leibniz and his ideas about partitions in the 17th century[14], they are considered the founders of modern combinatorics.

Both Pascal and Leibniz understood that algebra and combinatorics corresponded (aka, binomial expansion was equivalent to the choice function). This was expanded by De Moivre, who found the expansion of a multinomial[15]. 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[6]. He managed to approximate the binomial coefficients and factorial. Finally, he found a closed form for the Fibonacci numbers by inventing generating functions[16][17].

In the 18th century, Euler worked on problems of combinatorics. In addition to working on several problems of probability which link 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[18].

History of Combinatorics

Notes

1. ^ [1]
2. ^ a b "India". http://binomial.csueastbay.edu/India.html. Retrieved 2008-03-05.
3. ^ a b Hall, Rachel (2005-02-16) (PDF). Math for Poets and Drummers-The Mathematics of Meter. http://www.sju.edu/~rhall/Rhythms/poets.pdf. Retrieved 2008-03-05.
4. ^ Kulkarni, Amba. Recursion and Combinatorial Mathematics in Chandashāstra. http://arxiv.org/abs/math/0703658. Retrieved 2008-03-04.
5. ^ Bhaskara. "The Lilavati of Bhaskara". Brown University. http://www.brown.edu/Departments/History_Mathematics/lilavati.html. Retrieved 2008-03-06.
6. ^ a b c d e f Biggs, Norman; Keith Lloyd, Robin Wilson (1995). "44". in Ronald Grahm, Martin Grötschel, László Lovász (Google book). Handbook of Combinatorics. MIT Press. pp. 2163–2188. ISBN 0262571722. http://books.google.com/?id=kfiv_-l2KyQC. Retrieved 2008-03-08.
7. ^ a b Dieudonné, J.. "The Rhind/Ahmes Papyrus - Mathematics and the Liberal Arts". Historia Math. Truman State University. http://mtcs.truman.edu/~thammond/history/RhindPapyrus.html. Retrieved 2008-03-06.
8. ^ Gow, James (1968). A Short History of Greek Mathematics. AMS Bookstore. pp. 71. ISBN 0-828-40218-3. http://books.google.com/?id=68sYLQa9FuQC&printsec=frontcover.
9. ^ "Middle East". http://binomial.csueastbay.edu/MidEast.html. Retrieved 2008-03-08.
10. ^ History of Combinatorics, chapter in a textbook.
11. ^ Arthur T. White, ”Ringing the Cosets,” Amer. Math. Monthly 94 (1987), no. 8, 721-746; Arthur T. White, ”Fabian Stedman: The First Group Theorist?,” Amer. Math. Monthly 103 (1996), no. 9, 771-778.
12. ^ Devlin, Keith (10 2002). "The 800th birthday of the book that brought numbers to the west". Devlin's Angle. http://www.maa.org/devlin/devlin_10_02.html. Retrieved 2008-03-08.
13. ^ "Fibonacci Sequence- History". Net Industries. 2008. http://science.jrank.org/pages/2705/Fibonacci-Sequence-History.html. Retrieved 2008-03-08.
14. ^ Dickson, Leonard (2005) [1919]. "Chapter III". Diophantine Analysis. History of the Theory of Numbers. Mineola, New York: Dover Publications, Inc.. pp. 101. ISBN 0-486-44233-0.
15. ^ Hodgson, James; William Derham; Richard Mead (1708) (Google book). Miscellanea Curiosa. Volume II. pp. 183–191. http://books.google.com/?id=sr04AAAAMAAJ&printsec=titlepage. Retrieved 2008-03-08.
16. ^ O'Connor, John; Edmund Robertson (06 2004). "Abraham de Moivre". The MacTutor History of Mathematics archive. http://www-history.mcs.st-andrews.ac.uk/Biographies/De_Moivre.html. Retrieved 2008-03-09.
17. ^ Pang, Jong-Shi; Olvi Mangasarian (1999). "10.6 Generating Function". in Jong-Shi Pang (Google book). Computational Optimisation. Volume 1. Netherlands: Kluwer Academic Publishers. pp. 182–183. ISBN 0-792-38480-6. http://books.google.com/?id=kJa15IMxAoIC&printsec=frontcover#PPA5,M1. Retrieved 2008-03-09.
18. ^ "Combinatorics and probability". http://math.dartmouth.edu/~euler/. Retrieved 2008-03-08.

References

* 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.