History of combinatorics

File:Rhind Mathematical Papyrus.jpg

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.{{cite book|last1=Heath|first1=Sir Thomas|title=A history of Greek mathematics|url=https://archive.org/details/historyofgreekma0002heat|url-access=registration|date=1981|publisher=Dover|location=New York|isbn=0486240738|edition= Reprod. en fac-sim.}} 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.{{cite book

| last = Gow

| first = James

| title = A Short History of Greek Mathematics

| publisher = AMS Bookstore

| year = 1968

| pages = 71

| url = https://books.google.com/books?id=68sYLQa9FuQC

| isbn =0-8284-0218-3 }}

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.{{Cite journal|last=Acerbi|first=F.|title=On the shoulders of Hipparchus|url=https://link.springer.com/article/10.1007/s00407-003-0067-0|journal=Archive for History of Exact Sciences|year=2003|volume=57|issue=6|pages=465–502|doi=10.1007/s00407-003-0067-0|s2cid=122758966}}{{Cite journal|last=Stanley|first=Richard P.|date=2018-04-10|title=Hipparchus, Plutarch, Schröder, and Hough|url=https://www.tandfonline.com/doi/abs/10.1080/00029890.1997.11990645|journal=The American Mathematical Monthly|volume=104|issue=4|pages=344–350|language=en|doi=10.2307/2974582|jstor=2974582|issn=0002-9890}} There is also evidence that in the Ostomachion, Archimedes (3rd century BC) considered the configurations of a tiling puzzle,{{Cite journal|last1=Netz|first1=R.|last2=Acerbi|first2=F.|last3=Wilson|first3=N.|title=Towards a reconstruction of Archimedes' Stomachion|url=https://www.sciamvs.org/2004.html|journal=Sciamvs|volume=5|pages=67–99}} while some combinatorial interests may have been present in lost works of Apollonius.{{Cite journal|last=Hogendijk|first=Jan P.|date=1986|title=Arabic Traces of Lost Works of Apollonius|url=https://www.jstor.org/stable/41133783|journal=Archive for History of Exact Sciences|volume=35|issue=3|pages=187–253|doi=10.1007/BF00357307|jstor=41133783|s2cid=121613986|issn=0003-9519}}{{Cite journal|last=Huxley|first=G.|date=1967|title=Okytokion|url=https://grbs.library.duke.edu/article/view/11131/4205|journal=Greek, Roman, and Byzantine Studies|volume=8|issue=3|pages=203–204}}

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.{{cite web|title=India|url=http://binomial.csueastbay.edu/India.html|access-date=2008-03-05|archive-url=https://web.archive.org/web/20071114201718/http://binomial.csueastbay.edu/India.html|archive-date=2007-11-14|url-status=dead}} 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.{{cite journal

| last = Hall | first = Rachel Wells

| date = February 2008

| doi = 10.1080/10724117.2008.11974752

| issue = 3

| journal = Math Horizons

| jstor = 25678735

| pages = 10–24

| title = Math for poets and drummers

| url = https://scholar.archive.org/work/nphn7gqpm5afran7c43tm65m7y

| volume = 15}}{{cite arXiv|last=Kulkarni|first=Amba|title=Recursion and Combinatorial Mathematics in Chandashāstra|year=2007|eprint=math/0703658}} Pingala found the number of meters that had $n$ long notes and $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{{cite web

|last=Bhaskara

|author-link=Bhaskara II

|title=The Lilavati of Bhaskara

|publisher=Brown University

|url=http://www.brown.edu/Departments/History_Mathematics/lilavati.html

|access-date=2008-03-06

|archive-url=https://web.archive.org/web/20080325004552/http://www.brown.edu/Departments/History_Mathematics/lilavati.html

|archive-date=2008-03-25

|url-status=dead

}} and Hemacandra in 1100 AD. Bhaskara was the first known person to find the generalised choice function, although Brahmagupta may have known earlier.{{cite book

| last = Biggs

| first = Norman

|author2=Keith Lloyd |author3=Robin Wilson

| editor = Ronald Graham |editor2=Martin Grötschel | editor2-link = Martin Grötschel |editor3=László Lovász

| title = Handbook of Combinatorics

| year = 1995

| url = https://books.google.com/books?id=kfiv_-l2KyQC

| format = Google book

| access-date = 2008-03-08

| publisher = MIT Press

| isbn = 0-262-57172-2

| pages = 2163–2188

| chapter = 44

}} 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.

File:Iching-hexagram-37.svg]]

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 $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.{{cite web

| last = Dieudonné

| first = J.

| title = The Rhind/Ahmes Papyrus - Mathematics and the Liberal Arts

| work = Historia Math

| publisher = Truman State University

| url = http://mtcs.truman.edu/~thammond/history/RhindPapyrus.html

| archive-url = https://archive.today/20121212144312/http://mtcs.truman.edu/~thammond/history/RhindPapyrus.html

| url-status = dead

| archive-date = 2012-12-12

| access-date = 2008-03-06 }} 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.{{cite web |last=Swaney |first=Mark |title=Mark Swaney on the History of Magic Squares |url=http://www.netmastersinc.com/secrets/magic_squares.htm

|archive-url=https://web.archive.org/web/20040807015853/http://www.netmastersinc.com/secrets/magic_squares.htm |archive-date=2004-08-07}} Magic squares remained an interest of China, and they began to generalize their original $3\backslash times3$ 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.{{cite web|title=Middle East|url=http://binomial.csueastbay.edu/MidEast.html|access-date=2008-03-08|archive-url=https://web.archive.org/web/20071114201734/http://binomial.csueastbay.edu/MidEast.html|archive-date=2007-11-14|url-status=dead}} 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.The short commentary on Exodus 3:13 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.[http://ncertbooks.prashanthellina.com/class_11.Mathematics.Mathematics/Ch-07(Permutation%20and%20Combinations%20FINAL%20%2004.01.06).pdf History of Combinatorics] {{Webarchive|url=https://web.archive.org/web/20081203092403/http://ncertbooks.prashanthellina.com/class_11.Mathematics.Mathematics/Ch-07(Permutation%20and%20Combinations%20FINAL%20%2004.01.06).pdf |date=2008-12-03 }}, chapter in a textbook.

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.

Arthur T. White, ”Ringing the Cosets,” Amer. Math. Monthly 94 (1987), no. 8, 721-746; Arthur T. White, ”Fabian Stedman: The First Group Theorist?,” Amer. Math. Monthly 103 (1996), no. 9, 771-778.

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.{{cite web

|url=http://www.maa.org/devlin/devlin_10_02.html

|title= The 800th birthday of the book that brought numbers to the west

|access-date= 2008-03-08

|last= Devlin

|first= Keith

|date=October 2002

|work=Devlin's Angle

}} 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, and the connections he made between Pascal's triangle and probability. 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.Leibniz's habilitation thesis De Arte Combinatoria was published as a book in 1666 and reprinted later Pascal and Leibniz are considered the founders of modern combinatorics.{{cite book

| last = Dickson

| first = Leonard

| title = Diophantine Analysis

| orig-year = 1919

| series = History of the Theory of Numbers

| year = 2005

| publisher = Dover Publications, Inc.

| location = Mineola, New York

| isbn = 0-486-44233-0

| pages = 101

| chapter = Chapter III

}}

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.{{cite book

| last = Hodgson

| first = James |author2=William Derham |author3=Richard Mead

| title = Miscellanea Curiosa

| url = https://books.google.com/books?id=sr04AAAAMAAJ

| format = Google book

| access-date = 2008-03-08

| series = Volume II

| year = 1708

| pages = 183–191

}} 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.{{Cite thesis |title=Inverse relations, generalized bibasic series, and their U(n) extensions |last=Bhatnagar |first=Gaurav |date=1995 |degree=PhD |publisher=Ohio State University |id=OhioLINK [http://rave.ohiolink.edu/etdc/view?acc_num=osu1487865929455351 osu1487865929455351]. {{ProQuest|304230935}}. {{ResearchGatePub|228567824}}. |page=7 |chapter=Chapter I: A Characterization of Inverse Relations}}{{Cite book |last=Rémond de Montmort |first=Pierre |url=https://gallica.bnf.fr/ark:/12148/bpt6k110519q/f346.item |title=Essay d'analyse sur les jeux de hazard |date=1713 |publisher=Chez Jacque Quillau |edition=2nd |location=Rue Galande, Paris |pages=299–303 |language=EN |chapter=Remarques de M. (Nicolas) Bernoulli |id={{Gale|U0104196246}}. Gallica [https://gallica.bnf.fr/ark:/12148/bpt6k110519q/f344.item ark:/12148/bpt6k110519q/f344.item].}} De Moivre also managed to approximate the binomial coefficients and factorial, and found a closed form for the Fibonacci numbers by inventing generating functions.

{{cite web

|url= http://www-history.mcs.st-andrews.ac.uk/Biographies/De_Moivre.html

|title= Abraham de Moivre

|access-date= 2008-03-09

|last= O'Connor

|first= John

|author2=Edmund Robertson

|date=June 2004

|work= The MacTutor History of Mathematics archive

}}{{cite book

| last = Pang

| first = Jong-Shi

|author2=Olvi Mangasarian

| editor = Jong-Shi Pang

| title = Computational Optimisation

| url = https://books.google.com/books?id=kJa15IMxAoIC

| format = Google book

| access-date = 2008-03-09

| series = Volume 1

| year = 1999

| publisher = Kluwer Academic Publishers

| location = Netherlands

| isbn = 0-7923-8480-6

| pages = 182–183

| chapter = 10.6 Generating Function

}}

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.{{cite web

| title = Combinatorics and probability

| url = http://math.dartmouth.edu/~euler/

| access-date = 2008-03-08

}}

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,{{cite book|last1=Birkhoff|first1=Garrett|title=Lattice theory|date=1984|publisher=American Mathematical Society|location=Providence, R.I.|isbn=978-0821810255|edition= 3d ed., reprinted with corrections.}} and the work of John von Neumann that truly established the subjects.{{cite book|last1=Stanley|first1=Richard P.|title=Enumerative combinatorics.|url=https://archive.org/details/enumerativecombi01stan_381|url-access=limited|date=2012|publisher=Cambridge University Press|location=Cambridge|isbn=978-1107602625|pages=[https://archive.org/details/enumerativecombi01stan_381/page/n390 391]–393|edition= 2nd.}} In the 1930s, Hall (1936) and Weisner (1935) independently stated the general Möbius inversion formula.{{cite journal|last1=Bender|first1=Edward A.|last2=Goldman|first2=J. R.|title=On the applications of Möbius inversion in combinatorial analysis|journal=Amer. Math. Monthly|volume=82|year=1975|issue=8|pages=789–803|url=http://www.maa.org/programs/maa-awards/writing-awards/on-the-applications-of-m-bius-inversion-in-combinatorial-analysis|doi=10.2307/2319793|jstor=2319793}} 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. Richard P. Stanley has had a big impact in contemporary combinatorics for his work in matroid theory,{{cite book|last1=Stanley|first1=Richard |title=Geometric Combinatorics |chapter=An introduction to hyperplane arrangements |series=IAS/Park City Mathematics Series |date=2007|volume=13|issue=IAS/Park City Mathematics Series|pages=389–496|doi=10.1090/pcms/013/08|isbn=9780821837368}} for introducing Zeta polynomials,{{cite journal|last1=Stanley|first1=Richard|title=Combinatorial reciprocity theorems|journal=Advances in Mathematics|date=1974|volume=14|issue=2|pages=194–253|doi=10.1016/0001-8708(74)90030-9|doi-access=free}} for explicitly defining Eulerian posets,{{cite journal|last1=Stanley|first1=Richard|title=Some aspects of groups acting on finite posets|journal=Journal of Combinatorial Theory|date=1982|volume=Ser. A 32|issue=2|pages=132–161|doi=10.1016/0097-3165(82)90017-6|doi-access=free}} developing the theory of binomial posets along with Rota and Peter Doubilet,{{cite journal|last1=Stanley|first1=Richard|title=Binomial posets, M¨obius inversion, and permutation enumeration|journal=Journal of Combinatorial Theory|date=1976|volume=Ser. A 20|issue=3|pages=336–356|doi=10.1016/0097-3165(76)90028-5|doi-access=free}} and more. Paul Erdős made seminal contributions to combinatorics throughout the century, winning the Wolf prize in-part for these contributions.{{cite web |url=http://www.wolffund.org.il/cat.asp?id=23&cat_title=MATHEMATICS |title=Wolf Foundation Mathematics Prize Page |publisher=Wolffund.org.il |access-date=2010-05-29 |archive-url=https://web.archive.org/web/20080410234620/http://www.wolffund.org.il/cat.asp?id=23&cat_title=MATHEMATICS |archive-date=2008-04-10 |url-status=dead }}

{{reflist|30em}}

• N.L. Biggs, The roots of combinatorics, Historia Mathematica 6 (1979), 109–136.
• Katz, Victor J. (1998). A History of Mathematics: An Introduction, 2nd Edition. Addison-Wesley Education Publishers. {{ISBN|0-321-01618-1}}.
• O'Connor, John J. and Robertson, Edmund F. (1999–2004). MacTutor History of Mathematics archive. St Andrews University.
• Rashed, R. (1994). The development of Arabic mathematics: between arithmetic and algebra. London.
• Wilson, R. and Watkins, J. (2013). Combinatorics: Ancient & Modern. Oxford.
• Stanley, Richard (2012). Enumerative combinatorics (2nd ed. ed.), 2nd Edition. Cambridge University Press. {{ISBN| 1107602629}}.

{{History of science}}

{{History of mathematics}}

{{DEFAULTSORT:History Of Combinatorics}}

Combinatorics

+