¶ Bao hàm - Loại trừ (Inclusion-Exclusion)

Nguồn: HackerEarth

Người dịch: Bùi Việt Dũng

¶ Phát biểu công thức

Công thức bao hàm - loại trừ được phát biểu như sau:

Để tính lực lượng của hợp của nhiều tập hợp, ta tính tổng lực lượng các tập hợp đó, rồi trừ đi lực lượng của giao của các cặp hai tập hợp khác nhau, rồi cộng lực lượng của giao các bộ ba tập hợp khác nhau, rồi trừ đi lực lượng của các bộ bốn tập hợp, và cứ thế cho đến khi ta xét đến giao của tất cả các tập hợp.

¶ Công thức dành cho tập hợp

Công thức bao hàm - loại trừ có dạng như sau:

∥⋃i=1nAi∥=∑i=1n∥Ai∥−∑i≠j∥Ai∩Aj∥+∥A1∩A2∩A3∥+∥A1∩A2∩A4∥+...+∥An−2∩An−1∩An∥−...−|bigcup_{i=1}^n A_i| = sum_{i=1}^n |A_i| - sum_{i ne j} |A_i cap A_j| + |A_1 cap A_2 cap A_3| + |A_1 cap A_2 cap A_4| + ... + |A_{n-2} cap A_{n-1} cap A_n| - ... -∥⋃i=1n​Ai​∥=∑i=1n​∥Ai​∥−∑i=j​∥Ai​∩Aj​∥+∥A1​∩A2​∩A3​∥+∥A1​∩A2​∩A4​∥+...+∥An−2​∩An−1​∩An​∥−...− (−1)n∥A1∩A2∩...∩An∥ (-1)^n|A_1 cap A_2 cap ... cap A_n|(−1)n∥A1​∩A2​∩...∩An​∥

Ta có thể viết công thức này một cách gọn hơn bằng cách tính tổng của các tập con. Gọi BBB là tập hợp các tập hợp AiA_iAi​. Khi đó công thức bao hàm - loại trừ có dạng:

∥⋃i=1nAi∥=∑C⊂B(−1)∥C∥−1∥⋂e∈Ce∥|bigcup_{i=1}^n A_i| = sum_{C subset B} (-1)^{|C|-1} | bigcap_{e in C} e |∥⋃i=1n​Ai​∥=∑C⊂B​(−1)∥C∥−1∥⋂e∈C​e∥

¶ Lập công thức bằng biểu đồ Venn (Venn diagrams)

Ta có biểu đồ sau biểu diễn ba tập hợp AAA, BBB và CCC.

Khi đó ta thấy lực lượng của A∪B∪CA cup B cup CA∪B∪C bằng lực lượng của AAA, BBB, CCC trừ đi lực lượng của A∩BA cap BA∩B, B∩CB cap CB∩C, C∩AC cap AC∩A rồi cộng thêm lực lượng của A∩B∩CA cap B cap CA∩B∩C.

∥A∪B∪C∥=∥A∥+∥B∥+∥C∥−∥A∩B∥−∥B∩C∥−∥C∩A∥+∥A∩B∩C∥| A cup B cup C | = |A| + |B| + |C| - |A cap B| - |B cap C| - |C cap A| + |A cap B cap C|∥A∪B∪C∥=∥A∥+∥B∥+∥C∥−∥A∩B∥−∥B∩C∥−∥C∩A∥+∥A∩B∩C∥

Tương tự, ta có thể lập công thức với nnn tập hợp.

¶ Công thức dành cho xác suất

Nếu ta có nnn biến cố A1,A2,...,AnA_1, A_2,...,A_nA1​,A2​,...,An​, P(Ai)P(A_i)P(Ai​) là xác suất của biến cố AiA_iAi​, xác suất của biến cố hợp của chúng (nghĩa là biến cố "có ít nhất một trong số nnn biến cố A1,A2,...,AnA_1, A_2, ..., A_nA1​,A2​,...,An​ xảy ra") là

P(⋃i=1nAi)=∑i=1nP(Ai)P(bigcup_{i=1}^n A_i) = sum_{i=1}^n P(A_i)P(⋃i=1n​Ai​)=∑i=1n​P(Ai​) −∑i≠jP(AiAj)- sum_{i ne j} P(A_i A_j)−∑i=j​P(Ai​Aj​) +P(A1A2A3)+ P(A_1 A_2 A_3)+P(A1​A2​A3​) +P(A1A2A4)+ P(A_1 A_2 A_4)+P(A1​A2​A4​) +...+P(An−2An−1An)+...+ P(A_{n-2} A_{n-1} A_n)+...+P(An−2​An−1​An​) −...−- ... -−...− (−1)n.P(A1A2...An)(-1)^n.P(A_1 A_2 ... A_n)(−1)n.P(A1​A2​...An​)

Nếu gọi BBB là tập hợp các tập hợp AiA_iAi​, công thức này cũng có thể viết gọn như sau:

P(⋃i=1nAi)=∑C⊂B(−1)∥C∥−1.P(⋂e∈Ce)P(bigcup_{i=1}^n A_i) = sum_{C subset B} (-1)^{|C|-1}. P(bigcap_{e in C} e)P(⋃i=1n​Ai​)=∑C⊂B​(−1)∥C∥−1.P(⋂e∈C​e)

¶ Chứng minh công thức bao hàm - loại trừ

Để thuật tiện trong chứng minh, ta sử dụng công thức viết gọn sau:

∥⋃i=1nAi∥=∑C⊂B(−1)∥C∥−1∥⋂e∈Ce∥|bigcup_{i=1}^n A_i| = sum_{C subset B} (-1)^{|C|-1} | bigcap_{e in C} e |∥⋃i=1n​Ai​∥=∑C⊂B​(−1)∥C∥−1∥⋂e∈C​e∥

với BBB là tập hợp các tập hợp AiA_iAi​.

Ta cần chứng minh một phần tử bất kì thuộc ít nhất một tập AiA_iAi​, sẽ chỉ được đếm một lần trong công thức.

Xét một phần tử xxx bất kì thuộc k≥1k geq 1k≥1 tập hợp AiA_iAi​. Ta thấy

• Trong công thức, khi ∥C∥=1|C| = 1∥C∥=1, xxx được đếm thêm kkk lần.

• Trong công thức, khi ∥C∥=2|C| = 2∥C∥=2, xxx được đếm bớt đi (k2)binom{k}{2}(2k​) lần bởi xxx bị đếm bớt đi khi ta xét một cặp 2 tập hợp khác nhau trong số kkk tập hợp chứa phần tử xxx.

• Trong công thức, khi ∥C∥=3|C| = 3∥C∥=3, xxx được đếm thêm (k3)binom{k}{3}(3k​) lần.

• ...

• Trong công thức, khi ∥C∥=k|C| = k∥C∥=k, xxx được đếm (kk)binom{k}{k}(kk​) lần. Nếu kkk lẻ thì xxx được đếm thêm, nếu kkk chẵn thì xxx được đếm bớt.

• Trong công thức, khi ∥C∥>k|C| > k∥C∥>k, xxx không được đếm.

Vì vậy, số lần xxx được đếm là T=(k1)−(k2)+(k3)−...+(−1)i−1.(ki)+...+(−1)k−1.(kk)T = binom{k}{1} - binom{k}{2} + binom{k}{3} - ... + (-1)^{i-1}.binom{k}{i} + ... + (-1)^{k-1}.binom{k}{k}T=(1k​)−(2k​)+(3k​)−...+(−1)i−1.(ik​)+...+(−1)k−1.(kk​).

Để tính TTT, ta khai triển (1−x)k(1-x)^k(1−x)k bằng nhị thức Niu-tơn (Newton binomial):

(1−x)k=(k0)−(k1).x+(k2).x2−(k3).x3+...+(−1)k.(kk).xk(1-x)^k = binom{k}{0} - binom{k}{1}.x + binom{k}{2}.x^2 - binom{k}{3}.x^3 + ... + (-1)^k.binom{k}{k}.x^k(1−x)k=(0k​)−(1k​).x+(2k​).x2−(3k​).x3+...+(−1)k.(kk​).xk.

Ta thấy với x=1x=1x=1, (1−x)k=T−1(1-x)^k = T-1(1−x)k=T−1, do đó T=(1−1)k+1=1T = (1-1)^k+1 = 1T=(1−1)k+1=1 hay điều phải chứng minh.

¶ Ứng dụng: Đếm số số nguyên tố cùng nhau với một số cho trước trong một đoạn

Đây là một bài toán dễ dựa trên công thức bao hàm - loại trừ.

Cho hai số nguyên nnn và rrr, đếm số số nguyên tố cùng nhau với nnn trong đoạn [1;r][1;r][1;r].

Thuật toán: Tìm phần bù (the inverse): Đếm số số không nguyên tố cùng nhau với nnn.

Xét các ước nguyên tố của nnn, đánh số chúng từ 1 đến kkk.

Ta có thể tính số số trong đoạn [1;r][1;r][1;r] chia hết cho pip_ipi​ bằng công thức [rpi][frac{r}{p_i}][pi​r​].

Tuy vậy, nếu ta chỉ tính tổng tất cả các số này, ta sẽ ra kết qủa sai. Đó là do một số số có thể chia hết cho nhiều pip_ipi​. Vì vậy ta cần sử dụng đến công thức bao hàm - loại trừ.

int solve (int n, int r) { int sum = 0; vector<int> p; for (int i=2; i*i<=n; ++i) if (n % i == 0) { p.push_back (i); while (n % i == 0) n /= i; } if (n > 1) p.push_back (n); for (int msk=1; msk<(1<<p.size()); ++msk) { int mult = 1, bits = 0; for (int i=0; i<(int)p.size(); ++i) if (msk & (1<<i)) { ++bits; mult *= p[i]; } int cur = r / mult; if (bits % 2 == 1) sum += cur; else sum -= cur; } return r - sum; }