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.