La combinatoria ye una caña de la matemática perteneciente al área de matemátiques discretes qu'estudia la enumeración, construcción y esistencia de propiedaes de configuraciones que satisfaen ciertes condiciones establecíes. Amás, estudia les ordenaciones o agrupaciones d'un determináu númberu d'elementos.
Los aspeutos de la combinatoria inclúin cuntar les estructures d'un tipu y tamañu dau (combinatories enumerativas), decidir cuándo pueden cumplise ciertos criterios y construyir y analizar oxetos que cumplan los criterios (como nos diseños combinatorios y la teoría de matroides) atopar oxetos "más grandes", "más pequeños" o "óptimos" (combinatoria estrema y optimización combinatoria), estudiar estructures combinatories surdíes nun contestu alxebraicu, o aplicar téuniques alxebraiques a problemes combinatorios (combinatoria alxebraica).
Los problemes combinatorios surden en munches árees de la matemática pura, especialmente en álxebra, teoría de probabilidaes, topoloxía y xeometría, y la combinatoria tamién tien munches aplicaciones na optimización matemática, la informática, la teoría ergódica y la física estadística.
Munches cuestiones combinatoriales fueron históricamente consideraes aislladamente, dando una solución fayadiza a un problema que surde en dalgún contestu matemáticu. A finales del sieglu XX, sicasí, desenvolviéronse métodos teóricos poderosos y xenerales, convirtiendo la combinatoria nuna caña independiente de les matemátiques por derechu propiu. Una de les partes más antigües y accesibles de la combinatoria ye la teoría de grafos, que tamién tien numberoses conexones naturales a otres árees. La combinatoria utilizar con frecuencia n'informática pa llograr fórmules y estimaciones nel analís d'algoritmos.
== Combinaciones ensin repetición Dau un conxuntu de n elementos estremables, llámase combinación ensin repetición de p elementos, con p < n, escoyíos ente los n, a cualquier subconxuntu de p elementos distintos del conxuntu.
El númberu de combinaciones ensin repetición de p elementos escoyíos ente los n nótase davezu
.
Exemplu
Un estudiante tien de responder a seis de les diez preguntes de les que consta un exame, ¿ente cuántos grupos d'entrugues distintes puede escoyer?
Trátase de determinar el númberu de grupos distintos de seis preguntes escoyíes del conxuntu de los diez, sabiendo que dos grupos coles mesmes entrugues, entá en distintu orde, coinciden. Nesti casu, el númberu de grupos d'entrugues distintos ente los que puede escoyese ye
== Combinaciones con repetición Dau un conxuntu de n elementos estremables, llámase combinación con repetición de p elementos escoyíos ente los n a cualquier coleición de p elementos del conxuntu, con repeticiones eventuales de dalgunos d'ellos.
El númberu de combinaciones con repetición de p elementos escoyíos ente los n nótase davezu
Exemplu
¿De cuántes formes pueden escoyese simultáneamente tres boles d'una urna na qu'hai siquier tres boles blanques y trés negres indistinguibles?
Cada grupu ye una disposicion non ordenar de trés colores formada polos colores blancu y negru con repeticion de dalgún d'ellos. Por tanto, trátase de determinar el númberu de grupos de tres elementos non ordenar. Nesti casu, el númberu de formes distintes d'escoyer simultáneamente tres boles del conxuntu ye
Historia
Los conceutos básicos sobre la combinatoria y los resultaos enumerativos apaecieron a lo llargo del mundu antiguu. Nel sieglu 6 AC, na antigua India, el médicu Sushruta asegura nel Susruta-samhita que ye posible formar 63 combinaciones a partir de 6 sabores distintos, tomaos ún per ún, de dos en dos, etc., asina calculando toles 2⁶ − 1 posibilidaes . El historiador griegu Plutarcu aldericó con Crisipo de Solos (3ᵉʳ sieglu AC) y Hiparco de Nicea (2º sieglu AC) sobre un problema enumerativo un tanto delicáu, el cuál demostróse más palantre que guardaba rellación col númberu Schröder–Hiparcos.Stanley, Richard P.; "Hipparchus, Plutarch, Schröder, and Hough", American Mathematical Monthly 104 (1997), num. 4, 344–350.Habsieger, Laurent; Kazarian, Maxim; y Lando, Sergei; "On the Second Number of Plutarch", American Mathematical Monthly 105 (1998), num. 5, 446.
Na Edá Media, la combinatoria siguió siendo estudiada, sobre manera fuera de la civilización Europea. El matemáticu indiu Mahāvīra (c. 850) acuñó una fórmula pal númberu de permutaciones y combinaciones, y ye posible qu'estes fórmules yá resultaren familiares a los matemáticos indios a principios del sieglu 6 DC. El filósofu y astrónomu Rabbi Abraham ibn Ezra (c. 1140) estableció la simetría de los coeficientes binomiales, ente que una fórmula concreta foi topada más palantre pol talmudista y matemáticu Gersónides, en 1321.. (Traducción de la edición Rusa de 1967) El triángulu aritméticu— una diagrama gráficu amosando les rellaciones ente los coeficientes binomiales— yá apaeciera en trataos matemáticos tan tras como'l sieglu 10, y col tiempu seríen meyor conocíos como'l Triángulu de Pascal.
Mientres el Renacimientu, xunto al restu de les matemátiques y les ciencies, la combinatoria esfrutó d'un renacer. Trabayos de Pascal, Newton, Jacob Bernoulli y Euler volviéronse fundamentales nel emerxente campu. Nos tiempos modernos, los trabayos de J. J. Sylvester (a finales del sieglu 19) y Percy MacMahon (a principios del sieglu 20) ayudaron a asitiar les bases pa la combinatoria enumerativa y combinatoria algebráica. La teoría de grafos tamién esfrutó d'una esplosión d'interés coles mesmes, cuantimás conexón col teorema de los cuatro colores.
Na segunda metá del sieglu 20, la combinatoria sufrió una crecedera rápida, que llevó al establecimientu de docenes de nuevos diarios y conferencies sobre esta tema.Vease Journals in Combinatorics and Graph Theory En parte, la crecedera foi aguiyáu poles nuevu conexones y aplicaciones n'otros campos, dende álxebra hasta probabilidaes, dende'l analís funcional a la teoría de númberos, etc. Estes conexones terminaron per romper los cantos ente la combinatoria y partes de la matemática y la informática teórica, pero coles mesmes causó cierta fragmentación dientro del campu.
Árees de la combinatoria Nun esiste una clasificación tayante de lo que constitúi una subárea, sinón que toes comparten ciertu grau de traslape ente sigo, al igual que con otres cañes de la matemática discreta. Distintos autores proponen delles divisiones de la combinatoria polo que cualquier llistáu ye puramente indicativu. Por casu, dellos autores consideren la teoría de grafos como una subárea de la combinatoria, ente qu'otros considerar un área independiente.
Ente les subdivisiones más comunes atópense les siguientes.
Combinatoria enumerativa La combinatoria enumerativa ye l'área más clásica de la combinatoria y concéntrase en cuntar el númberu de ciertos oxetos combinatorios. Anque cuntar el númberu d'elementos nun conxuntu ye un problema matemáticu bastante ampliu, munchos de los problemes que surden nes aplicaciones tienen una descripción combinatoria relativamente simple. Los númberos de Fibonacci son l'exemplu básicu d'un problema na combinatoria enumerativa. La forma de doce veces mayor apurre un marcu unificáu pa cuntar les permutaciones, combinaciones y particiones. Combinatoria analítica La combinatoria analítica referir a la enumeración d'estructures combinatories utilizando ferramientes d'analís complexu y teoría de probabilidaes. En contraste cola combinatoria enumerativa, qu'utiliza fórmules combinatories esplícites y funciones xeneradores pa describir los resultaos, la combinatoria analítica tien como oxetivu llograr fórmules asintóticas. Teoría de la partición La teoría de la partición estudia distintos problemes asintóticos y numberales rellacionaos con particiones enteres, y ta estrechamente rellacionada coles series , funciones especiales y polinomios ortogonales. Orixinalmente yera una parte de la teoría numbérica y l'analís, agora considérase una parte de la combinatoria o un campu independiente. Incorpora l'enfoque biyectivo y diverses ferramientes n'analises y teoría analítica de númberos, y tien conexones cola mecánica estadística.
Teoría de grafos Los grafos son oxetos básicos na combinatoria. Les entrugues van dende'l recuentu (por casu, el númberu de grafos en n vértices con cantos k) hasta estructurales (por casu, qué grafos contienen ciclos hamiltonianos) a entrugues alxebraiques (por casu, dau un grafo G y dos númberos x y y, ¿el "Polinomiu Tutte" TG (x, y) tien una interpretación combinatoria?). Cabo señalar que, magar hai conexones bien fuertes ente la teoría de los grafs y la combinatoria, dacuando estos dos considérense suxetos separaos. Esto debe al fechu de qu'ente que los métodos combinatorios aplicar a munchos problemes de teoría de grafos, los dos utilícense xeneralmente pa buscar soluciones a distintos problemes. Teoría del diseñu La teoría del diseñu ye un estudiu de diseños combinatorios, que son coleiciones de subconxuntos con ciertes propiedaes d'intersección. Los diseños de bloques son diseños combinatorios d'un tipu especial. Esta área ye una de les partes más antigües de la combinatoria, como nel problema de la escolina de Kirkman propuestu en 1850. La solución del problema ye un casu especial d'un sistema Steiner, que los sos sistemes xueguen un papel importante na clasificación de grupos finitos simples. L'área tien conexones adicionales cola teoría de la codificación y la combinatoria xeométrica. Xeometría finita La xeometría finita ye l'estudiu de sistemes xeométricos que tienen namái un númberu finito de puntos. Los principales elementos estudiaos son estructures análogues a les atopaes en xeometríes continues (planu euclidianu, espaciu proyectivo real, etc.) pero definíes combinatorialmente. Esta área apurre una rica fonte d'exemplos pa la teoría del diseñu. Nun tien de confundir se cola xeometría discreta (xeometría combinatoria). Teoría del orde La teoría del orde ye l'estudiu de conxuntos parcialmente ordenaos, tanto finitos como infinitos. Na álxebra, la xeometría, la teoría de númberos y en tola teoría combinatoria y gráfica apaecen dellos exemplos d'ordes parciales. Delles clases notables y exemplos d'ordes parciales inclúin redes y álxebres booleanas. Teoría del matroide La teoría del matroide abstrae parte de la xeometría. Estudia les propiedaes de conxuntos (xeneralmente, conxuntos finitos) de vectores nun espaciu vectorial que nun dependen de los coeficientes particulares nuna rellación de dependencia llinial. Non yá la estructura sinón tamién les propiedaes enumerativas pertenecen a la teoría del matroide. La teoría del matroide foi introducida por Hassler Whitney y estudiada como parte de la teoría del orde. Agora ye un campu d'estudiu independiente con una serie de conexones con otres partes de la combinatoria. Combinatoria estrema La combinatoria estrema estudia les entrugues estremes sobre los sistemes de conxuntos. Los tipos d'entrugues encetaes nesti casu son sobre'l mayor grafo posible que satisfai ciertes propiedaes. Por casu, el mayor grafo llibre de triángulos en 2n vértices ye un grafo bipartitu completu Kn, n. De cutiu ye demasiáu difícil inclusive p'atopar la respuesta estrema f (n) esautamente y namái puede dase una estimación asintótica.La teoría de Ramsey ye otra parte de la combinatoria estrema. Indica que cualesquier configuración abondo grande va contener dalgún tipu d'orde. Ye una xeneralización avanzada del principiu del palombar. Combinatoria probabilítica