Cho tập hợp $X= { 1,2,...,n } $. Gọi $A,B$ là hai tập con của $X$. Tìm tất cả các bộ $(A,B)$ thỏa mãn $A$ không phải là tập con của $B$ và $B$ cũng không
phải là tập con của $A$
Ta sẽ đếm số tập hợp như sau:
Có $n$ cách chọn 1 phần tử thuộc $A$ nhưng không thuộc $B$
Có $n-1$ cách chọn 1 phần tử thuộc $B$ nhưng không thuộc $A$
Với $n-2$ phần tử còn lại:
Mỗi phần tử có thể thuộc một trong 4 trạng thái sau: chỉ thuộc $A$, chỉ thuộc $B$, thuộc cả $A$ và $B$, không thuộc cả $A$ và $B$
Vậy có tổng cộng $\left ( n-1 \right ).n.4^{n-2}$ cách chọn bộ tập con $A$ và $B$
Gọi :
$P=A\B$ (gồm các phần tử thuộc $A$ mà không thuộc $B$)
$Q=B\A$ (gồm các phần tử thuộc $B$ mà không thuộc $A$)
$R=A\cap B$ và $S=\overline{A}\cap \overline{B}$ ($P,Q,R,S$ từng đôi một không giao nhau)
$A$ ko là tập con của $B$ và $B$ ko là tập con của $A$ khi và chỉ khi $P$ và $Q$ đều không rỗng.
Gọi số phần tử của $P,Q,R,S$ lần lượt là $p,q,r,s$ ---> $p+q+r+s=n$.Xét các TH sau :
$1)$ $p+q=2$ ($p,q\neq 0$) ; $r+s=n-2$
+ Chọn $2$ trong $n$ phần tử ---> $C_{n}^{2}$ cách
+ Xếp mỗi phần tử đẫ chọn vào $P$ hoặc $Q$ sao cho $P$ và $Q$ đều không rỗng ---> $2^{2}-2$ cách
+ Xếp mỗi phần tử còn lại vào $R$ hoặc $S$ ---> $2^{n-2}$ cách
$\Rightarrow$ TH 1 có $C_{n}^{2}.(2^2-2).2^{n-2}=C_{n}^{2}.(2^n-2^{n-1})$ cách chọn bộ $(A,B)$
$2)$ $p+q=3$ ($p,q\neq 0$) ; $r+s=n-3$
+ Chọn $3$ trong $n$ phần tử ---> $C_{n}^{3}$ cách
+ Xếp mỗi phần tử đẫ chọn vào $P$ hoặc $Q$ sao cho $P$ và $Q$ đều không rỗng ---> $2^{3}-2$ cách
+ Xếp mỗi phần tử còn lại vào $R$ hoặc $S$ ---> $2^{n-3}$ cách
$\Rightarrow$ TH 2 có $C_{n}^{3}.(2^3-2).2^{n-3}=C_{n}^{3}.(2^n-2^{n-2})$ cách chọn bộ $(A,B)$
$3)$ $p+q=4$ ($p,q\neq 0$) ; $r+s=n-4$
+ Chọn $4$ trong $n$ phần tử ---> $C_{n}^{4}$ cách
+ Xếp mỗi phần tử đẫ chọn vào $P$ hoặc $Q$ sao cho $P$ và $Q$ đều không rỗng ---> $2^{4}-2$ cách
+ Xếp mỗi phần tử còn lại vào $R$ hoặc $S$ ---> $2^{n-4}$ cách
$\Rightarrow$ TH 3 có $C_{n}^{4}.(2^4-2).2^{n-4}=C_{n}^{4}.(2^n-2^{n-3})$ cách chọn bộ $(A,B)$
...............................................................................
..............................................................................
$n-1)$ $p+q=n$ ($p,q\neq 0$) ; $r+s=0$
+ Xếp mỗi phần tử (trong $n$ phần tử) vào $P$ hoặc $Q$ sao cho $P$ và $Q$ đều không rỗng ---> $2^{n}-2$ cách
$\Rightarrow$ TH n-1 có $C_{n}^{n}.(2^n-2)$ cách chọn bộ $(A,B)$
Cộng tất cả n-1 TH trên lại $\Rightarrow$ tổng số cách chọn là :
$(C_{n}^{2}+C_{n}^{3}+...+C_{n}^{n}).2^n-(C_{n}^{2}.2^{n-1}+C_{n}^{3}.2^{n-2}+...+C_{n}^{n}.2)=(C_{n}^{2}+C_{n}^{3}+...+C_{n}^{n}).2^n-2(C_{n}^{2}.2^{n-2}+C_{n}^{3}.2^{n-3}+...+C_{n}^{n}.2^0)=(2^n-n-1).2^n-2(3^n-2^n-n.2^{n-1})=2^{2n}+2^n-2.3^n$ cách chọn.
Chẳng hạn khi $n=3$ thì có $2^6+2^3-2.3^3=18$ cách chọn 2 tập $A$ và $B$ thoả mãn ĐK bài toán (Ban LNH kiểm tra lại)
Bài viết đã được chỉnh sửa nội dung bởi chanhquocnghiem: 21-12-2013 - 10:24