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^*).
(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