Combinación (matemáticas)
(no hay ningún subconjunto de más elementos que el total).
En total tenemos n(n-1)···(n-k+1) opciones para elegir los k elementos por orden.
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.
[4] (la última forma es estándar en los textos en francés, rumano, ruso y chino[5][6]).
Sin embargo, el mismo número aparece en muchos otros contextos matemáticos, donde se denota por
para todos los números naturales k a la vez por la relación (dada por la fórmula binomial)
Ahora, si denotamos todas las variables Xs como una variable no etiquetada X, de modo que el producto se convierte en (1 + X)n, la expresión
Los coeficientes binomiales se pueden calcular explícitamente de varias maneras.
Para determinar un coeficiente binomial individual, es más práctico utilizar la fórmula
Otro cálculo alternativo, equivalente al primero, se basa en escribir
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 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:
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 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 numérico combinatorio.
También se conoce como "rango"/"ranking" y "unranking" en matemáticas computacionales.
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.
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.
Si S tiene n elementos, el número de k- multisubconjuntos se denota por
una notación análoga al coeficiente binomial, que cuenta k-subconjuntos.
Esta relación se puede demostrar fácilmente utilizando una representación conocida como barras y estrellas:[11]
Demostración:Podemos representar una solución de la ecuación diofántica anterior como sigue.
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.
Igual que con los coeficientes binomiales, existen varias relaciones entre estas expresiones de elección múltiple.
Esta identidad se desprende del intercambio de las estrellas y las barras en la representación anterior.
Este resultado se puede verificar enumerando todos los 3-multisubconjuntos del conjunto S = {1,2,3,4}.
El coeficiente binomial es el caso especial en el que k elementos entran en el contenedor elegido y el resto (
En ese caso, la fórmula anterior recupera la del coeficiente binomial:
Esto ilustra que .
