Editing Combinatorics (section)

== History ==
[[Image:Plain-bob-minor 2.png|150px|right|thumb|An example of [[change ringing]] (with six bells), one of the earliest nontrivial results in [[graph theory]].]]

{{Main|History of combinatorics}}

Basic combinatorial concepts and enumerative results appeared throughout the [[Ancient history|ancient world]]. 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 [[composition (combinatorics)|compositions]] of 1s and 2s that [[Summation|sum]] to a given total.<ref name="Biggs">{{cite book
| last1 = Biggs
| first1 = Norman
| first2 = Keith 
| last2= Lloyd 
| first3 = Robin
| last3 = Wilson
 | editor = Ronald Grahm, Martin Grötschel, László Lovász
 | title = Handbook of Combinatorics
 | year = 1995
 | url = https://books.google.com/books?id=kfiv_-l2KyQC
 | format = Google book
 | accessdate = 2008-03-08
 | publisher = MIT Press
 | isbn = 0262571722
 | pages = 2163–2188
 | chapter = 44
 }}</ref> [[Timeline of Indian history|Indian]] [[physician]] [[Sushruta]] asserts in [[Sushruta Samhita]] that 63 combinations can be made out of 6 different tastes, taken one at a time, two at a time, etc., thus computing all 2<sup>6</sup>&nbsp;−&nbsp;1 possibilities.  [[Ancient Greece|Greek]] [[historian]] [[Plutarch]] discusses 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 number]]s.<ref>{{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|access-date=2021-03-12|archive-date=2022-01-23|archive-url=https://web.archive.org/web/20220123111759/https://link.springer.com/article/10.1007%2Fs00407-003-0067-0|url-status=live}}</ref><ref>[[Richard P. Stanley|Stanley, Richard P.]]; "Hipparchus, Plutarch, Schröder, and Hough", ''American Mathematical Monthly'' '''104''' (1997), no. 4, 344–350.</ref><ref>{{cite journal |doi=10.1080/00029890.1998.12004906 |title=On the Second Number of Plutarch |year=1998 |last1=Habsieger |first1=Laurent |last2=Kazarian |first2=Maxim |last3=Lando |first3=Sergei |journal=The American Mathematical Monthly |volume=105 |issue=5 |pages=446 }}</ref> Earlier, in the ''[[Ostomachion]]'', [[Archimedes]] (3rd century BCE) may have considered the number of configurations of a [[tiling puzzle]],<ref>{{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|access-date=2021-03-12|archive-date=2021-04-16|archive-url=https://web.archive.org/web/20210416095205/https://www.sciamvs.org/2004.html|url-status=live}}</ref> while combinatorial interests possibly were present in lost works by [[Apollonius of Perga|Apollonius]].<ref>{{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|access-date=2021-03-26|archive-date=2021-04-18|archive-url=https://web.archive.org/web/20210418221029/https://www.jstor.org/stable/41133783|url-status=live}}</ref><ref>{{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|access-date=2021-03-26|archive-date=2021-04-16|archive-url=https://web.archive.org/web/20210416100956/https://grbs.library.duke.edu/article/view/11131/4205|url-status=live}}</ref>

In the [[Middle Ages]], combinatorics continued to be studied, largely outside of the [[Culture of Europe|European civilization]]. The [[India]]n mathematician [[Mahāvīra (mathematician)|Mahāvīra]] ({{circa|850}}) provided formulae for the number of [[permutation]]s and [[combination]]s,<ref>{{MacTutor | id=Mahavira}}</ref><ref>{{cite book |last=Puttaswamy |first=Tumkur K. |contribution=The Mathematical Accomplishments of Ancient Indian Mathematicians |editor-last=Selin |editor-first=Helaine |title=Mathematics Across Cultures: The History of Non-Western Mathematics |publisher=Kluwer Academic Publishers |location=Netherlands |url=https://books.google.com/books?id=2hTyfurOH8AC |year=2000 |isbn=978-1-4020-0260-1 |page=417 <!-- pages 409–422 --> |access-date=2015-11-15 |archive-date=2021-04-16 |archive-url=https://web.archive.org/web/20210416100852/https://books.google.com/books?id=2hTyfurOH8AC |url-status=live }}</ref> and these formulas may have been familiar to Indian mathematicians as early as the 6th century CE.<ref>{{cite journal | last1 = Biggs | first1 = Norman L. | year = 1979 | title = The Roots of Combinatorics | journal = Historia Mathematica | volume = 6 | issue = 2| pages = 109–136 | doi=10.1016/0315-0860(79)90074-0| doi-access = free }}</ref>  The [[philosopher]] and [[astronomer]] Rabbi [[Abraham ibn Ezra]] ({{circa|1140}}) established the symmetry of [[binomial coefficient]]s, while a closed formula was obtained later by the [[talmudist]] and [[mathematician]] [[Levi ben Gerson]] (better known as Gersonides), in 1321.<ref>{{citation|title=Probability Theory: A Historical Sketch|first=L.E.|last=Maistrov|publisher=Academic Press|year=1974|isbn=978-1-4832-1863-2|url=https://books.google.com/books?id=2ZbiBQAAQBAJ&pg=PA35|page=35|access-date=2015-01-25|archive-date=2021-04-16|archive-url=https://web.archive.org/web/20210416091311/https://books.google.com/books?id=2ZbiBQAAQBAJ&pg=PA35|url-status=live}}. (Translation from 1967 Russian ed.)</ref>
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 cycle]]s in certain [[Cayley graph]]s on permutations.<ref>{{cite journal |doi=10.1080/00029890.1987.12000711 |title=Ringing the Cosets |year=1987 |last1=White |first1=Arthur T. |journal=The American Mathematical Monthly |volume=94 |issue=8 |pages=721–746 }}</ref><ref>{{cite journal |doi=10.1080/00029890.1996.12004816 |title=Fabian Stedman: The First Group Theorist? |year=1996 |last1=White |first1=Arthur T. |journal=The American Mathematical Monthly |volume=103 |issue=9 |pages=771–778 }}</ref>

During the [[Renaissance]], together with the rest of mathematics and the [[science]]s, combinatorics enjoyed a rebirth. Works of [[Blaise Pascal|Pascal]], [[Isaac Newton|Newton]], [[Jacob Bernoulli]] and [[Leonhard Euler|Euler]] became foundational in the emerging field. In modern times, the works of [[James Joseph Sylvester|J.J. Sylvester]] (late 19th century) and [[Percy Alexander MacMahon|Percy MacMahon]] (early 20th century) helped lay the foundation for [[Enumerative combinatorics|enumerative]] and [[algebraic combinatorics]]. [[Graph theory]] also enjoyed an increase of interest at the same time, especially in connection with the [[four color problem]].

In the second half of the 20th century, combinatorics enjoyed a rapid growth, which led to establishment of dozens of new journals and conferences in the subject.<ref>See [http://www.math.iit.edu/~kaul/Journals.html#CGT Journals in Combinatorics and Graph Theory] {{Webarchive|url=https://web.archive.org/web/20210217150357/http://www.math.iit.edu/~kaul/Journals.html#CGT |date=2021-02-17 }}</ref> In part, the growth was spurred by new connections and applications to other fields, ranging from algebra to probability, from [[functional analysis]] to [[number theory]], etc.  These connections shed the boundaries between combinatorics and parts of mathematics and theoretical computer science, but at the same time led to a partial fragmentation of the field.