El número de k-combinaciones de un conjunto dado S de n elementos se denota a menudo en los textos de combinatoria elemental por C ( n , k ) {\displaystyle C(n,k)}
, o por una variación como C k n {\displaystyle C_{k}^{n}}
, n C k {\displaystyle {}_{n}C_{k}}
, n C k {\displaystyle {}^{n}C_{k}}
, C n , k {\displaystyle C_{n,k}}
o incluso C n k {{displaystyle C_{n}^{k}}
(esta última forma era estándar en los textos franceses, rumanos, rusos, chinos y polacos). Sin embargo, el mismo número aparece en muchos otros contextos matemáticos, donde se denota por ( n k ) {\displaystyle {\tbinom {n}{k}}
(a menudo se lee como «n elige k»); en particular, aparece como un coeficiente en la fórmula binomial, de ahí su nombre coeficiente binomial. Se puede definir ( n k ) {\displaystyle {\tbinom {n}{k}}
para todos los números naturales k a la vez por la relación ( 1 + X ) n = ∑ k ≥ 0 ( n k ) X k , {\displaystyle (1+X)^{n}={suma _{k\geq 0}{binom {n}{k}X^{k},
de lo que se deduce que
( n 0 ) = ( n n ) = 1 ,
y, además, ( n k ) = 0 {{declaración}}={binom {n}{k}=0}
para k > n.
Para ver que estos coeficientes cuentan k-combinaciones de S, se puede considerar primero una colección de n variables distintas Xs etiquetadas por los elementos s de S, y expandir el producto sobre todos los elementos de S:
∏ s ∈ S ( 1 + X s ) ; {\displaystyle \prod _{s\in S}(1+X_{s});}
tiene 2n términos distintos correspondientes a todos los subconjuntos de S, dando cada subconjunto el producto de las variables correspondientes Xs. Ahora, estableciendo todas las Xs iguales a la variable no etiquetada X, de modo que el producto se convierte en (1 + X)n, el término para cada combinación k de S se convierte en Xk, de modo que el coeficiente de esa potencia en el resultado es igual al número de tales combinaciones k.
Los coeficientes de los binomios se pueden calcular explícitamente de varias maneras. Para obtener todos ellos para las expansiones hasta (1 + X)n, se puede utilizar (además de los casos básicos ya dados) la relación de recursión
( n k ) = ( n – 1 k – 1 ) + ( n – 1 k ) , {\displaystyle {\binom {n}{k}}={binom {n-1}{k-1}}+{binom {n-1}{k},}
para 0 < k < n, que se deduce de (1 + X)n = (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
( n k ) = n ( n – 1 ) ( n – 2 ) ⋯ ( n – k + 1 ) k ! {\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 tales k-permutaciones que dan la misma k-combinación cuando se ignora el orden.
Cuando k supera n/2, la fórmula anterior contiene factores comunes al numerador y al denominador, y al cancelarlos se obtiene la relación
( n k ) = ( n n – k ) , {\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 del binomio, y también puede entenderse en términos de combinaciones k tomando el complemento de tal combinación, que es una combinación (n – k).
Por último, hay una fórmula que exhibe esta simetría directamente, y tiene el mérito de ser fácil de recordar:
( n k ) = 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 es ciertamente menos eficiente computacionalmente que esa fórmula.
La última fórmula puede entenderse directamente, considerando las n! permutaciones de todos los elementos de S. Cada una de esas 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 ú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 desprenden las relaciones entre los números adyacentes del triángulo de Pascal en las tres direcciones:
( n k ) = { ( n k – 1 ) n – k + 1 k si k > 0 ( n – 1 k ) n n – k si k < n ( n – 1 k – 1 ) n k si n , k > 0 {\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}{k}& {cuadra {texto{si}}k<n{binom {n-1}{k-1}{frac {n}{k}& {cuadra {texto{si}}n,k>0\end{cases}}}
.
Junto con los casos básicos ( n 0 ) = 1 = ( n n ) {\displaystyle {\tbinom {n}{0}}=1={tbinom {n}{n}}
, éstas permiten calcular sucesivamente, respectivamente, todos los números de combinaciones de un mismo conjunto (una fila del 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 recuento de combinacionesEditar
Como ejemplo concreto, se puede calcular el número de manos de cinco cartas posibles de una baraja estándar de cincuenta y dos cartas como:
( 52 5 ) = 52 × 51 × 50 × 49 × 48 5 × 4 × 3 × 2 × 1 = 311.875.200 120 = 2.598.960. {\displaystyle {52 \\N-elegir 5}={frac {52 \N- 51 \N- 50 \N- 49 \N- 48}{5 \N- 4 \N- 3 \N- 2 \N – 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, tras lo cual sólo se requiere la multiplicación de los factores restantes:
( 52 5 ) ¡¡= 52 ! ¡¡¡5 ! 47 ! = 52 × 51 × 50 × 49 × 48 × 47 ! 5 × 4 × 3 × 2 × 1 × 47 ! = 52 × 51 × 50 × 49 × 48 5 × 4 × 3 × 2 = ( 26 × 2 ) × ( 17 × 3 ) × ( 10 × 5 ) × 49 × ( 12 × 4 ) 5 × 4 × 3 × 2 = 26 × 17 × 10 × 49 × 12 = 2,598,960. {\displaystyle {\begin{alignedat}{2}{52}{elegir 5}&={frac {52!}{5!}{47!}} {9782>={frac {52}{51}{50}{49}{48}{5}{4}{3}{2}{cancelar}{1}{cortando} {47!}}}}&={frac {52 veces 51 veces 50 veces 49 veces 48}{5 veces 4 veces 3 veces 2}}&={frac {(26 veces {cancelación {2}})\N-(17 veces {cancelación {3})\N-(10 veces {cancelación {5}) {5}){a veces 49 {a veces 12 {a veces 4})}{{a veces 5}}{a veces 4}}{a veces {a veces 3}{a veces 2}{a veces 82}={26}{a veces 17}{a veces 10}{a veces 49}{a veces 12}{a}{a}{a}},}598{,}960.\Fin de la alineación.
Otro cálculo alternativo, equivalente al primero, se basa en escribir
( n k ) = ( n – 0 ) 1 × ( n – 1 ) 2 × ( n – 2 ) 3 × ⋯ × ( n – ( k – 1 ) ) k , {\displaystyle {n \\channel k}= {\frac {(n-0)}{1}{tiempos {\frac {(n-1)}{2}{tiempos {\frac {(n-2)}{3}{tiempos \cdots}{tiempos {\frac {(n-(k-1))}{k},}
lo que da
( 52 5 ) = 52 1 × 51 2 × 50 3 × 49 4 × 48 5 = 2.598,960 {\displaystyle {52}{elegir 5}={frac {52}{1}veces {{frac {51}{2}}veces {{frac {50}{3}veces {{frac {49}{4}=2{,}598{,}960}
.
Cuando se evalúa en el siguiente orden, 52 ÷ 1 × 51 ÷ 2 × 50 ÷ 3 × 49 ÷ 4 × 48 ÷ 5, se puede calcular utilizando sólo aritmética de 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.
Usando la fórmula simétrica en términos de factoriales sin realizar simplificaciones se obtiene un cálculo bastante extenso:
( 52 5 ) = n ! k ! ¡( n – k ) ! = 52 ! 5 ! ¡( 52 – 5 ) ! = 52 ! 5 ! 47 ! = 80 , 658 , 175 , 170 , 943 , 878 , 571 , 660 , 636 , 856 , 403 , 766 , 975 , 289 , 505 , 440 , 883 , 277 , 824 , 000 , 000 , 000 , 000 120 × 258 , 623 , 241 , 511 , 168 , 180 , 642 , 964 , 355 , 153 , 611 , 979 , 969 , 197 , 632 , 389 , 120 , 000 , 000 , 000 = 2,598,960. {\displaystyle {\begin{aligned}{52}{elegir 5}&={frac {n!}{k!(n-k)!}}={frac {52!}{5!(52-5)!}}={frac {52!}{5!47!}}\\&={\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}}\\&=2{,}598{,}960.\Fin.
Enumeración de k-combinacionesEditar
Se pueden enumerar todas las k-combinaciones de un conjunto dado S de n elementos en algún orden fijo, lo que establece una biyección desde un intervalo de ( n k ) {\displaystyle {\tbinom {n}{k}}
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. Esta última opción tiene la ventaja de que al añadir un nuevo elemento mayor a S no se modifica la parte inicial de la enumeración, sino que simplemente se añaden las nuevas k-combinaciones del conjunto mayor después de las anteriores. Repitiendo este proceso, la enumeración puede ampliarse indefinidamente con k-combinaciones de conjuntos cada vez más grandes. Además, si los intervalos de los números enteros empiezan en 0, la combinación k en un lugar i de la enumeración puede calcularse fácilmente a partir de i, y la biyección así obtenida se conoce como sistema numérico combinatorio. También se conoce como «rank»/»ranking» y «unranking» en matemáticas computacionales.
Hay muchas maneras de enumerar k combinaciones. Una forma es visitar todos los números binarios menores que 2n. Elegir aquellos números que tengan k bits distintos de cero, aunque esto es muy ineficiente incluso para n pequeños (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 unos 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 sencilla y más rápida es seguir los k números de índice de los elementos seleccionados, empezando por {0 .. k-1} (basado en cero) o {1 .. k} (basado en uno) como la primera combinación k permitida y luego pasar repetidamente a la siguiente combinación k permitida incrementando el último 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 tal índice existe y restablecer los números de índice después de x a {x+1, x+2, …}.