Combinaciones y Permutaciones

Permutaciones: el orden importa

Pregunta: ¿De cuántas formas puedes ordenar K objetos elegidos de N objetos?

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

Analogía: Estás entregando medallas de oro, plata y bronce a 10 atletas. ¿Cuántas combinaciones de podio hay? El orden importa (oro ≠ plata).

$P(10, 3) = 10 \times 9 \times 8 = 720$

long long permutaciones(int n, int k) {
    long long resultado = 1;
    for (int i = 0; i < k; i++) {
        resultado *= (n - i);
    }
    return resultado;
}

Combinaciones: el orden NO importa

Pregunta: ¿De cuántas formas puedes elegir K objetos de N, sin importar el orden?

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

Analogía: De un grupo de 10 amigos, quieres elegir 3 para formar un equipo. No importa quién sea "primero" — solo quiénes están en el equipo.

$C(10, 3) = \frac{10!}{3! \times 7!} = \frac{720}{6} = 120$

Cálculo con factoriales modulares

const int MOD = 1e9 + 7;
const int MAXN = 1000005;
long long fact[MAXN], inv_fact[MAXN];

long long pot(long long b, long long e, long long m) {
    long long r = 1; b %= m;
    while (e > 0) {
        if (e & 1) r = r * b % m;
        b = b * b % m; e >>= 1;
    }
    return r;
}

void precalcular() {
    fact[0] = 1;
    for (int i = 1; i < MAXN; i++) fact[i] = fact[i-1] * i % MOD;
    inv_fact[MAXN-1] = pot(fact[MAXN-1], MOD-2, MOD);
    for (int i = MAXN-2; i >= 0; i--) inv_fact[i] = inv_fact[i+1] * (i+1) % MOD;
}

long long C(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n] % MOD * inv_fact[k] % MOD * inv_fact[n-k] % MOD;
}

Cálculo con el Triángulo de Pascal

Sin módulo, para valores pequeños:

long long C[1005][1005];

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

Basado en la identidad: $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$

Propiedades útiles

• $\binom{n}{0} = \binom{n}{n} = 1$
• $\binom{n}{k} = \binom{n}{n-k}$ (simetría)
• $\sum_{k=0}^{n} \binom{n}{k} = 2^n$ (todos los subconjuntos)
• $\binom{n}{1} = n$

Aplicaciones en competencias

1. Caminos en una cuadrícula

¿De cuántas formas puedes ir de $(0,0)$ a $(n,m)$ moviéndote solo derecha o abajo?

Necesitas hacer $n$ movimientos abajo y $m$ derecha, en cualquier orden:

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

// De (0,0) a (n,m)
long long caminos(int n, int m) {
    return C(n + m, n);
}

2. Distribución de objetos

¿De cuántas formas puedes repartir N objetos idénticos en K cajas?

$\binom{N + K - 1}{K - 1}$

3. Subconjuntos de tamaño K

// Generar todos los subconjuntos de tamaño K
void generarSubconjuntos(vector<int> &v, int k, int inicio,
                          vector<int> &actual) {
    if (actual.size() == k) {
        for (int x : actual) cout << x << " ";
        cout << endl;
        return;
    }

    for (int i = inicio; i < v.size(); i++) {
        actual.push_back(v[i]);
        generarSubconjuntos(v, k, i + 1, actual);
        actual.pop_back();
    }
}

Ejercicio de práctica

De un grupo de N estudiantes, ¿de cuántas formas puedes elegir un comité de K personas? Imprime la respuesta módulo $10^9+7$.

Entrada: 10 3 Salida: 120

#include <iostream>
using namespace std;

const int MOD = 1e9 + 7;
const int MAXN = 1000005;
long long fact[MAXN], inv_fact[MAXN];

long long pot(long long b, long long e, long long m) {
    long long r = 1; b %= m;
    while (e > 0) {
        if (e & 1) r = r * b % m;
        b = b * b % m; e >>= 1;
    }
    return r;
}

void precalcular() {
    fact[0] = 1;
    for (int i = 1; i < MAXN; i++) fact[i] = fact[i-1] * i % MOD;
    inv_fact[MAXN-1] = pot(fact[MAXN-1], MOD-2, MOD);
    for (int i = MAXN-2; i >= 0; i--) inv_fact[i] = inv_fact[i+1] * (i+1) % MOD;
}

long long C(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n] % MOD * inv_fact[k] % MOD * inv_fact[n-k] % MOD;
}

int main() {
    precalcular();
    int n, k;
    cin >> n >> k;
    cout << C(n, k) << endl;
    return 0;
}