Matemáticasmatemáticascombinatoriapascalcoeficientes-binomiales

Triángulo de Pascal

Comprende el triángulo de Pascal y sus aplicaciones en programación competitiva

OOI Oaxaca9 de febrero de 20269 min read

¿Qué es el Triángulo de Pascal?

El Triángulo de Pascal es una representación visual de los coeficientes binomiales, donde cada número es la suma de los dos números directamente encima de él.

Fila 0:           1
Fila 1:          1 1
Fila 2:         1 2 1
Fila 3:        1 3 3 1
Fila 4:       1 4 6 4 1
Fila 5:      1 5 10 10 5 1
Fila 6:     1 6 15 20 15 6 1
Fila 7:    1 7 21 35 35 21 7 1

El elemento en la fila $n$ y posición $k$ (ambos empezando desde 0) es:

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

Propiedad fundamental

La propiedad que define el triángulo de Pascal es:

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

Esta recurrencia nos permite construir el triángulo sin calcular factoriales.

¿Por qué funciona?

Piensa en elegir $k$ elementos de $n$ :

O incluimos el elemento $n$ (y elegimos $k-1$ de los restantes $n-1$ ): $\binom{n-1}{k-1}$
O no incluimos el elemento $n$ (y elegimos $k$ de los restantes $n-1$ ): $\binom{n-1}{k}$

Implementación básica

Construir el triángulo completo

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5000;
const long long MOD = 1e9 + 7;

long long pascal[MAXN + 1][MAXN + 1];

void construirPascal() {
    for (int i = 0; i <= MAXN; i++) {
        pascal[i][0] = 1;  // C(n, 0) = 1

        for (int j = 1; j <= i; j++) {
            pascal[i][j] = (pascal[i-1][j-1] + pascal[i-1][j]) % MOD;
        }
    }
}

int main() {
    construirPascal();

    // Imprimir las primeras 10 filas
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j <= i; j++) {
            cout << pascal[i][j] << " ";
        }
        cout << endl;
    }

    // Consulta: C(10, 3)
    cout << "C(10, 3) = " << pascal[10][3] << endl;  // 120

    return 0;
}

Complejidad: $O(n^2)$ espacio y tiempo para precálculo.

Calcular solo una fila

Si solo necesitas una fila específica:

vector<long long> filasPascal(int n) {
    vector<long long> fila(n + 1);
    fila[0] = 1;

    for (int k = 1; k <= n; k++) {
        // C(n, k) = C(n, k-1) * (n - k + 1) / k
        fila[k] = fila[k-1] * (n - k + 1) / k;
    }

    return fila;
}

Calcular fila con módulo

vector<long long> filaPascalMod(int n, long long mod) {
    vector<long long> fila(n + 1);
    fila[0] = 1;

    for (int k = 1; k <= n; k++) {
        fila[k] = fila[k-1] * (n - k + 1) % mod;
        // Necesitamos inverso modular de k
        fila[k] = fila[k] * potencia(k, mod - 2, mod) % mod;
    }

    return fila;
}

Patrones en el Triángulo de Pascal

Simetría

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

El triángulo es simétrico respecto al centro.

Suma de una fila

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

// Verificar que la suma de la fila n es 2^n
long long sumaFila(int n) {
    long long suma = 0;
    for (int k = 0; k <= n; k++) {
        suma += pascal[n][k];
    }
    return suma;  // Debería ser 2^n
}

Suma alternada

$\sum_{k=0}^{n} (-1)^k \binom{n}{k} = 0 \quad \text{(para } n > 0\text{)}$

Diagonales

Primera diagonal: Todos 1s
Segunda diagonal: Números naturales (1, 2, 3, 4, ...)
Tercera diagonal: Números triangulares (1, 3, 6, 10, ...)
Cuarta diagonal: Números tetraédricos (1, 4, 10, 20, ...)

         1                    ← Primera diagonal (todos 1)
        1 1
       1 2 1                  ← Segunda diagonal (1, 2, 3, 4...)
      1 3 3 1
     1 4 6 4 1                ← Tercera diagonal (1, 3, 6, 10...)
    1 5 10 10 5 1

Potencias de 11

Las primeras filas, leídas como números, son potencias de 11:

Fila 0: 1 = $11^0$
Fila 1: 11 = $11^1$
Fila 2: 121 = $11^2$
Fila 3: 1331 = $11^3$
Fila 4: 14641 = $11^4$

Números de Fibonacci

La suma de las diagonales "superficiales" da los números de Fibonacci:

         1                    → 1
        1 1                   → 1
       1 2 1                  → 2
      1 3 3 1                 → 3
     1 4 6 4 1                → 5
    1 5 10 10 5 1             → 8

Teorema de Lucas

Para calcular $\binom{n}{k} \mod p$ donde $p$ es primo y $n$ puede ser muy grande:

$\binom{n}{k} \equiv \prod_{i=0}^{m} \binom{n_i}{k_i} \pmod{p}$

donde $n = n_m p^m + ... + n_1 p + n_0$ y $k = k_m p^m + ... + k_1 p + k_0$ son las representaciones en base $p$ .

// Precalcular Pascal hasta p
long long lucasPascal[5001][5001];

void precalcularLucas(int p) {
    for (int i = 0; i < p; i++) {
        lucasPascal[i][0] = 1;
        for (int j = 1; j <= i; j++) {
            lucasPascal[i][j] = (lucasPascal[i-1][j-1] + lucasPascal[i-1][j]) % p;
        }
    }
}

long long lucas(long long n, long long k, int p) {
    if (k > n) return 0;
    if (k == 0 || k == n) return 1;

    long long resultado = 1;

    while (n > 0 || k > 0) {
        int ni = n % p;
        int ki = k % p;

        if (ki > ni) return 0;

        resultado = resultado * lucasPascal[ni][ki] % p;

        n /= p;
        k /= p;
    }

    return resultado;
}

Uso:

int main() {
    int p = 1009;  // Primo pequeño
    precalcularLucas(p);

    // Calcular C(10^18, 10^9) mod 1009
    long long n = 1e18, k = 1e9;
    cout << lucas(n, k, p) << endl;

    return 0;
}

Aplicaciones

Expansión binomial

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

Caminos en cuadrícula

El número de caminos de $(0, 0)$ a $(m, n)$ moviéndose solo derecha/arriba es $\binom{m+n}{n}$ .

Problema: Sumar elementos de una diagonal

// Suma de la k-ésima diagonal (empezando de 0)
// La diagonal k tiene elementos C(k,0), C(k+1,1), C(k+2,2), ...
long long sumaDiagonal(int k, int numElementos) {
    long long suma = 0;
    for (int i = 0; i < numElementos; i++) {
        suma += pascal[k + i][i];
    }
    return suma;
}

Problema: Identidad del bastón de hockey

$\binom{r}{r} + \binom{r+1}{r} + \binom{r+2}{r} + ... + \binom{n}{r} = \binom{n+1}{r+1}$

// Verificar la identidad
bool verificarBaston(int r, int n) {
    long long sumaIzquierda = 0;
    for (int i = r; i <= n; i++) {
        sumaIzquierda += pascal[i][r];
    }

    long long derecha = pascal[n + 1][r + 1];

    return sumaIzquierda == derecha;
}

Problemas de práctica

Problema 1: Contar subconjuntos

Dado un conjunto de $n$ elementos, ¿cuántos subconjuntos de tamaño exactamente $k$ existen?

long long subconjuntos(int n, int k) {
    return pascal[n][k];
}

Problema 2: Coeficiente en expansión

Encuentra el coeficiente de $x^3$ en $(2x + 3)^5$ :

$\binom{5}{3} \cdot 2^3 \cdot 3^2 = 10 \cdot 8 \cdot 9 = 720$

long long coeficienteExpansion(int n, int k, int a, int b) {
    return pascal[n][k] * potencia(a, k) % MOD * potencia(b, n - k) % MOD;
}

Problema 3: Contar caminos

¿Cuántos caminos hay de $(0, 0)$ a $(5, 3)$ ?

long long caminos(int x, int y) {
    return pascal[x + y][y];
}

// caminos(5, 3) = C(8, 3) = 56

Problema 4: Probabilidad binomial

La probabilidad de obtener exactamente $k$ éxitos en $n$ intentos con probabilidad $p$ de éxito:

$P(X = k) = \binom{n}{k} p^k (1-p)^{n-k}$

double probabilidadBinomial(int n, int k, double p) {
    return pascal[n][k] * pow(p, k) * pow(1 - p, n - k);
}

Problema 5: Paridad de C(n, k)

$\binom{n}{k}$ es impar si y solo si $k \land (n - k) = 0$ (AND bit a bit).

bool esImpar(long long n, long long k) {
    return (k & (n - k)) == 0;
}

Template completo

#include <bits/stdc++.h>
using namespace std;

const long long MOD = 1e9 + 7;
const int MAXN = 5000;

long long pascal[MAXN + 1][MAXN + 1];

long long potencia(long long base, long long exp, long long mod = MOD) {
    long long resultado = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) resultado = resultado * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return resultado;
}

void construirPascal() {
    for (int i = 0; i <= MAXN; i++) {
        pascal[i][0] = 1;
        for (int j = 1; j <= i; j++) {
            pascal[i][j] = (pascal[i-1][j-1] + pascal[i-1][j]) % MOD;
        }
    }
}

// C(n, k) usando el triángulo precalculado
long long C(int n, int k) {
    if (k > n || k < 0) return 0;
    return pascal[n][k];
}

// Suma de fila n
long long sumaFila(int n) {
    return potencia(2, n);
}

// Elementos de la diagonal k
vector<long long> diagonal(int k, int limite) {
    vector<long long> resultado;
    for (int i = 0; k + i <= limite; i++) {
        resultado.push_back(pascal[k + i][i]);
    }
    return resultado;
}

int main() {
    construirPascal();

    // Ejemplos de uso
    cout << "C(10, 3) = " << C(10, 3) << endl;
    cout << "Suma fila 10 = " << sumaFila(10) << endl;

    // Imprimir diagonal 2
    cout << "Diagonal 2: ";
    for (long long x : diagonal(2, 10)) {
        cout << x << " ";
    }
    cout << endl;

    return 0;
}

Resumen

Propiedad	Fórmula
Recurrencia	$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$
Simetría	$\binom{n}{k} = \binom{n}{n-k}$
Suma de fila	$\sum_{k=0}^{n} \binom{n}{k} = 2^n$
Suma alternada	$\sum_{k=0}^{n} (-1)^k \binom{n}{k} = 0$
Bastón de hockey	$\sum_{i=r}^{n} \binom{i}{r} = \binom{n+1}{r+1}$