History of Combinatorics - Combinatorics in The West

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. 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. 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. Together with Leibniz and his ideas about partitions in the 17th century, 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. 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. He managed to approximate the binomial coefficients and factorial. Finally, he found a closed form for the Fibonacci numbers by inventing generating functions.

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.