History of combinatorics
Encyclopedia
History of mathematics
The area of study known as the history of mathematics is primarily an investigation into the origin of discoveries in mathematics and, to a lesser extent, an investigation into the mathematical methods and notation of the past....
, dedicated to the history
History
History is the discovery, collection, organization, and presentation of information about past events. History can also mean the period of time after writing was invented. Scholars who write about history are called historians...
of combinatorics
Combinatorics
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...
and its variations, from antiquity to modern times.
Earliest uses
The earliest books about combinatorics are from India. A JainJainism
Jainism is an Indian religion that prescribes a path of non-violence towards all living beings. Its philosophy and practice emphasize the necessity of self-effort to move the soul towards divine consciousness and liberation. Any soul that has conquered its own inner enemies and achieved the state...
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
Binomial coefficient
In mathematics, binomial coefficients are a family of positive integers that occur as coefficients in the binomial theorem. They are indexed by two nonnegative integers; the binomial coefficient indexed by n and k is usually written \tbinom nk , and it is the coefficient of the x k term in...
. The next ideas of Combinatorics came from Pingala
Pingala
Pingala is the traditional name of the author of the ' , the earliest known Sanskrit treatise on prosody.Nothing is known about Piṅgala himself...
, 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
Mahavira (mathematician)
Mahavira was a 9th-century Indian Jain mathematician from Gulbarga who asserted that the square root of a negative number did not exist. He gave the sum of a series whose terms are squares of an arithmetical progression and empirical rules for area and perimeter of an ellipse. He was patronised by...
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
Brahmagupta
Brahmagupta was an Indian mathematician and astronomer who wrote many important works on mathematics and astronomy. His best known work is the Brāhmasphuṭasiddhānta , written in 628 in Bhinmal...
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.
I Ching
The I Ching or "Yì Jīng" , also known as the Classic of Changes, Book of Changes and Zhouyi, is one of the oldest of the Chinese classic texts...
. 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 6 = 64 hexagrams. A monk also may have counted the number of configurations to a game similar to Go
Go (board game)
Go , is an ancient board game for two players that originated in China more than 2,000 years ago...
around 700 AD. Although China had relatively few advancements in enumerative combinatorics, they solved a combinatorial design
Combinatorial design
Combinatorial design theory is the part of combinatorial mathematics that deals with the existence and construction of systems of finite sets whose intersections have specified numerical properties....
problem, the magic square
Magic square
In recreational mathematics, a magic square of order n is an arrangement of n2 numbers, usually distinct integers, in a square, such that the n numbers in all rows, all columns, and both diagonals sum to the same constant. A normal magic square contains the integers from 1 to n2...
, around 100 AD.
In Greece, Plutarch
Plutarch
Plutarch then named, on his becoming a Roman citizen, Lucius Mestrius Plutarchus , c. 46 – 120 AD, was a Greek historian, biographer, essayist, and Middle Platonist known primarily for his Parallel Lives and Moralia...
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.
The philosopher and astronomer
Astronomer
An astronomer is a scientist who studies celestial bodies such as planets, stars and galaxies.Historically, astronomy was more concerned with the classification and description of phenomena in the sky, while astrophysics attempted to explain these phenomena and the differences between them using...
Rabbi Abraham ibn Ezra
Abraham ibn Ezra
Rabbi Abraham ben Meir Ibn Ezra was born at Tudela, Navarre in 1089, and died c. 1167, apparently in Calahorra....
(c. 1140) established the symmetry of binomial coefficient
Binomial coefficient
In mathematics, binomial coefficients are a family of positive integers that occur as coefficients in the binomial theorem. They are indexed by two nonnegative integers; the binomial coefficient indexed by n and k is usually written \tbinom nk , and it is the coefficient of the x k term in...
s, while a closed formula was obtained later by the talmudist and mathematician
Mathematician
A mathematician is a person whose primary area of study is the field of mathematics. Mathematicians are concerned with quantity, structure, space, and change....
Levi ben Gerson (better known as Gersonides), in 1321.
The arithmetical triangle— a graphical diagram showing relationships among the binomial coefficient
Binomial coefficient
In mathematics, binomial coefficients are a family of positive integers that occur as coefficients in the binomial theorem. They are indexed by two nonnegative integers; the binomial coefficient indexed by n and k is usually written \tbinom nk , and it is the coefficient of the x k term in...
s— was presented by mathematicians in treatises dating as far back as the 10th century, and would eventually become known as Pascal's triangle
Pascal's triangle
In mathematics, Pascal's triangle is a triangular array of the binomial coefficients in a triangle. It is named after the French mathematician, Blaise Pascal...
. Later, in Medieval England, campanology
Campanology
Campanology is the study of bells. It encompasses the physical realities of bells — how they are cast, tuned and sounded — as well as the various methods devised to perform bell-ringing....
provided examples of what is now known as Hamiltonian cycles in certain Cayley graph
Cayley graph
In mathematics, a Cayley graph, also known as a Cayley colour graph, Cayley diagram, group diagram, or colour group is a graph that encodes the abstract structure of a group. Its definition is suggested by Cayley's theorem and uses a specified, usually finite, set of generators for the group...
s on permutations.
Combinatorics in the West
Combinatorics came to Europe in the 13th century through two mathematicians, Leonardo Fibonacci and Jordanus de Nemore. Fibonacci's Liber AbaciLiber Abaci
Liber Abaci is a historic book on arithmetic by Leonardo of Pisa, known later by his nickname Fibonacci...
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 triangle
In mathematics, Pascal's triangle is a triangular array of the binomial coefficients in a triangle. It is named after the French mathematician, Blaise Pascal...
.
Pascal
Blaise Pascal
Blaise Pascal , was a French mathematician, physicist, inventor, writer and Catholic philosopher. He was a child prodigy who was educated by his father, a tax collector in Rouen...
'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 coefficient
Binomial coefficient
In mathematics, binomial coefficients are a family of positive integers that occur as coefficients in the binomial theorem. They are indexed by two nonnegative integers; the binomial coefficient indexed by n and k is usually written \tbinom nk , and it is the coefficient of the x k term in...
s and factorial
Stirling's approximation
In mathematics, Stirling's approximation is an approximation for large factorials. It is named after James Stirling.The formula as typically used in applications is\ln n! = n\ln n - n +O\...
. 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
Graeco-Latin square
In mathematics, a Graeco-Latin square or Euler square or orthogonal Latin squares of order n over two sets S and T, each consisting of n symbols, is an n×n arrangement of cells, each cell containing an ordered pair , where s is in S and t is in T, such that every row and every column contains...
, Eulerian numbers, and others. He also invented graph theory by solving the Seven Bridges of Königsberg
Seven Bridges of Königsberg
The Seven Bridges of Königsberg is a historically notable problem in mathematics. Its negative resolution by Leonhard Euler in 1735 laid the foundations of graph theory and prefigured the idea of topology....
problem, which also led to the formation of topology
Topology
Topology is a major area of mathematics concerned with properties that are preserved under continuous deformations of objects, such as deformations that involve stretching, but no tearing or gluing...
. Finally, he broke ground with partitions
Partition of a set
In mathematics, a partition of a set X is a division of X into non-overlapping and non-empty "parts" or "blocks" or "cells" that cover all of X...
by the use of generating functions.