Coeficientes binomiales

Los coeficientes binomiales (binomial coefficients) $\binom n k$ son el número de formas de seleccionar un conjunto de $k$ elementos de $n$ elementos distintos sin tener en cuenta el orden de disposición de estos elementos (es decir, el número de conjuntos no ordenados).

Los coeficientes binomiales son también los coeficientes en la expansión de $(a + b) ^ n$ (el llamado teorema del binomio):

$$(a+b)^n = \binom n 0 a^n + \binom n 1 a^{n-1} b + \binom n 2 a^{n-2} b^2 + \cdots + \binom n k a^{n-k} b^k + \cdots + \binom n n b^n$$

Se cree que esta fórmula, así como el triángulo que permite calcular de forma eficiente los coeficientes, fue descubierta por Blaise Pascal en el siglo XVII. No obstante, ya la conocía el matemático chino Yang Hui, que vivió en el siglo XIII. Quizá la descubrió el sabio persa Omar Khayyam. Además, el matemático indio Pingala, que vivió antes, en el siglo III a. C., obtuvo resultados similares. El mérito de Newton es que generalizó esta fórmula para exponentes que no son naturales.

Cálculo

Fórmula analítica para el cálculo:

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

Esta fórmula se puede deducir fácilmente del problema de las disposiciones ordenadas (número de formas de seleccionar $k$ elementos distintos de $n$ elementos distintos). Primero, contemos el número de selecciones ordenadas de $k$ elementos. Hay $n$ formas de seleccionar el primer elemento, $n-1$ formas de seleccionar el segundo, $n-2$ formas de seleccionar el tercero, y así sucesivamente. Como resultado, obtenemos la fórmula del número de disposiciones ordenadas: $n (n-1) (n-2) \cdots (n - k + 1) = \frac {n!} {(n-k)!}$. Podemos pasar fácilmente a las disposiciones no ordenadas, observando que cada disposición no ordenada corresponde a exactamente $k!$ disposiciones ordenadas ($k!$ es el número de permutaciones posibles de $k$ elementos). Obtenemos la fórmula final dividiendo $\frac {n!} {(n-k)!}$ por $k!$.

Fórmula de recurrencia (asociada al famoso “triángulo de Pascal”):

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

Es fácil deducirla usando la fórmula analítica.

Nótese que para $n \lt k$ se asume que el valor de $\binom n k$ es cero.

Propiedades

Los coeficientes binomiales tienen muchas propiedades distintas. Aquí están las más simples:

• Regla de simetría:

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

• Extracción de un factor:

  $$\binom n k = \frac n k \binom {n-1} {k-1}$$

• Suma sobre $k$:

  $$\sum_{k = 0}^n \binom n k = 2 ^ n$$

• Suma sobre $n$:

  $$\sum_{m = 0}^n \binom m k = \binom {n + 1} {k + 1}$$

• Suma sobre $n$ y $k$:

  $$\sum_{k = 0}^m \binom {n + k} k = \binom {n + m + 1} m$$

• Suma de los cuadrados:

  $${\binom n 0}^2 + {\binom n 1}^2 + \cdots + {\binom n n}^2 = \binom {2n} n$$

• Suma ponderada:

  $$1 \binom n 1 + 2 \binom n 2 + \cdots + n \binom n n = n 2^{n-1}$$

• Relación con los números de Fibonacci:

  $$\binom n 0 + \binom {n-1} 1 + \cdots + \binom {n-k} k + \cdots + \binom 0 n = F_{n+1}$$

Cálculo

Cálculo directo usando la fórmula analítica

La primera fórmula, la directa, es muy fácil de programar, pero es probable que este método desborde incluso para valores relativamente pequeños de $n$ y $k$ (incluso si la respuesta cabe por completo en algún tipo de dato, el cálculo de los factoriales intermedios puede provocar desbordamiento). Por lo tanto, este método a menudo solo se puede usar con aritmética de grandes números:

int C(int n, int k) {
    int res = 1;
    for (int i = n - k + 1; i <= n; ++i)
        res *= i;
    for (int i = 2; i <= k; ++i)
        res /= i;
    return res;
}

Implementación mejorada

Nótese que en la implementación anterior el numerador y el denominador tienen la misma cantidad de factores ($k$), cada uno de los cuales es mayor o igual que 1. Por lo tanto, podemos reemplazar nuestra fracción por un producto de $k$ fracciones, cada una de las cuales es de valor real. Sin embargo, en cada paso, después de multiplicar la respuesta actual por cada una de las fracciones siguientes, la respuesta seguirá siendo entera (esto se sigue de la propiedad de extracción de un factor).

Implementación en C++:

int C(int n, int k) {
    double res = 1;
    for (int i = 1; i <= k; ++i)
        res = res * (n - k + i) / i;
    return (int)(res + 0.01);
}

Acá casteamos con cuidado el número de punto flotante a un entero, teniendo en cuenta que, debido a los errores acumulados, puede quedar ligeramente por debajo del valor verdadero (por ejemplo, $2.99999$ en lugar de $3$).

Triángulo de Pascal

Usando la relación de recurrencia podemos construir una tabla de coeficientes binomiales (triángulo de Pascal) y tomar el resultado de ella. La ventaja de este método es que los resultados intermedios nunca superan la respuesta y calcular cada nuevo elemento de la tabla requiere solo una suma. La desventaja es la ejecución lenta para $n$ y $k$ grandes si solo se necesita un único valor y no la tabla completa (porque para calcular $\binom n k$ habrá que construir una tabla de todos los $\binom i j, 1 \le i \le n, 1 \le j \le n$, o al menos hasta $1 \le j \le \min (i, 2k)$). La complejidad temporal se puede considerar $\mathcal{O}(n^2)$.

Implementación en C++:

const int maxn = ...;
int C[maxn + 1][maxn + 1];
C[0][0] = 1;
for (int n = 1; n <= maxn; ++n) {
    C[n][0] = C[n][n] = 1;
    for (int k = 1; k < n; ++k)
        C[n][k] = C[n - 1][k - 1] + C[n - 1][k];
}

Si no hace falta la tabla completa de valores, basta con guardar solo las dos últimas filas (la fila $n$-ésima actual y la $n-1$-ésima anterior).

Cálculo en $O(1)$ {data-toc-label=“Cálculo en O(1)”}

Por último, en algunas situaciones conviene precalcular todos los factoriales para producir después cualquier coeficiente binomial necesario con solo dos divisiones. Esto puede ser ventajoso al usar aritmética de grandes números, cuando la memoria no permite precalcular todo el triángulo de Pascal.

Cálculo de coeficientes binomiales módulo $m$ {data-toc-label=“Cálculo de coeficientes binomiales módulo m”}

Con bastante frecuencia aparece el problema de calcular coeficientes binomiales módulo algún $m$.

Coeficiente binomial para $n$ pequeño {data-toc-label=“Coeficiente binomial para n pequeño”}

El enfoque del triángulo de Pascal discutido antes se puede usar para calcular todos los valores de $\binom{n}{k} \bmod m$ para $n$ razonablemente pequeño, ya que requiere complejidad temporal $\mathcal{O}(n^2)$. Este enfoque puede manejar cualquier módulo, porque solo se usan operaciones de suma.

Coeficiente binomial módulo un primo grande

La fórmula de los coeficientes binomiales es

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

así que si queremos calcularlo módulo algún primo $m > n$ obtenemos

$$\binom n k \equiv n! \cdot (k!)^{-1} \cdot ((n-k)!)^{-1} \mod m.$$

Primero precalculamos todos los factoriales módulo $m$ hasta $\text{MAXN}!$ en tiempo $O(\text{MAXN})$.

factorial[0] = 1;
for (int i = 1; i <= MAXN; i++) {
    factorial[i] = factorial[i - 1] * i % m;
}

Y después podemos calcular el coeficiente binomial en tiempo $O(\log m)$.

long long binomial_coefficient(int n, int k) {
    return factorial[n] * inverse(factorial[k] * factorial[n - k] % m) % m;
}

Incluso podemos calcular el coeficiente binomial en tiempo $O(1)$ si precalculamos los inversos de todos los factoriales en $O(\text{MAXN} \log m)$ usando el método habitual para calcular el inverso, o incluso en tiempo $O(\text{MAXN})$ usando la congruencia $(x!)^{-1} \equiv ((x-1)!)^{-1} \cdot x^{-1}$ y el método para calcular todos los inversos en $O(n)$.

long long binomial_coefficient(int n, int k) {
    return factorial[n] * inverse_factorial[k] % m * inverse_factorial[n - k] % m;
}

Coeficiente binomial módulo una potencia de primo { #mod-prime-pow}

Acá queremos calcular el coeficiente binomial módulo alguna potencia de primo, es decir $m = p^b$ para algún primo $p$. Si $p > \max(k, n-k)$, entonces podemos usar el mismo método descrito en la sección anterior. Pero si $p \le \max(k, n-k)$, entonces al menos uno de $k!$ y $(n-k)!$ no es coprimo con $m$, y por lo tanto no podemos calcular los inversos: no existen. No obstante, podemos calcular el coeficiente binomial.

La idea es la siguiente: Para cada $x!$ calculamos el mayor exponente $c$ tal que $p^c$ divide a $x!$, es decir $p^c | x!$. Sea $c(x)$ ese número. Y sea $g(x) := \frac{x!}{p^{c(x)}}$. Entonces podemos escribir el coeficiente binomial como:

$$\binom n k = \frac {g(n) p^{c(n)}} {g(k) p^{c(k)} g(n-k) p^{c(n-k)}} = \frac {g(n)} {g(k) g(n-k)}p^{c(n) - c(k) - c(n-k)}$$

Lo interesante es que $g(x)$ ahora está libre del divisor primo $p$. Por lo tanto $g(x)$ es coprimo con $m$, y podemos calcular los inversos modulares de $g(k)$ y $g(n-k)$.

Después de precalcular todos los valores de $g$ y $c$, lo que se puede hacer de forma eficiente con programación dinámica en $\mathcal{O}(n)$, podemos calcular el coeficiente binomial en tiempo $O(\log m)$. O precalcular todos los inversos y todas las potencias de $p$, y entonces calcular el coeficiente binomial en $O(1)$.

Nótese que, si $c(n) - c(k) - c(n-k) \ge b$, entonces $p^b | p^{c(n) - c(k) - c(n-k)}$, y el coeficiente binomial es $0$.

Coeficiente binomial módulo un número arbitrario

Ahora calculamos el coeficiente binomial módulo algún módulo arbitrario $m$.

Sea la factorización en primos de $m$ igual a $m = p_1^{e_1} p_2^{e_2} \cdots p_h^{e_h}$. Podemos calcular el coeficiente binomial módulo $p_i^{e_i}$ para cada $i$. Esto nos da $h$ congruencias distintas. Como todos los módulos $p_i^{e_i}$ son coprimos, podemos aplicar el Teorema Chino del Resto para calcular el coeficiente binomial módulo el producto de los módulos, que es el coeficiente binomial deseado módulo $m$.

Coeficiente binomial para $n$ grande y módulo pequeño {data-toc-label=“Coeficiente binomial para n grande y módulo pequeño”}

Cuando $n$ es demasiado grande, los algoritmos $\mathcal{O}(n)$ discutidos arriba se vuelven impracticables. Sin embargo, si el módulo $m$ es pequeño todavía hay formas de calcular $\binom{n}{k} \bmod m$.

Cuando el módulo $m$ es primo, hay 2 opciones:

• Se puede aplicar el teorema de Lucas , que parte el problema de calcular $\binom{n}{k} \bmod m$ en $\log_m n$ problemas de la forma $\binom{x_i}{y_i} \bmod m$ donde $x_i, y_i < m$. Si cada coeficiente reducido se calcula usando factoriales e inversos factoriales precalculados, la complejidad es $\mathcal{O}(m + \log_m n)$.
• Se puede usar el método para calcular el factorial módulo P para obtener los valores de $g$ y $c$ requeridos y usarlos como se describe en la sección de módulo potencia de primo. Esto toma $\mathcal{O}(m \log_m n)$.

Cuando $m$ no es primo pero es libre de cuadrados, se pueden obtener los factores primos de $m$ y calcular el coeficiente módulo cada factor primo con cualquiera de los métodos anteriores, y la respuesta global se obtiene con el Teorema Chino del Resto.

Cuando $m$ no es libre de cuadrados, se puede aplicar una generalización del teorema de Lucas para potencias de primo  en lugar del teorema de Lucas.

Problemas de práctica

• Codechef - Number of ways 
• Codeforces - Curious Array 
• LightOj - Necklaces 
• HACKEREARTH: Binomial Coefficient 
• SPOJ - Ada and Teams 
• SPOJ - Greedy Walking 
• UVa 13214 - The Robot’s Grid 
• SPOJ - Good Predictions 
• SPOJ - Card Game 
• SPOJ - Topper Rama Rao 
• UVa 13184 - Counting Edges and Graphs 
• Codeforces - Anton and School 2 
• Codeforces - Bacterial Melee 
• Codeforces - Points, Lines and Ready-made Titles 
• SPOJ - The Ultimate Riddle 
• CodeChef - Long Sandwich 
• Codeforces - Placing Jinas 

Referencias

• Blog fishi.devtail.io 
• Pregunta en Mathematics StackExchange 
• Pregunta en CodeChef Discuss