This article may require cleanup to meet Wikipedia's quality standards. Please improve this article if you can. (November 2009)

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

[edit] 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 ⁶ = 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 ¹² 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]

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

[edit] Notes

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