Ver el código de «Combinación (matemáticas)»

En [[matemáticas]] y, en concreto, en [[combinatoria]], una '''combinación''' es una selección de elementos de un conjunto que tiene miembros distintos, de modo que el orden de selección no importa (a diferencia de las [[Permutación|permutaciones]]). Por ejemplo, dadas tres frutas, digamos una manzana, una naranja y una pera, hay tres combinaciones de dos frutas que se pueden extraer de este conjunto: podemos elegir una manzana y una pera; una manzana y una naranja; o una pera y una naranja. Más formalmente, una ''k''-combinación de un [[conjunto]] ''S'' es un [[subconjunto]] de ''k'' elementos distintos de ''S.'' Dos combinaciones son idénticas si y solo si cada combinación tiene los mismos miembros. (El orden de elección de los elementos no importa; si el orden importara, elegir la manzana y luego la pera sería distinto de elegir la pera y luego la manzana).

Si el conjunto donde elegir tiene ''n'' elementos, el número de ''k'' combinaciones (es decir, el número de subconjuntos de ''k'' elementos), denotado por <math>C(n,k)</math> o <math>C^n_k</math>, es igual al [[coeficiente binomial]]

<math display="block"> \binom nk = \frac{n(n-1)\dotsb(n-k+1)}{k(k-1)\dotsb1},</math>

que se puede escribir usando [[Factorial|factoriales]] como <math>\textstyle\frac{n!}{k!(n-k)!}</math> cuando <math>k\leq n</math>, y vale cero cuando <math>k>n</math> (no hay ningún subconjunto de más elementos que el total). 

Esta fórmula se demuestra de la manera siguiente: Primero elegimos ''k'' elementos distintos del conjunto de ''n'' por orden. Para elegir el primero tenemos ''n'' opciones; para el segundo, como ya no podemos elegir el ya hemos elegido, ''n-1'' opciones; para el tercero, ''n-2'', y así hasta el ''k''-ésimo, para el que tenemos ''n-(k-1)=n-k+''1 opciones. En total tenemos ''n(n-1)···(n-k+1)'' opciones para elegir los ''k'' elementos por orden. 

Así tendríamos el número de elecciones ''ordenadas'' de ''k'' elementos. En efecto, contando de esta forma, estamos contando varias veces la misma selección de elementos simplemente porque los hemos tomado en órdenes distintos. Por ejemplo, estamos contando como distintas las elecciones que toman los mismos elementos pero que el primer elemento que elige una la otra lo elige en último lugar. En general, estamos contando cada combinación (cada elección de un mismo subconjunto de elementos) tantas veces como maneras tenemos de reordenar sus elementos (formas de elegirlos en un cierto orden). Como el número de formas de reordenar un conjunto de ''k'' elementos es ''k!=k(k-1)···1'', el número de elecciones de ''k'' elementos sin importar su orden (i.e. de ''k''-combinaciones) es

<math display="block"> \binom nk = \frac{n(n-1)\dotsb(n-k+1)}{k(k-1)\dotsb1}</math>

Una combinación es una combinación de ''n'' cosas tomadas ''k'' a la vez ''sin repetición''. Para referirse a combinaciones en las que se permite la repetición, a menudo se utilizan los términos<ref>When the term ''combination'' is used to refer to either situation (as in {{Cita Harvard|Brualdi|2010}}) care must be taken to clarify whether sets or multisets are being discussed.</ref> ''k''-combinación con repetición, ''k''-[[multiconjunto]], <ref>{{Harvsp|Mazur|2010|loc=p. 10}}</ref> o ''k''-selección.<ref>{{Harvsp|Ryser|1963|loc=p. 7}} also referred to as an ''unordered selection''.</ref> Si en el ejemplo anterior de las frutas fuera posible tener más de un ejemplar de fruta de cada tipo habría tres selecciones 2 más: una con dos manzanas, una con dos naranjas y una con dos peras.

Aunque el conjunto de tres frutas era lo suficientemente pequeño para escribir una lista completa de combinaciones, esto se vuelve poco práctico a medida que aumenta el tamaño del conjunto. Por ejemplo, una [[Manos de póquer|mano de póquer]] se puede describir como una combinación de 5 (''k''&nbsp;=&nbsp;5) de cartas de una baraja de 52 cartas (''n''&nbsp;=&nbsp;52). Las 5 cartas de la mano son todas distintas, y el orden de las cartas en la mano no importa (te repartan las cartas en el orden en que te las repartan, la mano que tienes es la misma). Usando la fórmula de arriba, hay 2.598.960 combinaciones de este tipo y la probabilidad de sacar una mano concreta al azar es por tanto de 1&nbsp;/&nbsp;2.598.960.

== Número de ''k'' combinaciones ==
[[Archivo:Combinations_without_repetition;_5_choose_3.svg|miniaturadeimagen| Subconjuntos de 3 elementos de un conjunto de 5 elementos]]
El número de ''k''-combinaciones de un conjunto ''S'' de ''n'' elementos se denota a menudo en textos de [[combinatoria]] elemental por <math>C(n,k)</math>, o mediante variaciones como <math>C^n_k</math>, <math>{}_nC_k</math>, <math>{}^nC_k</math>, <math>C_{n,k}</math> o incluso <math>C_n^k</math> <ref>{{Harvsp|Uspensky|1937|p=18}}</ref> (la última forma es estándar en los textos en francés, rumano, ruso y chino<ref>{{Cita libro|título=High School Textbook for full-time student (Required) Mathematics Book II B|edición=2nd|ubicación=China|idioma=zh|fecha=June 2006|editorial=People's Education Press|páginas=107–116|isbn=978-7-107-19616-4}}</ref><ref>{{Cita libro|url=http://www.shuxue9.com/pep/gzxuanxiu23/ebook/31.html|título=人教版高中数学选修2-3 (Mathematics textbook, volume 2-3, for senior high school, People's Education Press)|editorial=People's Education Press|página=21}}</ref>). Sin embargo, el mismo número aparece en muchos otros contextos matemáticos, donde se denota por <math>\tbinom nk</math> (a menudo leído como " ''n'' sobre ''k'' "); en particular, aparece como coeficiente en la [[Teorema del binomio|fórmula binomial]], y de ahí su nombre, [[coeficiente binomial]]. 

Se puede definir <math>\tbinom nk</math> para todos los números naturales ''k'' a la vez por la relación (dada por la fórmula binomial)

<math display="block">(1 + X)^n = \sum_{k\geq0}\binom{n}{k} X^k,</math>

de lo cual se desprende claramente que

<math display="block">\binom{n}{0} = \binom{n}{n} = 1,</math>

y además

<math display="block">\binom{n}{k} = 0</math>

para ''k > n''.

Para ver que estos coeficientes cuentan ''k''-combinaciones de ''S'', primero se puede considerar una colección de ''n'' variables distintas ''X''<sub>''s''</sub> etiquetadas por los elementos ''s'' de ''S'', y expandir el [[Multiplicación|producto]] sobre todos los elementos de ''S'':

<math display="block">\prod_{s\in S}(1+X_s);</math>

Expandiendo el producto en una suma, esta tiene 2<sup>''n''</sup> sumandos distintos correspondientes a todos los subconjuntos de ''S'': cada sumando es el producto de unas <math>X_{s_1}X_{s_2}\dots X_{s_k}</math> y a cada uno de estos le podemos hacer corresponder el subconjunto <math>\{s_1,s_2,\dots,s_k\}\subseteq S</math>. Ahora, si denotamos todas las variables ''X''<sub>''s''</sub> como una variable no etiquetada ''X'', de modo que el producto se convierte en {{Nowrap|(1 + ''X'')<sup>''n''</sup>}}, la expresión <math>X_{s_1}X_{s_2}\dots X_{s_k}</math> de cada ''k''-combinación de ''S'' se convierte indistintamente de sus elementos y su orden en ''X''<sup>''k''</sup>, de modo que el coeficiente de esa potencia en el resultado es igual al número de dichas ''k''-combinaciones.

Los coeficientes binomiales se pueden calcular explícitamente de varias maneras. Para obtenerlos todos para las expansiones de (1 + ''X''), (1 + ''X'')<sup>2</sup>, ..., {{Nowrap|(1 + ''X'')<sup>''n''</sup>}}, se puede utilizar (además de los casos básicos ya dados) la relación de recursión

<math display="block">\binom{n}{k} = \binom{n - 1}{k - 1} + \binom{n - 1}{k},</math>

para 0 < ''k'' < ''n'', lo cual se sigue algebraicamente de que {{Nowrap|(1 + ''X'')<sup>''n''</sup>}} = {{Nowrap|(1 + ''X'')<sup>''n'' − 1</sup>(1 + ''X'')}}; esto conduce a la construcción del [[triángulo de Pascal]]. Una manera combinatoria de justificar esta relación surge de usar que <math>\tbinom nk</math> es el número de subconjuntos de ''k'' elementos de un conjunto ''S'' de ''n''. Así, fijamos un elemento <math>s_0\in S</math>. Los subconjuntos de ''k'' elementos de ''S'' se pueden separar en aquellos que contengan a ''s<sub>0</sub>'' y aquellos que no. Podemos calcular la cantidad que hay de los primeros: al haber elegido ya el elemento ''s<sub>0</sub>,'' sólo nos faltan por elegir ''k-1'' elementos de los ''n-1'' restantes. De estos hay <math>\tbinom {n-1}{k-1}</math>. Por otro lado, también podemos contar el número de ''k''-combinaciones que ''no'' contienen a ''s<sub>0</sub>'': hay que elegir un subconjunto de ''k'' elementos de los ''n-1'' restantes, esto es, hay <math>\tbinom {n-1}{k}</math> opciones. De aquí se sigue que <math>\tbinom nk =\tbinom{n-1}{k-1}+\tbinom{n-1}{k}</math>.

Para determinar un coeficiente binomial individual, es más práctico utilizar la fórmula

<math display="block">\binom nk = \frac{n(n-1)(n-2)\cdots(n-k+1)}{k!},</math>

cuya demostración ya se ha dado en la introducción.

Cuando ''k'' es mayor que ''n''/2, la fórmula anterior contiene factores comunes en el numerador y el denominador, y al cancelarlos se obtiene la relación

<math display="block"> \binom nk = \binom n{n-k},</math>

para 0 ≤ ''k'' ≤ ''n''. Esto expresa una simetría que es evidente a partir de la fórmula binomial, y que también puede entenderse en términos de ''k''-combinaciones tomando el [[Complemento de un conjunto|complemento]] de dicha combinación, que es una {{Nowrap|(''n'' − ''k'')}}-combinación (cada ''k''-combinación determina una (''n - k'')-combinación y viceversa: aquellos elementos que no han sido escogidos; por tanto tiene que haber la misma cantidad de cada una).

Finalmente, hay una fórmula que muestra esta simetría directamente y tiene el mérito de ser fácil de recordar:

<math display="block"> \binom nk = \frac{n!}{k!(n-k)!},</math>

donde ''n''<nowiki>!</nowiki> denota el [[factorial]] de ''n''. Se obtiene de la fórmula anterior multiplicando denominador y numerador por {{Nowrap|(''n'' − ''k'')}}! , por lo que de hecho computacionalmente es menos eficiente que esa fórmula.


De las fórmulas anteriores se deducen las relaciones entre los números adyacentes en el triángulo de Pascal en las tres direcciones:

<math display="block">
\binom nk =
\begin{cases}
\binom n{k-1} \frac {n-k+1}k &\quad \text{si } k > 0 \\
\binom {n-1}k \frac n{n-k} &\quad \text{si } k < n \\
\binom {n-1}{k-1} \frac nk &\quad \text{si } n, k > 0
\end{cases}.
</math>

Junto con los casos básicos <math>\tbinom n0=1=\tbinom nn</math>, estos permiten el cálculo sucesivo de todos los números de combinaciones de un conjunto de un mismo número de elementos (una fila en el triángulo de Pascal), de ''k''-combinaciones de conjuntos de tamaños crecientes y de combinaciones con un [[Complemento de un conjunto|complemento]] de tamaño fijo {{Nowrap|''n'' − ''k''}}.

=== Ejemplo de conteo de combinaciones ===
Como ejemplo concreto, se puede calcular el número de manos de cinco cartas posibles a partir de una baraja estándar de cincuenta y dos cartas como: <ref>{{Harvsp|Mazur|2010|loc=p. 21}}</ref>

<math display="block"> {52 \choose 5} = \frac{52\times51\times50\times49\times48}{5\times4\times3\times2\times1} = \frac{311{,}875{,}200}{120} = 
2{,}598{,}960.</math>

Alternativamente, se puede utilizar la fórmula en términos de factoriales y cancelar algunos factores del numerador con algunos del denominador, después de lo cual sólo se requiere la multiplicación de los factores restantes: <math display="block">\begin{alignat}{2}
 {52 \choose 5}
  &= \frac{52!}{5!47!} \\[5pt]
  &= \frac{52\times51\times50\times49\times48\times\cancel{47!}}{5\times4\times3\times2\times\cancel{1}\times\cancel{47!}} \\[5pt]
  &= \frac{52\times51\times50\times49\times48}{5\times4\times3\times2} \\[5pt]
  &= \frac{(26\times\cancel{2})\times(17\times\cancel{3})\times(10\times\cancel{5})\times49\times(12\times\cancel{4})}{\cancel{5}\times\cancel{4}\times\cancel{3}\times\cancel{2}} \\[5pt]
  &= {26\times17\times10\times49\times12} \\[5pt]
  &= 2{,}598{,}960.
\end{alignat}</math>

Otro cálculo alternativo, equivalente al primero, se basa en escribir

<math display="block"> {n \choose k} = \frac { ( n - 0 ) }1 \times \frac { ( n - 1 ) }2 \times \frac { ( n - 2 ) }3 \times \cdots \times \frac { ( n - (k - 1) ) }k,</math>

lo cual da

<math display="block"> {52 \choose 5} = \frac{52}1 \times \frac{51}2 \times \frac{50}3 \times \frac{49}4 \times \frac{48}5 = 2{,}598{,}960.</math>

Cuando se evalúa en el siguiente orden, {{Math|52 ÷ 1 × 51 ÷ 2 × 50 ÷ 3 × 49 ÷ 4 × 48 ÷ 5}}, esto se puede calcular utilizando sólo aritmética de [[Número entero|números enteros]]. La razón es que cuando se calcula cada división, el resultado intermedio que se produce es en sí mismo un coeficiente binomial, por lo que nunca se producen [[División (matemática)|restos]] (los coeficientes binomiales son por definición el número de combinaciones de un conjunto, es decir, números enteros).

Utilizando la fórmula simétrica en términos de factoriales sin realizar simplificaciones se obtiene un cálculo bastante extenso:

<math display="block">
\begin{align}
 {52 \choose 5} &= \frac{n!}{k!(n-k)!} = \frac{52!}{5!(52-5)!} = \frac{52!}{5!47!} \\[6pt]
&= \tfrac{80,658,175,170,943,878,571,660,636,856,403,766,975,289,505,440,883,277,824,000,000,000,000}{120\times258,623,241,511,168,180,642,964,355,153,611,979,969,197,632,389,120,000,000,000} \\[6pt]
&= 2{,}598{,}960.
\end{align}</math>

=== Enumeración de ''k''-combinaciones ===
Se pueden [[Enumeración|enumerar]] todas ''las k''-combinaciones de un conjunto dado ''S'' de ''n'' elementos en un orden fijo, lo que establece una [[Función biyectiva|biyección]] de un intervalo de <math>\tbinom nk</math> números enteros con el conjunto de esas ''k''-combinaciones. Suponiendo que ''S'' es un conjunto ordenado, por ejemplo ''S'' = {1, 2, ..., ''n''}, hay dos posibilidades naturales para ordenar sus ''k'' combinaciones: comparando primero sus elementos más pequeños (como en las ilustraciones anteriores) o comparando primero sus elementos más grandes. La última opción tiene la ventaja de que agregar un nuevo elemento más grande a ''S'' no cambiará la parte inicial de la enumeración, sino que sólo agregará las nuevas ''k''-combinaciones del conjunto más grande después de las anteriores. Repitiendo este proceso, la enumeración puede extenderse indefinidamente con ''k''-combinaciones de conjuntos cada vez más grandes. Si además se toman los intervalos de los números enteros comenzando en el &nbsp;0, entonces la ''i''-ésima ''k''-combinación de la enumeración se puede calcular fácilmente a partir de ''i'', y la biyección así obtenida se conoce como [[Sistema de numeración combinatoria|sistema numérico combinatorio]]. También se conoce como "rango"/"ranking" y "unranking" en matemáticas computacionales. <ref>{{Cita web|url=http://www.site.uottawa.ca/~lucia/courses/5165-09/GenCombObj.pdf|título=Generating Elementary Combinatorial Objects|fechaacceso=2017-04-10|autor=Lucia Moura|sitioweb=Site.uottawa.ca|urlarchivo=https://ghostarchive.org/archive/20221009/http://www.site.uottawa.ca/~lucia/courses/5165-09/GenCombObj.pdf|fechaarchivo=2022-10-09}}</ref> <ref>{{Cita web|url=http://www.sagemath.org/doc/reference/sage/combinat/subset.html|título=SAGE : Subsets|fechaacceso=2017-04-10|sitioweb=Sagemath.org|formato=PDF}}</ref>

Hay muchas formas de enumerar ''k''-combinaciones. Una forma es rastrear los números de índice ''k'' de los elementos seleccionados, comenzando con {0 .. ''k'' −1} (basado en cero) o {1 .. ''k'' } (basado en uno) como la primera ''k''-combinación permitida. Luego, pasar repetidamente a la siguiente ''k-''combinación permitida incrementando el número de índice más pequeño para el cual esto no crearía dos números de índice iguales y, al mismo tiempo, restableciendo todos los números de índice más pequeño a sus valores iniciales.

== Combinaciones con repetición ==
Una ''k''-'''combinación con repetición''', o ''k''-'''multicombinación''', o '''[[Multiconjunto|multisubconjunto]]''' de tamaño ''k'' de un conjunto ''S'' de tamaño ''n'' queda definida por un conjunto de ''k'' elementos no necesariamente distintos de ''S'', donde no se tiene en cuenta el orden: dos secuencias definen el mismo multiconjunto si una puede obtenerse de la otra permutando los términos. En otras palabras, es una elección de ''k'' elementos de un conjunto de ''n'' elementos que permite duplicados (es decir, con reemplazo) pero ignora ordenamientos diferentes (por ejemplo, {2,1,2} = {1,2,2}). Si se asocia un índice a cada elemento de ''S'' y se piensa en los elementos de ''S'' como ''tipos'' de objetos, entonces podemos denotar por <math>x_i</math> el número de elementos del tipo ''i'' en un multisubconjunto. 

Volviendo al ejemplo de las frutas de la introducción, teníamos tres frutas: una manzana, una naranja y una pera. Las 2-combinaciones eran elecciones de subconjuntos de dos elementos (de dos frutas distintas). Para entender las ''k''-multicombinaciones, o multiconjuntos de ''k'' elementos, supóngase que tenemos una cantidad arbitrariamente grande de esas frutas (las manzanas, naranjas y peras son los ''tipos'' de fruta anteriores). Las 2-multicombinaciones se corresponderían con elegir dos frutas cualesquiera, permitiendo duplicados: podemos tomar dos manzanas, dos naranjas o dos peras además de las 2-combinaciones. Las ''k''-multicombinaciones se corresponderían con tomar ''k'' frutas cualesquiera, permitiendo repetir tipos.

Otra manera de verlo es que el número de multisubconjuntos de tamaño ''k'' de un conjunto de tamaño ''n'' es el número de soluciones enteras no negativas (lo que permite cero) de la [[ecuación diofántica]]: <ref>{{Harvsp|Brualdi|2010|loc=p. 52}}</ref>

<math display="block">x_1 + x_2 + \ldots + x_n = k.</math>

En efecto, el conjunto <math>\{1,\dots, n\}</math> es el conjunto de tipos de objetos que hay para elegir. De cada tipo ''i'' tenemos que elegir una cantidad ''x<sub>i</sub>'' de manera que en total la cantidad de objetos elegidos sea ''k'', es decir, imponemos que <math>x_1 + x_2 + \ldots + x_n = k.</math>

Si ''S'' tiene ''n'' elementos, el número de ''k-'' multisubconjuntos se denota por

<math display="block">\left(\!\!\binom{n}{k}\!\!\right),</math>

una notación análoga al [[coeficiente binomial]], que cuenta ''k''-subconjuntos. Esta expresión también se puede dar en términos de coeficientes binomiales:

<math display="block">\left(\!\!\binom{n}{k}\!\!\right)=\binom{n+k-1}{k}.</math>

Esta relación se puede demostrar fácilmente utilizando una representación conocida como [[Barras y estrellas (combinatoria)|barras y estrellas]]:<ref>In the article [[Barras y estrellas (combinatoria)|Stars and bars (combinatorics)]] the roles of {{Mvar|n}} and {{Mvar|k}} are reversed.</ref>

 '''Demostración:'''{{Artículo principal|Barras y estrellas (combinatoria)}}

Podemos representar una solución de la ecuación diofántica anterior como sigue. Dibujamos <math>x_1</math> ''estrellas'', luego un separador (una ''barra''), luego otras <math>x_2</math> estrellas, luego otra barra, y así sucesivamente. El número total de estrellas en esta representación es ''k'' y el número total de barras, ''n -'' 1 (pues una separación en ''n'' partes necesita ''n -'' 1 separadores). Así pues, una secuencia de ''k + n -'' 1 símbolos (estrellas y barras) corresponde a una solución de la ecuación si contiene ''k'' estrellas. Cualquier solución se puede representar eligiendo ''k'' de las ''k + n -'' 1 posiciones para ser ocupadas por estrellas, y rellenando las otras con barras. Por ejemplo, la solución <math>x_1=3,x_2=2,x_3=0,x_4=5</math> de la ecuación <math>x_1+x_2+x_3+x_4=10</math> (''n ='' 4 y ''k ='' 10) se puede representar por 

☆☆☆|☆☆||☆☆☆☆☆.

Así pues, hay una [[Función biyectiva|biyección]] entre ''k''-multiconjuntos de un conjunto de ''n'' elementos y colocaciones de ''k'' estrellas en una lista de ''k + n -'' 1 símbolos, por lo que hay la misma cantidad de una cosa que da la otra. Pero la segunda cosa son el número de subconjuntos de ''k'' elementos de uno de ''k + n -'' 1 elementos, es decir, viene dado, por definición, por <math>\tbinom{n+k-1}{k}.\quad\square</math>
[[Archivo:Combinations_with_repetition;_5_multichoose_3.svg|miniaturadeimagen|405x405px| [[Función biyectiva|Biyección]] entre 3-subconjuntos de un 7-conjunto (izquierda) y 3-multiconjuntos con elementos de un 5-conjunto (derecha).<br />Esto ilustra que <math display="inline"> \binom{7}{3} = \left(\!\! \binom{5}{3}\!\!\right)</math> .]]
Igual que con los coeficientes binomiales, existen varias relaciones entre estas expresiones de elección múltiple. Por ejemplo, para <math> n \ge 1, k \ge 0</math>, se satisface que

<math display="block">\left(\!\!\binom{n}{k}\!\!\right)=\left(\!\!\binom{k+1}{n-1}\!\!\right).</math>Esta identidad se desprende del intercambio de las estrellas y las barras en la representación anterior.<ref>{{Harvsp|Benjamin|Quinn|2003|loc=p. 72 (identity 145)}}</ref>

=== Ejemplo de conteo de multisubconjuntos ===
Por ejemplo, si hay cuatro tipos de donuts (''n''&nbsp;=&nbsp;4) en un menú para elegir y se quieren tres donuts (''k''&nbsp;=&nbsp;3), el número de formas de elegir las donuts (con repetición porque podemos pedir el mismo más de una vez) se puede calcular como

<math display="block">\left(\!\!\binom{4}{3}\!\!\right) = \binom{4+3-1}3 = \binom{6}{3} = \frac{6 \times 5 \times 4}{3 \times 2 \times 1} = 20.</math>

Este resultado se puede verificar enumerando todos los 3-multisubconjuntos del conjunto ''S'' = {1,2,3,4}. Esto se muestra en la siguiente tabla.<ref>{{Harvsp|Benjamin|Quinn|2003|loc=p. 71}}</ref> La segunda columna enumera los donuts que realmente eligió, la tercera columna muestra las solución entera no negativa <math>[x_1,x_2,x_3,x_4]</math> de la ecuación <math>x_1 + x_2 + x_3 + x_4 = 3</math> que se corresponde con la elección y la última columna da la representación de las soluciones mediante estrellas y barras. <ref>{{Harvsp|Mazur|2010|loc=p. 10}} where the stars and bars are written as binary numbers, with stars = 0 and bars = 1.</ref>
{| class="wikitable" style="margin-left: auto; margin-right: auto; border; none"
!N.º
!3-multiset
!Eq. solution
!Stars and bars
|-
|1
|{1,1,1}
|[3,0,0,0]
|<math>\bigstar \bigstar \bigstar |||</math>
|-
|2
|{1,1,2}
|[2,1,0,0]
|<math>\bigstar \bigstar | \bigstar ||</math>
|-
|3
|{1,1,3}
|[2,0,1,0]
|<math>\bigstar \bigstar ||\bigstar|</math>
|-
|4
|{1,1,4}
|[2,0,0,1]
|<math>\bigstar \bigstar |||\bigstar</math>
|-
|5
|{1,2,2}
|[1,2,0,0]
|<math>\bigstar |\bigstar \bigstar ||</math>
|-
|6
|{1,2,3}
|[1,1,1,0]
|<math>\bigstar |\bigstar |\bigstar|</math>
|-
|7
|{1,2,4}
|[1,1,0,1]
|<math>\bigstar |\bigstar ||\bigstar</math>
|-
|8
|{1,3,3}
|[1,0,2,0]
|<math>\bigstar || \bigstar \bigstar |</math>
|-
|9
|{1,3,4}
|[1,0,1,1]
|<math>\bigstar ||\bigstar|\bigstar</math>
|-
|10
|{1,4,4}
|[1,0,0,2]
|<math>\bigstar |||\bigstar \bigstar</math>
|-
|11
|{2,2,2}
|[0,3,0,0]
|<math>|\bigstar \bigstar \bigstar ||</math>
|-
|12
|{2,2,3}
|[0,2,1,0]
|<math>|\bigstar \bigstar | \bigstar|</math>
|-
|13
|{2,2,4}
|[0,2,0,1]
|<math>|\bigstar \bigstar ||\bigstar</math>
|-
|14
|{2,3,3}
|[0,1,2,0]
|<math>|\bigstar |\bigstar \bigstar |</math>
|-
|15
|{2,3,4}
|[0,1,1,1]
|<math>|\bigstar | \bigstar | \bigstar</math>
|-
|16
|{2,4,4}
|[0,1,0,2]
|<math>|\bigstar ||\bigstar \bigstar</math>
|-
|17
|{3,3,3}
|[0,0,3,0]
|<math>||\bigstar \bigstar \bigstar |</math>
|-
|18
|{3,3,4}
|[0,0,2,1]
|<math>||\bigstar \bigstar |\bigstar</math>
|-
|19
|{3,4,4}
|[0,0,1,2]
|<math>||\bigstar |\bigstar \bigstar</math>
|-
|20
|{4,4,4}
|[0,0,0,3]
|<math>|||\bigstar \bigstar \bigstar</math>
|}

== Número de formas de colocar objetos en contenedores ==
Una combinación también puede pensarse como una selección de ''dos'' conjuntos de elementos: los que van en el contenedor "de elementos elegidos" y los que van en el contenedor "de elementos no elegidos". Esto se puede generalizar a cualquier número de contenedores con la restricción de que cada artículo debe ir exactamente a un contenedor. El número de formas de colocar objetos en contenedores viene dado por el [[Teorema multinomial|coeficiente multinomial]]

<math display="block"> {n \choose k_1, k_2, \ldots, k_m} = \frac{n!}{k_1!\, k_2! \cdots k_m!},</math>

donde ''n'' es el número de artículos, ''m'' es el número de contenedores y <math>k_i</math> es el número de artículos que van al contenedor ''i''.

Una forma de ver por qué se cumple esta ecuación es numerar primero los objetos arbitrariamente del ''1'' al ''n'' y poner los objetos con números <math>1, 2, \ldots, k_1</math> En el primer contenedor, en orden, los objetos con números <math>k_1+1, k_1+2, \ldots, k_2</math> en el segundo contenedor en orden, y así sucesivamente. Hay <math>n!</math> numeraciones distintas, pero muchas de ellas son equivalentes, porque lo que importa es el conjunto de elementos en un contenedor, no su orden en el mismo. Cada permutación del contenido de cada contenedor produce una forma equivalente de colocar los elementos en los contenedores. Sabemos que el número de maneras de reordenar <math>k_i</math> elementos es <math>k_i!</math>. Como resultado, cada [[clase de equivalencia]] consta de <math>k_1!\, k_2! \cdots k_m!</math> numeraciones distintas, y el número de clases de equivalencia es <math>\textstyle\frac{n!}{k_1!\, k_2! \cdots k_m!}</math>.

El coeficiente binomial es el caso especial en el que ''k'' elementos entran en el contenedor elegido y el resto (<math>n-k</math>) de los artículos van al contenedor de no elegidos. En ese caso, la fórmula anterior recupera la del coeficiente binomial:

<math display="block"> \binom nk = {n \choose k, n-k} = \frac{n!}{k!(n-k)!}. </math>

== Véase también ==

*  [[Coeficiente binomial]]
* [[Combinatoria]]
* [[Diseño de bloque]]
* [[Grafo de Kneser]]
* [[Multiconjunto]]
* [[Triángulo de Pascal]]
* [[Permutación]]
* [[Probabilidad]]
* [[Subconjunto]]

== Notas y referencias ==
{{Listaref|30em}}

== Bibliografía ==

* {{Obra citada|título=Proofs that Really Count: The Art of Combinatorial Proof|apellidos=Benjamin|nombre=Arthur T.|enlaceautor=Arthur T. Benjamin|editorial=The Mathematical Association of America|serie=The Dolciani Mathematical Expositions 27|apellidos2=Quinn|nombre2=Jennifer J.|enlaceautor2=Jennifer Quinn|ISBN=978-0-88385-333-7|year=2003}}
* {{Obra citada|título=Introductory Combinatorics|apellidos=Brualdi|nombre=Richard A.|enlaceautor=Richard A. Brualdi|edición=5th|editorial=Pearson Prentice Hall|ISBN=978-0-13-602040-0|year=2010}}
* Erwin Kreyszig, ''Advanced Engineering Mathematics'', John Wiley & Sons, INC, 1999.
* {{Obra citada|título=Combinatorics: A Guided Tour|apellidos=Mazur|nombre=David R.|editorial=Mathematical Association of America|ISBN=978-0-88385-762-5|year=2010}}
* {{Obra citada|título=Combinatorial Mathematics|apellidos=Ryser|nombre=Herbert John|enlaceautor=H. J. Ryser|editorial=Mathematical Association of America|serie=The Carus Mathematical Monographs 14|year=1963}}
* {{Obra citada|título=Introduction to Mathematical Probability|apellidos=Uspensky|nombre=James|enlaceautor=J. V. Uspensky|url=https://archive.org/details/in.ernet.dli.2015.263184/page/n25/mode/2up|editorial=McGraw-Hill|year=1937}}

== Enlaces externos ==
{{Traducido ref|en|Combination|oldid=1236399734}}
* [https://www.topcoder.com/community/data-science/data-science-tutorials/basics-of-combinatorics/ Tutorial de Topcoder sobre combinatoria]
* [http://mathforum.org/library/drmath/sets/high_perms_combs.html Muchos tipos de problemas comunes sobre permutaciones y combinaciones, con soluciones detalladas]
* [http://www.murderousmaths.co.uk/books/unknownform.htm La fórmula desconocida] para combinaciones en las que las elecciones se pueden repetir y el orden ''no'' importa
* [http://www.lucamoroni.it/the-dice-roll-sum-problem/ Problema del lanzamiento de dados con una suma dada] Una aplicación de las combinaciones con repetición al lanzamiento de múltiples dados
{{Control de autoridades}}
[[Categoría:Combinatoria]]
[[Categoría:Wikipedia:Páginas con traducciones sin revisar]]