Ví dụ 2: Cho tập A={1,2,..,2n}. Một tập con B của A gọi là một tập cân nếu trong tập đó số các số chẵn và các số lẻ bằng nhau. ( Tập rỗng là một tập cân). Tính số tập cân của A.
Giải.
Gọi N là họ các tập con của A có đúng n phần tử, B là một tập cân. $B_1, B_2$ tương ứng các tập số chẵn và lẻ của B thì $B_1=B_2$.
Ta xây dựng một ánh xạ như sau;
$f: B \rightarrow N$
Trong đó $f(B)=B_1 \cup (Y\setminus B_2)$
$\Rightarrow |f(B)|=|B_1|+|Y|-|B_2|$ vậy muốn cho $f(B)$ thuộc $N$ thì trước hết $Y$ phải có n phần tử và Y không có phần tử chung với $B_1$. Như vậy $Y$ phải tập tất cả số lẻ của tập $A$ ($|Y|=n)$
Nên f đơn ánh
Nếu có tập $M$ thuộc $N$. Kí hiệu $M_1$, $M_2$ là tập số chẵn số lẻ của M thì $|M_1|+|M_2|=n$. Ta phải tìm xây dựng $B_1,B_2$ theo $M_1, M_2$ sao cho $|B_1|=|B_2|$ thì $B_2=Y \setminus M_2$ và $B_1=M_1$. $\Rightarrow f(B)=M$.
Như vậy ta xây dựng song ánh giữa B và N.
Vậy A có tấp cả $C^n_{2n}$
Nhận xét: Tại sao lại xây dựng f đi từ B đến N ? Thực ra qua một vài phép liệt kê ta sẽ thấy !
Một số bài tập cho bạn đọc:
1/(Bài toán chia kẹo của Euler) Có m chiếc kẹo giống nhau chia cho n em bé. Hỏi có bao nhiêu cách chia?
Đây cũng chính là bài toán: “Tìm số nghiệm không âm của phương trình : 
($n, m \in N^*$).
Các bạn có thể nghiên cứu chuyên đề tại đây.
2( Lấy trong TLCT)/ Cho trước số nguyên dương n và số nguyên dương r thoả $r<n-r+1$. Giả sử X={1,2..n}. Hoi r có bao nhiêu tập con A của X đồng thời có tính chất:
+ Chứa r phần tử
+ Không chứa hai số nguyên liên tiếp.
(Gợi ý: Các bạn thử liệt kê như Vd 2 các bạn sẽ có hướng làm).
Không có nhận xét nào:
Đăng nhận xét