History of combinatorics

Earliest records

The earliest recorded use of combinatorial techniques comes from problem 79 of the Rhind papyrus, which dates to the 16th century BC. The problem concerns a certain geometric series, and has similarities to Fibonacci's problem of counting the number of compositions of 1s and 2s that sum to a given total.

In Greece, Plutarch wrote that Xenocrates of Chalcedon (396–314 BC) discovered the number of different syllables possible in the Greek language. This would have been the first attempt on record to solve a difficult problem in permutations and combinations. The claim, however, is implausible: this is one of the few mentions of combinatorics in Greece, and the number they found, 1.002 × 10 ¹², seems too round to be more than a guess.

Later, an argument between Chrysippus (3rd century BC) and Hipparchus (2nd century BC) of a rather delicate enumerative problem, which was later shown to be related to Schröder–Hipparchus numbers, is mentioned. There is also evidence that in the Ostomachion, Archimedes (3rd century BC) considered the configurations of a tiling puzzle, while some combinatorial interests may have been present in lost works of Apollonius.

In India, the Bhagavati Sutra had the first mention of a combinatorics problem; the problem asked how many possible combinations of tastes were possible from selecting tastes in ones, twos, threes, etc. from a selection of six different tastes (sweet, pungent, astringent, sour, salt, and bitter). The Bhagavati is also the first text to mention the choose function. In the second century BC, Pingala included an enumeration problem in the Chanda Sutra (also Chandahsutra) which asked how many ways a six-syllable meter could be made from short and long notes. Pingala found the number of meters that had ${\displaystyle n}$ long notes and ${\displaystyle k}$ short notes; this is equivalent to finding the binomial coefficients.

The ideas of the Bhagavati were generalized by the Indian mathematician Mahavira in 850 AD, and Pingala's work on prosody was expanded by Bhāskara II 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 describes a hexagram as a permutation with repetitions of six lines where each line can be one of two states: solid or dashed. In describing hexagrams in this fashion they determine that there are ${\displaystyle 2^6=64}$ possible hexagrams. A Chinese 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, around 100 AD they solved the Lo Shu Square which is the combinatorial design problem of the normal magic square of order three. Magic squares remained an interest of China, and they began to generalize their original ${\displaystyle 3\times 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. The work of Hindus influenced Arabs as seen in the work of al-Khalil ibn Ahmad who considered the possible arrangements of letters to form syllables. His calculations show an understanding of permutations and combinations. In a passage from the work of Arab mathematician Omar Khayyam that dates to around 1100, it is corroborated that the Hindus had knowledge of binomial coefficients, but also that their methods reached the middle east.

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 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 17th century England, campanology provided examples of what is now known as Hamiltonian cycles in certain Cayley graphs on permutations.