Inclusión-exclusión

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

Cuenta el tamaño de una unión sin contar nada dos veces: suma los conjuntos por separado, resta las intersecciones de a dos, vuelve a sumar las de a tres, y así alternando el signo. El caso más chico es el que ya conoces: |A ∪ B| = |A| + |B| − |A ∩ B|.

Complejidad: O(2^k · k) recorriendo los subconjuntos de k conjuntos. Práctico hasta k ≈ 20.

Cuándo usarlo

Contar directo te haría contar repetido, pero contar cada condición por separado es fácil. Clásicos: cuántos enteros hasta n son divisibles por alguno de estos números, cuántas permutaciones evitan ciertas posiciones, cuántos objetos cumplen al menos una de varias propiedades.

Implementación recomendada (C++)

// ¿Cuántos enteros de [1, n] son divisibles por AL MENOS UNO de los k de d?
long long divisibles_por_alguno(long long n, const vector<long long>& d) {
    int k = d.size();
    long long total = 0;
    for (int masc = 1; masc < (1 << k); masc++) {   // cada subconjunto no vacío
        long long l = 1;                            // mcm de los elegidos
        bool se_pasa = false;
        for (int i = 0; i < k; i++)
            if (masc >> i & 1) {
                long long g = gcd(l, d[i]);         // std::gcd, de C++17
                if (l / g > n / d[i]) { se_pasa = true; break; }  // el mcm supera n
                l = l / g * d[i];
            }
        if (se_pasa) continue;                      // ese grupo no aporta nada
        int cuantos = __builtin_popcount(masc);
        total += (cuantos % 2 ? +1 : -1) * (n / l); // impares suman, pares restan
    }
    return total;
}

⚠️ Notas

Por qué los signos alternan. Toma un elemento que está en exactamente m de los conjuntos y cuenta cuántas veces lo toca la fórmula: aparece en C(m,1) términos de tamaño 1, en C(m,2) de tamaño 2, etc. La cuenta total es C(m,1) − C(m,2) + C(m,3) − … , que vale 1 para todo m ≥ 1 (es el binomio de (1−1)^m despejado). O sea: los signos están calibrados justo para que cada elemento de la unión se cuente una vez y exactamente una. Ver Coeficientes binomiales.

Cuenta el complemento cuando sea más corto. Muchas veces “al menos uno” es incómodo y “ninguno” es directo: los que no cumplen nada son n menos la unión. El ejemplo canónico es contar los coprimos con n, que sale aplicando esta misma fórmula sobre los factores primos de n (Factorización, o Criba de Eratóstenes si necesitas muchos).

⚠️ El mcm desborda antes de lo que crees. Con tres números del orden de 10^9, el mcm de a pares ya roza 10^18. Por eso el código compara l / g > n / d[i] antes de multiplicar: si el mcm va a pasarse de n, ese subconjunto aporta 0 y se descarta sin llegar a calcularlo. Multiplicar primero y revisar después es un desbordamiento silencioso.

El techo es 2^k, no n. Con k = 20 son un millón de subconjuntos y va cómodo; con k = 30 son mil millones y ya no. Si tienes muchos conjuntos, casi siempre el problema tiene estructura (primos distintos, conjuntos anidados) que evita recorrerlos todos.

🔗 Relacionados