Combinación

Selección de elementos de un conjunto

En matemáticas , 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 permutaciones ). Por ejemplo, dadas 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. (La disposición de los miembros en cada conjunto no importa). Si el conjunto tiene n elementos, el número de k -combinaciones, denotado por o , es igual al coeficiente binomial. ${\displaystyle C(n,k)}$ ${\displaystyle C_{k}^{n}}$

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

que se puede escribir usando factoriales como siempre que , y que es cero cuando . Esta fórmula se puede derivar del hecho de que cada k -combinación de un conjunto S de n miembros tiene permutaciones así o bien . ^[1] El conjunto de todas las k -combinaciones de un conjunto S se denota a menudo por . ${\displaystyle \textstyle {\frac {n!}{k!(n-k)!}}}$ ${\displaystyle k\leq n}$ ${\displaystyle k>n}$ ${\displaystyle k!}$ ${\displaystyle P_{k}^{n}=C_{k}^{n}\times k!}$ ${\displaystyle C_{k}^{n}=P_{k}^{n}/k!}$ ${\displaystyle \textstyle {\binom {S}{k}}}$

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 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 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) 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 obtener una mano cualquiera al azar es de 1/2.598.960.

Número dea-combinaciones

Subconjuntos de 3 elementos de un conjunto de 5 elementos

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

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

de lo cual se desprende claramente que

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

y más allá

$${\displaystyle {\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 :

$${\displaystyle \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, al establecer todas las X _s iguales a la variable no etiquetada 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 recursión

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

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

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

$${\displaystyle {\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 dichas 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

$${\displaystyle {\binom {n}{k}}={\binom {n}{n-k}},}$$

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, hay una fórmula que muestra esta simetría directamente y tiene el mérito de ser fácil de recordar:

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

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 las n ! permutaciones de todos los elementos de S . Cada una de estas permutaciones da una k -combinación seleccionando sus primeros k elementos. Hay muchas selecciones duplicadas: cualquier permutación combinada de los primeros k elementos entre sí, y de los ( n  −  k ) elementos finales entre sí produce la misma combinación; esto explica la división en la 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:

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

Junto con los casos básicos , 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 . ${\displaystyle {\tbinom {n}{0}}=1={\tbinom {n}{n}}}$

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]

$${\displaystyle {52 \choose 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 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 {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 escribir

$${\displaystyle {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}},}$$

Lo cual da

$${\displaystyle {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.}$$

Si se evalúa en el orden siguiente, 52 ÷ 1 × 51 ÷ 2 × 50 ÷ 3 × 49 ÷ 4 × 48 ÷ 5 , esto se puede calcular utilizando únicamente aritmética de números enteros. La razón es que cuando se produce cada división, el resultado intermedio que se produce es en sí mismo un coeficiente binomial, por lo que nunca se producen residuos.

Utilizando la fórmula simétrica en términos de factoriales sin realizar simplificaciones se obtiene 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}{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}}}$$

Enumerandoa-combinaciones

Se pueden enumerar todas las k -combinaciones de un conjunto dado S de n elementos en un orden fijo, lo que establece una biyección a partir de un intervalo de números enteros con el conjunto de esas k -combinaciones. Suponiendo que S está 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 añadir un nuevo elemento más grande a S no cambiará 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 se puede extender indefinidamente con k -combinaciones de conjuntos cada vez más grandes. Si además se toma que los intervalos de los números enteros comienzan en 0, entonces la k -combinación en un lugar dado i en la enumeración se puede calcular fácilmente a partir de i , y la biyección así obtenida se conoce como el sistema de numeración combinatoria . También se conoce como "rango"/"ranking" y "unranking" en matemáticas computacionales. ^{[9] [10]} ${\displaystyle {\tbinom {n}{k}}}$

Existen muchas formas de enumerar k combinaciones. Una forma es hacer un seguimiento de los k números de índice 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, al mismo tiempo que se restablecen todos los números de índice más pequeños a sus valores iniciales.

Número de combinaciones con repetición

Una k - combinación con repeticiones , o k - multicombinación , o multisubconjunto de tamaño k de un conjunto S de tamaño n, está dada por un conjunto de k elementos no necesariamente distintos de S , donde el orden no se toma en cuenta: dos secuencias definen el mismo multiconjunto si una puede obtenerse de la otra permutando los términos. En otras palabras, es una muestra de k elementos de un conjunto de n elementos permitiendo duplicados (es decir, con reemplazo) pero sin tener en cuenta diferentes ordenaciones (por ejemplo, {2,1,2} = {1,2,2}). Asociemos un índice a cada elemento de S y pensemos en los elementos de S como tipos de objetos, entonces podemos dejar que denote el número de elementos de tipo i en un multisubconjunto. El número de multisubconjuntos de tamaño k es entonces el número de soluciones enteras no negativas (lo que permite cero) de la ecuación diofántica : ^[11] ${\displaystyle x_{i}}$

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

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

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

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

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

Esta relación se puede demostrar fácilmente utilizando una representación conocida como estrellas y barras . ^[13]

Prueba

Una solución de la ecuación diofántica anterior se puede representar con estrellas , un separador (una barra ), luego 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 rellenando las posiciones restantes con barras. Por ejemplo, la solución de la ecuación ( n = 4 y k = 10) se puede representar mediante ^[14] ${\displaystyle x_{1}}$ ${\displaystyle x_{2}}$ ${\displaystyle x_{1}=3,x_{2}=2,x_{3}=0,x_{4}=5}$ ${\displaystyle x_{1}+x_{2}+x_{3}+x_{4}=10}$

$${\displaystyle \bigstar \bigstar \bigstar |\bigstar \bigstar ||\bigstar \bigstar \bigstar \bigstar \bigstar .}$$

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

Biyección entre 3-subconjuntos de un conjunto de 7 (izquierda) y 3-multiconjuntos con elementos de un conjunto de 5 (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 , ${\displaystyle n\geq 1,k\geq 0}$

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

Ejemplo de conteo de multisubconjuntos

Por ejemplo, si tiene cuatro tipos de donas ( n  = 4) en un menú para elegir y desea tres donas ( k  = 3), la cantidad de formas de elegir las donas con repetición se puede calcular como

$${\displaystyle \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 subconjuntos de 3 elementos del conjunto S = {1,2,3,4}. Esto se muestra en la siguiente tabla. ^[16] La segunda columna enumera los anillos que realmente eligió, la tercera columna muestra las soluciones enteras no negativas de la ecuación y la última columna proporciona la representación de las soluciones con estrellas y barras. ^[17] ${\displaystyle [x_{1},x_{2},x_{3},x_{4}]}$ ${\displaystyle x_{1}+x_{2}+x_{3}+x_{4}=3}$

Número dea-combinaciones para todosa

El número de k -combinaciones para todos los k es el número de subconjuntos de un conjunto de n elementos. Hay varias formas de ver que este número es 2 ⁿ . En términos de combinaciones, , 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 por los 1 dígitos del conjunto de números de base 2 contando desde 0 hasta 2 ⁿ  − 1, donde cada posición de dígito es un elemento del conjunto de n . ${\textstyle \sum _{0\leq {k}\leq {n}}{\binom {n}{k}}=2^{n}}$

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

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

Representando estos subconjuntos (en el mismo orden) como numerales 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 determinados. El muestreo por rechazo es extremadamente lento para muestras de gran tamaño. 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, seleccionar ese elemento con una probabilidad que cambia dinámicamente (consulte Muestreo de yacimientos ). Otra forma es seleccionar un entero aleatorio no negativo menor que y convertirlo en una combinación utilizando el sistema de números combinatorios . ${\textstyle {\frac {k-\#{\text{samples chosen}}}{n-\#{\text{samples visited}}}}}$ ${\displaystyle \textstyle {\binom {n}{k}}}$

Número de formas de colocar objetos en los contenedores

Una combinación también puede considerarse como una selección de dos conjuntos de elementos: los que van en el contenedor elegido y los que van en el contenedor no elegido. Esto se puede generalizar a cualquier número de contenedores con la restricción de que cada elemento debe ir exactamente en un contenedor. La cantidad de formas de colocar objetos en los contenedores está dada por el coeficiente multinomial.

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

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

Una forma de ver por qué se cumple esta ecuación es numerar primero los objetos arbitrariamente de 1 a n y poner los objetos con números en el primer contenedor en orden, los objetos con números en el segundo contenedor en orden, y así sucesivamente. Hay 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 de los contenidos de cada contenedor produce una forma equivalente de colocar los elementos en los contenedores. Como resultado, cada clase de equivalencia consta de numeraciones distintas, y el número de clases de equivalencia es . ${\displaystyle 1,2,\ldots ,k_{1}}$ ${\displaystyle k_{1}+1,k_{1}+2,\ldots ,k_{2}}$ ${\displaystyle n!}$ ${\displaystyle k_{1}!\,k_{2}!\cdots k_{m}!}$ ${\displaystyle \textstyle {\frac {n!}{k_{1}!\,k_{2}!\cdots k_{m}!}}}$

El coeficiente binomial es el caso especial en el que k elementos van al contenedor elegido y los elementos restantes van al contenedor no elegido: ${\displaystyle n-k}$

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

Véase también

• Portal de matemáticas

• Coeficiente binomial
• Combinatoria
• Diseño de bloques
• Gráfica de Kneser
• Lista de temas de permutación
• Conjunto múltiple
• Probabilidad

Notas

1. Reichl, Linda E. (2016). "2.2. Conteo de estados microscópicos". Un curso moderno de física estadística . WILEY-VCH. pág. 30. ISBN 978-3-527-69048-0.
2. Mazur 2010, pág. 10
3. Ryser 1963, p. 7 también conocida como selección desordenada .
4. Cuando se utiliza el término combinación para referirse a cualquiera de las dos situaciones (como en (Brualdi 2010)), se debe tener cuidado de aclarar si se está hablando de conjuntos o multiconjuntos.
5. Uspensky 1937, pág. 18
6. Libro de texto de secundaria para estudiantes de tiempo completo (obligatorio) Libro de matemáticas II B (en chino) (2.ª ed.). China: People's Education Press. Junio ​​de 2006. págs. 107-116. ISBN 978-7-107-19616-4.
7. 人教版高中数学选修2-3 (Libro de texto de matemáticas, volumen 2-3, para la escuela secundaria superior, People's Education Press). Prensa de Educación Popular. pag. 21.
8. Mazur 2010, pág. 21
9. Lucia Moura. "Generación de objetos combinatorios elementales" (PDF) . Site.uottawa.ca . Archivado (PDF) del original el 9 de octubre de 2022 . Consultado el 10 de abril de 2017 .
10. "SAGE: Subconjuntos" (PDF) . Sagemath.org . Consultado el 10 de abril de 2017 .
11. Brualdi 2010, pág. 52
12. Benjamin y Quinn 2003, pág. 70
13. En el artículo Estrellas y barras (combinatoria) se invierten los roles de n y k .
14. Benjamin y Quinn 2003, págs. 71-72
15. Benjamin y Quinn 2003, pág. 72 (identidad 145)
16. Benjamin y Quinn 2003, pág. 71
17. Mazur 2010, p. 10 donde las estrellas y las barras se escriben como números binarios, con estrellas = 0 y barras = 1.

Referencias

• Benjamin, Arthur T. ; Quinn, Jennifer J. (2003), Pruebas que realmente cuentan: el arte de la prueba combinatoria , 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 de 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, Asociación Matemática de América
• Uspensky, James (1937), Introducción a la probabilidad matemática, McGraw-Hill

Enlaces externos

• Tutorial de Topcoder sobre combinatoria
• Muchos tipos comunes de problemas matemáticos de permutación y combinación, con soluciones detalladas
• La fórmula desconocida para combinaciones en las que las opciones se pueden repetir y el orden no importa
• Problema de lanzamiento de dados con una suma dada Una aplicación de las combinaciones con repetición al lanzamiento de múltiples dados