Ver el código de «Combinatoria»

La '''combinatoria''', también llamada '''teoría coordinatoria''',<ref>{{Cita libro|apellidos=Robledo Herrera|nombre=Alamiro|título=Lecciones de álgebra elemental moderna|año=1973|editorial=Editorial Universitaria de la Universidad de Concepción|ubicación=Santiago de Chile|página=321|capítulo=Teoría coordinatoria|volumen=3}}</ref> es una rama de la [[matemáticas|matemática]] perteneciente al área de [[matemáticas discretas]] que estudia la enumeración, construcción y existencia de propiedades de configuraciones que satisfacen ciertas condiciones establecidas. Además, estudia las ordenaciones o agrupaciones de un determinado número de elementos.

Los aspectos de la combinatoria incluyen contar las estructuras de un tipo y tamaño dado (combinatorias enumerativas), decidir cuándo pueden cumplirse ciertos criterios y construir y analizar objetos que cumplan los criterios (como en los diseños combinatorios y la teoría de [[matroide]]s) encontrar objetos "más grandes", "más pequeños" u  estructuras combinatorias surgidas en un contexto algebraico, o aplicar técnicas algebraicas a problemas combinatorios (combinatoria algebraica).

En este último campo, avances recientes han introducido la «enumeración irracional», que extiende las técnicas de conteo a objetos con dimensiones no enteras mediante el uso de exponentes irracionales en funciones generadoras.<ref>{{cita publicación|apellidos1=Bevan|nombre1=David|apellidos2=Condé|nombre2=Julien|título=Introducing irrational enumeration: analytic combinatorics for objects of irrational size|publicación=Combinatorics|fecha=22 Dec 2025|páginas=29|url=https://arxiv.org/abs/2412.14682}}</ref>

Los problemas combinatorios surgen en muchas áreas de la [[Matemáticas puras|matemática pura]], especialmente en [[álgebra]], [[teoría de probabilidades]], [[topología]] y [[geometría]], y la combinatoria también tiene muchas aplicaciones en la optimización matemática, la informática, la [[teoría ergódica]] y la [[física estadística]]. Recientemente, su uso se ha extendido a la [[economía espacial]]; por ejemplo, utilizando herramientas de geometría discreta para resolver los complejos problemas combinatorios que surgen al modelar la ubicación óptima, el tamaño y la distribución de plantas industriales en grandes espacios geográficos (Oberfield et al., 2020).<ref>{{cita publicación|apellidos1=Oberfield|nombre1=Ezra|apellidos2=Rossi-Hansberg|nombre2=Esteban|apellidos3=Sarte|nombre3=Pierre-Daniel|apellidos4=Trachter|nombre4=Nicholas|título=The University of Chicago Press|publicación=Journal of Political Economy|fecha=2024/3/1|páginas=70|url=https://www.nber.org/system/files/working_papers/w32256/w32256.pdf}}</ref>

Muchas cuestiones combinatoriales han sido históricamente consideradas aisladamente, dando una solución adecuada a un problema que surge en algún contexto matemático. A finales del {{siglo|XX||s}}, sin embargo, se desarrollaron métodos teóricos poderosos y generales, convirtiendo la combinatoria en una rama independiente de las matemáticas por derecho propio. Una de las partes más antiguas y accesibles de la combinatoria es la [[teoría de grafos]], que también tiene numerosas conexiones naturales a otras áreas. La combinatoria se utiliza con frecuencia en informática para obtener fórmulas y estimaciones en el análisis de [[algoritmo]]s.

== Combinatoria ==
[[Archivo:Dgcombinatoria-variaciones-permutaciones-combinaciones.svg|derecha|300px]]
Para saber qué caso de combinatoria estamos tratando hay que determinar tres características:
* Si influye o no el orden de los elementos.
* Si el número de elementos disponibles en el conjunto: '''n''', es igual o distinto de los presentes en cada suceso: '''r'''.
* Si se producen o no repeticiones en el suceso.
[[Archivo:Combinatoria 01.svg|derecha|300px]]
Ver el diagrama de la derecha. Se pueden diferenciar:
: '''P''': Permutaciones sin repetición.
: '''V''': Variaciones sin repetición.
: '''C''': Combinaciones sin repetición.
: '''PR''': Permutaciones con repetición.
: '''VR''': Variaciones con repetición.
: '''CR''': Combinaciones con repetición.

: <math>
   \begin{array}{|l|l|}
      \hline
      PR_n^{r,s,t, \dots} = \cfrac{n!}{r!  \cdot s!  \cdot t!  \cdot \dots} &
      P_n = n! \\
      \hline
      VR_n^r = n^r &
      V_n^r = \cfrac{n!}{(n-r)!}  \\
      \hline
      CR_n^r = \dbinom{n+r-1}{r} = \cfrac{(n+r-1)!}{r!(n-1)!} &
      C_n^r = \dbinom{n}{r} = \cfrac{n!}{r!  \cdot (n-r)!} \\
      \hline
   \end{array}
</math>

=== Combinatoria sin repetición ===
La combinatoria estudia tres tipos de casos con elementos finitos: permutaciones, variaciones y combinaciones en este caso sin repetición, dado que cada elemento solo puede aparecer una sola vez en cada evento.
: <math>
   \text{Combinatoria sin repetición}
   \left \{
      \begin{array}{l}
         \text{Permutaciones sin repetición} \\
         \text{Variaciones sin repetición} \\
         \text{Combinaciones sin repetición}
      \end{array}
   \right .
</math>

Veamos estos casos:

==== Permutaciones sin repetición ====
Las [[Permutación|permutaciones]] de n elementos son las posibles ordenaciones de un conjunto de n elementos distintos.

Su número:
: <math>
   P_n =
   n  \cdot (n-1)  \cdot (n-2) \cdot 3  \cdot 2  \cdot 1 =
   n!
</math>

(se lee “factorial de n”). Por convenio 0!=1

En la calculadora: con la tecla '''x!''' se calcula “factorial de x” , siendo x un [[número entero]] no negativo.

Ejemplo:
¿Cuántos números de 4 cifras distintas pueden escribirse con los dígitos 2, 3 , 5 y 8?

Solución:
: <math>
   P_4 =
   4! =
   4  \cdot 3  \cdot 2  \cdot 1 =
   24
</math>

Hay 24 números y son:
: <math>
   \begin{array}{|rr|rr|rr|rr|}
      \hline
       1: & 2358 &  7: & 3258 & 13: & 5238 & 19: & 8235 \\
       2: & 2385 &  8: & 3285 & 14: & 5283 & 20: & 8253 \\
       3: & 2538 &  9: & 3528 & 15: & 5328 & 21: & 8325 \\
       4: & 2583 & 10: & 3582 & 16: & 5382 & 22: & 8352 \\
       5: & 2853 & 11: & 3825 & 17: & 5823 & 23: & 8523 \\
       6: & 2835 & 12: & 3852 & 18: & 5832 & 24: & 8532 \\
      \hline
   \end{array}
</math>

==== Variaciones sin repetición ====
Las [[Variación (combinatoria)|variaciones]] de n elementos tomados de r en r : posibles muestras ordenadas de r elementos distintos que se pueden extraer de un conjunto de n elementos, siendo <math> r \leq n </math>.
 
Su número:
: <math>
   V_n^r =
   \cfrac{n!}{(n-r)!} =
   n  \cdot (n-1)  \cdot (n-2) \dots (n-r+1)
</math>

(r factores enteros consecutivos decrecientes a partir de n) 

En la calculadora: con la tecla '''nPr''' se calcula: : <math> V_n^r \, , \; siendo \; r \leq n </math>.

Notemos que: <math> V_n^n = P_n = n! </math>

Ejemplo:

En una carrera con 6 atletas, ¿de cuántas formas distintas podrían repartirse las medallas de oro y plata? 

Solución:
: <math>
   V_{6}^2 =
   \cfrac{6!}{(6-2)!} =
   \cfrac{6!}{4!} =
   \cfrac{6 \cdot 5 \cdot 4!}{4!} =
   6 \cdot 5 =
   30
</math>

formas distintas y serían, numerando los dorsales del 1 al 6 y señalando primero el oro y segundo la plata:
: <math>
   \begin{array}{|rr|rr|rr|}
       \hline
       1: & 12 & 11: & 31 & 21: & 51 \\
       2: & 13 & 12: & 32 & 22: & 52 \\
       3: & 14 & 13: & 34 & 23: & 53 \\
       4: & 15 & 14: & 35 & 24: & 54 \\
       5: & 16 & 15: & 36 & 25: & 56 \\
       6: & 21 & 16: & 41 & 26: & 61 \\
       7: & 23 & 17: & 42 & 27: & 62 \\
       8: & 24 & 18: & 43 & 28: & 63 \\
       9: & 25 & 19: & 45 & 29: & 64 \\
      10: & 26 & 20: & 46 & 30: & 65 \\
      \hline
   \end{array}
</math>

==== Combinaciones sin repetición ====
Las [[Combinación (matemáticas)|combinaciones]] de n elementos tomados de r en r: posibles muestras sin orden de r elementos distintos que se pueden extraer de un conjunto de n elementos <math> ( r \leq n ) </math>.

El número de combinaciones de r elementos de un conjunto de n viene dado por el [[coeficiente binomial]]:
: <math>
   C_n^r =
   \binom{n}{r} =
  
   \frac{n!}{r!  \cdot (n-r)!}
</math>

En la calculadora: con la tecla '''nCr''' se calcula <math>\binom{n}{r}</math> (que se lee “n sobre r”)

Ejemplo:

En una reunión de 8 personas debe nombrarse una comisión formada por dos de ellas. ¿Cuántas comisiones distintas podrían nombrarse?

Solución:
: <math>
   C_{8}^2 =
   \binom{8}{2} =
   \cfrac{8!}{2! \cdot (8-2)!} =
   \cfrac{8!}{2! \cdot 6!} =
   \frac{8 \cdot 7 \cdot 6!}{2! \cdot 6!} =
   \cfrac{8 \cdot 7}{2 \cdot 1} =
   4 \cdot 7 =
   28
</math>

comisiones distintas y serían estas, numerando a las personas del 1 al 8:
: <math>
   \begin{array}{|rr|rr|rr|rr|}
      \hline
       1: & 12 &  8: & 23 & 15: & 35 & 22: & 48 \\
       2: & 13 &  9: & 24 & 16: & 36 & 23: & 56 \\
       3: & 14 & 10: & 25 & 17: & 37 & 24: & 57 \\
       4: & 15 & 11: & 26 & 18: & 38 & 25: & 58 \\
       5: & 16 & 12: & 27 & 19: & 45 & 26: & 67 \\
       6: & 17 & 13: & 28 & 20: & 46 & 27: & 68 \\
       7: & 18 & 14: & 34 & 21: & 47 & 28: & 78 \\
      \hline
   \end{array}
</math>

=== Combinatoria con repetición ===
La combinatoria con repetición estudia los casos de combinatoria en los que algunos elementos pueden aparecer más de una vez en un evento, como en el caso anterior se pueden ver: permutaciones, variaciones y combinaciones:
: <math>
   \text{Combinatoria con repetición}
   \left \{
      \begin{array}{l}
         \text{Permutaciones con repetición} \\
         \text{Variaciones con repetición} \\
         \text{Combinaciones con repetición}
      \end{array}
   \right .
</math>

Veamos estos casos:

==== Permutaciones con repetición ====
Las [[permutaciones con repetición]] son las posibles ordenaciones de una secuencia de n signos entre los que hay algunos repetidos (uno se repite x veces, otro y veces, otro z veces… etc.).

Su número:
: <math>
   PR_n^{x,y,z, \dots} =
   \frac{n!}{x!  \cdot y!  \cdot z!  \cdot \dots}
</math>

Notemos que:
: <math>
   PR_n^{x,n-x} =
   \binom{n}{x}
</math>

Ejemplo:
¿Cuántos números distintos de 6 cifras se pueden escribir usando tres unos, dos cincos y un ocho?

Solución:
: <math>
   PR_6^{3,2,1} =
   \cfrac{6!}{3!  \cdot 2!  \cdot 1!} =
   \cfrac{6 \cdot 5 \cdot 4 \cdot 3!}{3!  \cdot 2} =
   \cfrac{6 \cdot 5 \cdot 4}{2} =
   6 \cdot 5 \cdot 2 =
   60
</math>

números distintos y son:
: <math>
   \begin{array}{|rr|rr|rr|rr|rr|rr|}
      \hline
       1: & 111558 & 11: & 118515 & 21: & 155811 & 31: & 511158 & 41: & 518151 & 51: & 811155 \\
       2: & 111585 & 12: & 118551 & 22: & 158115 & 32: & 511185 & 42: & 518511 & 52: & 811515 \\
       3: & 111855 & 13: & 151158 & 23: & 158151 & 33: & 511518 & 43: & 551118 & 53: & 811551 \\
       4: & 115158 & 14: & 151185 & 24: & 158511 & 34: & 511581 & 44: & 551181 & 54: & 815115 \\
       5: & 115185 & 15: & 151518 & 25: & 181155 & 35: & 511815 & 45: & 551811 & 55: & 815151 \\
       6: & 115518 & 16: & 151581 & 26: & 181515 & 36: & 511851 & 46: & 558111 & 56: & 815511 \\
       7: & 115581 & 17: & 151815 & 27: & 181551 & 37: & 515118 & 47: & 581115 & 57: & 851115 \\
       8: & 115815 & 18: & 151851 & 28: & 185115 & 38: & 515181 & 48: & 581151 & 58: & 851151 \\
       9: & 115851 & 19: & 155118 & 29: & 185151 & 39: & 515811 & 49: & 581511 & 59: & 851511 \\
      10: & 118155 & 20: & 155181 & 30: & 185511 & 40: & 518115 & 50: & 585111 & 60: & 855111 \\
      \hline
   \end{array}
</math>

==== Variaciones con repetición ====
Las [[variaciones con repetición]] de n elementos tomados de r en r: posibles muestras ordenadas de r elementos no necesariamente distintos que se pueden extraer de un conjunto de n elementos.

Su número:
: <math>
   VR_n^r =
   n^r
</math>

Notemos que aquí puede ser r > n

Ejemplo:
¿Cuántos números distintos de 3 cifras se escriben usando solamente las cifras 1, 2, 5 y 8 ?

Solución:
: <math>
   VR_4^3 =
   4^3 =
   64
</math>

números distintos y son:
: <math>
   \begin{array}{|rr|rr|rr|rr|rr|rr|rr|rr|}
      \hline
       1: & 111 &  9: & 151 & 17: & 211 & 25: & 251 & 33: & 511 & 41: & 551 & 49: & 811 & 57: & 851 \\
       2: & 112 & 10: & 152 & 18: & 212 & 26: & 252 & 34: & 512 & 42: & 552 & 50: & 812 & 58: & 852 \\
       3: & 115 & 11: & 155 & 19: & 215 & 27: & 255 & 35: & 515 & 43: & 555 & 51: & 815 & 59: & 855 \\
       4: & 118 & 12: & 158 & 20: & 218 & 28: & 258 & 36: & 518 & 44: & 558 & 52: & 818 & 60: & 858 \\
       5: & 121 & 13: & 181 & 21: & 221 & 29: & 281 & 37: & 521 & 45: & 581 & 53: & 821 & 61: & 881 \\
       6: & 122 & 14: & 182 & 22: & 222 & 30: & 282 & 38: & 522 & 46: & 582 & 54: & 822 & 62: & 882 \\
       7: & 125 & 15: & 185 & 23: & 225 & 31: & 285 & 39: & 525 & 47: & 185 & 55: & 825 & 63: & 885 \\
       8: & 128 & 16: & 188 & 24: & 228 & 32: & 288 & 40: & 528 & 48: & 588 & 56: & 828 & 64: & 888 \\
      \hline
   \end{array}
</math>

==== Combinaciones con repetición ====
Las [[combinaciones con repetición]] de n elementos tomados de r en r: posibles muestras no ordenadas de r elementos no necesariamente distintos que se pueden extraer de un conjunto de n elementos.

Su número:
: <math>
   CR_n^r =
   \binom{n+r-1}{r} = \cfrac{(n+r-1)!}{r!(n-1)!}
</math>

Notemos que aquí puede ser r > n

Ejemplo:
Un banco ofrece un regalo a elegir entre 5 posibles regalos por cada cartilla. Un señor que tiene tres cartillas en dicho banco ¿de cuántas formas puede elegir el lote de tres obsequios si no le importa repetir regalos?

Solución:
: <math>
   CR_5^3 =
   \binom{5+3-1}{3} =
   \cfrac{(5+3-1)!}{3!*(5-1)!} =
   \cfrac{7!}{3! * 4!} =
   \cfrac{7*6*5*4!}{3! * 4!} =
   \cfrac{7*6*5}{3*2*1} =
   \cfrac{7*6*5}{6} =
   7*5 =
   35
</math> 

lotes distintos y son:
: <math>
   \begin{array}{|rr|rr|rr|rr|rr|}
      \hline
       1: & 1 \; 1 \; 1 &  8: & 1 \; 2 \; 4 & 15: & 1 \; 5 \; 5 & 22: & 2 \; 3 \; 5 & 29: & 3 \; 4 \; 4 \\
       2: & 1 \; 1 \; 2 &  9: & 1 \; 2 \; 5 & 16: & 2 \; 2 \; 2 & 23: & 2 \; 4 \; 4 & 30: & 3 \; 4 \; 5 \\
       3: & 1 \; 1 \; 3 & 10: & 1 \; 3 \; 3 & 17: & 2 \; 2 \; 3 & 24: & 2 \; 4 \; 5 & 31: & 3 \; 5 \; 5 \\
       4: & 1 \; 1 \; 4 & 11: & 1 \; 3 \; 4 & 18: & 2 \; 2 \; 4 & 25: & 2 \; 5 \; 5 & 32: & 4 \; 4 \; 4 \\
       5: & 1 \; 1 \; 5 & 12: & 1 \; 3 \; 5 & 19: & 2 \; 2 \; 5 & 26: & 3 \; 3 \; 3 & 33: & 4 \; 4 \; 5 \\
       6: & 1 \; 2 \; 2 & 13: & 1 \; 4 \; 4 & 20: & 2 \; 3 \; 3 & 27: & 3 \; 3 \; 4 & 34: & 4 \; 5 \; 5 \\
       7: & 1 \; 2 \; 3 & 14: & 1 \; 4 \; 5 & 21: & 2 \; 3 \; 4 & 28: & 3 \; 3 \; 5 & 35: & 5 \; 5 \; 5 \\
      \hline
   \end{array}
</math>

== Historia ==

Los conceptos básicos sobre la combinatoria y los resultados enumerativos han aparecido a lo largo del [[Edad antigua|mundo antiguo]]. En el {{siglo|VI||s}} a.&nbsp;C., en la antigua India, el médico [[Sushruta]] asegura en el [[Susruta-samhita]] que es posible formar 63 [[Combinación (matemáticas)|combinaciones]] a partir de 6 sabores distintos, tomados de uno en uno, de dos en dos, etc., así calculando todas las 2<sup>6</sup>&nbsp;&minus;&nbsp;1 posibilidades. El [[historiador]] [[Antigua Grecia|griego]] [[Plutarco]] debatió con [[Crisipo de Solos]] ({{siglo|III||s}} a.&nbsp;C.) e [[Hiparco de Nicea]] ({{siglo|II||s}} a.&nbsp;C.) sobre un problema enumerativo un tanto delicado, el cual se demostró más adelante que guardaba relación con el [[número Schröder–Hiparco]]s.<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>

En la [[Edad Media]], la combinatoria continuó siendo estudiada, sobre todo fuera de la [[Cultura de Europa|civilización Europea]]. El matemático [[India|indio]] [[Mahāvīra (matemático)|Mahāvīra]] (c.&nbsp;850) acuñó una fórmula para el número de [[permutacion]]es y [[Combinación (matemáticas)|combinaciones]],<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 |title=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 |year=2000 |isbn=978-1-4020-0260-1 |page=417 <!-- pages 409–422 -->}}</ref> y es posible que estas fórmulas ya resultaran familiares a los matemáticos indios a principios del {{siglo|VI||s}} d.&nbsp;C.<ref>{{cita publicación | last1 = Biggs | first1 = Norman L. | año = 1979 | título = The Roots of Combinatorics | url = | publicación = Historia Mathematica | volumen = 6 | número = | páginas = 109–136 | doi=10.1016/0315-0860(79)90074-0}}</ref> El [[filósofo]] y [[astrónomo]] Rabbi [[Abraham ibn Ezra]] (c. 1140) estableció la simetría de los [[coeficientes binomiales]], mientras que una fórmula concreta fue hallada más adelante por el [[talmud]]ista y [[matemático]] [[Gersónides]], en 1321.<ref>{{citation|title=Probability Theory: A Historical Sketch|first=L. E.|last=Maistrov|publisher=Academic Press|year=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ángulo aritmético —un diagrama gráfico mostrando las relaciones entre los coeficientes binomiales— ya había aparecido en tratados matemáticos tan atrás como el {{siglo|X||s}}, y con el tiempo serían mejor conocidos como el [[Triángulo de Pascal]].

Durante el [[Renacimiento]], junto al resto de las matemáticas y las [[ciencia]]s, la combinatoria disfrutó de un renacer. Trabajos de [[Blaise Pascal|Pascal]], [[Isaac Newton|Newton]], [[Jacob Bernoulli]] y [[Leonhard Euler|Euler]] se volvieron fundamentales en el emergente campo. En los tiempos modernos, los trabajos de [[James Joseph Sylvester|J. J. Sylvester]] (a finales del {{siglo|XIX||s}}) y [[Percy Alexander MacMahon|Percy MacMahon]] (a principios del {{siglo|XX||s}}) ayudaron a asentar las bases para la [[combinatoria enumerativa]] y [[combinatoria algebraica]]. La [[teoría de grafos]] también disfrutó de una explosión de interés al mismo tiempo, en especial conexión con el [[teorema de los cuatro colores]].

En la segunda mitad del {{siglo|XX||s}}, la combinatoria sufrió un crecimiento rápido, que llevó al establecimiento de docenas de nuevos diarios y conferencias sobre este tema.<ref>Véase [http://www.math.iit.edu/~kaul/Journals.html#CGT Journals in Combinatorics and Graph Theory]</ref> En parte, el crecimiento fue estimulado por las nuevas conexiones y aplicaciones en otros campos, desde álgebra hasta probabilidades, desde el [[análisis funcional]] a la [[teoría de números]], etc. Estas conexiones terminaron por romper los bordes entre la combinatoria y partes de la matemática y la informática teórica, pero al mismo tiempo causó cierta fragmentación dentro del campo.

== Áreas de la combinatoria ==
No existe una clasificación tajante de lo que constituye una subárea, sino que todas comparten cierto grado de traslape entre sí, al igual que con otras ramas de la matemática discreta. Diferentes autores proponen varias divisiones de la combinatoria por lo que cualquier listado es meramente indicativo. Por ejemplo, algunos autores consideran la [[teoría de grafos]] como una subárea de la combinatoria, mientras que otros la consideran un área independiente.

Entre las subdivisiones más comunes se encuentran las siguientes:

=== Combinatoria enumerativa ===
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 en 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. La forma de doce veces mayor proporciona un marco unificado para contar las permutaciones, combinaciones y particiones.

=== Combinatoria analítica ===
La combinatoria analítica se refiere a la enumeración de estructuras combinatorias utilizando herramientas de [[análisis complejo]] y teoría de probabilidades. En contraste con 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.

=== Teoría de la partición ===
La teoría de la partición estudia diferentes problemas asintóticos y numerales relacionados con particiones enteras, y está estrechamente relacionada con las series, [[Función especial|funciones especiales]] y polinomios ortogonales. Originalmente era una parte de la teoría numérica y el análisis, ahora se considera una parte de la combinatoria o un campo independiente. Incorpora el enfoque biyectivo y diversas herramientas en análisis y teoría analítica de números, y tiene conexiones con la mecánica estadística.

=== Teoría de grafos ===
Los grafos son objetos básicos en la combinatoria. Las preguntas van desde el recuento (por ejemplo, el número de grafos en n vértices con bordes k) hasta estructurales (por ejemplo, qué grafos contienen ciclos hamiltonianos) a preguntas algebraicas (por ejemplo, dado un grafo G y dos números x e y, el "Polinomio Tutte" TG (x, y) ¿tiene una interpretación combinatoria?). Cabe señalar que, si bien hay conexiones muy fuertes entre la teoría de grafos y la combinatoria, a veces estos dos se consideran sujetos separados. Esto se debe al hecho de que mientras que los métodos combinatorios se aplican a muchos problemas de teoría de grafos, los dos se utilizan generalmente para buscar soluciones a diferentes problemas.

=== 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 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 Steiner, cuyos sistemas juegan un papel importante en la clasificación de grupos finitos simples. El área tiene conexiones adicionales con la teoría de la codificación y la combinatoria geométrica.
=== Geometría finita ===
La geometría finita es el estudio de sistemas geométricos que tienen solo un número finito de puntos. Los principales elementos estudiados son estructuras análogas a las encontradas en geometrías continuas (plano euclidiano, [[espacio proyectivo]] real, etc.) pero definidas combinatorialmente. 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).

=== Teoría del orden ===
La [[teoría del orden]] es el estudio de conjuntos parcialmente ordenados, tanto finitos como infinitos. En el álgebra, la geometría, la teoría de números y en toda la teoría combinatoria y gráfica aparecen varios ejemplos de órdenes parciales. Algunas clases notables y ejemplos de órdenes parciales incluyen redes y álgebras booleanas.
=== Teoría del matroide ===
La teoría del matroide abstrae parte de la geometría. Estudia las propiedades de conjuntos (generalmente, conjuntos finitos) de vectores en un [[espacio vectorial]] que no dependen de los coeficientes particulares en una relación de dependencia lineal. No solo la estructura sino también las propiedades enumerativas pertenecen a la teoría del matroide. La teoría del matroide 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.
=== Combinatoria extrema ===
La combinatoria extrema estudia las preguntas extremas sobre los sistemas de conjuntos. Los tipos de preguntas abordadas en este caso son sobre el mayor grafo posible que satisface ciertas propiedades. Por ejemplo, el mayor grafo libre de triángulos en 2n vértices es un grafo bipartito completo Kn, n. A menudo es demasiado difícil incluso para encontrar la respuesta extrema f(n) exactamente y solo se puede dar una estimación asintótica. La teoría de Ramsey es otra parte de la combinatoria extrema. Indica que cualquier configuración suficientemente grande contendrá algún tipo de orden. Es una generalización avanzada del principio del palomar.

=== Combinatoria probabilística ===
En la combinatoria probabilística, las preguntas son del tipo siguiente: ¿cuál es la probabilidad de una cierta propiedad para un objeto aleatorio discreto, tal como un grafo al azar? Por ejemplo, ¿cuál es el número promedio de triángulos en un grafo al azar? Los métodos probabilísticos también se utilizan para determinar la existencia de objetos combinatorios con ciertas propiedades prescritas (para las cuales pueden ser difíciles de encontrar ejemplos explícitos), simplemente observando 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) demostró ser altamente eficaz en aplicaciones a la combinatoria extremal y a la teoría de los grafos. Un área estrechamente relacionada es el estudio de cadenas de Markov finitas, especialmente en objetos combinatorios. Aquí también se utilizan herramientas probabilísticas para estimar el tiempo de mezclado.
A menuda asociada con Paul Erdős, que hizo el trabajo pionero en el tema, la combinatoria probabilística fue vista tradicionalmente como un conjunto de herramientas para estudiar problemas en otras partes de la combinatoria. Sin embargo, con el crecimiento de las aplicaciones para el análisis de algoritmos en la informática, así como la probabilidad clásica, la teoría aditiva y probabilística de número, el área creció recientemente para convertirse en un campo independiente de la combinatoria.

=== Combinatoria algebraica ===
La combinatoria algebraica es un área de matemáticas que emplea métodos de álgebra abstracta, notablemente teoría de grupo y teoría de representación, en varios contextos combinatorios y, a la inversa, aplica técnicas combinatorias a problemas en álgebra. La combinatoria algebraica está continuamente expandiendo su alcance, tanto en temas como en técnicas, y puede ser vista como el área de matemáticas donde la interacción de métodos combinatorios y algebraicos es particularmente fuerte y significativa.

=== Combinatoria de palabras ===
La combinatoria de palabras trata de lenguajes formales. Se plantea de forma independiente dentro de varias ramas de las matemáticas, incluyendo la teoría de números, la teoría de grupos y la probabilidad. Tiene aplicaciones a la combinatoria enumerativa, al análisis fractal, a la informática teórica, a la teoría de los autómatas y a la lingüística. Aunque 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 el campo.
=== Combinatoria geométrica ===
La combinatoria geométrica está relacionada con la geometría convexa y discreta, en particular la combinatoria poliédrica. Se pregunta, por ejemplo, cuántas caras de cada dimensión puede tener un politopo convexo. Las propiedades métricas de los politopos juegan también un papel importante. Por ejemplo: el teorema de Cauchy sobre la rigidez de los politopos convexos. También se consideran politopos especiales, como el permutohedra, el associahedra y los politopos de Birkhoff. Debemos tener en cuenta que la geometría combinatoria es un nombre anticuado para la geometría discreta.
=== Combinatoria topológica ===
Los análogos combinatorios de conceptos y métodos en topología se usan para estudiar dibujo gráfico, división justa, particiones, conjuntos parcialmente ordenados, árboles de decisión, problemas de collar y teoría de Morse discreta. No debe confundirse con la topología combinatoria que es un nombre antiguo para la topología algebraica.
=== Combinatoria aritmética ===
La combinatoria aritmética surgió de la interacción entre la [[teoría numérica]], la combinatoria, la teoría ergódica y el [[análisis armónico]]. Se trata de estimaciones combinatorias asociadas con operaciones aritméticas (adición, sustracción, multiplicación y división). La combinatoria aditiva se refiere al caso especial cuando 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 los [[sistemas dinámicos]].
=== Combinatoria infinita ===
La combinatoria infinita, o teoría de conjuntos combinatoria, es una extensión de ideas en combinatoria a conjuntos infinitos. Es una parte de la teoría de conjuntos, un área de lógica matemática, pero utiliza herramientas e ideas tanto de la teoría de conjuntos como de la combinatoria extrema. Gian-Carlo Rota usó el nombre de combinatoria continua para describir la probabilidad geométrica, ya que hay muchas analogías entre el recuento y la medida.
=== Combinatoria de conjuntos ===
La combinatoria de conjuntos es una rama de las [[matemáticas]], la [[lógica matemática]] y la [[teoría de conjuntos]] que estudia la enumeración, construcción, existencia de propiedades de configuraciones que satisfacen ciertas condiciones establecidas relacionadas con los conjuntos, por lo cual estudia las ordenaciones o agrupaciones de un determinado número de elementos mediante [[diagramas de Euler]], [[Leibniz]], [[Venn]] y operaciones basadas en la [[teoría de conjuntos]], los cuales aparecieron a lo largo de las [[interacciones numéricas elementales]].

== Combinatoria enumerativa ==
La '''combinatoria enumerativa''' o '''enumeración''' estudia los métodos para contar (enumerar) las distintas configuraciones de los elementos de un [[conjunto]] que cumplan ciertos criterios especificados. 
 
Esta fue una de las primeras áreas de la combinatoria en ser desarrollada, y como otras áreas más recientes se estudian solo en cursos especializados, es común que se haga referencia a esta subárea cuando se menciona ''combinatoria'' en entornos escolares.

En todo problema combinatorio hay varios conceptos claves que debemos distinguir:

* '''1. Población:'''
Se llama así al conjunto de los elementos que estamos estudiando. Designaremos con una '''m''' al número de elementos del conjunto.

* '''2. Muestra:'''
Se trata de un subconjunto de la población. Se denominará con la letra '''n''' al número de elementos que forman la muestra.

Los tipos de la muestra vienen determinados por dos aspectos:

'''Orden'''

Determina si es importante o no que los elementos de la muestra aparezcan ordenados.

'''Repetición''' 

La posibilidad de repetición o no de los elementos.

;Ejemplo.
¿De cuántas formas se puede obtener 8 al tirar 2 dados?

Imagina que queremos contar de cuantas formas se puede obtener 8 al tirar un par de dados. Uno puede realizar el clásico diagrama de coordenadas:
: <math>
   \begin{array}{r|rrrrrr}
      & 1 & 2 & 3 & 4 & 5 & 6 \\
      \hline
      1 & 2 & 3 & 4 &  5 &  6 &  7 \\
      2 & 3 & 4 & 5 &  6 &  7 & \underline{ 8 } \\
      3 & 4 & 5 & 6 &  7 & \underline{ 8 } &  9 \\
      4 & 5 & 6 & 7 & \underline{ 8 } &  9 & 10 \\
      5 & 6 & 7 & \underline{ 8 } &  9 & 10 & 11 \\
      6 & 7 & \underline{ 8 } & 9 & 10 & 11 & 12 \\
   \end{array}
</math>
Y concluir que hay 5 formas de obtener el 8. Con el mismo diagrama, podemos encontrar el resultado f(k) para cualquier suma k:
: <math>
   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.
</math>

Pero ¿qué pasa si queremos tirar tres dados?, ¿cinco dados?, ¿20 dados?, ¿m dados? Ya no es práctico usar la representación de coordenadas, necesitamos un nuevo modelo.

Consideremos solo un dado. ¿De cuántas formas podemos obtener el valor k? Pues de una forma si k=1,2,3,4,5,6 y 0 de cualquier otra forma. Vamos a codificar todos los resultados posibles en una única expresión:
<math>a + a^{2} + a^{3} + a^{4} + a^{5} + a^{6} </math>.

Entre las cuentas, puede perder uno de punto de vista la idea central: estamos representando una sucesión de varios valores (formas de tirar un dado) mediante un solo objeto algebraico (un poliomio), y manipulaciones con este objeto nos dan información acerca de la combinatoria del problema.

El método puede modificarse para resolver problemas similares (por ejemplo, si quisiéramos saber de cuántas formas se puede obtener 30 al tirar 3 dados normales y dos dados en forma de icosaedro, intentaríamos encontrar el coeficiente de <math> \, a^{30} </math> en el desarrollo de <math> ( a + a^{2} + a^{3} + a^{4} + a^{5} + a^{6} )^{3} \cdot ( a + a^{2} + a^{3} + \dots +  a^{20} ) ^{2} </math>.

Este es un caso particular del método de funciones generadoras, en el que una serie de potencias representa una cantidad (posiblemente infinita) de valores de una sucesión.

; Ejemplo.
Considérese el conjunto <math> S=\{A, E, I, O, U\} </math>. Podemos imaginar que estos elementos corresponden a tarjetas dentro de un sombrero.
* Un primer problema podría consistir en hallar el número de formas diferentes en que podemos sacar las tarjetas una después de otra (es decir, el número de [[permutación|permutaciones]] del conjunto).
: Por ejemplo, dos formas distintas podrían ser: ''EIAOU'' o ''OUAIE''.
* Después, se puede preguntar por el número de formas en que se puede sacar solo 3 tarjetas del sombrero (es decir, el número de 3-permutaciones del conjunto).
: En este caso, ejemplos pueden ser ''IOU'', ''AEI'' o ''EAI''.
* También se puede preguntar sobre cuáles son los posibles grupos de 3 tarjetas que se pueden extraer, sin dar consideración al orden en que salen (en otras palabras, el valor de un [[coeficiente binomial]]).
: Aquí, consideraríamos ''AOU'' y ''UAO'' como un mismo resultado.
* Otro problema consiste en hallar el número de formas en que pueden salir 5 tarjetas, una tras otra, pero en cada momento se regresa la tarjeta escogida al sombrero.
: En este problema los resultados posibles podrían ser ''EIOUO'', ''IAOEU'' o ''IEAEE''.

La combinatoria enumerativa estudia las técnicas y métodos que permiten resolver problemas anteriores, así como otros más complejos, cuando el número de elementos del conjunto es arbitrario. De esta forma, en el primer ejemplo la generalización correspondiente es determinar el número de formas en que se pueden ordenar todos los elementos de un conjunto con ''n'' elementos, siendo la respuesta el [[factorial]] de ''n''.

== Combinatoria extremal ==
El enfoque aquí es determinar qué tan grande o pequeña debe ser una colección de objetos para que satisfaga una condición previamente establecida; 

; Ejemplo.
Considérese un conjunto ''S''. con ''n'' elementos. A continuación se empieza a hacer un listado de subconjuntos de tal manera que cualquier pareja de subconjuntos del listado tenga algún elemento en común.

Para esclarecer, sea <math>S=\{A, B, C, D\}</math> y un posible listado de subconjuntos podría ser
:: <math>\{B, C\}, \{A, B\}, \{A, B, C, D\}, \{B, D\}, \ldots</math>
Conforme aumenta el listado (y dado que hay una cantidad [[finita]] de opciones), el proceso se hace cada vez más complicado. Por ejemplo, no podríamos añadir el conjunto {''A'', D''} al listado pues aunque tiene elementos en común con los últimos 3 subconjuntos del listado, no comparte ningún elemento con el primero.

La pregunta sobre qué tan grande puede hacerse el listado de forma que cualquier pareja de subconjuntos tenga un elemento en común es un ejemplo de problema de combinatoria extremal (o combinatoria extrema). La respuesta a este problema es que si el conjunto original tiene ''n'' elementos, entonces el listado puede tener como máximo <math>2^{n-1}</math> subconjuntos.

== Campos relacionados ==
=== Optimización combinatoria ===
La optimización combinatoria es el estudio de la optimización de objetos discretos y combinatorios. Comenzó como parte de la teoría combinatoria y la teoría de grafos, pero ahora se ve como una rama de la matemática aplicada y la informática, relacionada con la investigación de operaciones, la teoría de algoritmos y la teoría de la complejidad computacional.
=== Teoría de la codificación ===
La teoría de la codificación comenzó como parte de la teoría del diseño con construcciones combinatoriales tempranas de códigos correctores de errores. La idea principal del tema 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.
=== Geometría discreta y computacional ===
La geometría discreta (también llamada geometría combinatoria) también comenzó como una parte de la combinatoria, con resultados tempranos en politopos convexos y "números cercanos". Con la aparición de aplicaciones de geometría discreta a la geometría computacional, estos dos campos se fusionaron parcialmente y se convirtieron en un campo de estudio independiente. Siguen existiendo muchas conexiones con combinatorias geométricas y topológicas, que pueden ser vistas como consecuencia de la geometría discreta temprana.
=== Combinatoria y sistemas dinámicos ===
Los aspectos combinatorios de los sistemas dinámicos son otro campo emergente. Aquí se pueden definir sistemas dinámicos sobre objetos combinatorios. Véase, por ejemplo, el [[sistema dinámico]] de grafos.
=== Combinatoria y física ===
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 en una mano, y los polinomios cromáticos y de Tutte por otra parte.

== Cardinalidad de la Unión de Conjuntos ==
=== Principio de la suma ===

==== Para [[conjuntos disjuntos]] ====
Sean <math>A_1</math> y <math>A_2</math> [[conjuntos disjuntos]] (<math>A_1 \cap A_2 = \varnothing</math>) entonces: <math>|A_1 \cup A_2| = |A_1| + |A_2|</math>

Tal y como enuncia El Principio de la Suma: 

{{teorema|tipo=conjetura|El número de elementos en una unión de conjuntos disjuntos es igual a la suma de los tamaños de todos los conjuntos}}

Este principio se puede demostrar por inducción sobre el número de conjuntos. 

La demostración puede empezar basándose en que los conjuntos {<math>0,1,2,3,...,m-1</math>} y {<math>n, n+1 ,..., n+m-1</math>}. Este principio puede extenderse a tres o más conjuntos, en tal caso, dice que si <math>A_1, A_2, ..., A_n</math> son conjuntos disjuntos dos a dos (<math>A_i \cap A_j = \varnothing</math> para <math>i \neq j</math>):

<math>|A \cup A_2 \cup A_3 ... \cup A_n| = |A_1| + |A_2| + ... +|A_n|</math>

Aun así, el principio de la suma puede enunciarse como:

{{teorema|tipo=conjetura|Si una primera tarea se puede realizar de <math>n_1</math> formas y una segunda tarea se puede realizar de <math>n_2</math>
formas suponiendo que las dos tareas son incompatibles, entonces, hay <math>n_1</math> + <math>n_2</math> formas de realizar una de las dos tareas.}}

==== Para conjuntos no disjuntos ====
Sean <math>A_1</math> y <math>A_2</math> dos conjuntos (<math>A_1 \cap A_2 \neq \varnothing</math>) entonces: <math>|A_1 \cup A_2| = |A_1| + |A_2| - |A_1 \cap A_2|</math>

Para demostrar este enunciado se puede empezar suponiendo que <math>A_1 = (A_1 \backslash A_2) \cup (A_1 \cap A_2) </math> con <math>(A_1 \backslash A_2) \cap (A_1 \cap A_2) = \varnothing  </math> luego <math>|A_1| = |A_1\backslash A_2| + |A_1 \cap A_2| </math>                                        provocando que:<math>|A_1 \backslash A_2| = |A_1| - |A_1 \cap A_2| </math> 

Dado que <math>A_1 \cup A_2 = (A_1 \backslash A_2) \cup (A_1 \cap A_2) \cup (A_2\backslash A_1) </math>:

<math>|A_1 \cup A_2| = |A_1 \backslash A_2| + |A_1 \cap A_2| + |A_2 \backslash A_1| = |A_1| - |A_1 \cap A_2| +
|A_1 \cap A_2| + |A_2| - |A_1 \cap A_2| = |A_1| + |A_2| - |A_1 \cap A_2| </math>

=== Principio del producto ===
Sean <math>A_1  </math> y <math>A_2 </math> dos conjuntos: <math>|A_1 \times A_2| = |A_1| \cdot |A_2| </math>.

Para demostrar este enunciado se debe encontrar una biyección entre {<math>0,1,...,m+n-1 </math>} y  {<math>0,1,...,m-1 </math>} <math>\times </math>{<math>0,1,...,n-1 </math>}. La biyección vendría dada por <math>a \mapsto (a\bmod b, a </math> div <math>m) </math>.

El principio puede generalizarse a tres o más conjuntos obteniéndose: <math>|A_1 \times A_2 \times ... \times A_m| = |A_1| \cdot |A_2| ... |A_m| </math>

Además, este principio puede ser enunciado de la siguiente manera:
{{teorema|tipo=conjetura|Si una tarea podemos dividirla en dos o más tareas consecutivas de forma que hay <math>n_1</math> formas de realizar la primera tarea, y <math>n_2</math> formas de realizar la segunda tarea, entonces hay <math>n_1 n_2</math>formas de completar la tarea.}}

=== Generalización del principio de Inclusión-Exclusión ===
Sea S un conjunto finito <math>|S| = N </math> y <math>p_1, p_2, ..., p_k </math> una colección de propiedades o condiciones que son cumplidas por al menos un elemento del conjunto S. 

Se indica mediante <math>\overline {p_i} </math> que no cumpla la propiedad  <math>p_i </math>. 

De esta manera <math>N(p_i) </math> es el número de elementos de S que cumplen <math>p_i </math> y <math>N(\overline{p_i}) = N - N(p_i) </math> es el número de elementos de S que no cumplen <math>p_i </math>. 

El número de elementos de S que no cumplen ninguna propiedad <math>p_i, 1 \leq i \leq k </math> será:

<math>\overline N = N(\overline p_1 \overline p_2 \overline p_3 ... \overline p_k) = N - \sum _{1 \leq i \leq k} N(p_i) + \sum _{1 \leq i, j \leq k} N(p_i p_j) + ... + (-1)^k N(p_1 p_2 ... p_k) </math>

== Binomio de Newton ==
Dados dos números a, b ∈ R sabemos que el desarrollo del cuadrado del binomio a + b viene dado por: (a + b)<sup>2</sup> = a<sup>2</sup> + 2ab + b<sup>2</sup>. 

Podemos reescribir este desarrollo como: 

<math>(a+b)^2= \binom{2}{0} a^0b^2 + \binom{2}{1} a^1b^1 + \binom{2}{2} a^2b^0 = \sum_{k=0}^2 \binom{2}{k} a^k b^{2-k}</math>

Análogamente para el desarrollo del cubo de un binomio: 

(a + b)<sup>3</sup> = a<sup>3</sup> + 3a<sup>2</sup>b + 3ab<sup>2</sup> + b<sup>3</sup> que también puede reescribirse como:

<math>(a+b)^3= \binom{3}{0} a^0b^3 + \binom{3}{1} a^1b^2 + \binom{3}{2} a^2b^1 + \binom{3}{3} a^3b^0 = \sum_{k=0}^3 \binom{3}{k} a^k b^{3-k}</math>

La fórmula del binomio de Newton generaliza lo anterior al desarrollo de cualquier potencia natural de un binomio y se expresa de la siguiente manera.

=== Teorema 1 (Fórmula del binomio de Newton) ===
Para cualesquiera números a, b ∈ R y cualquier número n ∈ N se verifica: 
: <math>
   (a+b)^n = 
   \sum_{k=0}^n \binom{n}{k} a^k b^{n-k}
</math>

==== Demostración ====
Por inducción respecto de n demostraremos que la proposición 

<math>p(n): \forall a,b\epsilon R ,(a+b)^n= \sum_{k=0}^n \binom{n}{k} a^k b^{n-k}</math> es verdadera para todo número natural n. 

Paso base: Probemos que p(1) es V.

<math>p(1): \forall a,b\epsilon R ,(a+b)^1= \sum_{k=0}^1 \binom{1}{k} a^k b^{1-k}</math>

El miembro izquierdo de la igualdad es simplemente a + b. El miembro derecho es: 

<math> \binom{1}{0} a^0b^1 + \binom{1}{1} a^1b^0 = a + b</math> de modo que p(1) es verdadera. 

(HI)Hipótesis inductiva: Supongamos que p(n) es verdadera. 

Ahora probaremos que necesariamente p(n + 1) es verdadera, bajo el supuesto (HI). Para ello procedemos así:

<math>(a+b)^{n+1}= (a+b)(a+b)^n=(a+b) \sum_{k=0}^n \binom{n}{k} a^k b^{n-k}=</math>

<math>= a\sum_{k=0}^n \binom{n}{k} a^k b^{n-k} + b\sum_{k=0}^n \binom{n}{k} a^k b^{n-k}= </math>

<math>=\sum_{k=0}^n \binom{n}{k} a^{k+1} b^{n-k} + \sum_{k=0}^n \binom{n}{k} a^{k} b^{n-k+1}= </math>

<math>=\sum_{j=1}^{n+1} \binom{n}{j-1} a^{j} b^{n-j+1} + \sum_{j=0}^n \binom{n}{j} a^{j} b^{n-j+1}= </math>

<math>= \binom{n}{n} a^{n+1}+\sum_{j=1}^{n} \binom{n}{j-1} a^{j} b^{n-j+1} + \binom{n}{0} b^{n+1}+ \sum_{j=1}^n \binom{n}{j} a^{j} b^{n-j+1}= </math>

<math>= \binom{n}{0} b^{n+1}+ \{\sum_{j=1}^{n} [\binom{n}{j-1} +  \binom{n}{j}] a^{j} b^{n-j+1}\} + \binom{n}{n} a^{n+1}= </math>

<math>= \binom{n}{0} b^{n+1}+ \sum_{j=1}^{n} \binom{n+1}{j}a^{j} b^{n-j+1} + \binom{n}{n} a^{n+1}= </math>

<math>= \binom{n+1}{0}a^0 b^{n+1}+ \sum_{j=1}^{n} \binom{n+1}{j}a^{j} b^{n-j+1} + \binom{n+1}{n+1} a^{n+1}b^0= </math>

<math>= \sum_{j=0}^{n+1} \binom{n+1}{j}a^{j} b^{n+1-j}= </math>

que muestra que p(n + 1) es verdadera. Luego, por inducción completa p(n) es verdadera para todo n ∈ N.

== Principios de la Combinatoria ==

=== Principio fundamental de conteo ===
El principio fundamental de conteo establece que si hay ''p'' formas de hacer una cosa, y ''q'' formas de hacer otra cosa, entonces hay ''p × q'' formas de hacer ambas cosas.

'''<u>Ejemplo 1:</u>'''

Suponga que tiene 3 camisas (llamémoslas A, B, y C), y 4 pares de pantalones (llamémoslos ''w'' , ''x'' , ''y'' , y ''z'' ). Entonces Usted tiene

3 × 4 = 12

combinaciones posibles:

A ''w'' , A ''x'' , A ''y'' , A ''z''

B ''w'' , B ''x'' , B ''y'' , B ''z''

C ''w'' , C ''x'' , C ''y'' , C ''z''

'''<u>Ejemplo 2:</u>'''

Suponga que lanza un dado de 6 caras y saca una carta de un mazo de 52 cartas. Hay 6 resultados posibles con el dado, y 52 resultados posibles con el mazo de cartas. Así, hay un total de

6 × 52 = 312 resultados posibles del experimento.

El principio de conteo puede extenderse a situaciones donde tenga más de 2 opciones. Por ejemplo, si hay ''p'' formas de hacer una cosa, ''q'' formas para una segunda cosa, y ''r'' formas de hacer una tercera cosa, entonces hay ''p × q × r'' formas de hacer las tres cosas.

=== Principio de la Multiplicación ===
Si se desea realizar una actividad que consta de r pasos, en donde el primer paso de la actividad a realizar puede ser llevado a cabo de N<sub>1</sub> maneras o formas, el segundo paso de N<sub>2</sub> maneras o formas y el r-ésimo paso de N<sub>r</sub> maneras o formas, entonces esta actividad puede ser llevada a efecto de. El principio multiplicativo implica que cada uno de los pasos de la actividad deben ser llevados a efecto, uno tras otro. Si un evento E1 puede suceder de n1 maneras diferentes, el evento E2 puede ocurrir de n2 maneras diferentes, y así sucesivamente hasta el evento Ep el cual puede ocurrir de np maneras diferentes, entonces el total de maneras distintas en que puede suceder el evento “ocurren E1 y E2…..y Ep” es igual a producto.

''N1 x N2 x ..........x  Nr  maneras o formas''

'''<u>Ejemplo:</u>'''

Se dispone de 3 vías para viajar de C1 a C2   y de 4 vías para viajar de C2 a C1. ¿De cuántas formas se puede organizar el viaje de ida y vuelta de C1 a C2.Respuesta: (3)(4)=12

=== Principio Aditivo ===
Si se desea llevar a efecto una actividad, la cual tiene formas alternativas para ser realizada, donde la primera de esas alternativas puede ser realizada de M maneras o formas, la segunda alternativa puede realizarse de N maneras o formas ..... y la última de las alternativas puede ser realizada de W maneras o formas, entonces esa actividad puede ser llevada  a cabo de,

                       M + N + .........+ W  maneras o formas

'''<u>Ejemplos:</u>'''

1)      Una persona desea comprar una lavadora de ropa, para lo cual ha pensado que puede seleccionar de entre las marcas Whirpool, Easy y General Electric, cuando acude a hacer la compra se encuentra que la lavadora de la marca W se presenta en dos tipos de carga ( 8 u 11 kilogramos), en cuatro colores diferentes y puede ser automática o semiautomática, mientras que la lavadora de la marca E, se presenta en tres tipos de carga (8, 11 o 15 kilogramos), en dos colores diferentes y puede ser automática o semiautomática y la lavadora de la marca GE, se presenta en solo un tipo de carga, que es de 11 kilogramos, dos colores diferentes y solo hay semiautomática. ¿Cuántas maneras tiene esta persona de comprar una lavadora?

Solución:

M = Número de maneras de seleccionar una lavadora Whirpool

N = Número de maneras de seleccionar una lavadora de la marca Easy

W = Número de maneras de seleccionar una lavadora de la marca General Electric

M = 2 x 4 x 2 = 16 maneras

N = 3 x 2 x 2 = 12 maneras

W = 1 x 2 x 1 = 2 maneras

M + N + W = 16 + 12 + 2 = <u>30 maneras de seleccionar una lavadora</u>

=== Principio de la Suma o de la Adición ===
Si una primera operación puede realizarse de m maneras y una segunda operación de n maneras, entonces una operación o la otra pueden efectuarse de:

                     m+n maneras.

'''<u>Ejemplo:</u>'''

Una pareja que se tiene que casar, junta dinero para el enganche de su casa, en el fraccionamiento lomas de la presa le ofrecen un modelo económico o un condominio, en el fraccionamiento Playas le ofrecen un modelo económico como modelos un residencial, un californiano y un provenzal. ¿Cuántas alternativas diferentes de vivienda le ofrecen a la pareja?

PRESA                     PLAYAS

Económico             Residencial

Condominio           Californiano

                             Provenzal

  m=2                           n=3            b=7        v=9         e=3      q=1        x=54           p=67        y=90       

          2+3= 5 maneras

=== Principio de permutación ===

A diferencia de la fórmula de la multiplicación, se la utiliza para determinar el número de posibles arreglos cuando solo hay un solo grupo de objetos. Permutación: un arreglo o posición de r objetos seleccionados de un solo grupo de n objetos posibles. Si nos damos cuenta los arreglos a, b, c y b, a, c son permutaciones diferentes, la fórmula que se utiliza para contar el número total de permutaciones distintas es: 

                                             <u>FÓRMULA</u>: n P r = n!/(n - r)!

'''<u>Ejemplo:</u>''' ¿Cómo se puede designar los cuatro primeros lugares de un concurso, donde existen 15 participantes?

Aplicando la fórmula de la permutación tenemos:                                         

n P r = n! (n - r)! = 15! = 15*14*13*12 *11*10*9*8*7*6*5*4*3*2*1 /(15-4)! 11*10*9*8*7*6*5*4*3*2*1 = 32760

Donde:

n= número total de objetos

r= número de objetos seleccionados

!= factorial, producto de los números naturales entre 1 y n.

NOTA: se pueden cancelar números cuando se tienen las mismas cifras en numerador y denominador.

=== Principio de combinación ===

En una [[permutación]], el orden de los objetos de cada posible resultado es diferente. Si el orden de los objetos no es importante, cada uno de estos resultados se denomina [[Combinación (matemáticas)|combinación]]. Por ejemplo, si se quiere formar un equipo de trabajo formado por 2 personas seleccionadas de un grupo de tres (A, B y C). Si en el equipo hay dos funciones diferentes, entonces si importa el orden, los resultados serán permutaciones. Por el contrario si en el equipo no hay funciones definidas, entonces no importa el orden y los resultados serán combinaciones. Los resultados en ambos casos son los siguientes:

Permutaciones: AB, AC, BA, CA, BC, CB

Combinaciones: AB, AC, BC

Combinaciones: Es el número de formas de seleccionar r objetos de un grupo de n objetos sin importar el orden.

La fórmula de combinaciones es:

                                  n C r = n! / [r!(n – r)!]

<u>'''Ejemplo:'''</u> En una compañía se quiere establecer un código de colores para identificar cada una de las 42 partes de un producto. Se quiere marcar con 3 colores de un total de 7 cada una de las partes, de tal suerte que cada una tenga una combinación de 3 colores diferentes. ¿Será adecuado este código de colores para identificar las 42 partes del producto?
Usando la fórmula de combinaciones:

                 n! = 7! = 5040
                 r! (n – r )! =  3! (7 – 3)! = 3! 4! =6 * 24 = 144

Entonces:        n C r = 5040 / 144 =35

El tomar tres colores de 7 posibles no es suficiente para identificar las 42 partes del producto.

== Véase también ==
* [[Permutación]] 
* [[Coeficiente binomial]]
* [[Teoría de Ramsey]]
* [[Combinaciones con repetición]]
*[[Factorial|Factorial de un número]]
{{Portal|Matemática}}

== Referencias ==
{{listaref}}

=== 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. Ámsterdam, 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
* ''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/
*https://www.unirioja.es/talleres/creatividad_matematica/SeminarioBachillerato/COMBINATORIA.pdf
*https://sites.google.com/site/estadisticayprobabilidad111/8---principio-fundamental-de-conteo
*https://www.varsitytutors.com/hotmath/hotmath_help/spanish/topics/fundamental-counting-principle#:~:text=El%20principio%20fundamental%20de%20conteo,formas%20de%20hacer%20ambas%20cosas.&text=resultados%20posibles%20del%20experimento.,tenga%20m%C3%A1s%20de%202%20opciones.

== Enlaces externos ==

* [https://guias.usal.es/node/222245 Matemática Discreta y Lógica - Universidad de Salamanca]
{{traducido ref|en|Combinatorics|oldid=751280119|24 de noviembre de 2016|parcial}}
{{commonscat|Combinatorics|Combinatoria}}
* {{springer|title=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"] {{Wayback|url=http://www.math.illinois.edu/~dwest/openp/gloss.html |date=20170817044031 }}
* [http://www.mat.univie.ac.at/~slc/divers/software.html List of Combinatorics Software and Databases]
*[https://upcommons.upc.edu/bitstream/handle/2117/186922/matd-combinatoria-recurrencias-4760.pdf Ejemplos y demostraciones. Combinatoria]
*[https://www.youtube.com/watch?v=cx-zcOhmBcY Principio de Inclusión-Exclusión]

* http://portal.perueduca.edu.pe/modulos/mod_matconteo/mod_4publish/index.html
* http://cibermath.com/cuarto/principios-fundamentales-de-conteo.htm
[[Categoría:Combinatoria| ]]