History of combinatorics

From Wikipedia, the free encyclopedia
Jump to: navigation, search

The history of combinatorics is an area of study within the history of mathematics, dedicated to the history of combinatorics and its variations, from antiquity to modern times.

Earliest records[edit]

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 6 = 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 magic square, around 100 AD.[5]

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.[6][7]

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.[8]

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. (See http://en.wikipedia.org/wiki/Al-Karaji)

The philosopher and astronomer Rabbi Abraham ibn Ezra (c. 1140) counted the permutations with repetitions in vocalization of Divine Name.[9] 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.[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[edit]

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.[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,[14] they are considered the founders of modern combinatorics.[15]

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.[16] 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.[17][18]

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.[19]

Notes[edit]

  1. ^ a b "India". Retrieved 2008-03-05. 
  2. ^ a b Hall, Rachel (2005-02-16). Math for Poets and Drummers-The Mathematics of Meter (PDF). Retrieved 2008-03-05. 
  3. ^ Kulkarni, Amba. Recursion and Combinatorial Mathematics in Chandashāstra. arXiv:math/0703658. 
  4. ^ Bhaskara. "The Lilavati of Bhaskara". Brown University. Archived from the original on 2008-03-25. Retrieved 2008-03-06. 
  5. ^ a b c d e f Biggs, Norman; Keith Lloyd, Robin Wilson (1995). "44" (Google book). In Ronald Grahm, Martin Grötschel, László Lovász. Handbook of Combinatorics. MIT Press. pp. 2163–2188. ISBN 0-262-57172-2. Retrieved 2008-03-08. 
  6. ^ a b Dieudonné, J. "The Rhind/Ahmes Papyrus - Mathematics and the Liberal Arts". Historia Math. Truman State University. Retrieved 2008-03-06. 
  7. ^ Gow, James (1968). A Short History of Greek Mathematics. AMS Bookstore. p. 71. ISBN 0-8284-0218-3. 
  8. ^ "Middle East". Retrieved 2008-03-08. 
  9. ^ The short commentary on Exodus 3:13
  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 (October 2002). "The 800th birthday of the book that brought numbers to the west". Devlin's Angle. Retrieved 2008-03-08. 
  13. ^ "Fibonacci Sequence- History". Net Industries. 2008. Retrieved 2008-03-08. 
  14. ^ Leibniz habilitation thesis De Arte Combinatoria was published as a book in 1666 and reprinted later
  15. ^ Dickson, Leonard (2005) [1919]. "Chapter III". Diophantine Analysis. History of the Theory of Numbers. Mineola, New York: Dover Publications, Inc. p. 101. ISBN 0-486-44233-0. 
  16. ^ Hodgson, James; William Derham; Richard Mead (1708). Miscellanea Curiosa (Google book). Volume II. pp. 183–191. Retrieved 2008-03-08. 
  17. ^ O'Connor, John; Edmund Robertson (June 2004). "Abraham de Moivre". The MacTutor History of Mathematics archive. Retrieved 2008-03-09. 
  18. ^ Pang, Jong-Shi; Olvi Mangasarian (1999). "10.6 Generating Function" (Google book). In Jong-Shi Pang. Computational Optimisation. Volume 1. Netherlands: Kluwer Academic Publishers. pp. 182–183. ISBN 0-7923-8480-6. Retrieved 2008-03-09. 
  19. ^ "Combinatorics and probability". Retrieved 2008-03-08. 

References[edit]

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