Bài toán đếm số lượng phần tử riêng

Bài toán: Cho n tập hợp $A_1,A_2,...,A_n (n\in \mathbb{N^{*}})$

Đếm số lượng của tập B gồm các phần tử chỉ thuộc đúng một trong các tập hợp trên.

 

Giải

Bổ đề: $\sum\limits_{i=1}^{n-1}(-1)^i i \binom{n}{i}=-(-1)^{n}.n$ (*)

Ta sẽ chứng minh bổ đề trên bằng biến đổi.

$(*)\Leftrightarrow \sum\limits_{i=1}^{n}(-1)^i i \binom{n}{i}=0$

Ta có:

$\sum\limits_{i=1}^{n}(-1)^i i \binom{n}{i}=\sum\limits_{i=1}^{n-1}(-1)^i i \left ( \binom{n-1}{i-1}+\binom{n-1}{i} \right)+(-1)^n n \binom{n}{n}$

$=\sum\limits_{i=0}^{n-2}(-1)^{i+1}(i+1)\binom{n-1}{i}+\sum\limits_{i=1}^{n-1}(-1)^i i \binom{n-1}{i}+(-1)^n n \binom{n-1}{n-1}$

$=(-1)^1 1 \binom{n-1}{0}-\sum\limits_{i=1}^{n-2}(-1)^i\binom{n-1}{i}+(-1)^{n-1} (n-1) \binom{n-1}{n-1}+(-1)^n n \binom{n-1}{n-1}$

$=-\sum\limits_{i=0}^{n-2}(-1)^i\binom{n-1}{i}-(-1)^{n-1}\binom{n-1}{n-1}$
$=-\sum\limits_{i=0}^{n-1}(-1)^{n-1}\binom{n-1}{i}=0$

Vậy bổ đề được chứng minh hoàn toàn.

Quay lại bài toán:

Ý tưởng: Đầu tiên, ta sẽ tìm cách "loại trừ" các phần tử thuộc đúng k tập hợp $ 2 \leq k \leq n$ trong n tập hợp trên.

Xét k=2, khi đó ta xét biểu thức $B_n=\sum\limits_{1\leqslant  i \leqslant  n}^{}A_i-2\sum\limits_{1\leqslant i_1 < i_2 \leqslant n}^{}|A_i \bigcap A_2|$

Ta thấy rằng, tất cả các phần tử thuộc đúng 2 tập hợp trong biểu thức $B_2$ đã được loại trừ, chỉ còn lại những phần tử thuộc đúng 1 tập hợp. Tuy nhiên, ta đã "loại trừ" không chính xác các phần tử thuộc từ 3 tập hợp trở lên.

Do đó, ta sẽ thiết lập $B_3$,$B_4$,...,$B_k$ theo ý tưởng trên để "loại trừ" chính xác các phần tử thuộc đúng k tập hợp, lúc này $B_n$ sẽ là kết quả cần tìm vì khi đó $B_n$ đã loại hết được những phần tử thuộc 2 đến n tập hợp và dĩ nhiên không loại trừ dư vì không tồn tại phần tử nào thuộc n+1 tập hợp trở lên.

Giả sử: $B_k=-\sum\limits_{j=1}^{k}\left ((-1)^j j  \sum\limits_{1\leqslant i_2<i_3<...<i_j\leqslant n  }^{}| A_{i_{1}} \bigcap A_{i_{2}}\bigcap ... \bigcap A_{i_{j}}| \right)$  đúng đến k

Thấy rằng, với k=1,2 thì (*) đúng. Ta sẽ chứng minh điều giả sử cũng đúng với $n=k+1$

Xét những phần tử bị loại trừ không chính xác thuộc đúng k+1 tập hợp.

Ta sẽ đếm số lượng phần tử bị "loại trừ" không chính xác này ứng với mỗi nhân tử $\sum\limits_{1\leqslant i_2<i_3<...<i_j\leqslant n  }^{}| A_{i_{1}} \bigcap A_{i_{2}}\bigcap ... \bigcap A_{i_{k_{j}}}|$ của $B_k$.

Xét một phần tử bất kì thuộc đúng k+1 tập hợp. Khi đó, nhân tử ứng với $j$ này đã đếm phần tử này số lần bằng số cách chọn ra j tập hợp trong k+1 tập hợp và bằng $\binom{k+1}{j}$

Do đó, số lượng bị "loại trừ" không chính xác thuộc đúng k+1 tập hợp này trong $B_{k}$ là:

$C_{k+1}=-\sum\limits_{j=1}^{k}(-1)^j j \binom{k+1}{j}=(-1)^{k+1} (k+1)$(Theo bổ đề *)

Vậy $B_{k+1}=B_{k}-C_k$

$=-\sum\limits_{j=1}^{k}\left ((-1)^j j  \sum\limits_{1\leqslant i_2<i_3<...<i_j\leqslant n  }^{}| A_{i_{1}} \bigcap A_{i_{2}}\bigcap ... \bigcap A_{i_{j}}| \right)-(-1)^{k+1} (k+1)$

$=-\sum\limits_{j=1}^{k+1}\left ((-1)^j j  \sum\limits_{1\leqslant i_2<i_3<...<i_j\leqslant n  }^{}| A_{i_{1}} \bigcap A_{i_{2}}\bigcap ... \bigcap A_{i_{j}}| \right)$

Do đó, ta được:

$B_k=-\sum\limits_{j=1}^{k}\left ((-1)^j j  \sum\limits_{1\leqslant i_2<i_3<...<i_j\leqslant n  }^{}| A_{i_{1}} \bigcap A_{i_{2}}\bigcap ... \bigcap A_{i_{j}}| \right)$ đúng với mọi $ 2 \leq k \leq n$ (theo nguyên lý qui nạp)

Thay k=n, kết quả phép đếm là:

$B=B_{n}=-\sum\limits_{j=1}^{n}\left ((-1)^j j  \sum\limits_{1\leqslant i_2<i_3<...<i_j\leqslant n  }^{}| A_{i_{1}} \bigcap A_{i_{2}}\bigcap ... \bigcap A_{i_{j}}| \right)$