Coeficientes Binomiais

Coeficientes binomiais $\binom n k$ são o número de maneiras de selecionar um conjunto de $k$ elementos a partir de $n$ elementos diferentes sem levar em conta a ordem de organização desses elementos (ou seja, o número de conjuntos não ordenados).

Os coeficientes binomiais também são os coeficientes na expansão de $(a + b) ^ n$ (o chamado teorema do binômio):

$$ (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 $$

Acredita-se que essa fórmula, assim como o triângulo que permite o cálculo eficiente dos coeficientes, tenha sido descoberta por Blaise Pascal no século XVII. No entanto, era conhecido pelo matemático chinês Yang Hui, que viveu no século XIII. Talvez tenha sido descoberto por um estudioso persa Omar Khayyam. Além disso, o matemático indiano Pingala obteve resultados semelhantes. O mérito de Newton é que ele generalizou essa fórmula para expoentes que não são naturais.

Cálculo

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

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

Essa fórmula pode ser deduzida do problema de resolver o - número de maneiras de selecionar $k$ elementos diferentes de $n$ elementos diferentes - . Primeiro, vamos contar o número de seleções ordenadas de $k$ elementos. Existem $n$ maneiras de selecionar o primeiro elemento, $n-1$ maneiras de selecionar o segundo elemento, $n-2$ maneiras de selecionar o terceiro elemento e assim por diante. Como resultado, obtemos a fórmula do número de arranjos ordenados: $n (n-1) (n-2) \cdots (n - k + 1) = \frac {n!} {(n-k)!}$. Podemos facilmente passar para arranjos não ordenados, observando que cada arranjo não ordenado corresponde exatamente a $k!$ arranjos ordenados ($k!$ é o número de permutações possíveis de $k$ elementos). Obtemos a fórmula final dividindo $\frac {n!} {(n-k)!}$ by $k!$.

Fórmula recursiva (associada ao famoso "Triângulo de Pascal"):

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

Nota: é mais fácil de deduzir isso usando a fórmula analítica.

Observe que para $n \lt k$ o valor de $\binom n k$ é assumido como zero.

Propriedades

Os coeficientes binomiais têm muitas propriedades diferentes. Aqui estão as mais simples deles:

Cálculo

Cálculo direto usando a fórmula analítica

A primeira fórmula direta é mais fácil de codificar, mas é provável que esse método cause overflow mesmo para valores relativamente pequenos de $n$ e $k$ (mesmo se a resposta se encaixar completamente em alguns dos tipos de dados, o cálculo dos fatoriais intermediários pode causar overflow). Portanto, esse método geralmente só pode ser usado com aritmética longa:

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;
}

Implementação aprimorada

Observe que, na implementação acima, o numerador e denominador têm o mesmo número de fatores ($k$), cada um dos quais é maior que ou igual a 1. Portanto, podemos substituir nossa fração por um produto de $k$ frações, cada uma das quais é com um valor real. No entanto, em cada etapa após multiplicar a resposta atual por cada uma das próximas frações, a resposta ainda será inteira (isso segue da propriedade da fatoração). Implementação em 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);
}

Aqui, projetamos cuidadosamente o número do tipo float para um número inteiro, levando em consideração que, devido aos erros acumulados, ele pode ser um pouco menor que o valor real (por exemplo $2.99999$ em vez de $3$).

Triângulo de Pascal

Usando a relação recursiva, podemos construir uma tabela de coeficientes binomiais (triângulo de Pascal) e obter o resultado dela. A vantagem desse método é que os resultados intermediários nunca excedem a resposta e o cálculo de cada novo elemento da tabela requer apenas uma adição. A falha é a execução lenta para grandes $n$ e $k$ se você precisar apenas de um valor único e não de toda a tabela (porque, para calcular $\binom n k$ será necessário criar uma tabela com todos os $\binom i j, 1 \le i \le n, 1 \le j \le n$, ou pelo menos até $1 \le j \le \min (i, 2k)$). A complexidade do tempo pode ser considerada como $\mathcal{O}(n^2)$. Implementação em 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];
}

Se a tabela inteira de valores não for necessária, armazenar apenas duas últimas linhas será suficiente (a atual $n$-ésima linha e a $n-1$-ésima anterior).

Cálculo em $O(1)$

Finalmente, em algumas situações, é benéfico pré-calcular todos os fatoriais para produzir qualquer coeficiente binomial necessário com apenas duas divisões posteriormente. Isso pode ser vantajoso quando se usa aritmética longa, quando a memória não permite a pré-computação de todo o triângulo de Pascal.

Calculando coeficientes binomiais módulo $m$.

Você pode precisar em algum problema calcular os coeficientes binomiais módulo algum número $m$.

Coeficiente binomial para pequenos $n$

A abordagem discutida anteriormente do triângulo de Pascal pode ser usada para calcular todos os valores de $\binom{n}{k} \bmod m$ para $n$'s razoavelmente pequenos, pois requer complexidade de tempo $\mathcal{O}(n^2)$. Essa abordagem pode lidar com qualquer módulo, pois apenas operações de adição são usadas.

Coeficiente binomial módulo algum número primo grande

A fórmula para os coeficientes binomiais é $$\binom n k = \frac {n!} {k!(n-k)!},$$ então se quisermos calculá-lo módulo algum primo $m > n$, obtemos: $$\binom n k \equiv n! \cdot (k!)^{-1} \cdot ((n-k)!)^{-1} \mod m.$$

Primeiro, pré-calculamos todos os fatoriais módulo $m$ até $\text{MAXN}!$ em tempo $O(\text{MAXN})$.

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

E depois podemos calcular o coeficiente binomial em tempo $O(\log m)$.

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

Podemos até calcular o coeficiente binomial em $O(1)$ se pré-calcularmos os inversos de todos os fatoriais em $O(\text{MAXN} \log m)$ usando o método regular para calcular o inverso, ou mesmo em $O(\text{MAXN})$ usando a congruência $(x!)^{-1} \equiv ((x-1)!)^{-1} \cdot x^{-1}$ e o método para calcular todos os inversos em $O(n)$.

Coeficiente binomial módulo uma potência prima

Aqui queremos calcular o coeficiente binomial módulo alguma potência prima, ou seja, $m = p^b$ para algum primo $p$. Se $p > \max(k, n-k)$, podemos usar o mesmo método descrito na seção anterior. Mas se $p \le \max(k, n-k)$, então, pelo menos um dos $k!$ e $(n-k)!$ não são coprimos com $m$, e, portanto, não podemos calcular os inversos - eles não não existe. No entanto, podemos calcular os coeficientes binomiais.

A idéia é a seguinte: Calculamos para cada $x!$ o maior expoente $c$ no qual $p^c$ divide $x!$, ou seja, $p^c ~|~ x!$. Seja $c(x)$ esse número. E seja $g(x) := \frac{x!}{p^{c(x)}}$. Então, podemos escrever o 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)}$$

O interessante é que agora $g(x)$ está livre do divisor primo $p$. Portanto, $g(x)$ é coprimo de m, e podemos calcular os inversos modulares de $g(k)$ e $g(n-k)$.

Após pré-computar todos os valores de $g$ e $c$, o que pode ser feito com eficiência usando programação dinâmica em $\mathcal{O}(n)$, podemos calcular o coeficiente binomial em $O(\log m)$. Ou pré-calcular todos os inversos e todas as potências de $p$, e depois calcular os coeficientes binomiais em $O(1)$.

Observe que, se $c(n) - c(k) - c(n-k) \ge b$, então $p^b ~|~ p^{c(n) - c(k) - c(n-k)}$, e o coeficiente binomial será $0$.

Coeficiente binomial módulo um número arbitrário

Agora calculamos o coeficiente binomial módulo algum número arbitrário $m$.

Deixe que a fatoração em primos de $m$ seja $m = p_1^{e_1} p_2^{e_2} \cdots p_h^{e_h}$. Podemos calcular o coeficiente binomial módulo $p_i^{e_i}$ para todo $i$. Isso nos dá $h$ diferentes congruências. Como todos os módulos $p_i^{e_i}$ são coprimos, podemos aplicar o teorema chinês do resto para calcular o coeficiente binomial módulo o produto do módulo, que é o desejado coeficiente binomial módulo $m$.

Coeficiente binomial para grandes $n$ e pequenos módulos

Quando $n$ é muito grande, os algoritmos lineares $\mathcal{O}(n)$ discutidos acima se tornam impraticáveis. No entanto, se o módulo $m$ for pequeno, ainda existem maneiras de calcular $\binom{n}{k} \bmod m$.

Quando o módulo $m$ for primo, existem 2 opções:

Quando $m$ não é primo, mas sim um quadrado, os fatores primos de $m$ podem ser obtidos e o coeficiente módulo cada fator primo pode ser calculado usando qualquer um dos métodos acima, e a resposta geral pode ser obtida pelo Teorema do Resto Chinês.

Quando $m$ não for um quadrado, a generalização do teorema de Lucas para potências primas pode ser aplicada em vez do teorema de Lucas.

Problemas

Referências