Combinatoria

De Wikipedia, la enciclopedia libre
Saltar a navegación , búsqueda

Combinatoria es una rama de las matemáticas relacionadas con el estudio de finitos o contables discretas estructuras . Aspectos de la combinatoria incluyen contar las estructuras de un determinado tipo y tamaño ( combinatoria enumerativa ), la decisión de cuándo ciertos criterios se pueden cumplir, y la construcción de reunión y el análisis de los objetos de los criterios (como en diseños combinatorios y matroide teoría), la búsqueda de "la más grande", " más pequeños ", o" óptimos "los objetos ( combinatoria extremal y optimización combinatoria ), y el estudio de las estructuras combinatorias que surge en una algebraica contexto, o la aplicación de técnicas algebraicas para problemas combinatorios ( combinatoria algebraica ).

Problemas combinatorios surgir en muchas áreas de las matemáticas puras, especialmente en álgebra , teoría de la probabilidad , topología y geometría , [1] y la combinatoria también tiene muchas aplicaciones en optimización , ciencias de la computación , teoría ergódica y la física estadística . Muchas cuestiones combinatorias han sido históricamente considerada de forma aislada, dando una solución ad hoc a un problema que surge en un contexto matemático. A finales del siglo XX, sin embargo, los métodos teóricos potentes y generales se desarrollaron, por lo que la combinatoria en una rama independiente de las matemáticas en su propio derecho. Una de las partes más antiguas y más accesible de la combinatoria es la teoría de grafos , que también cuenta con numerosas conexiones con otras áreas naturales. Combinatoria se utiliza con frecuencia en la informática para obtener fórmulas y cálculos en el análisis de algoritmos .

Un matemático que estudia la combinatoria se llama combinatorialist.

Contenido

[ editar ] Historia

Un ejemplo de cambio de timbre (con seis campanas), uno de los primeros resultados no triviales en teoría de grafos.

Conceptos básicos de combinatoria enumerativa y los resultados aparecieron en todo el mundo antiguo . En sexto siglo BCE, médico Sushruta afirma en Sushruta Samhita 63 combinaciones que se pueden hacer fuera de 6 sabores diferentes, tomados de uno en uno, de dos en dos, etc, por lo que computar todos 2 6 -1 posibilidades. griego historiador Plutarco habla una discusión entre Crisipo (3 ª siglo aC) y Hiparco (siglo segundo antes de Cristo) de un problema enumerativo bastante delicada, que más tarde se demostró que se relaciona con el número de Schröder . [2] [3] En el Ostomachion , Arquímedes (siglo 3 aC) considera un rompecabezas de mosaico .

En la Edad Media , la combinatoria continuó a estudiar, en gran medida fuera de la civilización europea . El indio matemático Mahāvīra (c. 850), siempre fórmulas para el número de permutaciones y combinaciones, [4] [5] y estas fórmulas puede haber sido familiar para los matemáticos indios ya en el siglo sexto CE. [6] El filósofo y astrónomo Rabí Abraham ibn Ezra (c. 1140) estableció la simetría de los coeficientes binomiales , mientras que una fórmula cerrada se obtuvo después por el talmudista y matemático Levi ben Gerson (más conocido como Gersónides), en 1321. [7] El triángulo aritmético un gráfico diagrama que muestra las relaciones entre los coeficientes del binomio-fue presentado por los matemáticos en los tratados que datan desde el siglo 10, y con el tiempo llegaría a ser conocido como el triángulo de Pascal . Más tarde, en la Inglaterra medieval , Campanología dio ejemplos de lo que hoy se conoce como ciclos hamiltonianos en ciertos grafos de Cayley sobre permutaciones. [8]

Durante el Renacimiento , junto con el resto de las matemáticas y las ciencias , la combinatoria disfrutado de un renacimiento. Las obras de Pascal , Newton , Jacob Bernoulli y Euler se convirtió en fundamental en el campo emergente. En los tiempos modernos, las obras de JJ Sylvester (siglo 19) y Percy MacMahon (siglo 20) sentó las bases para enumerativos y la combinatoria algebraica . teoría de grafos también disfrutó de una explosión de interés, al mismo tiempo, sobre todo en relación con la cuatro colores problema .

En la segunda mitad del siglo 20, la combinatoria disfrutado de un rápido crecimiento, lo que condujo al establecimiento de docenas de nuevas revistas y conferencias en la materia. [9] En parte, el crecimiento fue impulsado por las nuevas conexiones y aplicaciones a otros campos, que van desde álgebra a la probabilidad, a partir del análisis funcional a la teoría de números, etc Estas conexiones arrojar los límites entre la combinatoria y partes de las matemáticas y las ciencias de la computación teórica, pero al mismo tiempo llevó a una fragmentación parcial del campo.

[ editar ] Enfoques y subcampos de la combinatoria

[ edit ] combinatoria enumerativa

Cinco árboles binarios en tres vértices , un ejemplo de números catalanas .

Combinatoria enumerativa es la zona más clásica de la combinatoria, y se centra en contar el número de ciertos objetos combinatorios. Aunque contar el número de elementos en un conjunto es un lugar amplio de problemas matemáticos , muchos de los problemas que surgen en las aplicaciones tienen una descripción combinatoria relativamente simple. números de Fibonacci es el ejemplo básico de un problema en combinatoria enumerativa. El camino doce veces proporciona un marco unificado para contar permutaciones , combinaciones y particiones .

[ edit ] combinatoria analíticos

Combinatoria analíticos se refiere a la enumeración de las estructuras combinatorias utilizando herramientas de análisis complejo y teoría de la probabilidad . En contraste con combinatoria enumerativa que utiliza fórmulas explícita combinatoria y funciones generatrices para describir los resultados, combinatoria analíticos se propone obtener fórmulas asintótica .

[ editar ] Teoría de reparto

Teoría de particiones estudia enumeración diversos problemas relacionados con asintóticas particiones enteras , y está estrechamente relacionada con la q-series , funciones especiales y polinomios ortogonales . Originalmente una parte de la teoría de números y análisis , ahora se considera una parte de la combinatoria o un campo independiente. Se incorpora el enfoque biyectiva y diversas herramientas en el análisis, la teoría analítica de números , y tiene conexiones con la mecánica estadística .

[ editar ] La teoría de grafos

Los gráficos son objetos básicos de combinatoria. El rango de preguntas de contar (por ejemplo, el número de gráficos de n vértices con bordes k) a estructurales (por ejemplo, que contienen gráficos de los ciclos hamiltonianos) a cuestiones algebraicas (por ejemplo, dado un grafo G y dos números x e y, ¿el Tutte polinomio G T (x, y) tiene una interpretación combinatoria?). Cabe señalar que si bien existen conexiones muy fuertes entre la teoría de grafos y combinatoria, estos dos son a veces considerados como temas separados. [10]

[ editar ] La teoría del diseño

La teoría del diseño es un estudio de diseños combinatorios , que son colecciones de subconjuntos con ciertas intersecciones propiedades. diseños de bloque son diseños combinatorios de un tipo especial. Esta zona es una de las partes más antiguas de la combinatoria, como en el problema colegiala Kirkman propuesto en 1850. La solución del problema es un caso especial de un sistema de Steiner , que los sistemas juegan un papel importante en la clasificación de grupos finitos simples . La zona cuenta con nuevas conexiones a la combinatoria y teoría de códigos geométricos.

[ edit ] Finite geometría

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 geometrías continuas ( plano euclídeo , espacio proyectivo real , etc), pero definidos combinatoria son los principales puntos estudiados. Esta zona ofrece una rica fuente de ejemplos para la teoría del Diseño . No se debe confundir con geometría discreta ( geometría combinatoria ).

[ editar ] Teoría del pedido

Diagrama de Hasse de la powerset de {x, y, z} ordenado por la inclusión .

Teoría de la orden es el estudio de conjuntos parcialmente ordenados , tanto finitas e infinitas. Varios ejemplos de órdenes parciales aparecen en álgebra , geometría teoría de números, ya lo largo de la combinatoria y teoría de grafos. Clases notables y ejemplos de órdenes parciales incluyen celosías y álgebras de Boole .

[ editar ] Teoría Matroid

Matroid teoría abstrae parte de la geometría . Se estudian las propiedades de los conjuntos (por lo general, conjuntos finitos) de los vectores en un espacio vectorial que no dependen de los coeficientes determinados en una dependencia lineal relación. No sólo la estructura, sino también las propiedades enumerativos pertenecen a la teoría matroide. Teoría Matroid se introdujo por Hassler Whitney y estudiado como una parte de la teoría de la orden. Es ahora un campo independiente de estudio con un número de conexiones con otras partes de la combinatoria.

[ editar ] combinatoria Extremal

Combinatoria extremal Extremal estudia las preguntas sobre los sistemas establecidos . Los tipos de preguntas abordadas en este caso se refieren a la mayor gráfica posible que satisface ciertas propiedades. Por ejemplo, el más grande sin triángulos gráfico de 2n vértices es un grafo bipartito completo K n, n. A menudo es muy difícil incluso encontrar la respuesta extremal f (n) exactamente y uno sólo puede dar una estimación asintótica .

Ramsey teoría es otra parte de la combinatoria extremal. Declara que toda suficientemente grande configuración contendrá algún tipo de orden. Se trata de una generalización avanzada del principio del palomar .

[ editar ] combinatoria probabilistas

En combinatoria probabilistas, las preguntas son del tipo: ¿cuál es la probabilidad de que una determinada propiedad de un objeto aleatoria discreta, como un grafo aleatorio ? Por ejemplo, ¿cuál es el número medio de triángulos en un grafo aleatorio? Métodos probabilísticos se utilizan también para determinar la existencia de objetos combinatorios con ciertas propiedades establecidos (por ejemplos explícitos que podría ser difícil de encontrar), simplemente mediante la observación de que la probabilidad de seleccionar aleatoriamente un objeto con esas propiedades es mayor que 0. Este enfoque (a menudo referido como el método probabilístico ) resultó altamente eficaz en aplicaciones a la combinatoria extremal y la teoría de grafos. Un área estrechamente relacionado es el estudio de finitos cadenas de Markov , especialmente sobre objetos combinatorios. Herramientas aquí de nuevo probabilísticos se utilizan para estimar el tiempo de mezclado .

A menudo se asocia con Paul Erdös , quien hizo el trabajo pionero sobre el tema, la combinatoria probabilistas fue visto tradicionalmente como un conjunto de herramientas para el estudio de problemas en otras partes de la combinatoria. Sin embargo, con el crecimiento de las aplicaciones de análisis de algoritmos en la informática , así como la probabilidad clásica, aditivo y la teoria de probabilidades , el área hace poco creció hasta convertirse en un campo independiente de la combinatoria.

[ editar ] combinatoria algebraica

Diagrama de Young de una partición (5,4,1).

Combinatoria algebraica es un área de las matemáticas que emplea métodos de álgebra abstracta , en particular la teoría de grupos y teoría de la representación , en diversos contextos combinatorias y, por el contrario, aplica técnicas combinatorias a los problemas de álgebra . En la última década más o menos, la combinatoria algebraica llegó a ser vista más expansivo como el área de las matemáticas, donde la interacción de los métodos combinatorios y algebraicos es particularmente fuerte y significativo. Uno de los de más rápido desarrollo en los subcampos combinatoria algebraica es álgebra conmutativa combinatoria .

[ edit ] Combinatoria de palabras

Construcción de una palabra Thue-Morse infinito .

Combinatoria de palabras se ocupa de los lenguajes formales . Surgió de forma independiente en varias ramas de las matemáticas, incluyendo la teoría de números , teoría de grupos y probabilidad . Tiene aplicaciones a la combinatoria enumerativa, análisis fractal , ciencias de la computación teórica , la teoría de autómatas y la lingüística . Mientras que muchas aplicaciones son nuevas, el clásico Chomsky-Schützenberger jerarquía de clases de gramáticas formales es quizás el mejor resultado conocido en el campo.

[ editar ] combinatoria geométrica

Un icosaedro .

Combinatoria geométrica está relacionada a convexo y geometría discreta , en particular combinatoria poliédricos . Se pregunta, por ejemplo, cuántos rostros de cada dimensión puede un politopo convexo tiene. métricas propiedades de politopos jugar un papel importante también, por ejemplo, el teorema de Cauchy en la rigidez de politopos convexos. Politopos especiales también se consideran como permutohedra , associahedra y politopos Birkhoff . Debemos tener en cuenta que la geometría combinatoria es un nombre antiguo para la geometría discreta.

[ editar ] combinatoria topológicos

División de un collar con dos cortes.

Análogos combinatorias de los conceptos y métodos de la topología se utiliza para estudiar coloración de grafos , división justa , particiones , conjuntos parcialmente ordenados , árboles de decisión , problemas de collar y discreto teoría de Morse . No se debe confundir con topología combinatoria que es un nombre antiguo para la topología algebraica .

[ editar ] combinatoria aritméticas

Combinatoria aritméticos surgieron de la interacción entre la teoría de números , la combinatoria, teoría ergódica y análisis armónico . Se trata de estimaciones combinatorios asociados con las operaciones aritméticas (suma, resta, multiplicación y división). Combinatoria aditivos se refiere al caso especial en que sólo las operaciones de suma y resta están involucradas. Una técnica importante en combinatoria aritmética es la teoría ergódica de sistemas dinámicos .

[ edit ] combinatoria Infinitary

Infinitary combinatoria o la teoría de conjuntos, combinatoria es una extensión de las ideas en la combinatoria a conjuntos infinitos. Es una parte de la teoría de conjuntos , un área de la lógica matemática , sino que utiliza las herramientas y las ideas de la teoría de conjuntos y combinatoria extremal ambos.

Gian-Carlo Rota utiliza la combinatoria nombre continuas [11] para describir la probabilidad y la teoría de la medida , ya que hay muchas analogías entre el conteo y medida.

[ edit ] campos relacionados

[ edit ] optimización combinatoria

Optimización combinatoria es el estudio de optimización en objetos discretos y combinatoria. Comenzó como una parte de la combinatoria y teoría de grafos, pero ahora se ve como una rama de las matemáticas aplicadas y ciencias de la computación, en relación con la investigación de operaciones , teoría de algoritmos y teoría de la complejidad computacional .

[ editar ] La teoría de codificación

Codificación teoría que empezó como una parte de la teoría del diseño con las primeras construcciones combinatorias de códigos correctores de errores . La idea principal de la asignatura es diseñar métodos eficientes y confiables de transmisión de datos. Es ahora un gran campo de estudio, una parte de teoría de la información .

[ editar ] geometría discreta y computacional

Geometría discreta (también llamada geometría combinatoria) también comenzó una parte de la combinatoria, con los primeros resultados sobre politopos convexos y números de besos . Con la aparición de las aplicaciones de la geometría discreta a la geometría computacional , estos dos campos parcialmente fusionados y se convirtió en un campo de estudio. Quedan muchas conexiones con la combinatoria geométrica y topológica, que a su vez se pueden ver como excrecencias de la geometría discreta temprano.

[ edit ] Combinatoria y sistemas dinámicos

Aspectos combinatorios de sistemas dinámicos es otro campo emergente. Aquí sistemas dinámicos se pueden definir en objetos combinatorios. Véase por ejemplo el sistema gráfico dinámico .

[ edit ] Combinatoria y la física

Existen interacciones crecientes entre la combinatoria y la física , en particular 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 las cromáticas y polinomios de Tutte en la otra mano.

[ editar ] Véase también

[ editar ] Notas

  1. ^ Björner y Stanley, p. 2
  2. ^ RP Stanley ", Hiparco, Plutarco, Schröder y Hough", Amer. Math. 104 mensuales (1997), no. 4, 344-350.
  3. ^ L. Habsieger, M. Kazarian, S. Lando, en el segundo número de Plutarco, Amer. Math. Mensual 105 (1998), no. 5, 446.
  4. ^ O'Connor, John J. ; Robertson, Edmund F. , "Combinatoria" , Historia de las Matemáticas MacTutor archivo , de la Universidad de St Andrews , http://www-history.mcs.st-andrews.ac.uk/Biographies/ Mahavira.html .
  5. ^ Puttaswamy, TK (2000), "Las contribuciones matemáticas de los antiguos matemáticos indios" , en Selin, Helaine, Matemáticas Across Cultures: La Historia de las Matemáticas no occidentales, Países Bajos: Kluwer Academic Publishers, p.
  6. ^ NL Biggs, Las raíces de la combinatoria, Historia Mathematica 6 (1979), 109-136.
  7. ^ Historia de la Combinatoria , capítulo de un libro de texto.
  8. ^ Arthur T. White, "Zumbido las clases laterales", Amer. Math. Mensual 94 (1987), no. 8, 721-746; Arthur T. White, "Fabian Stedman: El teórico del primer grupo,?" Amer. Math. Mensual 103 (1996), no. 9, 771-778.
  9. ^ Vea Revistas en Combinatoria y campos relacionados y conferencias en la Combinatoria
  10. ^ 2-Digit MSC comparación , por Daniel P. Sanders.
  11. ^ combinatoria continuos y profinito

[ editar ] Referencias

[ editar ] Enlaces externos