History of combinatorics

Last updated

The mathematical field of combinatorics was studied to varying degrees in numerous ancient societies. Its study in Europe dates to the work of Leonardo Fibonacci in the 13th century AD, which introduced Arabian and Indian ideas to the continent. It has continued to be studied in the modern era.

Contents

Earliest records

A portion of the Rhind papyrus. Rhind Mathematical Papyrus.jpg
A portion of the Rhind papyrus.

The earliest recorded use of combinatorial techniques comes from problem 79 of the Rhind papyrus, which dates to the 16th century BCE. 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. [1]

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. [2] The claim, however, is implausible: this is one of the few mentions of combinatorics in Greece, and the number they found, 1.002 × 10 12, seems too round to be more than a guess. [3] [4]

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

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. [10] 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. [11] [12] Pingala found the number of meters that had long notes and 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 [10] [13] and Hemacandra in 1100 AD. Bhaskara was the first known person to find the generalised choice function, although Brahmagupta may have known earlier. [1] 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. [11]

A hexagram Iching-hexagram-37.svg
A hexagram

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 possible hexagrams. A Chinese monk also may have counted the number of configurations to a game similar to Go around 700 AD. [3] 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. [1] [14] Magic squares remained an interest of China, and they began to generalize their original square between 900 and 1300 AD. China corresponded with the Middle East about this problem in the 13th century. [1] The Middle East also learned about binomial coefficients from Indian work and found the connection to polynomial expansion. [15] 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 Umar al-Khayyami 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 Rabbi Abraham ibn Ezra (c. 1140) counted the permutations with repetitions in vocalization of Divine Name. [16] 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. [17] 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. [18]

Combinatorics in the West

Combinatorics came to Europe in the 13th century through 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. [19] 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. [1] 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, and the connections he made between Pascal's triangle and probability. [1] From a letter Leibniz sent to Daniel Bernoulli we learn that Leibniz was formally studying the mathematical theory of partitions in the 17th century, although no formal work was published. Together with Leibniz, Pascal published De Arte Combinatoria in 1666 which was reprinted later. [20] Pascal and Leibniz are considered the founders of modern combinatorics. [21]

Both Pascal and Leibniz understood that the binomial expansion was equivalent to the choice function. The notion that algebra and combinatorics corresponded was expanded by De Moivre, who found the expansion of a multinomial. [22] De Moivre also found the formula for derangements using the principle of principle of inclusion-exclusion, a method different from Nikolaus Bernoulli, who had found it previously. [1] De Moivre also managed to approximate the binomial coefficients and factorial, and found a closed form for the Fibonacci numbers by inventing generating functions. [23] [24]

In the 18th century, Euler worked on problems of combinatorics, and several problems of probability which are linked to combinatorics. Problems Euler worked on include the Knights tour, Graeco-Latin square, Eulerian numbers, and others. To solve the Seven Bridges of Königsberg problem he invented graph theory, which also led to the formation of topology. Finally, he broke ground with partitions by the use of generating functions. [25]

Contemporary combinatorics

In the 19th century, the subject of partially ordered sets and lattice theory originated in the work of Dedekind, Peirce, and Schröder. However, it was Garrett Birkhoff's seminal work in his book Lattice Theory published in 1967, [26] and the work of John von Neumann that truly established the subjects. [27] In the 1930s, Hall (1936) and Weisner (1935) independently stated the general Möbius inversion formula. [28] In 1964, Gian-Carlo Rota's On the Foundations of Combinatorial Theory I. Theory of Möbius Functions introduced poset and lattice theory as theories in Combinatorics. [27] Richard P. Stanley has had a big impact in contemporary combinatorics for his work in matroid theory, [29] for introducing Zeta polynomials, [30] for explicitly defining Eulerian posets, [31] developing the theory of binomial posets along with Rota and Peter Doubilet, [32] and more. Paul Erdős made seminal contributions to combinatorics throughout the century, winning the Wolf prize in-part for these contributions. [33]

Notes

  1. 1 2 3 4 5 6 7 Biggs, Norman; Keith Lloyd; Robin Wilson (1995). "44". In Ronald Graham; Martin Grötschel; László Lovász (eds.). Handbook of Combinatorics (Google book). MIT Press. pp. 2163–2188. ISBN   0-262-57172-2 . Retrieved 2008-03-08.
  2. ↑ Heath, Sir Thomas (1981). A history of Greek mathematics (Reprod. en fac-sim. ed.). New York: Dover. ISBN   0486240738.
  3. 1 2 Dieudonné, J. "The Rhind/Ahmes Papyrus - Mathematics and the Liberal Arts". Historia Math. Truman State University. Archived from the original on 2012-12-12. Retrieved 2008-03-06.
  4. ↑ Gow, James (1968). A Short History of Greek Mathematics. AMS Bookstore. p. 71. ISBN   0-8284-0218-3.
  5. ↑ Acerbi, F. (2003). "On the shoulders of Hipparchus". Archive for History of Exact Sciences. 57 (6): 465–502. doi:10.1007/s00407-003-0067-0. S2CID   122758966.
  6. ↑ Stanley, Richard P. (2018-04-10). "Hipparchus, Plutarch, Schröder, and Hough". The American Mathematical Monthly. 104 (4): 344–350. doi:10.2307/2974582. ISSN   0002-9890. JSTOR   2974582.
  7. ↑ Netz, R.; Acerbi, F.; Wilson, N. "Towards a reconstruction of Archimedes' Stomachion". Sciamvs. 5: 67–99.
  8. ↑ Hogendijk, Jan P. (1986). "Arabic Traces of Lost Works of Apollonius". Archive for History of Exact Sciences. 35 (3): 187–253. doi:10.1007/BF00357307. ISSN   0003-9519. JSTOR   41133783. S2CID   121613986.
  9. ↑ Huxley, G. (1967). "Okytokion". Greek, Roman, and Byzantine Studies. 8 (3): 203–204.
  10. 1 2 "India". Archived from the original on 2007-11-14. Retrieved 2008-03-05.
  11. 1 2 Hall, Rachel Wells (February 2008). "Math for poets and drummers". Math Horizons. 15 (3): 10–24. doi:10.1080/10724117.2008.11974752. JSTOR   25678735.
  12. ↑ Kulkarni, Amba (2007). "Recursion and Combinatorial Mathematics in Chandashāstra". arXiv: math/0703658 .
  13. ↑ Bhaskara. "The Lilavati of Bhaskara". Brown University. Archived from the original on 2008-03-25. Retrieved 2008-03-06.
  14. ↑ Swaney, Mark. "Mark Swaney on the History of Magic Squares". Archived from the original on 2004-08-07.
  15. ↑ "Middle East". Archived from the original on 2007-11-14. Retrieved 2008-03-08.
  16. ↑ The short commentary on Exodus 3:13
  17. ↑ History of Combinatorics, chapter in a textbook.
  18. ↑ Arthur T. White, ”Ringing the Cosets,” Amer. Math. Monthly94 (1987), no. 8, 721-746; Arthur T. White, ”Fabian Stedman: The First Group Theorist?,” Amer. Math. Monthly103 (1996), no. 9, 771-778.
  19. ↑ Devlin, Keith (October 2002). "The 800th birthday of the book that brought numbers to the west". Devlin's Angle. Retrieved 2008-03-08.
  20. ↑ Leibniz's habilitation thesis De Arte Combinatoria was published as a book in 1666 and reprinted later
  21. ↑ Dickson, Leonard (2005) [1919]. "Chapter III". Diophantine Analysis. History of the Theory of Numbers. Mineola, New York: Dover Publications, Inc. p. 101. ISBN   0-486-44233-0.
  22. ↑ Hodgson, James; William Derham; Richard Mead (1708). Miscellanea Curiosa (Google book). Volume II. pp. 183–191. Retrieved 2008-03-08.
  23. ↑ O'Connor, John; Edmund Robertson (June 2004). "Abraham de Moivre". The MacTutor History of Mathematics archive. Retrieved 2008-03-09.
  24. ↑ Pang, Jong-Shi; Olvi Mangasarian (1999). "10.6 Generating Function". In Jong-Shi Pang (ed.). Computational Optimisation (Google book). Volume 1. Netherlands: Kluwer Academic Publishers. pp. 182–183. ISBN   0-7923-8480-6 . Retrieved 2008-03-09.
  25. ↑ "Combinatorics and probability" . Retrieved 2008-03-08.
  26. ↑ Birkhoff, Garrett (1984). Lattice theory (3d ed., reprinted with corrections. ed.). Providence, R.I.: American Mathematical Society. ISBN   978-0821810255.
  27. 1 2 Stanley, Richard P. (2012). Enumerative combinatorics (2nd. ed.). Cambridge: Cambridge University Press. pp.  391–393. ISBN   978-1107602625.
  28. ↑ Bender, Edward A.; Goldman, J. R. (1975). "On the applications of Möbius inversion in combinatorial analysis". Amer. Math. Monthly. 82 (8): 789–803. doi:10.2307/2319793. JSTOR   2319793.
  29. ↑ Stanley, Richard (2007). "An introduction to hyperplane arrangements". Geometric Combinatorics. IAS/Park City Mathematics Series. Vol. 13. pp. 389–496. doi:10.1090/pcms/013/08. ISBN   9780821837368.
  30. ↑ Stanley, Richard (1974). "Combinatorial reciprocity theorems". Advances in Mathematics . 14 (2): 194–253. doi: 10.1016/0001-8708(74)90030-9 .
  31. ↑ Stanley, Richard (1982). "Some aspects of groups acting on finite posets". Journal of Combinatorial Theory. Ser. A 32 (2): 132–161. doi: 10.1016/0097-3165(82)90017-6 .
  32. ↑ Stanley, Richard (1976). "Binomial posets, M¨obius inversion, and permutation enumeration". Journal of Combinatorial Theory . Ser. A 20 (3): 336–356. doi: 10.1016/0097-3165(76)90028-5 .
  33. ↑ "Wolf Foundation Mathematics Prize Page". Wolffund.org.il. Archived from the original on 2008-04-10. Retrieved 2010-05-29.

Related Research Articles

Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many applications ranging from logic to statistical physics and from evolutionary biology to computer science.

In mathematics, a combination is a selection of items from a set that has distinct members, such that the order of selection does not matter. For example, given three fruits, say an apple, an orange and a pear, there are three combinations of two that can be drawn from this set: an apple and a pear; an apple and an orange; or a pear and an orange. More formally, a k-combination of a set S is a subset of k distinct elements of S. So, two combinations are identical if and only if each combination has the same members. If the set has n elements, the number of k-combinations, denoted by or , is equal to the binomial coefficient

Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures.

In mathematics, a combinatorial class is a countable set of mathematical objects, together with a size function mapping each object to a non-negative integer, such that there are finitely many objects of each size.

Acharya Pingala was an ancient Indian poet and mathematician, and the author of the Chandaḥśāstra, also called the Pingala-sutras, the earliest known treatise on Sanskrit prosody.

Enumerative combinatorics is an area of combinatorics that deals with the number of ways that certain patterns can be formed. Two examples of this type of problem are counting combinations and counting permutations. More generally, given an infinite collection of finite sets Si indexed by the natural numbers, enumerative combinatorics seeks to describe a counting function which counts the number of objects in Sn for each n. Although counting the number of elements in a set is a rather broad mathematical problem, many of the problems that arise in applications have a relatively simple combinatorial description. The twelvefold way provides a unified framework for counting permutations, combinations and partitions.

<span class="mw-page-title-main">Outline of trigonometry</span> Overview of and topical guide to trigonometry

The following outline is provided as an overview of and topical guide to trigonometry:

<span class="mw-page-title-main">Ordered Bell number</span> Number of weak orderings

In number theory and enumerative combinatorics, the ordered Bell numbers or Fubini numbers count the number of weak orderings on a set of elements. Weak orderings arrange their elements into a sequence allowing ties, such as might arise as the outcome of a horse race. Starting from , these numbers are

The Stanley–Wilf conjecture, formulated independently by Richard P. Stanley and Herbert Wilf in the late 1980s, states that the growth rate of every proper permutation class is singly exponential. It was proved by Adam Marcus and Gábor Tardos and is no longer a conjecture. Marcus and Tardos actually proved a different conjecture, due to Zoltán Füredi and Péter Hajnal, which had been shown to imply the Stanley–Wilf conjecture by Klazar (2000).

<i>Ars Conjectandi</i> 1713 book on probability and combinatorics by Jacob Bernoulli

Ars Conjectandi is a book on combinatorics and mathematical probability written by Jacob Bernoulli and published in 1713, eight years after his death, by his nephew, Niklaus Bernoulli. The seminal work consolidated, apart from many combinatorial topics, many central ideas in probability theory, such as the very first version of the law of large numbers: indeed, it is widely regarded as the founding work of that subject. It also addressed problems that today are classified in the twelvefold way and added to the subjects; consequently, it has been dubbed an important historical landmark in not only probability but all combinatorics by a plethora of mathematical historians. The importance of this early work had a large impact on both contemporary and later mathematicians; for example, Abraham de Moivre.

<span class="mw-page-title-main">Fence (mathematics)</span> Partially ordered set with alternatingly-related elements

In mathematics, a fence, also called a zigzag poset, is a partially ordered set (poset) in which the order relations form a path with alternating orientations:

<span class="mw-page-title-main">Triangular array</span> Concept in mathematics and computing

In mathematics and computing, a triangular array of numbers, polynomials, or the like, is a doubly indexed sequence in which each row is only as long as the row's own index. That is, the ith row contains only i elements.

In algebra and in particular in algebraic combinatorics, a quasisymmetric function is any element in the ring of quasisymmetric functions which is in turn a subring of the formal power series ring with a countable number of variables. This ring generalizes the ring of symmetric functions. This ring can be realized as a specific limit of the rings of quasisymmetric polynomials in n variables, as n goes to infinity. This ring serves as universal structure in which relations between quasisymmetric polynomials can be expressed in a way independent of the number n of variables.

John Stembridge is a Professor of Mathematics at University of Michigan. He received his Ph.D. from Massachusetts Institute of Technology in 1985 under the direction of Richard P. Stanley. His dissertation was called Combinatorial Decompositions of Characters of SL(n,C).

In mathematics, a differential poset is a partially ordered set satisfying certain local properties. This family of posets was introduced by Stanley (1988) as a generalization of Young's lattice, many of whose combinatorial properties are shared by all differential posets. In addition to Young's lattice, the other most significant example of a differential poset is the Young–Fibonacci lattice.

<span class="mw-page-title-main">Schröder–Hipparchus number</span> Number in combinatorics

In combinatorics, the Schröder–Hipparchus numbers form an integer sequence that can be used to count the number of plane trees with a given set of leaves, the number of ways of inserting parentheses into a sequence, and the number of ways of dissecting a convex polygon into smaller polygons by inserting diagonals. These numbers begin

<span class="mw-page-title-main">Henry W. Gould</span> American mathematician

Henry Wadsworth Gould is a Professor Emeritus of Mathematics at West Virginia University.

<span class="mw-page-title-main">Lattice path</span> Sequence of end-to-end vectors across points of a lattice

In combinatorics, a lattice pathL in the d-dimensional integer lattice of length k with steps in the set S, is a sequence of vectors such that each consecutive difference lies in S. A lattice path may lie in any lattice in , but the integer lattice is most commonly used.

<span class="mw-page-title-main">Sergey Kitaev</span> Russian-British mathematician

Sergey Kitaev is a Professor of Mathematics at the University of Strathclyde, Glasgow, Scotland. He obtained his Ph.D. in mathematics from the University of Gothenburg in 2003 under the supervision of Einar Steingrímsson. Kitaev's research interests concern aspects of combinatorics and graph theory.

References

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.