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