Historia de la combinatoria

El campo matemático de la combinatoria se estudió en distintos grados en numerosas sociedades antiguas . Su estudio en Europa se remonta a la obra de Leonardo Fibonacci en el siglo XIII d. C., que introdujo las ideas árabes e indias en el continente. Ha seguido estudiándose en la era moderna .

El primer uso registrado de técnicas combinatorias proviene del problema 79 del papiro de Rhind , que data del siglo XVI a. C. El problema se refiere a una determinada serie geométrica y tiene similitudes con el problema de Fibonacci de contar la cantidad de composiciones de 1 y 2 que suman un total dado. ^[1]

En Grecia, Plutarco escribió que Jenócrates de Calcedonia (396–314 a. C.) descubrió el número de sílabas diferentes posibles en la lengua griega . Este habría sido el primer intento registrado de resolver un problema difícil en permutaciones y combinaciones . ^[2] La afirmación, sin embargo, es inverosímil: esta es una de las pocas menciones de la combinatoria en Grecia , y el número que encontraron, 1,002 × 10  ¹² , parece demasiado redondo para ser más que una suposición. ^{[3] [4]}

Más tarde, se menciona una discusión entre Crisipo (siglo III a. C.) e Hiparco (siglo II a. C.) sobre un problema enumerativo bastante delicado , que más tarde se demostró que estaba relacionado con los números de Schröder-Hipparchus . ^{[5] [6]} También hay evidencia de que en el Ostomachion , Arquímedes (siglo III a. C.) consideró las configuraciones de un rompecabezas de teselas , ^[7] mientras que algunos intereses combinatorios pueden haber estado presentes en las obras perdidas de Apolonio . ^{[8] [9]}

En la India , el Bhagavati Sutra tuvo la primera mención de un problema de combinatoria; el problema preguntaba cuántas combinaciones posibles de sabores eran posibles al seleccionar sabores en unos, dos, tres, etc. de una selección de seis sabores diferentes ( dulce , picante , astringente , agrio, salado y amargo). El Bhagavati es también el primer texto que menciona la función de elección . ^[10] En el siglo II a. C., Pingala incluyó un problema de enumeración en el Chanda Sutra (también Chandahsutra) que preguntaba de cuántas maneras se podía hacer un metro de seis sílabas a partir de notas cortas y largas. ^{[11] [12]} Pingala encontró el número de metros que tenían notas largas y notas cortas; esto es equivalente a encontrar los coeficientes binomiales . ${\estilo de visualización n}$${\estilo de visualización k}$

Las ideas de Bhagavati fueron generalizadas por el matemático indio Mahavira en el año 850 d. C., y el trabajo de Pingala sobre la prosodia fue ampliado por Bhāskara II ^{[10] [13]} y Hemacandra en el año 1100 d. C. Bhaskara fue la primera persona conocida en encontrar la función de elección generalizada , aunque Brahmagupta puede haberla conocido antes. ^[1] Hemacandra preguntó cuántos metros existían de una determinada longitud si se consideraba que una nota larga era el doble de larga que una nota corta, lo que equivale a encontrar los números de Fibonacci . ^[11]

El antiguo libro chino de adivinación I Ching describe un hexagrama como una permutación con repeticiones de seis líneas donde cada línea puede ser uno de dos estados: sólido o discontinuo . Al describir los hexagramas de esta manera, determinan que hay hexagramas posibles. Un monje chino también puede haber contado el número de configuraciones para un juego similar al Go alrededor del 700 d. C. ^[3] Aunque China tuvo relativamente pocos avances en combinatoria enumerativa, alrededor del 100 d. C. resolvieron el cuadrado Lo Shu , que es el problema de diseño combinatorio del cuadrado mágico normal de orden tres. ^{[1] [14]} Los cuadrados mágicos siguieron siendo un interés de China, y comenzaron a generalizar su cuadrado original entre 900 y 1300 d. C. China se comunicó con Oriente Medio sobre este problema en el siglo XIII. ^[1] Oriente Medio también aprendió sobre los coeficientes binomiales del trabajo indio y encontró la conexión con la expansión polinomial . ^[15] El trabajo de los hindúes influyó en los árabes como se ve en el trabajo de al-Khalil ibn Ahmad que consideró las posibles disposiciones de las letras para formar sílabas . Sus cálculos muestran una comprensión de las permutaciones y combinaciones . En un pasaje de la obra del matemático árabe Umar al-Khayyami que data de alrededor de 1100, se corrobora que los hindúes tenían conocimiento de los coeficientes binomiales, pero también que sus métodos llegaron al Medio Oriente. ${\displaystyle 2^{6}=64}$${\displaystyle 3\times 3}$

Abū Bakr ibn Muḥammad ibn al Ḥusayn Al-Karaji (c. 953–1029) escribió sobre el teorema del binomio y el triángulo de Pascal . En una obra ahora perdida conocida solo por una cita posterior de al-Samaw'al , Al-Karaji introdujo la idea del argumento por inducción matemática .

El filósofo y astrónomo rabino Abraham ibn Ezra (c. 1140) contó las permutaciones con repeticiones en la vocalización del Nombre Divino . ^[16] También estableció la simetría de los coeficientes binomiales , mientras que una fórmula cerrada fue obtenida más tarde por el talmudista y matemático Levi ben Gerson (más conocido como Gersonides), en 1321. ^[17] El triángulo aritmético, un diagrama gráfico que muestra las relaciones entre los coeficientes binomiales , fue presentado por los matemáticos en tratados que datan del siglo X, y eventualmente se conocería como el triángulo de Pascal . Más tarde, en la Inglaterra medieval , la campanología proporcionó ejemplos de lo que ahora se conoce como ciclos hamiltonianos en ciertos gráficos de Cayley sobre permutaciones . ^[18]

La combinatoria llegó a Europa en el siglo XIII a través de los matemáticos Leonardo Fibonacci y Jordanus de Nemore . El Liber Abaci de Fibonacci introdujo muchas de las ideas árabes e indias en Europa, incluida la de los números de Fibonacci . ^[19] Jordanus fue la primera persona en ordenar los coeficientes binomiales en un triángulo , como lo hizo en la proposición 70 de De Arithmetica . Esto también se hizo en Oriente Medio en 1265, y en China alrededor de 1300. ^[1] Hoy en día, este triángulo se conoce como el triángulo de Pascal .

La contribución de Pascal al triángulo que lleva su nombre proviene de su trabajo sobre pruebas formales al respecto, y las conexiones que hizo entre el triángulo de Pascal y la probabilidad . ^[1] De una carta que Leibniz envió a Daniel Bernoulli nos enteramos de que Leibniz estaba estudiando formalmente la teoría matemática de particiones en el siglo XVII, aunque no se publicó ningún trabajo formal. Junto con Leibniz, Pascal publicó De Arte Combinatoria en 1666 que fue reimpreso más tarde. ^[20] Pascal y Leibniz son considerados los fundadores de la combinatoria moderna. ^[21]

Tanto Pascal como Leibniz entendieron que la expansión binomial era equivalente a la función de elección . La noción de que el álgebra y la combinatoria se correspondían fue ampliada por De Moivre , quien encontró la expansión de un multinomio . ^[22] De Moivre también encontró la fórmula para los desarreglos utilizando el principio de inclusión-exclusión , ^[1] un método diferente de Nikolaus Bernoulli , quien lo había encontrado previamente. ^{[23] [24]} De Moivre también logró aproximar los coeficientes binomiales y factoriales , y encontró una forma cerrada para los números de Fibonacci inventando funciones generadoras . ^{[25] [26]}

En el siglo XVIII, Euler trabajó en problemas de combinatoria y varios problemas de probabilidad vinculados a la combinatoria. Los problemas en los que trabajó Euler incluyen la vuelta de caballo , el cuadrado grecolatino , los números eulerianos y otros. Para resolver el problema de los siete puentes de Königsberg inventó la teoría de grafos , que también condujo a la formación de la topología . Finalmente, fue pionero en las particiones mediante el uso de funciones generadoras . ^[27]

En el siglo XIX, el tema de los conjuntos parcialmente ordenados y la teoría de redes se originó en el trabajo de Dedekind , Peirce y Schröder . Sin embargo, fue el trabajo seminal de Garrett Birkhoff en su libro Lattice Theory publicado en 1967, ^[28] y el trabajo de John von Neumann lo que realmente estableció los temas. ^[29] En la década de 1930, Hall (1936) y Weisner (1935) enunciaron de forma independiente la fórmula general de inversión de Möbius . ^[30] En 1964, On the Foundations of Combinatorial Theory I. Theory of Möbius Functions de Gian-Carlo Rota introdujo la teoría de conjuntos parcialmente ordenados y de redes como teorías en combinatoria. ^[29] Richard P. Stanley ha tenido un gran impacto en la combinatoria contemporánea por su trabajo en la teoría de matroides , ^[31] por introducir los polinomios Zeta, ^[32] por definir explícitamente los posets eulerianos , ^[33] por desarrollar la teoría de posets binomiales junto con Rota y Peter Doubilet, ^[34] y más. Paul Erdős hizo contribuciones fundamentales a la combinatoria a lo largo del siglo, ganando el premio Wolf en parte por estas contribuciones. ^[35]

• NL Biggs, Las raíces de la combinatoria, Historia Mathematica 6 (1979), 109–136.
• Katz, Victor J. (1998). Una historia de las matemáticas: una introducción , 2.ª edición. Addison-Wesley Education Publishers. ISBN 0-321-01618-1 . 
• O'Connor, John J. y Robertson, Edmund F. (1999–2004). Archivo de Historia de las Matemáticas de MacTutor . Universidad de St Andrews .
• Rashed, R. (1994). El desarrollo de las matemáticas árabes: entre la aritmética y el álgebra . Londres.
• Wilson, R. y Watkins, J. (2013). Combinatoria: antigua y moderna . Oxford.
• Stanley, Richard (2012). Combinatoria enumerativa (2.ª ed.) , 2.ª edición. Cambridge University Press. ISBN 1107602629 .