Ver la fonte de Combinatoria

{{referencies|t=20170323|matemátiques}}
La '''combinatoria''' ye una caña de la [[matemátiques|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 [[matroide]]s) 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'[[algoritmu|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 

<math>C^{n}_p=\binom{n}{p} = \frac{n!}{p!(n-p)!}</math> .

'''Exemplu'''

Un estudiante tien de responder a seis de los 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 

<math>C^{10}_{6}=\binom{10}{6} = \frac{10!}{6!4!} = 210 </math>

== 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 

<math>CR^{p}_n= C^{p}_{n+p-1}=\binom{n+p-1}{p} = \frac{(n+p-1)!}{p!(n-1)!}</math>

'''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 

<math>CR^{3}_{2}=\binom{4}{3} = \frac{4!}{3!1!} = 4 </math>

== Historia ==

Los conceutos básicos sobre la combinatoria y los resultaos enumerativos apaecieron a lo llargo del [[Edá antigua|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⁶&nbsp;&minus;&nbsp;1 posibilidaes {{ensin referencies}}. El [[historiador]] [[Antigua Grecia|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]].<ref>[[Richard P. Stanley|Stanley, Richard P.]]; "Hipparchus, Plutarch, Schröder, and Hough", ''American Mathematical Monthly'' '''104''' (1997), num. 4, 344–350.</ref><ref>Habsieger, Laurent; Kazarian, Maxim; y Lando, Sergei; "On the Second Number of Plutarch", ''American Mathematical Monthly'' '''105''' (1998), num. 5, 446.</ref>

Na [[Edá Media]], la combinatoria siguió siendo estudiada, sobremanera fora de la [[Cultura d'Europa|civilización Europea]]. El matemáticu [[India|indiu]] [[Mahāvīra (matemáticu)|Mahāvīra]] (c. 850) acuñó una fórmula pal númberu de [[permutacion]]es y [[combinacion]]es,<ref>{{MacTutor | id=Mahavira}}</ref><ref>{{Citation |last=Puttaswamy |first=Tumkur K. |contribution= The Mathematical Accomplishments of Ancient Indian Mathematicians |editor-last=Selin |editor-first=Helaine |títulu=Mathematics Across Cultures: The History of Non-Western Mathematics |publisher=Kluwer Academic Publishers |location=Netherlands |url=https://books.google.com/books?id=2hTyfurOH8AC&printsec=frontcover#v=onepage&q&f=false |añu=2000 |isbn=978-1-4020-0260-1 |page=417 <!-- pages 409–422 -->}}</ref> y ye posible qu'estes fórmules yá resultaren familiares a los matemáticos indios a principios del sieglu 6 DC.<ref>{{cita publicación | last1 = Biggs | first1 = Norman L. | añu = 1979 | títulu = The Roots of Combinatorics | url = | journal = Historia Mathematica | volume = 6 | issue = | pages = 109–136 | doi=10.1016/0315-0860(79)90074-0}}</ref> 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 [[talmud]]ista y [[matemáticu]] [[Gersónides]], en 1321.<ref>{{citation|títulu=Probability Theory: A Historical Sketch|first=L. Y.|last=Maistrov|publisher=Academic Press|añu=1974|isbn=9781483218632|url=https://books.google.com/books?id=2ZbiBQAAQBAJ&pg=PA35|page=35}}. (Traducción de la edición Rusa de 1967)</ref>
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 [[ciencia|ciencies]], la combinatoria esfrutó d'un renacer. Trabayos de [[Blaise Pascal|Pascal]], [[Isaac Newton|Newton]], [[Jacob Bernoulli]] y [[Leonhard Euler|Euler]] volviéronse fundamentales nel emerxente campu. Nos tiempos modernos, los trabayos de [[James Joseph Sylvester|J. J. Sylvester]] (a finales del sieglu 19) y [[Percy Alexander MacMahon|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.<ref>Vease [http://www.math.iit.edu/~kaul/Journals.html#CGT Journals in Combinatorics and Graph Theory]</ref> 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 l'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 una á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===
Na combinatoria probabilística, les entrugues son del tipu siguiente: ¿cuál ye la probabilidá d'una cierta propiedá pa un oxetu aleatoriu discretu, tal como un grafo al azar? Por casu, ¿cuál ye'l númberu permediu de triángulos nun grafo al azar? Los métodos probabilísticos tamién s'utilicen pa determinar la esistencia d'oxetos combinatorios con ciertes propiedaes prescrites (pa les cualos pueden ser difíciles d'atopar exemplos esplícitos), a cencielles reparando que la probabilidá d'escoyer aleatoriamente un oxetu con eses propiedaes ye mayor que 0. Esti enfoque (de cutiu referíu como'l métodu probabilístico) demostró ser altamente eficaz n'aplicaciones a la combinatoria extremal y a la teoría de los grafos. Un área estrechamente rellacionada ye l'estudiu de cadenes de Markov finitas, especialmente n'oxetos combinatorios. Equí tamién s'utilicen ferramientes probabilísticas pa envalorar el tiempu d'entemecíu.
A menuda asociada con Paul Erdős, que fixo'l trabayu pioneru na tema, la combinatoria probabilística foi vista tradicionalmente como un conxuntu de ferramientes pa estudiar problemes n'otres partes de la combinatoria. Sicasí, cola crecedera de les aplicaciones pal analís d'algoritmos na informática, según la probabilidá clásica, la teoría aditiva y probabilística de númberu, l'área creció apocayá pa convertise nun campu independiente de la combinatoria.
===Combinatoria alxebraica===
La combinatoria alxebraica ye una área de matemátiques qu'emplega métodos d'álxebra astracta, notablemente teoría de grupu y teoría de representación, en dellos contestos combinatorios y, a la inversa, aplica téuniques combinatories a problemes n'álxebra. La combinatoria alxebraica ta de cutio espandiendo'l so algame, tantu en temes como en téuniques, y puede ser vista como l'área de matemátiques onde la interacción de métodos combinatorios y alxebraicos ye particularmente fuerte y significativa.
===Combinatoria de pallabres===
La combinatoria de pallabres trata de llinguaxes formales. Plantegar de forma independiente dientro de delles cañes de les matemátiques, incluyendo la teoría de númberos, la teoría de grupos y la probabilidá. Tien aplicaciones a la combinatoria enumerativa, al analís fractal, a la informática teórica, a la teoría de los autómates yá la llingüística. Anque munches aplicaciones son nueves, la xerarquía clásica de clases de gramátiques formales de Chomsky-Schützenberger ye quiciabes la resultancia más conocida nel campu.
===Combinatoria xeométrica===
La combinatoria xeométrica ta rellacionada cola xeometría convexo y discretosobremanera la combinatoria poliédrica. Pregúntase, por casu, cuántes cares de cada dimensión puede tener un politopo convexu. Les propiedaes métriques de los politopos xueguen tamién un papel importante. Por casu: el teorema de Cauchy sobre la rixidez de los politopos convexos. Tamién se consideren politopos especiales, como'l permutohedra, el associahedra y los politopos de Birkhoff. Tenemos De tener en cuenta que la xeometría combinatoria ye un nome anticuáu pa la xeometría discreta.
===Combinatoria topolóxica===
Los análogos combinatorios de conceutos y métodos en topoloxía usar pa estudiar dibuxu gráficu, división xusta, particiones, conxuntos parcialmente ordenaos, árboles de decisión, problemes de collar y teoría de Morse discreta. Nun tien de confundir se cola topoloxía combinatoria que ye un nome antiguu pa la topoloxía alxebraica.
===Combinatoria aritmética===
La combinatoria aritmética surdió de la interacción ente la teoría numbérica, la combinatoria, la teoría ergódica y l'analís harmónicu. Trátase d'estimaciones combinatories asociaes con operaciones aritmétiques (adición, sustracción, multiplicación y división). La combinatoria aditiva referir al casu especial cuando namái tán arreyaes les operaciones de suma y resta. Una téunica importante na combinatoria aritmética ye la teoría ergódica de los sistemes dinámicos.
===Combinatoria infinita===
La combinatoria infinita, o teoría de conxuntos combinatoria, ye una estensión d'idees en combinatoria a conxuntos infinitos. Ye una parte de la teoría de conxuntos, una área de lóxica matemática, pero utiliza ferramientes ya idees tanto de la teoría de conxuntos como de la combinatoria estrema. Gian-Carlo Rota usó'l nome de combinatoria continua pa describir la probabilidá xeométrica, yá que hai munches analoxíes ente'l recuentu y la midida.

== Combinatoria enumerativa ==
La '''combinatoria enumerativa''' o '''enumeración''' estudia los métodos pa cuntar (numberar) les distintes configuraciones de los elementos d'un [[conxuntu]] que cumplan ciertos criterios especificaos. 
 
Ésta foi una de les primeres árees de la combinatoria en ser desenvuelta, y como otres árees más recién estúdiense namái en cursos especializaos, ye común que se faiga referencia a esta subárea cuando se menta ''combinatoria'' en redolaes escolares.

En tou problema combinatoriu hai dellos conceutos claves que tenemos d'estremar:

* '''1. Población:'''
Llámase asina al conxuntu de los elementos que tamos estudiando. Vamos Designar con una '''m''' al númberu d'elementos del conxuntu.

* '''2. Amuesa:'''
Trátase d'un subconxuntu de la población. va denominar cola lletra '''n''' al númberu d'elementos que formen la muestra.

Los tipos de la muestra vienen determinaos por dos aspeutos:

'''Orde'''

Determina si ye importante o non que los elementos de la muestra apaezan ordenaos.

'''Repetición''' 

La posibilidá de repetición o non de los elementos.

;Exemplu.
¿De cuántes formes puede llograse 8 al tirar 2 dados?

Imaxina que queremos cuntar de cuantes formes puede llograse 8 al tirar un par de dados. Unu puede realizar el clásicu diagrama de coordenaes:

Y concluyir qu'hai 5 formes de llograr el 8. Col mesmu diagrama, podemos atopar la resultancia f(k) pa cualesquier suma k:

f(2)=1, f(3)=2, f(4)=3, f(5)=4, f(6)=5, f(7)=6, f(8)=5, f(9)=4, f(10)=3, f(11)=2, f(12)=1.

Pero ¿qué pasa si queremos tirar trés daos? ¿cinco daos? ¿20 dados? ¿m daos? Yá nun ye práuticu usar la representación de coordenaes, precisamos un nuevu modelu.

Consideremos namái un dadu. ¿De cuantes formes podemos llograr el valor k? Pos de 1 forma si k=1,2,3,4,5,6 y 0 de cualesquier otra forma. Vamos a codificar toles resultaos posibles nuna única espresión:
a + <math> \, a^{2} </math> + <math> \, a^{3} </math> + <math> \, a^{4} </math> + <math> \, a^{5} </math> + <math> \, a^{6} </math>

Ente les cuentes, puede perder unu de puntu de vista la idea central: tamos representando una socesión de dellos valores (formes de tirar un dadu) por aciu un solu oxetu alxebraicu (un poliomio), y manipulaciones con esti oxetu dannos información alrodiu de la combinatoria del problema.

El métodu puede modificar pa resolver problemes similares (por casu, si quixéramos saber de cuántes formes puede llograse 30 al tirar 3 dados normales y dos daos en forma d'icosaedru, intentaríamos atopar el coeficiente de <math> \, a^{30} </math> nel desenvolvimientu de (a + <math> \, a^{2} </math> + <math> \, a^{3} </math> + <math> \, a^{4} </math> + <math> \, a^{5} </math> + <math> \, a^{6} </math>)<math> \, ^{3} </math> · (a + <math> \, a^{2} </math> + <math> \, a^{3} </math> + ... + <math> \, a^{20} </math>)<math> \, ^{2} </math>

Este ye un casu particular del métodu de funciones xeneradores, nel qu'una serie de potencies representa una cantidá (posiblemente infinita) de valores d'una socesión.

; Exemplu.
Considérese'l conxuntu <math>S=\{A, E, I, O, U\}</math>. Podemos imaxinar qu'estos elementos correspuenden a tarxetes dientro d'un sombreru. 
* Un primer problema podría consistir en topar el númberu de formes distintes en que podemos sacar les tarxetes una dempués d'otra (esto ye, el númberu de [[permutación|permutaciones]] del conxuntu).
: Por casu, dos formes distintes podríen ser: ''EIAOU'' o ''OUAIE''. 
* Dempués, puede preguntar pol númberu de formes en que puede sacase namái 3 tarxetes del sombreru (esto ye, el númberu de 3-permutaciones del conxuntu).
: Nesti casu, exemplos pueden ser ''IOU'', ''AEI'' o ''EAI''.
* Tamién puede preguntar sobre cuálos son los posibles grupos de 3 tarxetes que pueden estrayese, ensin dar considerancia al orde en que salen (n'otres pallabres, el valor d'un [[coeficiente binomial]]). 
: Equí, consideraríamos ''AOU'' y ''UAO'' como una mesma resultancia.
* Otru problema consiste en topar el númberu de formes en que pueden salir 5 tarxetes, una tres otra, pero en cada momentu tórnase la tarxeta escoyida al sombreru. 
: Nesti problema los resultaos posibles podríen ser ''EIOUO'', ''IAOEU'' o ''IEAEE''.

La combinatoria enumerativa estudia les téuniques y métodos que dexen resolver problemes anteriores, según otros más complexos, cuando'l númberu d'elementos del conxuntu ye arbitrariu. D'esta forma, nel primer exemplu la xeneralización correspondiente ye determinar el númberu de formes en que pueden ordenar tolos elementos d'un conxuntu con ''n'' elementos, siendo la respuesta'l [[factorial]] de ''n''.

== Combinatoria extremal ==
L'enfoque equí ye determinar qué tan grande o pequeña ten de ser una coleición d'oxetos por que satisfaiga una condición primeramente establecida; 

; Exemplu.
Considérese un conxuntu ''S''. con ''n'' elementos. De siguío empiézase a faer un llistáu de subconxuntos de tal manera que cualquier pareya de subconxuntos del llistáu tenga dalgún elementu de mancomún. 

Pa esclariar, seya <math>S=\{A, B, C, D\}</math> y un posible llistáu de subconxuntos podría ser
:: <math>\{B, C\}, \{A, B\}, \{A, B, C, D\}, \{B, D\}, \ldots</math>
Conforme aumenta'l llistáu (y yá que hai una cantidá [[finita]] d'opciones), el procesu faise cada vez más complicáu. Por casu, nun podríamos añader el conxuntu {''A'', D''} al llistáu pos anque tien elementos de mancomún colos postreros 3 subconxuntos del llistáu, nun comparte nengún elementu col primeru.

La entruga sobre qué tan grande puede faese'l llistáu de forma que cualquier pareya de subconxuntos tenga un elementu de mancomún ye un exemplu de problema de combinatoria extremal (o combinatoria estrema). La respuesta a esti problema ye que si'l conxuntu orixinal tien ''n'' elementos, entós el llistáu puede tener a lo más <math>2^{n-1}</math> subconxuntos.

==Campos rellacionaos==
===Optimización combinatoria===
La optimización combinatoria ye l'estudiu de la optimización d'oxetos discretos y combinatorios. Empezó como parte de la teoría combinatoria y la teoría de grafos, pero agora vese como una caña de la matemática aplicada y l'informática, rellacionada cola investigación d'operaciones, la teoría d'algoritmos y la teoría de la complexidá computacional.
===Teoría de la codificación===
La teoría de la codificación empezó como parte de la teoría del diseñu con construcciones combinatoriales tempranes de códigos correutores d'errores. La idea principal de la tema ye diseñar métodos eficientes y confiables de tresmisión de datos. Agora ye un gran campu d'estudiu, parte de la teoría de la información.
===Xeometría discreta y computacional===
La xeometría discreta (tamién llamada xeometría combinatoria) tamién empezó como una parte de la combinatoria, con resultaos tempranes en politopos convexos y "númberos cercanos". Cola apaición d'aplicaciones de xeometría discreta a la xeometría computacional, estos dos campos fundiéronse parcialmente y convirtiéronse nun campu d'estudiu independiente. Siguen esistiendo munches conexones con combinatories xeométriques y topolóxiques, que pueden ser vistes de resultes de la xeometría discreta temprana.
===Combinatoria y sistemes dinámicos===
Los aspeutos combinatorios de los sistemes dinámicos son otru campu emerxente. Equí pueden definise sistemes dinámicos sobre oxetos combinatorios. Vease, por casu, el sistema dinámicu de grafos.
===Combinatoria y física===
Hai interacciones cada vez mayores ente la combinatoria y la física, particularmente la física estadística. Los exemplos inclúin una solución exacta del modelu de Ising, y una conexón ente'l modelu de Potts nuna mano, y los polinomios cromáticos y de Tutte per otra parte.

== Ver tamién ==
* [[Coeficiente binomial]]
* [[Teoría de Ramsey]]
* [[Combinaciones con repetición]]
 

== Referencies ==
{{llistaref}}

{{traducíu ref|en|Combinatorics|24 de payares de 2016||parcial}}
* ''Handbook of Combinatorics, Volumes 1 and 2'', R.L. Graham, M. Groetschel and L. Lovász (Eds.), [[MIT Press]], 1996. ISBN 0-262-07169-X
* ''[http://www-math.mit.edu/~rstan/ec/ Enumerative Combinatorics, Volumes 1 and 2]'', [[Richard P. Stanley]], [[Cambridge University Press]], 1997 and 1999, ISBN 0-521-55309-1N
* http://www.vitutor.com/pro/1/a_1.html
* https://combinatorica.wordpress.com/tag/combinatoria-enumerativa/

=== Bibliografía ===

* Björner, Anders; and Stanley, Richard P.; (2010); [http://www-math.mit.edu/~rstan/papers/comb.pdf ''A Combinatorial Miscellany'']
* Bóna, Miklós; (2011); [http://www.worldscientific.com/worldscibooks/10.1142/8027 ''A Walk Through Combinatorics (3rd Edition)'']. ISBN 978-981-4335-23-2, ISBN 978-981-4460-00-2(pbk)
* Graham, Ronald L.; Groetschel, Martin; and Lovász, László; eds. (1996); ''Handbook of Combinatorics'', Volumes 1 and 2. Amsterdam, NL, and Cambridge, MA: Elsevier (North-Holland) and [[MIT Press]]. ISBN 0-262-07169-X
* Lindner, Charles C.; and Rodger, Christopher A.; eds. (1997); ''Design Theory'', CRC-Press; 1st. edition (October 31, 1997). ISBN 0-8493-3986-3.
* [[John Riordan (mathematician)|Riordan, John]] (1958); ''An Introduction to Combinatorial Analysis'', New York, NY: Wiley & Sons (republished)
* [[Richard P. Stanley|Stanley, Richard P.]] (1997, 1999); [http://www-math.mit.edu/~rstan/ec/ ''Enumerative Combinatorics'', Volumes 1 and 2], [[Cambridge University Press]]. ISBN 0-521-55309-1, ISBN 0-521-56069-1
* van Lint, Jacobus H.; and Wilson, Richard M.; (2001); ''A Course in Combinatorics'', 2nd Edition, Cambridge University Press. ISBN 0-521-80340-3

== Enllaces esternos ==
{{commonscat|Combinatorics|Combinatoria}}
* {{springer|títulu=Combinatorial analysis|id=p/c023250}}
* [http://encyclopedia.jrank.org/CLI_COM/COMBINATORIAL_ANALYSIS.html Combinatorial Analysis] – an article in [[Encyclopædia Britannica Eleventh Edition]]
* [http://mathworld.wolfram.com/Combinatorics.html Combinatorics], a [[MathWorld]] article with many references.
* [http://www.mathpages.com/home/icombina.htm Combinatorics], from a ''MathPages.com'' portal.
* [http://www.combinatorics.net/Resources/hyper/Hyperbook.aspx The Hyperbook of Combinatorics], a collection of math articles links.
* [http://www.dpmms.cam.ac.uk/~wtg10/2cultures.pdf The Two Cultures of Mathematics] by W. T. Gowers, article on problem solving vs theory building.
* [http://www.math.illinois.edu/~dwest/openp/gloss.html "Glossary of Terms in Combinatorics"] {{Webarchive|url=https://web.archive.org/web/20170817044031/http://www.math.illinois.edu/~dwest/openp/gloss.html |date=2017-08-17 }}
* [http://www.mat.univie.ac.at/~slc/divers/software.html List of Combinatorics Software and Databases]


{{Tradubot|Combinatoria}}

{{control d'autoridaes}}
[[Categoría:Combinatoria enumerativa| ]]