Nguyên lý Bao hàm - Loại trừ (Inclusion-Exclusion Principle)

Phát biểu

Diễn đạt bằng lời:

Để tính số phần tử trong hợp của nhiều tập hợp:

• Cộng tất cả số phần tử của từng tập hợp riêng lẻ.
• Trừ đi số phần tử nằm trong từng giao của hai tập.
• Cộng lại số phần tử nằm trong giao của ba tập.
• Tiếp tục xen kẽ dấu trừ và cộng với các giao của 4, 5,... tập hợp.

Định nghĩa đầy đủ

Nguyên lý bao hàm - loại trừ là một phương pháp toán học dùng để đếm số lượng phần tử trong hợp của các tập hợp bằng cách cộng, trừ xen kẽ số lượng phần tử trong các giao của những tập hợp này để tránh việc đếm trùng lặp.

Nguyên lý này thường được sử dụng để giải quyết các bài toán đếm liên quan đến điều kiện kết hợp (OR) phức tạp.

Công thức tổng quát

Cho các tập hợp hữu hạn \(A_1, A_2, \dots, A_n\), ta có:

\[ |A_1 \cup A_2 \cup \dots \cup A_n| = \sum_{i=1}^{n} |A_i| - \sum_{1 \le i < j \le n}|A_i \cap A_j| + \sum_{1 \le i < j < k \le n}|A_i \cap A_j \cap A_k| - \dots + (-1)^{n+1}|A_1 \cap A_2 \cap \dots \cap A_n| \]

Ví dụ minh họa

Ví dụ 1

Bài toán: Có bao nhiêu số từ 1 đến 100 chia hết cho 2 hoặc 3 hoặc 5?

Giải: -\(A\): số chia hết cho 2,\(|A| = 50\)

-\(B\): số chia hết cho 3,\(|B| = 33\)

-\(C\): số chia hết cho 5,\(|C| = 20\)

-\(|A \cap B|\): chia hết cho 6,\(|A \cap B| = 16\)

-\(|A \cap C|\): chia hết cho 10,\(|A \cap C| = 10\)

-\(|B \cap C|\): chia hết cho 15,\(|B \cap C| = 6\)

-\(|A \cap B \cap C|\): chia hết cho 30,\(|A \cap B \cap C| = 3\)

Áp dụng nguyên lý: \[ |A \cup B \cup C| = 50 + 33 + 20 - 16 - 10 - 6 + 3 = 74 \]

Ví dụ 2

Bài toán: Có bao nhiêu số từ 1 đến 50 không chia hết cho 2, 3 hoặc 5?

Giải:

• Tổng số phần tử từ 1 đến 50 là \(50\).
• Số lượng số chia hết cho 2, 3 hoặc 5 (tương tự ví dụ 1) là \(37\).
• Vậy số lượng số không chia hết cho 2, 3 hoặc 5 là \(50 - 37 = 13\).

Ứng dụng trong lập trình thi đấu

• Đếm số lượng phần tử thỏa mãn các điều kiện "hoặc" phức tạp.
• Tính toán các bài toán liên quan đến chia hết, không chia hết, tìm số nguyên tố trong khoảng.
• Kết hợp với bitmasking để giải quyết nhanh các bài toán khi số lượng tập hợp nhỏ (\(n \leq 20\)).

Code template C++

Ví dụ 1

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

typedef long long ll;

// Hàm tính số lượng các số trong khoảng [1..n] chia hết cho ít nhất một số trong tập hợp a[]
ll inclusionExclusion(ll n, vector<ll>& a) {
    ll res = 0;
    int k = a.size();
    for (int mask = 1; mask < (1 << k); ++mask) {
        ll lcm = 1;
        for (int i = 0; i < k; ++i) {
            if (mask & (1 << i)) {
                lcm = lcm / __gcd(lcm, a[i]) * a[i];
                if (lcm > n) break;
            }
        }
        if (__builtin_popcount(mask) % 2 == 1)
            res += n / lcm;
        else
            res -= n / lcm;
    }
    return res;
}

int main() {
    vector<ll> a = {2, 3, 5};
    ll n = 100;
    cout << inclusionExclusion(n, a) << endl; // Kết quả: 74
    return 0;
}

Ví dụ 2

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

typedef long long ll;

// Hàm đếm số lượng số từ L đến R không chia hết cho bất kỳ số nào trong tập hợp a[]
ll countNotDivisible(ll L, ll R, vector<ll>& a) {
    auto countDivisible = [&](ll x) {
        ll res = 0;
        int k = a.size();
        for (int mask = 1; mask < (1 << k); ++mask) {
            ll lcm = 1;
            for (int i = 0; i < k; ++i) {
                if (mask & (1 << i)) {
                    lcm = lcm / __gcd(lcm, a[i]) * a[i];
                    if (lcm > x) break;
                }
            }
            if (lcm > x) continue;
            if (__builtin_popcount(mask) % 2 == 1)
                res += x / lcm;
            else
                res -= x / lcm;
        }
        return res;
    };

    return (R - L + 1) - (countDivisible(R) - countDivisible(L - 1));
}

int main() {
    vector<ll> a = {2, 3, 5};
    ll L = 1, R = 100;
    cout << countNotDivisible(L, R, a) << endl; // Số lượng số không chia hết cho 2,3,5 trong đoạn [1,100]
    return 0;
}

Mở rộng nâng cao

Công thức cho trường hợp phần bù

Khi muốn đếm số lượng phần tử không thuộc vào bất cứ tập nào, ta có thể sử dụng dạng phần bù của nguyên lý: \[ |\overline{A_1 \cup A_2 \cup \dots \cup A_n}| = |U| - |A_1 \cup A_2 \cup \dots \cup A_n| \]

Các ứng dụng nâng cao

• Tính số nguyên tố trong đoạn (sử dụng chung với thuật toán sàng Eratosthenes)
• Giải các bài toán lý thuyết đồ thị liên quan đến tính số lượng cách tô màu, số cách xếp hình.
• Kết hợp với kỹ thuật khác như quy hoạch động trên bitmask, thuật toán tổ hợp, và xác suất.