History of Combinatorics - Earliest Records

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. 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. 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 and Hemacandra in 1100 AD. Bhaskara was the first known person to find the generalised choice function, although Brahmagupta may have known earlier. 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.

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. Although China had relatively few advancements in enumerative combinatorics, they solved a combinatorial design problem, the magic square, around 100 AD.

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.

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. The Middle East also learned about binomial coefficients from Indian work, and found the connection to polynomial expansion.

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