Dùng phép song ánh để chứng minh bài toán tổ hợp- Phần 2

Hôm nay ta tiếp tục dùng phép song ánh để giải bài toán đếm trong tổ hợp.

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). 

Dùng phép song ánh để giải bài toán tổ hợp-Phần 1

Đối với một số bài tổ hợp đếm, thì thay vì đếm theo đề bài rất khó khăn ta có thể đếm bằng cách xây dựng một song ánh và áp dụng tính chất:
"Nếu có một phép song ánh đi từ tập X đến tập Y thì |X|=|Y| (trong đó X, Y là hai tập hữu hạn)". Và chuyển về một bài toán đơn giản hơn để tính toán.

Ví dụ: Gọi N là tất cả các số viết trong hệ thập phân có n chữ số trong đó chỉ có các chữ số 1,2,3,4 và số chữ số 1 bằng số chữ số 2. Tính |N|

Giải

Ta bắt đầu xây dựng một phép song ánh:

Gọi M là các số nguyên dương viết trong hệ thập phân có 2n chữ số, trong đó có n chữ số 1 và n chữ số 2. Ta sẽ chứng minh |M|=|N|

Với mỗi số có n chữ số gồm các chữ số 1,2,3,4 và số chữ số 1 bằng số chữ số 2, ta nhân đôi thành số có 2n chữ số theo quy tắc sau: đầu tiên, hai phiên bản của số này được viết kề nhau thành số có có 2 chữ số, sau đó các chữ số 3 ở n chữ số đầu và các chữ số 4 ở n chữ số sau được đổi thành chữ số 1, các chữ số 3 ở n chữ số sau và các chữ số 4 ở n chữ số đầu được đổi thành chữ số 2.

Như thế ta thu được một số có đúng n chữ số 1 và n chữ số 2. Rõ ràng đây là một đơn ánh. Ta thấy với mỗi phần tử thuộc M đều được xác định bởi 1 phần tử N bằng cách ta cắt n chữ số đầu và n chữ số còn lại rồi cộng theo quy tắc 1+1=1, 2+2=2, 1+2=3, 2+1=4, và ta thu được các số gồm các chữ số 1,2,3,4 với số chữ số 1 bằng số chữ số 2.

Vậy ta có |M|=|N|

Số phần tử của |M|=$2^n.C^n_{2n}$ nên $|N|=2^n.C^n_{2n}$.

Như vậy qua phép song ánh ta đã đếm số phần tử của N bằng cách đơn giản hơn do chỉ cần đếm số phần tử của tập M.

Sở dĩ có phép cộng trên là do ta đã sử dụng đơn ánh để xây dựng tính chất từ $M$ sang $N$.