La combinatoria es un área de las matemáticas que se ocupa principalmente del conteo , como medio y fin en la obtención de resultados, y de 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 .
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 , [1] así como en sus numerosas áreas de aplicación. Históricamente, muchas cuestiones 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 generales y potentes que convirtieron 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í sola tiene numerosas conexiones naturales con otras áreas. La combinatoria se utiliza frecuentemente en informática para obtener fórmulas y estimaciones en el análisis de algoritmos .
Se llama combinatoria al matemático que estudia combinatoria .
No existe un acuerdo universal sobre el alcance completo de la combinatoria. [3] Según HJ Ryser , una definición del tema es difícil porque atraviesa muchas subdivisiones matemáticas. [4] En la medida en que un área puede describirse por los tipos de problemas que aborda, la combinatoria está involucrada con:
Leon Mirsky ha dicho: "la combinatoria es una gama 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, 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. [6] Aunque se ocupan principalmente de sistemas finitos, algunas preguntas y técnicas combinatorias pueden extenderse a un entorno infinito (específicamente, contable ) pero discreto .
Conceptos combinatorios básicos y 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., 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 más tarde se demostró que estaba relacionado con los números de Schröder-Hiparco . [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 se siguió estudiando la combinatoria, 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 posteriormente 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 matemáticos en tratados que se remontan al siglo X y eventualmente llegaría a ser conocido como el triángulo de Pascal . Posteriormente, en la Inglaterra medieval , la campanología proporcionó ejemplos de lo que hoy 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 gozó de un renacimiento. Las obras de Pascal , Newton , Jacob Bernoulli y Euler se convirtieron en fundamentales en el campo emergente. En los 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 . Al mismo tiempo, la teoría de grafos también gozó de un creciente interés, 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 decenas de nuevas revistas y conferencias sobre el tema. [19] En parte, el crecimiento fue impulsado por nuevas conexiones y aplicaciones a otros campos, que van desde el álgebra hasta la probabilidad, desde el análisis funcional hasta la teoría de números , etc. Estas conexiones eliminan los límites entre la combinatoria y partes de las matemáticas y la informática teórica. pero al mismo tiempo condujo 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 combinatoria enumerativa. La forma doce proporciona un marco unificado para contar permutaciones , combinaciones y particiones .
La combinatoria analítica se refiere a 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 obtener fórmulas asintóticas .
La teoría de la partición estudia diversos problemas asintóticos y de enumeración relacionados con las particiones enteras , y está estrechamente relacionada con las series q , las funciones especiales y los polinomios ortogonales . Originalmente parte de la teoría y el análisis de números , ahora se considera parte de la combinatoria o un campo independiente. Incorpora el enfoque biyectivo y varias herramientas en análisis y 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 gráficos son objetos fundamentales en combinatoria. Las consideraciones de la teoría de grafos van desde la enumeración (p. ej., el número de gráficos en n vértices con k aristas) hasta estructuras existentes (p. ej., ciclos hamiltonianos) y representaciones algebraicas (p. ej., dado un gráfico G y dos números x e y , ¿ tutte polinomio 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 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 un estudio de 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 finitos simples . 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 del diseño de experimentos . Parte de la teoría básica de los diseños combinatorios se originó en el trabajo del estadístico Ronald Fisher sobre el diseño de experimentos biológicos. Las aplicaciones modernas también se encuentran 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. Estructuras análogas a las que se encuentran en las 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 conjuntos parcialmente ordenados , tanto finitos como infinitos. Proporciona un marco formal para describir afirmaciones como "esto es menor que aquello" o "esto precede a aquello". Varios ejemplos de órdenes parciales aparecen en álgebra , geometría, teoría de números y en combinatoria y teoría de grafos. Las clases y ejemplos notables de órdenes parciales incluyen celosías y álgebras booleanas .
La teoría matroide abstrae parte de la geometría . Estudia las propiedades de 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 matroide. La teoría matroide fue introducida por Hassler Whitney y estudiada como parte de la teoría del orden. Ahora es un campo de estudio independiente con varias conexiones con otras partes de la combinatoria.
La combinatoria extrema estudia cuán grande o 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 refiere a clases de sistemas de conjuntos ; esto se llama teoría de conjuntos extremos. Por ejemplo, en un conjunto de n elementos, ¿cuál es el mayor número de k subconjuntos de elementos que pueden cruzarse entre sí por pares? ¿Cuál es el mayor número de subconjuntos de los cuales ninguno contiene a otro? La última pregunta es respondida por el teorema de Sperner , que dio origen a gran parte de la teoría de conjuntos extremos.
Los tipos de preguntas abordadas en este caso son sobre el gráfico más grande posible que satisface ciertas propiedades. Por ejemplo, el gráfico sin triángulos más grande en 2n vértices es un gráfico bipartito completo K n, n . A menudo es demasiado difícil incluso encontrar exactamente la respuesta extrema f ( n ) y sólo se puede dar una estimación asintótica .
La teoría de Ramsey es otra parte de la combinatoria extrema. Afirma que cualquier configuración suficientemente grande contendrá algún tipo de orden. Es una generalización avanzada del principio del casillero .
En 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 gráfico aleatorio ? Por ejemplo, ¿cuál es el número promedio de triángulos en una gráfica aleatoria? Los métodos probabilísticos también se utilizan para determinar la existencia de objetos combinatorios con ciertas propiedades prescritas (para las cuales puede ser 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 conocido como método probabilístico ) demostró ser muy eficaz en aplicaciones de combinatoria extrema y teoría de grafos. Un área estrechamente relacionada es el estudio de cadenas finitas de Markov , especialmente en objetos combinatorios. Aquí nuevamente se utilizan herramientas probabilísticas para estimar el tiempo de mezcla . [ se necesita aclaración ]
A menudo asociada con Paul Erdős , quien realizó el trabajo pionero sobre el tema, la combinatoria probabilística 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 combinatoria.
La combinatoria algebraica es un área de las matemáticas que emplea métodos de álgebra abstracta , en particular teoría de grupos y teoría de representaciones , en diversos 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 amplia como un área de las matemáticas donde la interacción de los métodos combinatorios y algebraicos es particularmente fuerte y significativa. Así, 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 representaciones, son comunes la teoría de redes y el álgebra conmutativa .
La combinatoria de palabras se ocupa de los lenguajes formales . Surgió de forma independiente dentro de varias ramas de las matemáticas, incluidas la teoría de números , la teoría de grupos y la probabilidad . Tiene aplicaciones en combinatoria enumerativa, análisis fractal , informática teórica , teoría de autómatas y lingüística . Si bien muchas aplicaciones son nuevas, la jerarquía clásica de clases de gramáticas formales de Chomsky-Schützenberger es quizás el resultado más conocido en este campo.
La combinatoria geométrica está relacionada con la geometría convexa y discreta . Se pregunta, por ejemplo, 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 permutoedros , asociaedros y 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 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 de Arquímedes y los números besados también forma 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 coloración de gráficos , división equitativa , particiones , conjuntos parcialmente ordenados , árboles de decisión , problemas de collar y teoría Morse discreta . No debe confundirse con topología combinatoria , que es un nombre más antiguo para 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 a operaciones aritméticas (suma, resta, multiplicación y división). La teoría de números aditiva (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 combinatoria aritmética es la teoría ergódica de sistemas dinámicos .
La combinatoria infinita, o teoría combinatoria de conjuntos, es una extensión de las ideas de la combinatoria a 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 extrema. Algunas de las cosas estudiadas 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 de los sucesores de cardenales 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 contar y medir .
La optimización combinatoria es el estudio de la optimización de 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 asignatura es diseñar métodos eficientes y confiables de transmisión de datos. Ahora es un gran 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 en politopos convexos y números besados . 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. Quedan muchas conexiones con la combinatoria geométrica y topológica, que en sí mismas pueden verse como consecuencias de la geometría discreta temprana.
Los aspectos combinatorios de los sistemas dinámicos es otro campo emergente. Aquí los sistemas dinámicos se pueden definir sobre objetos combinatorios. Véase, por ejemplo, sistema dinámico de gráficos .
Hay interacciones cada vez mayores entre la combinatoria y la física , particularmente la física estadística . Los ejemplos incluyen una 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á saliendo de esta etapa inicial.
... la teoría combinatoria ha sido la madre de varias de las ramas más activas de las matemáticas actuales, que se han independizado... . El caso típico... de esto es la topología algebraica (anteriormente conocida como topología combinatoria)
Definiciones de Wikcionario
Medios de los comunes
Citas de Wikiquote
Libros de texto de Wikilibros