La combinatoria es un área de las matemáticas que se ocupa principalmente del conteo , tanto como medio como fin para obtener resultados, y de ciertas propiedades de las estructuras finitas . Está estrechamente relacionada 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 .
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 , en particular en álgebra , teoría de la probabilidad , topología y geometría , [1] así como en sus muchas áreas de aplicación. Muchas cuestiones combinatorias se han considerado históricamente 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 potentes y generales, convirtiendo la combinatoria en una rama independiente de las matemáticas por derecho propio. [2] 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 .
Un matemático que estudia la combinatoria se llama combinatorialista .
No existe un consenso universal sobre el alcance total de la combinatoria. [3] Según HJ Ryser , una definición del tema es difícil porque cruza muchas subdivisiones matemáticas. [4] 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 un conjunto de estudios vinculados que tienen algo en común y, sin embargo, divergen ampliamente en sus objetivos, sus métodos y el grado de coherencia que han alcanzado". [5] Una forma de definir la combinatoria es, tal vez, describir sus subdivisiones con sus problemas y técnicas. Este es el enfoque que se utiliza a continuación. Sin embargo, también hay razones puramente históricas para incluir o no algunos temas bajo el paraguas de la combinatoria. [6] Aunque se ocupan principalmente de sistemas finitos, algunas cuestiones y técnicas combinatorias se pueden extender a un entorno infinito (específicamente, contable ) pero discreto .
Los conceptos básicos de combinatoria y los resultados enumerativos aparecieron en todo el mundo antiguo . El médico indio Sushruta afirma en Sushruta Samhita que se pueden hacer 63 combinaciones a partir de 6 sabores diferentes, tomados uno a la vez, dos a la vez, etc., computando 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 más tarde 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.) puede haber considerado el número de configuraciones de un rompecabezas de mosaicos , [10] mientras que los intereses combinatorios posiblemente estaban presentes en las obras perdidas de Apolonio . [11] [12]
En la Edad Media , la combinatoria continuó estudiándose, en gran medida 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 d.C. [15] El filósofo y astrónomo Rabino Abraham ibn Ezra ( c. 1140 ) 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. [16] 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. [17] [18]
Durante el Renacimiento , junto con el resto de las matemáticas y las ciencias , la combinatoria experimentó un renacimiento. Los trabajos de Pascal , Newton , Jacob Bernoulli y Euler se convirtieron en fundamentales en el campo emergente. En tiempos modernos, los trabajos de JJ Sylvester (finales del siglo XIX) y Percy MacMahon (principios del siglo XX) ayudaron a sentar las bases de la combinatoria enumerativa y algebraica . La teoría de grafos también disfrutó de un aumento de interés al mismo tiempo, especialmente en relación con el problema de los cuatro colores .
En la segunda mitad del siglo XX, la combinatoria disfrutó de un rápido crecimiento, lo que llevó al establecimiento de docenas de nuevas revistas y conferencias sobre el tema. [19] En parte, el crecimiento fue impulsado por nuevas conexiones y aplicaciones a otros campos, desde el álgebra hasta la probabilidad, desde el análisis funcional hasta la teoría de números , etc. Estas conexiones eliminaron los límites entre la combinatoria y partes de las matemáticas y la informática teórica, pero al mismo tiempo llevaron a una fragmentación parcial del campo.
La combinatoria enumerativa es el área más clásica de la combinatoria y se concentra en contar el número de ciertos objetos combinatorios. Aunque contar el número de elementos de un conjunto es un problema matemático bastante amplio , muchos de los problemas que surgen en las aplicaciones tienen una descripción combinatoria relativamente simple. Los números de Fibonacci son el ejemplo básico de un problema en la combinatoria enumerativa. El método de doce pasos proporciona un marco unificado para contar permutaciones , combinaciones y particiones .
La combinatoria analítica se ocupa de la enumeración de estructuras combinatorias utilizando herramientas del análisis complejo y la teoría de la probabilidad . A diferencia de la combinatoria enumerativa, que utiliza fórmulas combinatorias explícitas y funciones generadoras para describir los resultados, la combinatoria analítica tiene como objetivo la obtención de fórmulas asintóticas .
La teoría de particiones estudia varios problemas de enumeración y asintóticos relacionados con particiones enteras , y está estrechamente relacionada con las series q , las funciones especiales y los polinomios ortogonales . Originalmente una parte de la teoría de números y el análisis , ahora se considera una parte de la combinatoria o un campo independiente. Incorpora el enfoque biyectivo y varias herramientas en el análisis y la teoría analítica de números y tiene conexiones con la mecánica estadística . Las particiones se pueden visualizar gráficamente con diagramas de Young o diagramas de Ferrers . Ocurren en varias ramas de las matemáticas y la física , incluido el estudio de polinomios simétricos y del grupo simétrico y en la teoría de representación de grupos en general.
Los grafos son objetos fundamentales en la combinatoria. Las consideraciones de la teoría de grafos van desde la enumeración (por ejemplo, el número de grafos en n vértices con k aristas) hasta las estructuras existentes (por ejemplo, los ciclos hamiltonianos) y las representaciones algebraicas (por ejemplo, dado un grafo G y dos números x e y , ¿el polinomio de Tutte T G ( x , y ) tiene una interpretación combinatoria?). Aunque existen conexiones muy fuertes entre la teoría de grafos y la combinatoria, a veces se las considera como temas separados. [20] Si bien los métodos combinatorios se aplican a muchos problemas de teoría de grafos, las dos disciplinas se utilizan generalmente para buscar soluciones a diferentes tipos de problemas.
La teoría del diseño es el estudio de los diseños combinatorios , que son colecciones de subconjuntos con ciertas propiedades de intersección . Los diseños de bloques son diseños combinatorios de un tipo especial. Esta área es una de las partes más antiguas de la combinatoria, como en el problema de la colegiala de Kirkman propuesto en 1850. La solución del problema es un caso especial de un sistema de Steiner , que juega un papel importante en la clasificación de grupos simples finitos . El área tiene más conexiones con la teoría de la codificación y la combinatoria geométrica.
La teoría del diseño combinatorio se puede aplicar al área de diseño de experimentos . Algunas de las teorías básicas de los diseños combinatorios se originaron en el trabajo del estadístico Ronald Fisher sobre el diseño de experimentos biológicos. También se encuentran aplicaciones modernas en una amplia gama de áreas, que incluyen geometría finita , programación de torneos , loterías , química matemática , biología matemática , diseño y análisis de algoritmos , redes , pruebas grupales y criptografía . [21]
La geometría finita es el estudio de sistemas geométricos que tienen sólo un número finito de puntos. Las estructuras análogas a las que se encuentran en geometrías continuas ( plano euclidiano , espacio proyectivo real , etc.) pero definidas combinatoriamente son los principales elementos estudiados. Esta área proporciona una rica fuente de ejemplos para la teoría del diseño . No debe confundirse con la geometría discreta ( geometría combinatoria ).
La teoría del orden es el estudio de los conjuntos parcialmente ordenados , tanto finitos como infinitos. Proporciona un marco formal para describir enunciados como "esto es menor que eso" o "esto precede a eso". Varios ejemplos de órdenes parciales aparecen en álgebra , geometría, teoría de números y en toda la combinatoria y teoría de grafos. Entre las clases y ejemplos notables de órdenes parciales se incluyen los retículos y las álgebras de Boole .
La teoría de matroides abstrae parte de la geometría . Estudia las propiedades de los conjuntos (normalmente, conjuntos finitos) de vectores en un espacio vectorial que no dependen de los coeficientes particulares en una relación de dependencia lineal . No sólo la estructura sino también las propiedades enumerativas pertenecen a la teoría de matroides. La teoría de matroides fue introducida por Hassler Whitney y estudiada como parte de la teoría del orden. Ahora es un campo de estudio independiente con una serie de conexiones con otras partes de la combinatoria.
La combinatoria extrema estudia cuán grande o cuán pequeña puede ser una colección de objetos finitos ( números , gráficos , vectores , conjuntos , etc.) si tiene que satisfacer ciertas restricciones. Gran parte de la combinatoria extrema se ocupa de las clases de sistemas de conjuntos ; esto se llama teoría de conjuntos extremales. Por ejemplo, en un conjunto de n elementos, ¿cuál es el mayor número de subconjuntos de k elementos que pueden intersecarse entre sí por pares? ¿Cuál es el mayor número de subconjuntos de los cuales ninguno contiene a otro? La última pregunta se responde con el teorema de Sperner , que dio origen a gran parte de la teoría de conjuntos extremales.
Los tipos de preguntas que se abordan en este caso se refieren al grafo más grande posible que satisface ciertas propiedades. Por ejemplo, el grafo libre de triángulos más grande con 2n vértices es un grafo bipartito completo K n,n . A menudo es demasiado difícil incluso encontrar la respuesta extrema f ( n ) con exactitud y solo se puede dar una estimación asintótica .
La teoría de Ramsey es otra parte de la combinatoria extrema. Establece que cualquier configuración suficientemente grande contendrá algún tipo de orden. Es una generalización avanzada del principio del palomar .
En la combinatoria probabilística, las preguntas son del siguiente tipo: ¿cuál es la probabilidad de una determinada propiedad para un objeto discreto aleatorio, como un grafo aleatorio ? Por ejemplo, ¿cuál es el número medio de triángulos en un grafo aleatorio? Los métodos probabilísticos también se utilizan para determinar la existencia de objetos combinatorios con ciertas propiedades prescritas (para los que puede resultar difícil encontrar ejemplos explícitos) observando que la probabilidad de seleccionar aleatoriamente un objeto con esas propiedades es mayor que 0. Este enfoque (a menudo denominado método probabilístico ) demostró ser muy eficaz en aplicaciones a la combinatoria extremal y la teoría de grafos. Un área estrechamente relacionada es el estudio de las cadenas finitas de Markov , especialmente en objetos combinatorios. Aquí nuevamente se utilizan herramientas probabilísticas para estimar el tiempo de mezcla . [ aclaración necesaria ]
La combinatoria probabilística , que a menudo se asocia con Paul Erdős , quien realizó el trabajo pionero sobre el tema, se consideraba tradicionalmente como un conjunto de herramientas para estudiar problemas en otras partes de la combinatoria. El área creció recientemente hasta convertirse en un campo independiente de la combinatoria.
La combinatoria algebraica es un área de las matemáticas que emplea métodos del álgebra abstracta , en particular la teoría de grupos y la teoría de la representación , en varios contextos combinatorios y, a la inversa, aplica técnicas combinatorias a problemas de álgebra . La combinatoria algebraica ha llegado a ser vista de manera más expansiva como un área de las matemáticas donde la interacción de los métodos combinatorios y algebraicos es particularmente fuerte y significativa. Por lo tanto, los temas combinatorios pueden ser de naturaleza enumerativa o involucrar matroides , politopos , conjuntos parcialmente ordenados o geometrías finitas . En el lado algebraico, además de la teoría de grupos y de la representación, la teoría de retículos y el álgebra conmutativa son comunes.
La combinatoria de palabras se ocupa de los lenguajes formales . Surgió de forma independiente en varias ramas de las matemáticas, incluidas la teoría de números , la teoría de grupos y la probabilidad . Tiene aplicaciones en la combinatoria enumerativa, el análisis fractal , la informática teórica , la teoría de autómatas y la lingüística . Si bien muchas aplicaciones son nuevas, la clásica jerarquía de clases de gramáticas formales de Chomsky-Schützenberger es quizás el resultado más conocido en el campo.
La combinatoria geométrica está relacionada con la geometría convexa y discreta . Por ejemplo, se pregunta cuántas caras de cada dimensión puede tener un politopo convexo . Las propiedades métricas de los politopos también desempeñan un papel importante, por ejemplo, el teorema de Cauchy sobre la rigidez de los politopos convexos. También se consideran politopos especiales, como los permutoedros , los asociahedros y los politopos de Birkhoff . La geometría combinatoria es un nombre histórico para la geometría discreta.
Incluye una serie de subáreas como la combinatoria poliédrica (el estudio de las caras de los poliedros convexos ), la geometría convexa (el estudio de los conjuntos convexos , en particular la combinatoria de sus intersecciones) y la geometría discreta , que a su vez tiene muchas aplicaciones en la geometría computacional . El estudio de los politopos regulares , los sólidos arquimedianos y los números de beso también es parte de la combinatoria geométrica. También se consideran politopos especiales, como el permutoedro , el asociaedro y el politopo de Birkhoff .
Los análogos combinatorios de conceptos y métodos en topología se utilizan para estudiar la coloración de grafos , la división justa , las particiones , los conjuntos parcialmente ordenados , los árboles de decisión , los problemas de collar y la teoría de Morse discreta . No debe confundirse con la topología combinatoria , que es un nombre más antiguo para la topología algebraica .
La combinatoria aritmética surgió de la interacción entre la teoría de números , la combinatoria, la teoría ergódica y el análisis armónico . Se trata de estimaciones combinatorias asociadas con operaciones aritméticas (suma, resta, multiplicación y división). La teoría aditiva de números (a veces también llamada combinatoria aditiva) se refiere al caso especial en el que solo están involucradas las operaciones de suma y resta. Una técnica importante en la combinatoria aritmética es la teoría ergódica de sistemas dinámicos .
La combinatoria infinitesimal, o teoría de conjuntos combinatorios, es una extensión de las ideas de la combinatoria a los conjuntos infinitos. Es parte de la teoría de conjuntos , un área de la lógica matemática , pero utiliza herramientas e ideas tanto de la teoría de conjuntos como de la combinatoria extremal. Algunas de las cosas que se estudian incluyen gráficos y árboles continuos , extensiones del teorema de Ramsey y el axioma de Martin . Los desarrollos recientes se refieren a la combinatoria del continuo [22] y a la combinatoria sobre sucesores de cardinales singulares. [23]
Gian-Carlo Rota utilizó el nombre de combinatoria continua [24] para describir la probabilidad geométrica , ya que existen muchas analogías entre el conteo y la medida .
La optimización combinatoria es el estudio de la optimización sobre objetos discretos y combinatorios. Comenzó como parte de la combinatoria y la teoría de grafos, pero ahora se considera una rama de las matemáticas aplicadas y la informática, relacionada con la investigación de operaciones , la teoría de algoritmos y la teoría de la complejidad computacional .
La teoría de la codificación comenzó como parte de la teoría del diseño con las primeras construcciones combinatorias de códigos de corrección de errores . La idea principal de la disciplina es diseñar métodos eficientes y confiables de transmisión de datos. Actualmente es un amplio campo de estudio, parte de la teoría de la información .
La geometría discreta (también llamada geometría combinatoria) también comenzó como parte de la combinatoria, con resultados tempranos sobre politopos convexos y números de beso . Con el surgimiento de aplicaciones de la geometría discreta a la geometría computacional , estos dos campos se fusionaron parcialmente y se convirtieron en un campo de estudio separado. Todavía quedan muchas conexiones con la combinatoria geométrica y topológica, que en sí mismas pueden considerarse como consecuencias de la geometría discreta temprana.
Los aspectos combinatorios de los sistemas dinámicos son otro campo emergente. En este campo, los sistemas dinámicos se pueden definir a partir de objetos combinatorios. Véase, por ejemplo, el sistema dinámico de grafos .
Cada vez hay más interacciones entre la combinatoria y la física , en particular la física estadística . Algunos ejemplos son la solución exacta del modelo de Ising y una conexión entre el modelo de Potts , por un lado, y los polinomios cromáticos y de Tutte, por el otro.
En mi opinión, la combinatoria está dejando atrás esta etapa temprana.
la teoría combinatoria ha sido la madre de varias de las ramas más activas de las matemáticas actuales, que se han vuelto independientes... . El caso típico de esto es la topología algebraica (antes conocida como topología combinatoria)
Definiciones de Wikcionario
Medios de comunicación de Commons
Citas de Wikiquote
Libros de texto de Wikilibros