Principle of inclusion and exclusion

Bài này là một mở đầu của phương pháp sàng trong các bài toán đếm. Ở phương pháp này, khi muốn đếm số phần tử của một tập $A$ , ta bắt đầu với một tập $B$ chứa $A$ , sau đó tìm cách loại đi các phần tử không nằm trong $A$ .

Để theo dõi bài này cho dễ, các bạn hãy xem qua các bài sau:

[1] https://nttuan.org/2011/09/15/basic-counting-principles/

[2] https://nttuan.org/2012/09/15/permutations/

[3] https://nttuan.org/2013/09/15/combinations/

Chúng ta biết rằng nếu $A$ và $B$ là các tập hữu hạn rời nhau thì $|A\cup B|=|A|+|B|$ , tổng quát hơn ta có: Nếu $A$ và $B$ là các tập hữu hạn bất kỳ thì $|A\cup B|=|A|+|B|-|A\cap B|,$ đây chính là nguyên lý bù-trừ cho hai tập hợp. Với $n>1$ tập hợp ta có định lí sau

Định lí. Nếu $A_1,A_2,\ldots,A_n$ là các tập hữu hạn thì

$\displaystyle \left|\bigcup_{i=1}^nA_i\right|=\sum_{1\leq i\leq n}|A_i|-\sum_{1\leq i<j\leq n}|A_i\cap A_j|+\cdots+(-1)^{n+1}\left|\bigcap_{1\leq i\leq n}A_i\right|.$

Chứng minh. Ta sẽ chứng minh rằng mỗi phần tử trong $\displaystyle\bigcup_{i=1}^nA_i$ được đếm đúng một lần trong vế phải. Gọi $x$ là một phần tử trong hợp đó và nó nằm trong dúng $m$ tập $A_i$ , khi đó trong vế phải nó sẽ được đếm đúng $C_m^1-C_m^2+\cdots+(-1)^{m+1}C_m^m=1$ lần (lưu ý $(1-1)^m=0$ ). $\Box$

Ngoài cách chứng minh trên các bạn có thể chứng minh định lí bằng phương pháp quy nạp toán học, tôi chọn giới thiệu cách chứng minh này vì phong cách tổ hợp của nó.

Ví dụ 1. Có bao nhiêu số nguyên dương $n$ sao cho $n$ là ước của ít nhất một trong hai số $10^{40}$ và $20^{30}$ ?

Lời giải. Gọi $A$ và $B$ lần lượt là tập các ước dương của $10^{40}$ và $20^{30}$ . Đề bài yêu cầu tính $|A\cup B|$ . Ta có $10^{40}=2^{40}5^{40}, 20^{30}=2^{60}5^{30}$ và $(10^{40},20^{30})=2^{40}5^{30}.$ Suy ra $|A|=(40+1)(40+1)=1681, |B|=(60+1)(30+1)=1891$ và $|A\cap B|=(40+1)(30+1)=1271.$ Bởi thế nên $|A\cup B|=|A|+|B|-|A\cap B|=2301.$ $\Box$

Ví dụ 2. Tìm số các số nguyên dương trong $\{1,2,\ldots,500\}$ chia hết cho $2$ hoặc $3$ hoặc $5.$

Lời giải. Đặt $S=\{1,2,\ldots,500\}$ . Gọi $A,B$ và $C$ lần lượt là tập các phần tử của $S$ chia hết cho $2,3$ và $5$ . Khi đó $A\cup B\cup C$ là tập các số nguyên dương trong $S$ chia hết cho $2$ hoặc $3$ hoặc $5.$ Đề bài yêu cầu tính $|A\cup B\cup C|$ .

Vì $2,3$ và $5$ là các số nguyên dương đôi một nguyên tố cùng nhau nên $A\cap B$ là tập các số nguyên dương trong $S$ chia hết cho $6$ , $B\cap C$ là tập các số nguyên dương trong $S$ chia hết cho $15$ , $C\cap A$ là tập các số nguyên dương trong $S$ chia hết cho $10$ , và $A\cap B\cap C$ là tập các số nguyên dương trong $S$ chia hết cho $30$ . Suy ra $|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|B\cap C|-|C\cap A|+|A\cap B\cap C|$ $\displaystyle=\left[\frac{500}{2}\right]+\left[\frac{500}{3}\right]+\left[\frac{500}{5}\right]-\left[\frac{500}{6}\right]-\left[\frac{500}{15}\right]-\left[\frac{500}{10}\right]+\left[\frac{500}{30}\right]=366.$ $\Box$

Với mỗi số nguyên dương $m$ , ký hiệu $\varphi (m)$ là số các số nguyên dương không vượt quá $m$ và nguyên tố cùng nhau với $m$ . Hàm số $\varphi:\mathbb{N}^*\to\mathbb{N}^*$ được gọi là hàm phi của Euler.

Ví dụ 3. Tính $\varphi (180)$ .

Lời giải. Vì $180=2^23^25$ nên $X$ chính là tập các số trong $S$ không chia hết cho $2,3$ và $5$ . Suy ra $S\setminus X=X_1\cup X_2\cup X_3$ với $X_1$ là tập các số trong $S$ chia hết cho $2$ , $X_2$ là tập các số trong $S$ chia hết cho $3$ , và $X_3$ là tập các số trong $S$ chia hết cho $5.$ Tương tự như bài toán trên ta có

$\displaystyle |X_1\cup X_2\cup X_3|=|X_1|+|X_2|+|X_3|-|X_1\cap X_2|-|X_2\cap X_3|-|X_3\cap X_1|+|X_1\cap X_2\cap X_3|$

$\displaystyle =\left[\frac{180}{2}\right]+\left[\frac{180}{3}\right]+\left[\frac{180}{5}\right]-\left[\frac{180}{6}\right]-\left[\frac{180}{15}\right]-\left[\frac{180}{10}\right]+\left[\frac{180}{30}\right]=132.$ Do đó $\varphi (180)=|X|=|S|-|S\setminus X|=180-132=48.$ $\Box$

Làm tương tự như trên ta có nếu $n$ có phân tích chính tắc $\displaystyle n=\prod p_i^{k_i}$ thì $\displaystyle\varphi (n)=n\prod \left(1-\frac{1}{p_i}\right).$

Ví dụ 4. Tìm số các lời giải nguyên không âm của phương trình $x_1+x_2+x_3=15$ với $x_1\leq 5,x_2\leq 6$ và $x_3\leq 7$ .

Lời giải. Gọi $A$ là tập các nghiệm nguyên không âm của phương trình $x_1+x_2+x_3=15,$ và $B$ là tập các nghiệm nguyên không âm của phương trình thỏa mãn $x_1\leq 5,x_2\leq 6$ và $x_3\leq 7.$ Ta cần tính $\mid B\mid.$ Ta có $A\setminus B=B_1\cup B_2\cup B_3,$ trong đó: $B_1$ là tập các nghiệm nguyên không âm của phương trình thỏa mãn $x_1>5.$ $B_2$ là tập các nghiệm nguyên không âm của phương trình thỏa mãn $x_2>6.$ $B_3$ là tập các nghiệm nguyên không âm của phương trình thỏa mãn $x_3>7.$

Theo nguyên lý bù-trừ, ta có $C^2_{17}-\mid B\mid =\mid A\mid -\mid B\mid =\mid A\setminus B\mid =\sum \mid B_i\mid -\sum \mid B_i\cap B_j\mid+\mid B_1\cap B_2\cap B_3\mid. \quad (*)$

Bộ số tự nhiên $(x_1,x_2,x_3)$ thuộc $B_1$ khi và chỉ khi $(x_1-6)+x_2+x_3=9,$ do đó $\mid B_1\mid =C^2_{11}.$ Hoàn toàn tương tự, ta có $\mid B_2\mid =C^2_{10}$ và $\mid B_3\mid = C_9^2.$

Bộ số tự nhiên $(x_1,x_2,x_3)$ thuộc $B_1\cap B_2$ khi và chỉ khi $(x_1-6)+(x_2-7)+x_3=2,$ do đó $\mid B_1\cap B_2\mid =C^2_{4}.$ Hoàn toàn tương tự, ta có $\mid B_2\cap B_3\mid =1,$ $\mid B_3\cap B_1\mid = C_3^2,$ và $\mid B_1\cap B_2\cap B_3\mid =0.$

Bây giờ thay các kết quả trên vào $(*)$ ta có $\mid B\mid =10.$ $\Box$

Ví dụ 5. Tìm số nghiệm nguyên của phương trình $x_1+x_2+x_3=28$ với $3\leq x_1\leq 9,0\leq x_2\leq 8$ và $7\leq x_3\leq 17$ .

Hướng dẫn. Đáp số: $28.$ Đặt $y_1=x_1-3,$ $y_2=x_2,$ và $y_3=x_3-7.$ Ta cần tính số nghiệm tự nhiên của phương trình $y_1+y_2+y_3=18$ thỏa mãn $y_1\leq 6,$ $y_2\leq 8$ và $y_3\leq 10.$ Đến đây làm như ví dụ trên. $\Box$

Ví dụ 6. Với $k=1,2,\ldots,1992$ cho $A_k$ là một tập với $44$ phần tử. Giả sử rằng $|A_i\cap A_j|=1$ với mỗi $i,j$ khác nhau trong $\{1,2,\ldots,1992\}.$ Tính $\displaystyle \left|\bigcup_{i=1}^{1992}A_i\right|.$

Hướng dẫn. Chứng minh giao của tất cả các tập chứa đúng một phần tử. Từ đó có đáp số là $85657.\Box$

Cuối cùng là một áp dụng quan trọng của nguyên lý bù-trừ vào bài toán Bernoulli-Euler về các bức thư sai địa chỉ.

Ví dụ 7 (Bài toán Bernoulli-Euler). Có $n>1$ bức thư khác nhau phải gửi đến $n$ địa chỉ khác nhau. Có bao nhiêu cách gửi mà các bức thư đều đến không đúng địa chỉ?

Lời giải. Theo ngôn ngữ ánh xạ, bài toán được phát biểu như sau: Có bao nhiêu song ánh từ $S=\{1,2,\ldots,n\}$ đến chính $S$ sao cho nó không có điểm bất động? Ta đếm số các song ánh có điểm bất động, số này bằng $\displaystyle C_n=\left|\bigcup_{1\leq i\leq n}A_i\right|,$ ở đây $A_i$ là tập các song ánh nhận $i$ làm điểm bất động. Theo nguyên lý bao hàm và loại trừ dễ có $\displaystyle C_n=\sum_{k=1}^nC_n^k(-1)^{k+1}(n-k)!$ và đáp số của bài toán là $D_n=n!-C_n\Box$ .