Le principe d'inclusion-exclusion (PIE) est une technique combinatoire fondamentale permettant de calculer le cardinal d'une union de plusieurs ensembles. En informatique, il est particulièrement efficace pour résoudre des problèmes de dénombrement où il est plus simple de compter le complémentaire d'un ensemble ou des intersections spécifiques.

Définition Théorique

Soient \(S_1, S_2, \dots, S_n\) des ensembles finis. La taille de leur union est donnée par la formule :

\[ | \bigcup_{i=1}^n S_i | = \sum_{i=1}^n |S_i| - \sum_{1 \le i < j \le n} |S_i \cap S_j| + \sum_{1 \le i < j < k \le n} |S_i \cap S_j \cap S_k| - \dots + (-1)^{n-1} | \bigcap_{i=1}^n S_i | \]

Dans la pratique algorithmique, on utilise souvent ce principe pour soustraire les cas "invalides" d'un ensemble total de possibilités.

Application 1 : Distribution d'objets dans des réceptaclse

Considérons le problème suivant : distribuer \(n\) boules distinctes dans \(m\) boîtes distinctes de telle sorte qu'aucune boîte ne reste vide.

L'approche par inclusion-exclusion consiste à définir \(S_i\) comme l'ensemble des répartitions où la boîte \(i\) est vide. Nous cherchons à calculer le nombre total de répartitions (\(m^n\)) moins la taille de l'union de tous les \(S_i\).

#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;

ll puissance_rapide(ll base, ll exp) {
    ll res = 1;
    while (exp > 0) {
        if (exp & 1) res *= base;
        base *= base;
        exp >>= 1;
    }
    return res;
}

ll combinaison(int n, int k) {
    if (k < 0 || k > n) return 0;
    ll res = 1;
    for (int i = 1; i <= k; ++i) {
        res = res * (n - i + 1) / i;
    }
    return res;
}

int main() {
    int n, m;
    if (!(cin >> n >> m)) return 0;

    ll cas_invalides = 0;
    for (int i = 1; i < m; ++i) {
        ll terme = combinaison(m, i) * puissance_rapide(m - i, n);
        if (i % 2 == 1) {
            cas_invalides += terme;
        } else {
            cas_invalides -= terme;
        }
    }

    cout << puissance_rapide(m, n) - cas_invalides << endl;
    return 0;
}

Application 2 : Problème de monnaie avec contraintes (Sac à dos)

Supposons que nous ayons 4 types de pièces avec des valeurs fixes \(c_1, c_2, c_3, c_4\). Pour chaque requête, on nous donne une limite de quantité \(d_i\) pour chaque pièce et un montant total \(S\). Combien de façons existe-t-il de constituer la somme \(S\) ?

Ici, une contrainte "invalide" est d'utiliser une pièce \(i\) plus de \(d_i\) fois. Si nous utilisons \(d_i + 1\) pièces de type \(i\), nous avons forcé un état invalide. Le reste de la somme peut être complété de manière illimitée (problème du sac à dos complet).

#include <iostream>

using namespace std;

const int MAX_VAL = 100005;
long long dp[MAX_VAL];
int valeurs[4], limites[4];

void resoudre() {
    for (int i = 0; i < 4; ++i) cin >> valeurs[i];
    
    dp[0] = 1;
    for (int i = 0; i < 4; ++i) {
        for (int j = valeurs[i]; j < MAX_VAL; ++j) {
            dp[j] += dp[j - valeurs[i]];
        }
    }

    int requetes;
    cin >> requetes;
    while (requetes--) {
        for (int i = 0; i < 4; ++i) cin >> limites[i];
        int somme_cible;
        cin >> somme_cible;

        long long total_invalide = 0;
        // Parcours de tous les sous-ensembles de contraintes violées (1 à 15 en binaire)
        for (int masque = 1; masque < 16; ++masque) {
            long long somme_temp = somme_cible;
            int nb_contraintes = 0;
            for (int i = 0; i < 4; ++i) {
                if ((masque >> i) & 1) {
                    // On force le dépassement de la limite pour la pièce i
                    somme_temp -= (long long)valeurs[i] * (limites[i] + 1);
                    nb_contraintes++;
                }
            }
            
            if (somme_temp >= 0) {
                if (nb_contraintes % 2 == 1) {
                    total_invalide += dp[somme_temp];
                } else {
                    total_invalide -= dp[somme_temp];
                }
            }
        }
        cout << dp[somme_cible] - total_invalide << endl;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    resoudre();
    return 0;
}

Synthèse Méthodologique

L'utilisation du principe d'inclusion-exclusion est optimale lorsque :

• Le calcul direct de l'ensemble cible est complexe.
• Les contraintes individuelles sont faciles à modéliser mathématiquement.
• Le nombre de conditions (n) est relativement petit, car la complexité temporelle croît généralement en \(2^n\).

Cette technique est souvent couplée à la programmation dynamique, au calcul de combinaisons ou aux masques binaires pour itérer sur les sous-ensembles de conditions.