La combinatoria es un área de las matemáticas que se ocupa principalmente del conteo, tanto como medio como para obtener resultados, y ciertas propiedades de las estructuras finitas . Está estrechamente relacionado con muchas otras áreas de las matemáticas y tiene muchas aplicaciones que van desde la lógica hasta la física estadística y desde la biología evolutiva hasta la informática .
El alcance completo de la combinatoria no está universalmente aceptado. [1] Según HJ Ryser , una definición del tema es difícil porque cruza muchas subdivisiones matemáticas. [2] En la medida en que un área puede describirse por los tipos de problemas que aborda, la combinatoria se ocupa de:
Leon Mirsky ha dicho: "La combinatoria es una gama de estudios vinculados que tienen algo en común y, sin embargo, difieren ampliamente en sus objetivos, sus métodos y el grado de coherencia que han alcanzado". [3] Una forma de definir la combinatoria es, quizás, describir sus subdivisiones con sus problemas y técnicas. Este es el enfoque que se utiliza a continuación. Sin embargo, también existen razones puramente históricas para incluir o no algunos temas bajo el paraguas de la combinatoria. [4] Aunque se trata principalmente de sistemas finitos, algunas preguntas y técnicas combinatorias pueden extenderse a un entorno infinito (específicamente, contable ) pero discreto .
La combinatoria es bien conocida por la amplitud de los problemas que aborda. Los problemas combinatorios surgen en muchas áreas de las matemáticas puras , especialmente en álgebra , teoría de la probabilidad , topología y geometría , [5] así como en sus muchas áreas de aplicación. Históricamente, muchas preguntas combinatorias se han considerado de forma aislada, dando una solución ad hoc a un problema que surge en algún contexto matemático. Sin embargo, a finales del siglo XX se desarrollaron métodos teóricos poderosos y generales, convirtiendo a la combinatoria en una rama independiente de las matemáticas por derecho propio. [6]Una de las partes más antiguas y accesibles de la combinatoria es la teoría de grafos , que por sí misma tiene numerosas conexiones naturales con otras áreas. La combinatoria se utiliza con frecuencia en informática para obtener fórmulas y estimaciones en el análisis de algoritmos .
Los conceptos combinatorios básicos y los resultados enumerativos aparecieron en todo el mundo antiguo . En el siglo VI a. C., el antiguo médico indio Sushruta afirma en Sushruta Samhita que se pueden hacer 63 combinaciones de 6 gustos diferentes, tomar uno a la vez, dos a la vez, etc., calculando así las 2 6 − 1 posibilidades. El historiador griego Plutarco analiza una discusión entre Crisipo (siglo III a. C.) e Hiparco (siglo II a. C.) sobre un problema enumerativo bastante delicado, que luego se demostró que estaba relacionado con los números de Schröder-Hipparchus . [7] [8] [9] Anteriormente, en el Ostomachion , Arquímedes (siglo III a. C.) pudo haber considerado el número de configuraciones de un rompecabezas de mosaico , [10] mientras que los intereses combinatorios posiblemente estaban presentes en las obras perdidas de Apolonio . [11] [12]
En la Edad Media , la combinatoria continuó siendo estudiada, en gran parte fuera de la civilización europea . El matemático indio Mahāvīra (c. 850) proporcionó fórmulas para el número de permutaciones y combinaciones , [13] [14] y estas fórmulas pueden haber sido familiares para los matemáticos indios ya en el siglo VI EC. [15] El filósofo y astrónomo Rabí Abraham ibn Ezra (c. 1140) estableció la simetría de los coeficientes binomiales , mientras que el talmudista obtuvo más tarde una fórmula cerrada .y el matemático Levi ben Gerson (más conocido como Gersonides), en 1321. [16] El triángulo aritmético, un diagrama gráfico que muestra las relaciones entre los coeficientes binomiales, fue presentado por matemáticos en tratados que datan del siglo X y eventualmente ser conocido 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. [17] [18]