Coeficientes binomiales

Tema: Matemática y Combinatoria · temarios: Syllabus OCI · Syllabus IOI

📍 Para profundizar: esta ficha amplía las clases de la Ruta de Aprendizaje. Puedes estudiarla cuando un problema requiera esta herramienta.

Qué hace

C(n, k) cuenta de cuántas formas puedes elegir k elementos entre n sin importar el orden. Esta página lo precalcula con el triángulo de Pascal (cada valor es la suma de los dos de arriba), sin necesidad de inverso modular.

Complejidad: O(N²) precálculo; O(1) consulta.

Cuándo usarlo

Conteo combinatorio con N moderado. Como el inverso modular está fuera del syllabus, Pascal es el camino para C(n,k) mód p.

Implementación recomendada (C++)

// Triángulo de Pascal: C[n][k] para n,k <= N. Sin inverso modular.
// Pasa mod = 0 si no quieres trabajar módulo nada.
vector<vector<long long>> pascal(int N, long long mod) {
    vector<vector<long long>> C(N + 1, vector<long long>(N + 1, 0));
    for (int n = 0; n <= N; n++) {
        C[n][0] = 1;                       // elegir 0 de n: una sola forma
        for (int k = 1; k <= n; k++) {
            C[n][k] = C[n-1][k-1] + C[n-1][k];   // los dos de arriba
            if (mod > 0) C[n][k] %= mod;
        }
    }
    return C;
}

⚠️ Notas

Si N es grande pero solo necesitas pocas filas, calcula fila a fila en O(N). Inclusión-exclusión y pigeonhole suelen acompañar a este precálculo.

🔗 Relacionados