Triángulo de Pascal

¿Qué es el Triángulo de Pascal?

Es un triángulo numérico donde cada número es la suma de los dos de arriba:

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

La magia: El número en la fila $n$, columna $k$ es exactamente $\binom{n}{k}$ (combinaciones de n en k).

Construcción

const int MAXN = 1005;
long long pascal[MAXN][MAXN];

void construir(int n) {
    for (int i = 0; i <= n; i++) {
        pascal[i][0] = 1;
        for (int j = 1; j <= i; j++) {
            pascal[i][j] = pascal[i-1][j-1] + pascal[i-1][j];
        }
    }
}

Con módulo:

const int MOD = 1e9 + 7;

void construirMod(int n) {
    for (int i = 0; i <= n; 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;
        }
    }
}

Propiedades del triángulo

1. Bordes: $\binom{n}{0} = \binom{n}{n} = 1$
2. Simetría: $\binom{n}{k} = \binom{n}{n-k}$
3. Suma de fila: $\sum_{k=0}^{n} \binom{n}{k} = 2^n$
4. Identidad de Pascal: $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$
5. Diagonal: La segunda diagonal es 1, 2, 3, 4, 5… (números naturales)
6. Tercera diagonal: 1, 3, 6, 10, 15… (números triangulares)

Aplicaciones

Potencias de binomios

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

Los coeficientes son exactamente la fila $n$ del triángulo:

• $(a+b)^3 = 1a^3 + 3a^2b + 3ab^2 + 1b^3$ → fila 3: 1, 3, 3, 1

Caminos en cuadrícula

$\binom{n+m}{n}$ da el número de caminos de $(0,0)$ a $(n,m)$.

Sumas de prefijos del triángulo

La suma de una columna del triángulo tiene una fórmula cerrada: $\sum_{i=k}^{n} \binom{i}{k} = \binom{n+1}{k+1}$

Ejercicio de práctica

Imprime las primeras N filas del Triángulo de Pascal.

Entrada: 6 Salida:

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1

#include <iostream>
using namespace std;

long long pascal[105][105];

int main() {
    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        pascal[i][0] = 1;
        for (int j = 1; j <= i; j++) {
            pascal[i][j] = pascal[i-1][j-1] + pascal[i-1][j];
        }
        for (int j = 0; j <= i; j++) {
            if (j > 0) cout << " ";
            cout << pascal[i][j];
        }
        cout << endl;
    }

    return 0;
}