Combinación
En matemáticas, a combinación es una selección de elementos de un conjunto que tiene miembros distintos, de manera que el orden de selección no importa (a diferencia de las permutaciones). Por ejemplo, dadas tres frutas, dicen una manzana, una naranja y un pera, hay tres combinaciones de dos que se pueden extraer de este conjunto: una manzana y un pera; una manzana y una naranja; o un pera y una naranja. Más formalmente, un k-combinación de un conjunto S es un subconjunto de k distintos elementos S. Por lo tanto, dos combinaciones son idénticas si y sólo si cada combinación tiene los mismos miembros. (El arreglo de los miembros en cada conjunto no importa.) Si el conjunto tiene n elementos, el número de k-combinaciones, denotadas como Ckn{displaystyle C_{k} {n}, es igual al coeficiente binomio
que se puede escribir utilizando factores como n!k!()n− − k)!{displaystyle textstyle {frac {}{k!(n-k)}}}} siempre k≤ ≤ n{displaystyle kleq n}, y que es cero cuando n}" xmlns="http://www.w3.org/1998/Math/MathML">k■n{displaystyle k]n}n" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/66e81682bf174c978e9008ffb557ba4da2cf7478" style="vertical-align: -0.338ex; width:5.704ex; height:2.176ex;"/>. Esta fórmula puede derivarse del hecho de que cada k-combinación de un conjunto S de n miembros k!{displaystyle k!} permutaciones así Pkn=Ckn× × k!{displaystyle P_{k} {n}=C_{n}times k! o Ckn=Pkn/k!{displaystyle ¡No!. El conjunto de todos k-combinaciones de un conjunto S a menudo se denota ()Sk){displaystyle textstyle {binom {} {}}}.
Una combinación es una combinación de n cosas tomadas k a la vez sin repetición. Para referirse a las combinaciones en las que se permite la repetición, a menudo se utilizan los términos k-selection, k-multiset, o k-combination with repeat. Si, en el ejemplo anterior, fuera posible tener dos de cualquier tipo de fruta, habría 3 2 selecciones 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 poco práctico a medida que aumenta el tamaño del conjunto. Por ejemplo, una mano de póquer se puede describir como una combinación de 5 (k = 5) de cartas 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 sacar una mano al azar es 1 / 2 598 960.
Número de k-combinaciones
El número de k-combinaciones de un conjunto dado S de n a menudo se denotan elementos en los textos combinatorios elementales C()n,k){displaystyle C(n,k)}, o por una variación como Ckn{displaystyle C_{k} {n}, nCk{displaystyle {}_{n}C_{k}, nCk{displaystyle {fn}C_{k}, Cn,k{displaystyle C_{n,k} o incluso Cnk{displaystyle C_{n} {k} (la última forma es estándar en textos francés, rumano, ruso, chino y polaco). El mismo número, sin embargo, ocurre en muchos otros contextos matemáticos, donde es denotado por ()nk){fnMicrosoft}} (a menudo leído como "n elegir k"); en particular, se presenta como un coeficiente en la fórmula binomial, por lo tanto su nombre coeficiente binomial. Uno puede definir ()nk){fnMicrosoft}} para todos los números naturales k a la vez por la relación
de donde se desprende que
y más allá,
para k > n.
Para ver que estos coeficientes cuentan combinaciones k de S, primero se puede considerar una colección de n variables distintas X s etiquetados por los elementos s de S, y expanda el producto sobre todos los elementos de S:
tiene 2n términos distintos correspondientes a todos los subconjuntos de S, cada subconjunto da el producto de las correspondientes variables Xs. Ahora configurando todas las Xs iguales a la variable no etiquetada X, para que el producto se convierta en (1 + X)n, el término para cada k- combinación de S se convierte en Xk, 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 formas. Para obtenerlos todos para las expansiones hasta (1 + X)n, uno puede usar (además de los casos básicos ya dados) la relación de recurrencia
para 0 < k < n, que sigue de (1 + X)n = (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 usar la fórmula
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 permutaciones k que dan la misma combinación k cuando se ignora el orden.
Cuando k excede a n/2, la fórmula anterior contiene factores comunes al numerador y al denominador, y al cancelarlos se obtiene la relación
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 combinaciones k al tomar el complemento de dicha combinación, que es un (n − k)-combinación.
Finalmente, hay una fórmula que exhibe esta simetría directamente y tiene el mérito de ser fácil de recordar:
donde n! denota el factorial de n. Se obtiene de la fórmula anterior multiplicando denominador y numerador por (n − k)!, por lo que ciertamente es computacionalmente menos eficiente que esa fórmula.
¡La última fórmula se puede entender directamente, considerando la n! permutaciones de todos los elementos de S. Cada una de estas permutaciones da una combinación k al seleccionar sus primeros elementos k. Hay muchas selecciones duplicadas: cualquier permutación combinada de los primeros elementos k entre sí, y de los elementos finales (n − k) entre entre sí produce la misma combinación; esto explica la división en la fórmula.
De las fórmulas anteriores, sigue las relaciones entre números adyacentes en el triángulo de Pascal en las tres direcciones:
Junto con los casos básicos ()n0)=1=()nn){fnMicrosoft {fn}=1={tbinom} {n} {n}}, estos permiten la computación sucesiva 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 de crecimiento, y de combinaciones con un complemento de tamaño fijo n − k.
Ejemplo de combinaciones de conteo
Como ejemplo específico, uno puede calcular el número de manos de cinco cartas posibles de una baraja estándar de cincuenta y dos cartas como:
Alternativamente, se puede usar la fórmula en términos de factoriales y cancelar los factores en el numerador contra partes de los factores en el denominador, después de lo cual solo se requiere la multiplicación de los factores restantes:
![{displaystyle {begin{alignedat}{2}{52 choose 5}&={frac {52!}{5!47!}}\[5pt]&={frac {52times 51times 50times 49times 48times {cancel {47!}}}{5times 4times 3times 2times {cancel {1}}times {cancel {47!}}}}\[5pt]&={frac {52times 51times 50times 49times 48}{5times 4times 3times 2}}\[5pt]&={frac {(26times {cancel {2}})times (17times {cancel {3}})times (10times {cancel {5}})times 49times (12times {cancel {4}})}{{cancel {5}}times {cancel {4}}times {cancel {3}}times {cancel {2}}}}\[5pt]&={26times 17times 10times 49times 12}\[5pt]&=2{,}598{,}960.end{alignedat}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5541f14cc4ca51756ec76a67071c816f69070dfa)
Otro cálculo alternativo, equivalente al primero, se basa en escribir
que da
Cuando se evalúa en el siguiente orden, 52 ÷ 1 × 51 ÷ 2 × 50 ÷ 3 × 49 ÷ 4 × 48 ÷ 5, esto se puede calcular usando solo aritmética de enteros. La razón es que cuando ocurre cada división, el resultado intermedio que se produce es en sí mismo un coeficiente binomial, por lo que nunca se producen residuos.
Usar la fórmula simétrica en términos de factoriales sin realizar simplificaciones da un cálculo bastante extenso:
![{displaystyle {begin{aligned}{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}{120times 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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/71b6bc44a40b770f570cabbf47c9476b54bb1d56)
Enumerar k-combinaciones
Uno puede enumerar todos k-combinaciones de un conjunto dado S de n elementos en algún orden fijo, que establece una bijeción desde un intervalo de ()nk){fnMicrosoft}} enteros con el conjunto de esos k-combinaciones. Sumas S es en sí mismo 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. Esta última opción tiene la ventaja de añadir un nuevo elemento más grande a S no cambiará la parte inicial de la enumeración, pero sólo añadir la nueva k-combinaciones del set más grande después de las anteriores. Repita este proceso, la enumeración puede extenderse indefinidamente con k-combinaciones de conjuntos cada vez más grandes. Si además los intervalos de los enteros se toman para empezar a 0, entonces los k-combinación en un lugar dado i en la enumeración se puede calcular fácilmente de i, y la bijeción así obtenida se conoce como el sistema de número combinatorio. También se conoce como "rank"/"ranking" y "unranking" en matemáticas computacionales.
Hay muchas formas de enumerar combinaciones k. Una forma es visitar todos los números binarios menores que 2n. Elija aquellos números que tengan k bits distintos de cero, aunque esto es muy ineficiente incluso para pequeños n (por ejemplo, n = 20 requeriría visitar alrededor de un millón de números mientras que el número máximo de combinaciones k permitidas es de unas 186 mil para k = 10). Las posiciones de estos 1 bits en dicho número es una combinación k específica del conjunto { 1,..., n }. Otra forma simple y más rápida 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 combinación permitida de k y luego pasar repetidamente a la siguiente combinación permitida de k incrementando la última número de índice si es menor que n-1 (basado en cero) o n (basado en uno) o el último número de índice x que es menor que el número de índice que le sigue menos uno si existe tal índice y restablecer los números de índice después de x a {x+1, x +2,...}.
Número de combinaciones con repetición
A k-combinación con repeticiones, o k-multicombinación, o multisubset de tamaño k de un conjunto S de tamaño n es dado por un conjunto de k no necesariamente elementos distintos S, donde el orden no se tiene en cuenta: dos secuencias definen el mismo multiset si se puede obtener del otro permutando los términos. En otras palabras, es una muestra de k elementos de un conjunto de n elementos que permiten duplicados (es decir, con reemplazo) pero que ignoran diferentes pedidos (por ejemplo, {2,1,2} = {1,2,2}). Asocia un índice a cada elemento S y pensar en los elementos de S como tipos de objetos, entonces podemos dejar xi{displaystyle x_{i}} denota el número de elementos de tipo i en un multisubset. El número de subconjuntos de tamaño k es entonces el número de entero no negativo (que permite cero) soluciones de la ecuación Diofantina:
Si S tiene n elementos, el número de dichos k-multisubconjuntos se denota por
una notación que es análoga al coeficiente binomial que cuenta k-subconjuntos. Esta expresión, n multichoose k, también se puede dar en términos de coeficientes binomiales:
Esta relación se puede demostrar fácilmente usando una representación conocida como estrellas y barras.
Una solución de la ecuación de Diofantina anterior puede ser representada por x1{displaystyle x_{1}} estrellas, un separador (a bar), entonces x2{displaystyle x_{2} más estrellas, otro separador, etc. El número total de estrellas en esta representación es k y el número de barras es n - 1 (desde que una separación en partes n necesita separadores n-1). Así, una cuerda de k + n - 1 (o n + k - 1) símbolos (estrellas y barras) corresponde a una solución si hay k estrellas en la cuerda. Cualquier solución puede ser representada por la elección k fuera de k + n − 1 posiciones para colocar estrellas y llenar las posiciones restantes con barras. Por ejemplo, la solución x1=3,x2=2,x3=0,x4=5{displaystyle x_{1}=3,x_{2}=2,x_{3}=0,x_{4}=5} de la ecuación x1+x2+x3+x4=10{displaystyle x_{1}+x_{2}+x_{3}+x_{4}=10} ()n = 4 y k = 10) puede ser representado por
El número de tales cadenas es el número de maneras de colocar 10 estrellas en 13 posiciones, ()1310)=()133)=286,{fnMicrosoft} {13}{10}={binom {13}{3}=286,} que es el número de 10-multisubsets de un conjunto con 4 elementos.
Esto ilustra que ()73)=()()53)){fnMicrosoft} {7} {}=left(!! {binom {5}!!derecha)}.
Al igual que con coeficientes binomiales, hay varias relaciones entre estas expresiones multichoose. Por ejemplo, n≥ ≥ 1,k≥ ≥ 0{displaystyle ngeq 1,kgeq 0},
Ejemplo de conteo de subconjuntos múltiples
Por ejemplo, si tiene cuatro tipos de donas (n = 4) en un menú para elegir y quiere tres donas (k = 3), el El número de formas de elegir las donas con repetición se puede calcular como
Este resultado puede ser verificado por enumerar todos los 3-multisubsets del conjunto S = {1,2,3,4}. Esto se muestra en la siguiente tabla. La segunda columna enumera los donuts que elegiste, la tercera columna muestra las soluciones de entero no negativo [x1,x2,x3,x4]{displaystyle [x_{1},x_{2},x_{3},x_{4}} de la ecuación x1+x2+x3+x4=3{displaystyle x_{1}+x_{2}+x_{3}+x_{4}=3} y la última columna da a las estrellas y barras representación de las soluciones.
![[x_{1},x_{2},x_{3},x_{4}]](https://wikimedia.org/api/rest_v1/media/math/render/svg/cbec11b6cf47c5e117f30ff33ecc05c54e84e9ec)
| No. | 3-multiset | Solución Eq. | Estrellas y bares |
|---|---|---|---|
| 1 | {1,1,1} | [3,0,0,0] | ★ ★ ★ ★ ★ ★ SilencioSilencioSilencio{displaystyle bigstar bigstar bigstar Silencioso |
| 2 | {1,1,2} | [2,1,0,0] | ★ ★ ★ ★ Silencio★ ★ SilencioSilencio{displaystyle bigstar bigstar Silenciobigstar |
| 3 | {1,1,3} | [2,0,1,0] | ★ ★ ★ ★ SilencioSilencio★ ★ Silencio{displaystyle bigstar bigstar ¦ |
| 4 | {1,1,4} | [2,0,0,1] | ★ ★ ★ ★ SilencioSilencioSilencio★ ★ {displaystyle bigstar bigstar ¦ |
| 5 | {1,2,2} | [1,2,0,0] | ★ ★ Silencio★ ★ ★ ★ SilencioSilencio{displaystyle bigstar Silenciobigstar bigstar Silencio. |
| 6 | {1,2,3} | [1,1,1,0] | ★ ★ Silencio★ ★ Silencio★ ★ Silencio{displaystyle bigstar ◾ |
| 7 | {1,2,4} | [1,1,0,1] | ★ ★ Silencio★ ★ SilencioSilencio★ ★ {displaystyle bigstar Silenciobigstar ¦ |
| 8 | {1,3,3} | [1,0,2,0] | ★ ★ SilencioSilencio★ ★ ★ ★ Silencio{displaystyle bigstar ← |
| 9 | {1,3,4} | [1,0,1,1] | ★ ★ SilencioSilencio★ ★ Silencio★ ★ {displaystyle bigstar Silenciosobigstar Silenciobigstar } |
| 10 | {1,4,4} | [1,0,0,2] | ★ ★ SilencioSilencioSilencio★ ★ ★ ★ {displaystyle bigstar ¦ |
| 11 | {2,2,2} | [0,3,0,0] | Silencio★ ★ ★ ★ ★ ★ SilencioSilencio{displaystyle Silenciobigstar bigstar bigstar presionante |
| 12 | {2,2,3} | [0,2,1,0] | Silencio★ ★ ★ ★ Silencio★ ★ Silencio{displaystyle Silenciobigstar bigstar ← |
| 13 | {2,2,4} | [0,2,0,1] | Silencio★ ★ ★ ★ SilencioSilencio★ ★ {displaystyle Silenciobigstar bigstar Silenciosobigstar } |
| 14 | {2,3,3} | [0,1,2,0] | Silencio★ ★ Silencio★ ★ ★ ★ Silencio{displaystyle Silenciobigstar Silenciosobigstar bigstar tención} |
| 15 | {2,3,4} | [0,1,1,1] | Silencio★ ★ Silencio★ ★ Silencio★ ★ {displaystyle Silenciobigstar. |
| 16 | {2,4,4} | [0,1,0,2] | Silencio★ ★ SilencioSilencio★ ★ ★ ★ {displaystyle Silenciobigstar Silenciosobigstar bigstar } |
| 17 | {3,3} | [0,0,3,0] | SilencioSilencio★ ★ ★ ★ ★ ★ Silencio{displaystyle Новоныйbigstar bigstar bigstar удель ный нель ный |
| 18 | {3,4} | [0,0,2,1] | SilencioSilencio★ ★ ★ ★ Silencio★ ★ {displaystyle TENEDIDO } |
| 19 | {3,4} | [0,0,1,2] | SilencioSilencio★ ★ Silencio★ ★ ★ ★ {displaystyle Нововоныйbigstar ¦ |
| 20 | {4,4} | [0,0,0,3] | SilencioSilencioSilencio★ ★ ★ ★ ★ ★ {displaystyle Нововывывывыеbigstar bigstar } |
Número de k-combinaciones para todas las k
El número de k-combinaciones para todos k es el número de subconjuntos de un conjunto de n elementos. Hay varias maneras de ver que este número es 2n. En términos de combinaciones, .. 0≤ ≤ k≤ ≤ n()nk)=2n{textstyle sum _{0leq {k}leq {n}{binom} {n}=2} {n}, que es la suma de la nth row (contando desde 0) de los coeficientes binomiales en el triángulo de Pascal. Estas combinaciones (subsets) se enumeran por los 1 dígitos del conjunto de números base 2 contando de 0 a 2n− 1, donde cada posición de dígitos es un elemento del conjunto de n.
Dadas 3 cartas numeradas del 1 al 3, hay 8 combinaciones distintas (subconjuntos), incluido el conjunto vacío:
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
Hay varios algoritmos para elegir una combinación aleatoria de un determinado conjunto o lista. El muestreo de inyección es extremadamente lento para grandes tamaños de muestra. Una manera de seleccionar un k-combinación eficiente de una población de tamaño n es iterar a través de cada elemento de la población, y en cada paso elegir ese elemento con una probabilidad de cambio dinámico k− − # # muestras seleccionadasn− − # # muestras visitadas{textstyle {frac {k-#{text{samples He elegido... (ver muestreo Reservoir). Otro es elegir un entero no negativo aleatorio menos que ()nk){displaystyle textstyle {binom {n}{k}} y convertirlo en una combinación usando el sistema de número combinatorio.
Número de formas de poner objetos en contenedores
Una combinación también se puede considerar como una selección de dos conjuntos de elementos: los que van al contenedor elegido y los que van al contenedor no elegido. 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 poner objetos en contenedores viene dado por el coeficiente multinomial
Donde n es el número de artículos, m es el número de contenedores, y ki{displaystyle K_{i} es el número de artículos que entran en bin i.
Una manera de ver por qué esta ecuación sostiene es numerar primero los objetos arbitrariamente de 1 a n y poner los objetos con números 1,2,...... ,k1{displaystyle 1,2,ldotsk_{1} en el primer bin en orden, los objetos con números k1+1,k1+2,...... ,k2{displaystyle k_{1}+1,k_{1}+2,ldotsk_{2}} en el segundo bin en orden, y así sucesivamente. Hay n!{displaystyle n!} numeraciones distintas, pero muchas de ellas son equivalentes, porque sólo el conjunto de elementos en un asunto de bin, no su orden en él. Cada permutación combinada de los contenidos de cada bins produce una manera equivalente de poner los elementos en contenedores. Como resultado, cada clase de equivalencia consiste en k1!k2!⋯ ⋯ km!{displaystyle k_{1}! k_{m}! numeración distinta, y el número de clases de equivalencia es n!k1!k2!⋯ ⋯ km!{displaystyle textstyle {frac ¡No! ¡Sí!.
El coeficiente binomial es el caso especial k ítems entran en el cubo elegido y el resto n− − k{displaystyle No. ítems entran en el contenedor no elegido:
