Combinación

En matemáticas , una combinación es una selección de elementos de un conjunto que tiene miembros distintos, de tal manera que el orden de selección no importa (a diferencia de las permutaciones ). Por ejemplo, dados tres frutas, digamos una manzana, una naranja y una pera, hay tres combinaciones de dos que se pueden extraer de este conjunto: 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. Por lo tanto, dos combinaciones son idénticas si y solo si cada combinación tiene los mismos miembros. (El orden de los miembros en cada conjunto no importa). Si el conjunto tiene n elementos, el número de k -combinaciones, denotado por $C(n,k)$ o $C_{k}^{n}$ , es igual al coeficiente binomial :

${\binom {n}{k}}={\frac {n(n-1)\dotsb (n-k+1)}{k(k-1)\dotsb 1}},$

que, utilizando la notación factorial , puede expresarse de forma compacta como

${\binom {n}{k}}={\frac {n!}{k!(nk)!}}$

cuando sea $n\geq k\geq 0$ Esta fórmula se puede derivar del hecho de que cada k -combinación de un conjunto S de n miembros tiene $k!$ permutaciones así $P_{k}^{n}=C_{k}^{n}\times k!$ o $C_{k}^{n}=P_{k}^{n}/k!$ . ^{[ 1 ]} El conjunto de todas las k -combinaciones de un conjunto S se suele denotar por $\textstyle {\binom {S}{k}}$ .

Una combinación es una selección de n elementos tomados de k en k sin repetición . Para referirse a combinaciones en las que se permite la repetición, se suelen usar los términos k -combinación con repetición, k - multiconjunto , ^{[ 2 ]} o k- selección, ^{[ 3 ] .}^{[ 4 ]} Si, en el ejemplo anterior, fuera posible tener dos de cualquier tipo de fruta, habría 3 selecciones de 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 como para escribir una lista completa de combinaciones, esto se vuelve impráctico a medida que aumenta el tamaño del conjunto. Por ejemplo, una mano de póker se puede describir como una combinación de 5 cartas ( k = 5) de una baraja de 52 cartas ( n = 52). Las 5 cartas de la mano son todas distintas y el orden de las cartas en la mano no importa. Hay 2.598.960 combinaciones de este tipo, y la probabilidad de obtener cualquier mano al azar es 1 / 2.598.960.

Número de k -combinaciones

El número de k -combinaciones de un conjunto S dado de n elementos se suele denotar en los textos de combinatoria elemental por $C(n,k)$ o mediante una variación como $C_{k}^{n}$ , ${}_{n}C_{k}$ , ${}^{n}C_{k}$ , $C_{n,k}$ o incluso $C_{n}^{k}$ ^{[ 5 ]} (la última forma es estándar en textos franceses, rumanos, rusos y chinos).^{[ 6 ]}^{[ 7 ]} Sin embargo, el mismo número aparece en muchos otros contextos matemáticos, donde se denota por ${\tbinom {n}{k}}$ (a menudo se lee como " n sobre k "); notablemente aparece como un coeficiente en la fórmula binomial , de ahí su nombre de coeficiente binomial. Se puede definir ${\tbinom {n}{k}}$ para todos los números naturales k a la vez por la relación

$(1+X)^{n}=\sum _ {k\geq 0}{\binom {n}{k}}X^{k},$

de lo cual queda claro que

${\binom {n}{0}}={\binom {n}{n}}=1,$

y más

${\binom {n}{k}}=0$

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 _s etiquetadas por los elementos s de S , y expandir el producto sobre todos los elementos de S :

$\prod _{s\in S}(1+X_{s});$

tiene 2 ⁿ términos distintos correspondientes a todos los subconjuntos de S , cada subconjunto da el producto de las variables correspondientes X _s . Ahora, haciendo que todas las X _s sean iguales a la variable sin etiquetar X , de modo que el producto se convierte en (1 + X ) ⁿ , el término para cada k -combinación de S se convierte en X ^k , de modo que el coeficiente de esa potencia en el resultado es igual al número de tales k -combinaciones.

Los coeficientes binomiales se pueden calcular explícitamente de varias maneras. Para obtenerlos todos para las expansiones hasta (1 + X ) ⁿ , se puede utilizar (además de los casos básicos ya dados) la relación de recurrencia.

${\binom {n}{k}}={\binom {n-1}{k-1}}+{\binom {n-1}{k}},$

para 0 < k < n , lo cual se deduce de (1 + X ) ⁿ = (1 + X ) ^{n − 1} (1 + X ) ; esto lleva a la construcción del triángulo de Pascal .

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

${\binom {n}{k}}={\frac {n(n-1)(n-2)\cdots (n-k+1)}{k!}}.$

El numerador da el número de k -permutaciones de n , es decir, de secuencias de k elementos distintos de S , mientras que el denominador da el número de tales k -permutaciones que dan la misma k -combinación cuando se ignora el orden.

Cuando k excede n /2, la fórmula anterior contiene factores comunes al numerador y al denominador, y al cancelarlos se obtiene la relación

${\binom {n}{k}}={\binom {n}{nk}},$

para 0 ≤ k ≤ n . Esto expresa una simetría que es evidente a partir de la fórmula binomial, y también puede entenderse en términos de k -combinaciones tomando el complemento de dicha combinación, que es una ( n − k ) -combinación.

Finalmente, existe una fórmula que muestra directamente esta simetría y que tiene la ventaja de ser fácil de recordar:

${\binom {n}{k}}={\frac {n!}{k!(nk)!}},$

donde n ! denota el factorial de n . Se obtiene de la fórmula anterior multiplicando el denominador y el numerador por ( n − k ) !, por lo que ciertamente es computacionalmente menos eficiente que esa fórmula.

La última fórmula se puede comprender directamente considerando las n ! permutaciones de todos los elementos de S. Cada permutación genera una k -combinación al seleccionar sus primeros k elementos. Existen muchas selecciones duplicadas: cualquier permutación combinada de los primeros k elementos entre sí, y de los últimos ( n − k ) elementos entre sí, produce la misma combinación; esto explica la división en la fórmula.

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

${\binom {n}{k}}={\begin{cases}\displaystyle {\binom {n}{k-1}}{\frac {n-k+1}{k}}&\quad {\text{si }}k>0\\\displaystyle {\binom {n-1}{k}}{\frac {n}{nk}}&\quad {\text{si }}k<n\\\displaystyle {\binom {n-1}{k-1}}{\frac {n}{k}}&\quad {\text{si }}n,k>0\end{cases}}.$

Junto con los casos básicos ${\tbinom {n}{0}}=1={\tbinom {n}{n}}$ , estos permiten el cálculo sucesivo de, respectivamente, todos los números de combinaciones del mismo conjunto (una fila en el triángulo de Pascal), de k -combinaciones de conjuntos de tamaños crecientes y de combinaciones con un complemento de tamaño fijo n − k .

Ejemplo de conteo de combinaciones

Como ejemplo específico, 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: ^{[ 8 ]}

${\binom {52}{5}}={\frac {52\times 51\times 50\times 49\times 48}{5\times 4\times 3\times 2\times 1}}={\frac {311{,}875{,}200}{120}}=2{,}598{,}960.$

Alternativamente, se puede utilizar la fórmula en términos de factoriales y cancelar los factores del numerador contra partes de los factores del denominador, después de lo cual solo se requiere la multiplicación de los factores restantes: ${\begin{alignedat}{2}{\binom {52}{5}}&={\frac {52!}{5!47!}}\\[5pt]&={\frac {52\times 51\times 50\times 49\times 48\times {\cancel {47!}}}{5\times 4\times 3\times 2\times {\cancel {1}}\times {\cancel {47!}}}}\\[5pt]&={\frac {52\times 51\times 50\times 49\times 48}{5\times 4\times 3\times 2}}\\[5pt]&={\frac {(26\times {\cancel {2}})\times (17\times {\cancel {3}})\times (10\times {\cancel {5}})\times 49\times (12\times {\cancel {4}})}{{\cancel {5}}\times {\cancel {4}}\times {\cancel {3}}\times {\cancel {2}}}}\\[5pt]&={26\times 17\times 10\times 49\times 12}\\[5pt]&=2{,}598{,}960.\end{alignedat}}$

Otro cálculo alternativo, equivalente al primero, se basa en la escritura.

${\binom {n}{k}}={\frac {(n-0)}{1}}\times {\frac {(n-1)}{2}}\times {\frac {(n-2)}{3}}\times \cdots \times {\frac {(n-(k-1))}{k}},$

lo cual da

${\binom {52}{5}}={\frac {52}{1}}\times {\frac {51}{2}}\times {\frac {50}{3}}\times {\frac {49}{4}}\times {\frac {48}{5}}=2{}598{}960.$

Al evaluarlo en el siguiente orden: $52 \div 1 \times 51 \div 2 \times 50 \div 3 \times 49 \div 4 \times 48 \div 5$ , se puede calcular utilizando únicamente aritmética de enteros . Esto se debe a que, en cada división, el resultado intermedio es un coeficiente binomial, por lo que no se generan restos.

Utilizar la fórmula simétrica en términos de factoriales sin realizar simplificaciones da como resultado un cálculo bastante extenso:

${\begin{aligned}{\binom {52}{5}}&={\frac {n!}{k!(nk)!}}={\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\times 258,623,241,511,168,180,642,964,355,153,611,979,969,197,632,389,120,000,000,000}}\\[6pt]&=2{,}598{,}960.\end{aligned}}$

Enumeración de k -combinaciones

Se pueden enumerar todas las k -combinaciones de un conjunto S dado de n elementos en algún orden fijo, lo que establece una biyección desde un intervalo de ${\tbinom {n}{k}}$ enteros con el conjunto de esas k -combinaciones. Suponiendo que S está ordenado, por ejemplo S = { 1, 2, ..., n }, existen 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. Esta última opción tiene la ventaja de que añadir un nuevo elemento más grande a S no modificará la parte inicial de la enumeración, sino que simplemente añadirá 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 mayores. Si además se toma que los intervalos de los enteros comiencen en 0, entonces la k -combinación en un lugar dado i en la enumeración puede calcularse fácilmente a partir de i , y la biyección así obtenida se conoce como el sistema numérico combinatorio . También se conoce como "rango"/"clasificación" y "desclasificación" en matemáticas computacionales . ^{[ 9 ]}^{[ 10 ]}

There are many ways to enumerate k combinations. One way is to track k index numbers of the elements selected, starting with {0 .. k−1} (zero-based) or {1 .. k} (one-based) as the first allowed k-combination. Then, repeatedly move to the next allowed k-combination by incrementing the smallest index number for which this would not create two equal index numbers, at the same time resetting all smaller index numbers to their initial values.

Number of combinations with repetition

A k-combination with repetitions, or k-multicombination, or multisubset of size k from a set S of size n is given by a set of k not necessarily distinct elements of S, where order is not taken into account: two sequences define the same multiset if one can be obtained from the other by permuting the terms. In other words, it is a sample of k elements from a set of n elements allowing for duplicates (i.e., with replacement) but disregarding different orderings (e.g. {2,1,2} = {1,2,2}). Associate an index to each element of S and think of the elements of S as types of objects, then we can let $x_{i}$ denote the number of elements of type i in a multisubset. The number of multisubsets of size k is then the number of nonnegative integer (so allowing zero) solutions of the Diophantine equation:^[11]

$x_{1}+x_{2}+\ldots +x_{n}=k.$

If S has n elements, the number of such k-multisubsets is denoted by

$\left(\!\!{\binom {n}{k}}\!\!\right),$

a notation that is analogous to the binomial coefficient which counts k-subsets. This expression, n multichoose k,^[12] can also be given in terms of binomial coefficients:

$\left(\!\!{\binom {n}{k}}\!\!\right)={\binom {n+k-1}{k}}.$

This relationship can be easily proved using a representation known as stars and bars.^[13]

Proof

A solution of the above Diophantine equation can be represented by $x_{1}$ stars, a separator (a bar), then $x_{2}$ más estrellas, otro separador, y así sucesivamente. El número total de estrellas en esta representación es k y el número de barras es n - 1 (ya que una separación en n partes necesita n - 1 separadores). Por lo tanto, una cadena de k + n - 1 (o n + k - 1) símbolos (estrellas y barras) corresponde a una solución si hay k estrellas en la cadena. Cualquier solución se puede representar eligiendo k de k + n − 1 posiciones para colocar estrellas y llenando las posiciones restantes con barras. Por ejemplo, la solución $x_{1}=3,x_{2}=2,x_{3}=0,x_{4}=5$ de la ecuación $x_{1}+x_{2}+x_{3}+x_{4}=10$ ( n = 4 y k = 10) se puede representar mediante ^{[ 14 ]}

$\bigstar \bigstar \bigstar |\bigstar \bigstar ||\bigstar \bigstar \bigstar \bigstar \bigstar .$

El número de tales cadenas es el número de maneras de colocar 10 estrellas en 13 posiciones, ${\textstyle {\binom {13}{10}}={\binom {13}{3}}=286,}$ que es el número de multisubconjuntos de 10 elementos de un conjunto con 4 elementos.

Biyección entre 3-subconjuntos de un 7-conjunto (izquierda) y 3-multiconjuntos con elementos de un 5-conjunto (derecha). Esto ilustra que ${\textstyle {\binom {7}{3}}=\left(\!\!{\binom {5}{3}}\!\!\right)}$ .

Al igual que con los coeficientes binomiales, existen varias relaciones entre estas expresiones de selección múltiple. Por ejemplo, para $n\geq 1,k\geq 0$ ,

$\left(\!\!{\binom {n}{k}}\!\!\right)=\left(\!\!{\binom {k+1}{n-1}}\!\!\right).$ Esta identidad se deduce del intercambio de las estrellas y las barras en la representación anterior. ^{[ 15 ]}

Ejemplo de conteo de subconjuntos múltiples

Por ejemplo, si tienes cuatro tipos de donas ( n = 4) en un menú para elegir y quieres tres donas ( k = 3), el número de maneras de elegir las donas con repetición se puede calcular como

$\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.$

Este resultado se puede verificar enumerando todos los multisubconjuntos de 3 elementos del conjunto S = {1,2,3,4}. Esto se muestra en la siguiente tabla. ^{[ 16 ]} La segunda columna enumera los donuts que usted eligió, la tercera columna muestra las soluciones enteras no negativas. $[x_{1},x_{2},x_{3},x_{4}]$ de la ecuación $x_{1}+x_{2}+x_{3}+x_{4}=3$ y la última columna muestra la representación de las soluciones mediante estrellas y barras. ^{[ 17 ]}

Número de combinaciones de k para todos los k

El número de k -combinaciones para todo k es el número de subconjuntos de un conjunto de n elementos. Hay varias maneras de ver que este número es 2 ⁿ . En términos de combinaciones, ${\textstyle \sum _{0\leq {k}\leq {n}}{\binom {n}{k}}=2^{n}}$ , que es la suma de la n -ésima fila (contando desde 0) de los coeficientes binomiales en el triángulo de Pascal . Estas combinaciones (subconjuntos) se enumeran mediante los 1 dígitos del conjunto de números en base 2 que cuentan desde 0 hasta 2 ⁿ − 1, donde cada posición de dígito es un elemento del conjunto de n .

Dadas 3 cartas numeradas del 1 al 3, existen 8 combinaciones distintas ( subconjuntos ), incluyendo el conjunto vacío :

$|\{\{\};\{1\};\{2\};\{1,2\};\{3\};\{1,3\};\{2,3\};\{1,2,3\}\}|=2^{3}=8$

Representando estos subconjuntos (en el mismo orden) como números de base 2:

0 – 000
1 – 001
2 – 010
3 – 011
4 – 100
5 – 101
6 – 110
7 – 111

Probabilidad: muestreo de una combinación aleatoria

Existen varios algoritmos para seleccionar una combinación aleatoria de un conjunto o lista dados. El muestreo por rechazo es extremadamente lento para tamaños de muestra grandes. Una forma de seleccionar una k -combinación de manera eficiente de una población de tamaño n es iterar sobre cada elemento de la población y, en cada paso, elegir ese elemento con una probabilidad que cambia dinámicamente. ${\textstyle {\frac {k-\#{\text{samples chosen}}}{n-\#{\text{samples visited}}}}}$ (véase Muestreo de embalse ). Otra opción es elegir un número entero no negativo aleatorio menor que $\textstyle {\binom {n}{k}}$ y convertirlo en una combinación utilizando el sistema numérico combinatorio .

Número de maneras de colocar objetos en contenedores

Una combinación también puede considerarse como una selección de dos conjuntos de elementos: aquellos que van al contenedor elegido y aquellos que van al contenedor no elegido. Esto puede generalizarse a cualquier número de contenedores con la restricción de que cada elemento debe ir a exactamente un contenedor. El número de maneras de colocar objetos en contenedores viene dado por el coeficiente multinomial.

${\binom {n}{k_{1},k_{2},\ldots ,k_{m}}}={\frac {n!}{k_{1}!\,k_{2}!\cdots k_{m}!}},$

donde n es el número de elementos, m es el número de contenedores y $k_{i}$ es el número de artículos que van en el contenedor i .

Una forma de ver por qué se cumple esta ecuación es numerar primero los objetos arbitrariamente del 1 al n y colocar los objetos con números $1,2,\ldots ,k_{1}$ en el primer contenedor en orden, los objetos con números $k_{1}+1,k_{1}+2,\ldots ,k_{1}+k_{2}$ en el segundo contenedor en orden, y así sucesivamente. Hay $n!$ numeraciones distintas, pero muchas de ellas son equivalentes, porque solo importa el conjunto de elementos en un contenedor, no su orden en él. Cada permutación combinada del contenido de cada contenedor produce una forma equivalente de colocar elementos en los contenedores. Como resultado, cada clase de equivalencia consta de $k_{1}!\,k_{2}!\cdots k_{m}!$ numeraciones distintas, y el número de clases de equivalencia es $\textstyle {\frac {n!}{k_{1}!\,k_{2}!\cdots k_{m}!}}$ .

El coeficiente binomial es el caso especial en el que k elementos entran en el intervalo elegido y los restantes $n-k$ Los artículos van al contenedor de artículos no seleccionados:

${\binom {n}{k}}={\binom {n}{k,n-k}}={\frac {n!}{k!(n-k)!}}.$

Véase también

Notes

↑Reichl, Linda E. (2016). "2.2. Counting Microscopic States". A Modern Course in Statistical Physics. WILEY-VCH. p. 30. ISBN 978-3-527-69048-0.
↑Mazur 2010, p. 10
↑Ryser 1963, p. 7 also referred to as an unordered selection.
↑When the term combination is used to refer to either situation (as in (Brualdi 2010)) care must be taken to clarify whether sets or multisets are being discussed.
↑Uspensky 1937, p. 18
↑High School Textbook for full-time student (Required) Mathematics Book II B (in Chinese) (2nd ed.). China: People's Education Press. June 2006. pp. 107–116. ISBN 978-7-107-19616-4.
↑人教版高中数学选修2-3[Mathematics textbook, volume 2-3, for senior high school, People's Education Press]. People's Education Press. p. 21. Archived from the original on 7 April 2023.
↑Mazur 2010, p. 21
↑Lucia Moura. "Generating Elementary Combinatorial Objects"(PDF). Site.uottawa.ca. Archived(PDF) from the original on 9 October 2022. Retrieved 10 April 2017.
↑"Subsets - Combinatorics". Sagemath.org. Retrieved 10 April 2017.
↑Brualdi 2010, p. 52
↑Benjamin & Quinn 2003, p. 70
↑In the article Stars and bars (combinatorics) the roles of $n$ and $k$ are reversed.
↑Benjamin & Quinn 2003, pp. 71 –72
↑Benjamin & Quinn 2003, p. 72 (identity 145)
↑Benjamin & Quinn 2003, p. 71
↑Mazur 2010, p. 10 where the stars and bars are written as binary numbers, with stars = 0 and bars = 1.

References

Benjamin, Arthur T.; Quinn, Jennifer J. (2003), Proofs that Really Count: The Art of Combinatorial Proof, The Dolciani Mathematical Expositions 27, The Mathematical Association of America, ISBN 978-0-88385-333-7
Brualdi, Richard A. (2010), Combinatoria introductoria (5.ª ed.), Pearson Prentice Hall, ISBN 978-0-13-602040-0
Erwin Kreyszig , Matemáticas avanzadas para ingeniería , John Wiley & Sons, INC, 1999.
Mazur, David R. (2010), Combinatoria: Una visita guiada , Asociación Matemática de América, ISBN 978-0-88385-762-5
Ryser, Herbert John (1963), Matemáticas combinatorias , The Carus Mathematical Monographs 14, Mathematical Association of America
Uspensky, James (1937), Introducción a la probabilidad matemática , McGraw-Hill

Enlaces externos

Muchos tipos comunes de problemas matemáticos de permutación y combinación, con soluciones detalladas.
La fórmula desconocida para combinaciones donde las opciones se pueden repetir y el orden no importa.
El problema de lanzar dados con una suma dada. Una aplicación de las combinaciones con repetición al lanzamiento de múltiples dados.

[1] Reichl, Linda E. (2016). "2.2. Counting Microscopic States". A Modern Course in Statistical Physics. WILEY-VCH. p. 30. ISBN 978-3-527-69048-0.

[2] Mazur 2010, p. 10

[3] Ryser 1963, p. 7 also referred to as an unordered selection.

[4] When the term combination is used to refer to either situation (as in (Brualdi 2010)) care must be taken to clarify whether sets or multisets are being discussed.

[5] Uspensky 1937, p. 18

[6] High School Textbook for full-time student (Required) Mathematics Book II B (in Chinese) (2nd ed.). China: People's Education Press. June 2006. pp. 107–116. ISBN 978-7-107-19616-4.

[7] 人教版高中数学选修2-3[Mathematics textbook, volume 2-3, for senior high school, People's Education Press]. People's Education Press. p. 21. Archived from the original on 7 April 2023.

[8] Mazur 2010, p. 21

[9] Lucia Moura. "Generating Elementary Combinatorial Objects"(PDF). Site.uottawa.ca. Archived(PDF) from the original on 9 October 2022. Retrieved 10 April 2017.

[10] "Subsets - Combinatorics". Sagemath.org. Retrieved 10 April 2017.

[11] Brualdi 2010, p. 52

[12] Benjamin & Quinn 2003, p. 70

[13] In the article Stars and bars (combinatorics) the roles of $n$ and $k$ are reversed.

[14] Benjamin & Quinn 2003, pp. 71 –72

[15] Benjamin & Quinn 2003, p. 72 (identity 145)

[16] Benjamin & Quinn 2003, p. 71

[17] Mazur 2010, p. 10 where the stars and bars are written as binary numbers, with stars = 0 and bars = 1.

[ 1 ]

[ 2 ]

[ 3 ] .

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[11]

[12]

[13]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]