Combinaciones y Permutaciones

Principios básicos de conteo

Principio de la suma

Si hay $a$ formas de hacer algo Y $b$ formas de hacer otra cosa diferente, hay $a + b$ formas de hacer una u otra.

Principio del producto

Si hay $a$ formas de hacer algo Y LUEGO $b$ formas de hacer otra cosa, hay $a \times b$ formas de hacer ambas cosas.

Permutaciones

Una permutación es un arreglo ordenado de elementos. El orden importa.

Permutaciones de $n$ elementos

$P_n = n!$

Ejemplo: ¿De cuántas formas podemos ordenar las letras A, B, C?

ABC, ACB, BAC, BCA, CAB, CBA → 6 formas = $3! = 6$

Permutaciones de $r$ elementos tomados de $n$

$P(n, r) = \frac{n!}{(n-r)!} = n \times (n-1) \times ... \times (n-r+1)$

Ejemplo: ¿Cuántos números de 3 dígitos distintos se pueden formar con 5?

$P(5, 3) = \frac{5!}{2!} = \frac{120}{2} = 60$

const long long MOD = 1e9 + 7;

long long permutaciones(int n, int r, long long* fact, long long* invFact) {
    if (r > n) return 0;
    return fact[n] * invFact[n - r] % MOD;
}

Permutaciones con repetición

Si tenemos $n$ elementos donde hay $n_1$ elementos del tipo 1, $n_2$ del tipo 2, etc.:

$P = \frac{n!}{n_1! \times n_2! \times ... \times n_k!}$

Ejemplo: ¿De cuántas formas podemos ordenar las letras de "MISSISSIPPI"?

• M: 1, I: 4, S: 4, P: 2
• Total: $\frac{11!}{1! \times 4! \times 4! \times 2!} = \frac{39916800}{1 \times 24 \times 24 \times 2} = 34650$

long long permutacionesConRepeticion(vector<int>& frecuencias, long long* fact, long long* invFact) {
    int n = 0;
    for (int f : frecuencias) n += f;

    long long resultado = fact[n];
    for (int f : frecuencias) {
        resultado = resultado * invFact[f] % MOD;
    }
    return resultado;
}

Combinaciones

Una combinación es una selección de elementos donde el orden NO importa.

Coeficiente binomial

$C(n, r) = \binom{n}{r} = \frac{n!}{r!(n-r)!}$

Ejemplo: ¿De cuántas formas podemos elegir 3 personas de un grupo de 5?

$\binom{5}{3} = \frac{5!}{3! \times 2!} = \frac{120}{6 \times 2} = 10$

long long combinaciones(int n, int r, long long* fact, long long* invFact) {
    if (r > n || r < 0) return 0;
    return fact[n] * invFact[r] % MOD * invFact[n - r] % MOD;
}

Propiedades importantes

1. $\binom{n}{0} = \binom{n}{n} = 1$
2. $\binom{n}{r} = \binom{n}{n-r}$ (simetría)
3. $\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}$ (Pascal)
4. $\sum_{r=0}^{n} \binom{n}{r} = 2^n$
5. $\binom{n}{0} - \binom{n}{1} + \binom{n}{2} - ... = 0$ (si $n > 0$)

Triángulo de Pascal

El triángulo de Pascal visualiza los coeficientes binomiales:

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

Cada número es la suma de los dos números directamente arriba de él.

Implementación

const int MAXN = 5000;
long long pascal[MAXN + 1][MAXN + 1];

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

Combinaciones con repetición

Elegir $r$ elementos de $n$ tipos, permitiendo repetición:

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

Ejemplo: ¿De cuántas formas podemos distribuir 5 dulces idénticos entre 3 niños?

$\binom{3 + 5 - 1}{5} = \binom{7}{5} = 21$

Template completo

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

const long long MOD = 1e9 + 7;
const int MAXN = 2e6;

long long fact[MAXN + 1];
long long invFact[MAXN + 1];

long long potencia(long long base, long long exp) {
    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 precalcular() {
    fact[0] = 1;
    for (int i = 1; i <= MAXN; i++) {
        fact[i] = fact[i-1] * i % MOD;
    }
    invFact[MAXN] = potencia(fact[MAXN], MOD - 2);
    for (int i = MAXN - 1; i >= 0; i--) {
        invFact[i] = invFact[i + 1] * (i + 1) % MOD;
    }
}

// C(n, r) = n! / (r! * (n-r)!)
long long C(int n, int r) {
    if (r > n || r < 0) return 0;
    return fact[n] * invFact[r] % MOD * invFact[n - r] % MOD;
}

// P(n, r) = n! / (n-r)!
long long P(int n, int r) {
    if (r > n) return 0;
    return fact[n] * invFact[n - r] % MOD;
}

// Combinaciones con repetición: C(n + r - 1, r)
long long H(int n, int r) {
    return C(n + r - 1, r);
}

int main() {
    precalcular();

    cout << "C(5, 3) = " << C(5, 3) << endl;  // 10
    cout << "P(5, 3) = " << P(5, 3) << endl;  // 60
    cout << "H(3, 5) = " << H(3, 5) << endl;  // 21

    return 0;
}

Problemas clásicos

Problema 1: Caminos en una cuadrícula

¿Cuántos caminos hay desde $(0, 0)$ hasta $(n, m)$ moviéndose solo derecha o arriba?

Necesitamos $n$ movimientos a la derecha y $m$ hacia arriba, en total $n + m$ movimientos.

$\text{Caminos} = \binom{n + m}{n} = \binom{n + m}{m}$

long long caminosCuadricula(int n, int m) {
    return C(n + m, n);
}

Problema 2: Caminos con obstáculos

Usar programación dinámica con combinaciones:

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

const long long MOD = 1e9 + 7;
// ... (precalcular factoriales)

int main() {
    precalcular();

    int n, m;
    cin >> n >> m;

    vector<string> grid(n);
    for (int i = 0; i < n; i++) cin >> grid[i];

    vector<vector<long long>> dp(n, vector<long long>(m, 0));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == '#') continue;

            if (i == 0 && j == 0) {
                dp[i][j] = 1;
            } else {
                if (i > 0) dp[i][j] = (dp[i][j] + dp[i-1][j]) % MOD;
                if (j > 0) dp[i][j] = (dp[i][j] + dp[i][j-1]) % MOD;
            }
        }
    }

    cout << dp[n-1][m-1] << endl;
    return 0;
}

Problema 3: Subconjuntos de tamaño $k$

¿Cuántos subconjuntos de tamaño exactamente $k$ tiene un conjunto de $n$ elementos?

$\text{Subconjuntos} = \binom{n}{k}$

Problema 4: Distribución de objetos

Distribuir $n$ objetos idénticos en $k$ cajas distinguibles:

• Sin restricciones: $\binom{n + k - 1}{k - 1}$ (Stars and Bars)
• Al menos 1 por caja: $\binom{n - 1}{k - 1}$

// n objetos en k cajas
long long distribuir(int n, int k) {
    return C(n + k - 1, k - 1);
}

// n objetos en k cajas, cada caja al menos 1
long long distribuirMinimo1(int n, int k) {
    if (n < k) return 0;
    return C(n - 1, k - 1);
}

Problema 5: Secuencias binarias

¿Cuántas secuencias binarias de longitud $n$ tienen exactamente $k$ unos?

$\text{Secuencias} = \binom{n}{k}$

Problema 6: Suma de combinaciones

Calcular $\sum_{i=0}^{k} \binom{n}{i}$:

long long sumaCombinaciones(int n, int k) {
    long long suma = 0;
    for (int i = 0; i <= k && i <= n; i++) {
        suma = (suma + C(n, i)) % MOD;
    }
    return suma;
}

Problema 7: Derangements (permutaciones sin puntos fijos)

Un derangement es una permutación donde ningún elemento está en su posición original.

$D_n = n! \sum_{i=0}^{n} \frac{(-1)^i}{i!} = (n-1)(D_{n-1} + D_{n-2})$

long long derangements(int n) {
    if (n == 0) return 1;
    if (n == 1) return 0;

    long long dp[n + 1];
    dp[0] = 1;
    dp[1] = 0;

    for (int i = 2; i <= n; i++) {
        dp[i] = (i - 1) * ((dp[i-1] + dp[i-2]) % MOD) % MOD;
    }

    return dp[n];
}

Identidades útiles

Identidad de Vandermonde

$\binom{m + n}{r} = \sum_{k=0}^{r} \binom{m}{k} \binom{n}{r-k}$

Identidad del bastón de hockey

$\sum_{i=0}^{r} \binom{n+i}{i} = \binom{n+r+1}{r}$

Números de Catalan

$C_n = \frac{1}{n+1} \binom{2n}{n} = \binom{2n}{n} - \binom{2n}{n+1}$

Aplicaciones: paréntesis balanceados, árboles binarios, caminos Dyck.

long long catalan(int n) {
    return C(2 * n, n) * potencia(n + 1, MOD - 2) % MOD;
}

Resumen

Ejercicios recomendados

1. CSES - Binomial Coefficients
2. CSES - Creating Strings II
3. CSES - Distributing Apples
4. Codeforces - Beautiful Numbers
5. AtCoder - Grid Paths