Combinatorics in the Middle Ages

views updated

Combinatorics in the Middle Ages

Overview

Combinatorics is concerned with defining a finite or discrete mathematical system, and then solving problems relating to the selection and arrangement of numbers or items within that system. A typical problem in combinatorics is to determine the number of possible configurations of a particular type, such as the values that could occur when rolling a pair of dice. Combinatorics has many applications in probability as well as in algebra and geometry.

Background

Combinatorics is an ancient branch of mathematics. In the Rhind Papyrus of Egypt, one of the oldest mathematical texts in existence, the 79th problem asks, "There are seven houses; in each house there are seven cats; each cat kills seven mice; each mouse has eaten seven grains of barley; each grain would have produced seven hekat. What is the sum of all the enumerated things?"

The Rhind Papyrus was copied by a scribe named Ahmes in about 1550 b.c. from a text that was about 300 years old at that time. A similar problem was preserved in the English nursery rhyme that begins, "When I was going to St. Ives, I met a man with seven wives."

One of the first recorded combinatorial constructs was the magic square. The magic square is an array of numbers in which the rows, columns, and diagonals all add up to the same sum. Magic squares appear in the Chinese book the I Ching, which dates from the twelfth century b.c.

Impact

Medieval scholars were fascinated by magic squares. Like the Chinese, Arab mathematicians who worked on them, including al-Buni, invested them with mystical significance. However, when the constructs were introduced to the West, in a text written by the Greek Byzantine scholar Manuel Moschopoulos in 1300, they were presented as pure mathematics.

Jewish mathematicians of the Middle Ages, including Rabbi Abraham ben Meir ibn Ezra (1092-1167), who lived in Muslim Spain, and Levi ben Gershom (1288-1344) of France, were particularly interested in combinatorial problems. The Hebrew mathematical tradition arose in the area of modern Israel around the eighth century, influenced by contacts with Islamic scholars and the innovations they brought from the Hindus, and influencing Arab mathematicians in turn. It spread with Jewish merchants and immigrant populations into Arab, Persian, Turkish, and Christian territories. Together, Jews and Arabs helped to bring the Hindu number system (what we often call "Arabic numerals") into Europe. At the time, the West was still laboring under the awkward Roman numeral system, which made arithmetic calculations difficult.

An important feature of Hebrew mathematics was its early understanding of variation in such values as the size of bricks and the positions of boundaries. Counting the number of possibilities in a situation, and weighing their likelihood, was also important in deciding legal questions in accordance with the complicated Talmudic code. This led to a tendency to apply combinatorics to statistical and probabilistic problems.

While it is often difficult to determine who originated specific mathematical methods, it may be established that the techniques are known in a particular community when they appear in the writings of scholars there. In India, the Jaina school of mathematics, established in the first century b.c., included a subject calledVikalpa, or permutations and combinations, in its course of study.

The Indian mathematician Bhaskara (1114-1185?) included a number of algebraic and combinatorial problems in his book Lilivati ("The Graceful," said to be named for his daughter). Often the problems were couched as diversions, such as riddles about the number of geese in a flock or swans in a lake. One was to figure out the number of combinations of stressed and unstressed syllables that are possible in a six-syllable verse.

An important algebraic application of combinatorics, for which rules were given in Lilivati, is the computation of the binomial coefficients. The binomial coefficients are those of the individual algebraic terms when the expression (a + b)ⁿ is multiplied out. For example, (a + b)² is equal to a² + 2ab + b². The coefficients in this expression are 1, 2, 1.

Binomial coefficients are often written in a triangular array called "Pascal's Triangle." The construct was named for the famous French mathematician and scientist Blaise Pascal (1623-1662), who developed many of the founding principles of probability theory. Its peak is a 1, because (a + b)⁰ is equal to 1. The next row has two 1s, because (a + b)¹ = a + b; both coefficients are equal to 1. Each succeeding row is made up of the next set of coefficients, derived from writing 1s on each side, and computing each inner coefficient by adding the two numbers directly above it.

Despite the name, Pascal was not the first to use a triangular figure to compute binomial coefficients. The same figure appears in an algebra text by Ibn Yahya al-Maghribi al-Samawal (1130?-1180?), a Jew (and later convert to Islam) in Baghdad, who, in turn, attributed it to al-Karaji (953-1029?). It was known to the Persian philosopher Nasir ad-Din al-Tusi (1201-1274) by 1265, and also had been developed in China, probably well before its appearance in the work of Chu Shih-chieh (1270?-1330?) in 1303.

Combinatorial problems have often been associated with games and puzzles. The Italian mathematician Leonardo Fibonacci (1170?-1250?) is most famous for devising a series in which each number is the sum of the previous two: 1, 1, 2, 3, 5, 8, . . . However, he is also credited with the "Rabbit Problem" of combinatorics. This puzzle requires the computation of the number of descendents of a pair of rabbits. According to the problem, the initial pair is left in an enclosure to produce a pair of offspring a month, which are assumed to become similarly fertile when they are two months old. In 1256 the Islamic mathematician Ibn Kallikan constructed a puzzle in which a chess board had 1 grain of wheat on the first square, two on the second, four on the third, eight on the fourth, and so on.

It was centuries before combinatorial techniques were widely used in the West. Pascal and his contemporary Pierre de Fermat (1601-1665) employed combinatorics to develop probability theory. The Swiss mathematician Leonhard Euler (1707-1783) solved the famous Königsberg Bridge problem by proving it had no solution. The river town of Königsberg stretched across two islands and the opposite banks of the river, and seven bridges connected these four landmasses. The object of the problem was to cross all seven bridges without having to cross any of them more than once, starting and ending from the same point. Euler showed that for such a journey to be possible, each landmass would have to have an even number of bridges connected to it. Similar recreational problems in combinatorics were circulated during the nineteenth century.

Around 1900, combinatorial theory contributed to graph theory, symbolic logic, and topology. The first comprehensive textbooks in the field, such as Eugen Netto's (1848-1919) Lehrbuch der Combinatorik, were written at about this time. Combinatorics became more prominent in mathematics in the twentieth century, with the development of computing technologies. Combinatorial problems arose in the areas of computer design, information theory, and coding. Graph theory has applications in designing and analyzing transportation and communication networks and other systems. However, the field still exists as a collection of discrete problems and methods, and mathematicians continue to search for a theory or set of principles to unify them.

SHERRI CHASIN CALVO