Historia del combinatoria

Nota

Iste articulo require revision linguistic

Corrige le errores de grammatica, orthographia o stilo in le articulo. Postea, retira iste aviso.

Le campo mathematic de combinatoria esseva studiate a differentes grados in multe societates antique. Su studio in Europa data ab le labor de Leonardo Fibonacci in le 13me seculo post Christo, que introduceva ideas arabic e indian al continente. Illo ha continuate esser studiate in le era moderne.

Registros le plus antique

Le uso le plus ancian registrate de technicas combinatori es trovate in le problema 79 del papyro Rhind, datante del 16me seculo a.C. Iste problema tracta de un certe serie geometric, e ha similaritates con le problema de Fibonacci super como contar le numero de compositiones de 1s e 2s que summan un total date.[1]

In Grecia, Plutarcho scribeva que Xenocrates de Chalcedon (396–314 a.C.) habeva discoperite le numero de syllabas differente possibile in le lingua grec. Isto haberea essite le prime tentativa registrate de solver un problema difficile de permutationes e combinationes.[2] Le affirmation, tamen, es improbabile: isto es un del rar mentions de combinatoria in Grecia, e le numero que illes trovava, 1.002 × 10¹², pare troppo rotunde pro esser plus que un supposition.[3][4]

Plus tarde, un disputa inter Chrysippus (3e seculo a.C.) e Hipparchus (2e seculo a.C.) super un problema enumerative delicatemente subtil—plus tarde monstrate como ligate al numeros de Schröder–Hipparchus—es mentionate.[5][6] Il ha etiam evidentia que in le Ostomachion, Archimedes (3e seculo a.C.) considerava le configurationes de un puzzle de tessellation,[7] e certe interesses combinatori pote haber essite presente in obras perdite de Apollonius.[8][9]

In India, le Bhagavati Sutra contineva le prime mention de un problema de combinatoria; le problema demandava quante combinationes de sapores esseva possibile per seleccionar sapores in un, duo, tres, etc., ex un selection de sex sapores differente (dulce, piccante, astringente, acre, salate, e amar). Le Bhagavati es etiam le prime texto que mentiona le function “sceglier”.[10] In le secunde seculo a.C., Pingala includeva un problema de enumeration in le Chanda Sutra (tamben Chandahsutra), que demandava in quante manieras un metro de sex syllabas pote esser formate ab notas curte e long.[11][12] Pingala trovava le numero de metros que habeva n notas long e k notas curte; isto es equivalent a calcular le coefficientes binomial.

Le ideas del Bhagavati esseva generalisate per le mathematico indian Mahavira in 850 d.C., e le obra de Pingala super prosodia esseva expandite per Bhāskara II[10][13] e Hemacandra in 1100 d.C. Bhaskara esseva le prime persona cognoscite a trovar le function generalisate de “sceglier”, ben que Brahmagupta pote haber lo sapite antea.[1] Hemacandra demandava quante metros existeva de un certe longitude si un nota longe esseva considerate como duple in longitud respecto a un nota curte—equivalente a calcular le numeros de Fibonacci.[11]

Le ancian libro chinese de divination I Ching describe un hexagramma como un permutation con repetitiones de sex lineas ubi cata linea pote esser in un de duo estados: solide o interruptite. In describer hexagrammas de iste maniera, illes determinava que il ha 2⁶ = 64 hexagrammas possibile. Un monacho chinese pote etiam haber contate le numero de configurationes de un jogo simile a Go circa le anno 700 d.C.[3] Ben que China habeva relativemente paucos progressos in combinatoria enumerative, circa le anno 100 d.C. illes resolvava le Quadrato de Lo Shu, que es le problema de designo combinatori del quadrato magic normal de ordine tres.[1][14] Quadratos magic restava un interesse in China, e illes comenciava a generalisar lor quadrato original 3×3 inter 900 e 1300 d.C. China correspondeva con le Medio Oriente super iste problema in le 13me seculo.[1] Le Medio Oriente etiam apprendeva super le coefficientes binomial ab le obra indian, e trovava le connexion con le expansion polynomial.[15] Le labor del hindus influentiava le arabes, como on vide in le obra de al-Khalil ibn Ahmad, qui considerava le arrangiamentos possibile de litteras pro formar syllabas. Su calculos monstra un comprehension de permutationes e combinationes. In un passage ab le obra del mathematico arabe Umar al-Khayyami, datante circa 1100, on confirma que le hindus habeva cognoscentia del coefficientes binomial, e que lor methodos attingeva le Medio Oriente.

Abū Bakr ibn Muḥammad ibn al-Ḥusayn Al-Karaji (circa 953–1029) scribeva super le theorema binomial e le triangulo de Pascal. In un obra ora perdite, cognoscite solmente per citationes posterior per al-Samaw’al, Al-Karaji introduceva le idea de argumento per induction mathematic.

Le philosopho e astronome rabbinic Abraham ibn Ezra (circa 1140) contava le permutationes con repetitiones in le vocalisation del Nomine Divine.[16] Ille etiam establiva le symmetria del coefficientes binomial, durante que un formula claus esseva plus tarde obtenite per le talmudista e mathematico Levi ben Gerson (plus cognoscite como Gersonides) in 1321.[17] Le triangulo arithmetic—un diagramma graphic monstrante le relationes inter le coefficientes binomial—esseva presentate per mathematicos in tractatos que data ab usque le 10me seculo, e esseva plus tarde cognoscite como le triangulo de Pascal. Plus tarde, in le Anglaterra del 17me seculo, le campanologia provideva exemplos del que nos cognosce hodie como cyclos Hamiltonian in certe graphos de Cayley super permutationes.[18]

Combinatoria in le Occidente

Le combinatoria attingeva Europa in le 13me seculo per le mathematicos Leonardo Fibonacci e Jordanus de Nemore. Le Liber Abaci de Fibonacci introduceva multe ideas arabe e indian in Europa, includente le numeros de Fibonacci.[19] Jordanus esseva le prime persona a arrangiar le coefficientes binomial in un triangulo, como ille faceva in le proposition 70 de De Arithmetica. Isto esseva etiam facite in le Medio Oriente in 1265, e in China circa 1300.[1] Hodie, iste triangulo es cognoscite como le triangulo de Pascal.

Le contribution de Pascal al triangulo que porta su nomine proveni de su labor super demonstrationes formal, e le connexiones que ille faceva inter le triangulo de Pascal e le probabilitate.[1] Ab un littera que Leibniz inviava a Daniel Bernoulli, nos apprende que Leibniz studiava formalmente le theoria mathematic del partitiones in le 17me seculo, ben que nulle obra formal esseva publicate. Insieme con Leibniz, Pascal publicava De Arte Combinatoria in 1666, que esseva plus tarde reimprimite.[20] Pascal e Leibniz es considerate como le fundatores del combinatoria moderne.[21]

Tanto Pascal como Leibniz comprendeva que le expansion binomial esseva equivalente al function de selection (sceglier). Le notion que algebra e combinatoria correspondeva esseva expandite per De Moivre, qui trovava le expansion de un multinomio.[22] De Moivre trovava etiam le formula pro derangements (permutationes sin fixate punctos) per le principio de inclusion-exclusion,[1] un methodo differente ab ille de Nikolaus Bernoulli, qui lo habeva trovate previemente.[23][24] De Moivre tamben succedeva approximar le coefficientes binomial e le factorial, e trovava un formula claus pro le numeros de Fibonacci per medio del invention de functiones generante.[25][26]

In le 18me seculo, Euler laborava super problemas de combinatoria, e plure problemas de probabilitate ligate al combinatoria. Inter le problemas tractate per Euler se include le tour del cavallero, le quadrato graeco-latin, le numeros eulerian, inter alteres. Pro solver le problema del Septem Pontes de Königsberg, ille inventava le theoria del graphos, que etiam conduceva al formation del topologia. Finalmente, ille faceva progressos importante con le partitiones per medio del uso de functiones generante.[27]

Combinatoria contemporanee

In le 19me seculo, le subjecto del insimules partialmente ordinate e le theoria del reticulos originava in le obras de Dedekind, Peirce, e Schröder. Totevia, esseva le obra fundamental de Garrett Birkhoff in su libro Lattice Theory, publicate in 1967,[28] e le labor de John von Neumann que vermente stabiliva iste subjectos.[29] In le annos 1930, Hall (1936) e Weisner (1935) formulava independentemente le formula general de inversion de Möbius.[30] In 1964, On the Foundations of Combinatorial Theory I. Theory of Möbius Functions de Gian-Carlo Rota introduceva le theoria de posets e reticulos como partes del combinatoria.[29]

Richard P. Stanley habeva un grande impacto in le combinatoria contemporanee per su labor in le theoria del matroides,[31] per le introduction del polynomos Zeta,[32] per le definition explicite del posets eulerian,[33] per le disveloppamento del theoria del posets binomial in collaborante con Rota e Peter Doubilet,[34] e plus ancora. Paul Erdős faceva contributiones fundamental al combinatoria durante tote le seculo, e recipeva le Premio Wolf in parte pro iste contributiones.[35]