Đại số tổ hợp

Bạn muốn biết từ một bộ bài 32 lá có thể chọn ra bao nhiêu bộ 5 lá khác nhau? Đó chính là loại bài toán mà đại số tổ hợp giải quyết. Có hai quy tắc đếm cơ bản: quy tắc cộng và quy tắc nhân. Mọi phương pháp khác chỉ là sự mở rộng của hai nguyên tắc này.

Quy tắc cộng

Quy tắc cộng rất đơn giản: nếu hai tập hợp A, B không có phần tử chung thì số cách chọn một phần tử từ hợp A ∪ B bằng |A| + |B|, tức là bằng tổng số phần tử của hai tập hợp.

Ta bắt đầu bằng một ví dụ dễ. Có 6 quả bóng đỏ và 8 quả bóng xanh dương. Ta đổ tất cả vào một thùng. Nếu rút ra một quả bóng thì có tất cả bao nhiêu khả năng? Lúc đầu ta có tập hợp các quả bóng đỏ, gọi là tập hợp A, và tập hợp các quả bóng xanh dương, gọi là B. Hai tập hợp này rời nhau, tức là không có quả bóng nào chung. Ta rút một quả bóng nên có tất cả |A| + |B| = 6 + 8 = 14 khả năng. Chỉ có vậy.

Quy tắc nhân

Lại xét hai tập hợp Z và M. Tập hợp Z gồm 3 người nữ, tập hợp M gồm 4 người nam. Hỏi từ hai tập hợp này có thể lập được bao nhiêu cặp nam – nữ khác nhau? Mỗi lần ta lấy một người nữ và ghép với một người nam. Đếm tất cả các cặp như sau: lấy một người nữ, chẳng hạn Lan, rồi lần lượt ghép với từng người nam. Ta được 4 cặp khác nhau, vì có thể ghép Lan với 4 người nam. Làm tương tự với 2 người nữ còn lại, mỗi người cũng tạo thêm 4 cặp. Vậy có tất cả 4 + 4 + 4 = 12 cặp.

Thực chất ta đã làm gì? Ta đã nhân số phần tử của hai tập hợp. Có 3 người nữ và 4 người nam, nên tổng số cặp là 3 · 4 = 12. Đó là quy tắc nhân. Như vậy, khi lập các cặp từ hai tập hợp, ta chỉ cần nhân số phần tử của tập hợp thứ nhất với số phần tử của tập hợp thứ hai.

Dưới đây có thể kiểm tra rằng điều này đúng. Đó là tất cả các cặp lập được từ 3 người nữ và 4 người nam. Mỗi hàng ứng với các khả năng của một người nữ, mỗi cột ứng với các khả năng của một người nam. Có 3 hàng và 4 cột, nên có tất cả số hàng · số cột khả năng.

$$\begin{array}{rcl}& & (Z_1;M_1),(Z_1;M_2),(Z_1;M_3),(Z_1;M_4),\\ & & (Z_2;M_1),(Z_2;M_2),(Z_2;M_3),(Z_2;M_4),\\ & & (Z_3;M_1),(Z_3;M_2),(Z_3;M_3),(Z_3;M_4)\end{array}$$

Ví dụ có lời giải

1. Có tất cả bao nhiêu số có hai chữ số? Một số có hai chữ số trông thế nào? Ở vị trí thứ nhất là một trong các chữ số 1, …, 9, còn ở vị trí thứ hai có thể thêm cả chữ số 0: 0, …, 9. Như vậy tập hợp thứ nhất có 9 chữ số, tập hợp thứ hai có 10 chữ số. Áp dụng quy tắc nhân, ta được kết quả: 9 · 10 = 90.

• Có bao nhiêu số có ba chữ số mà không chữ số nào xuất hiện hai lần? Ở vị trí thứ nhất lại có 9 chữ số, vì số không thể bắt đầu bằng chữ số 0. Ở vị trí thứ hai có thể là mọi chữ số kể cả 0, nhưng không được là chữ số đã đứng ở vị trí thứ nhất, nên từ 10 chữ số ta bớt đi 1 (chẳng hạn nếu số có ba chữ số bắt đầu bằng chữ số 4 thì rõ ràng ở vị trí thứ hai không thể có chữ số 4 nữa, vì khi đó chữ số 4 xuất hiện hai lần). Ở vị trí thứ ba lại có thể là mọi chữ số, trừ chữ số ở vị trí thứ nhất và thứ hai, với cùng lí do như trên. Nếu ở vị trí thứ nhất là chữ số 4 và ở vị trí thứ hai là chữ số 7 thì ở vị trí thứ ba có thể điền một chữ số thuộc {0; …; 9} ∖ {4; 7}. Từ 10 chữ số ta phải bớt đi 2. Bây giờ chỉ cần nhân: 9 · 9 · 8 = 648. Vậy có tất cả 648 số như thế.
• Gieo một con xúc xắc thông thường hai lần liên tiếp. Có thể nhận được bao nhiêu kết quả khác nhau? Ở lần gieo thứ nhất có 6 kết quả khác nhau. Ở lần gieo thứ hai cũng vậy, nên tổng số khả năng là 6 · 6 = 36.
• Gieo một con xúc xắc hai lần liên tiếp. Có thể nhận được bao nhiêu kết quả khác nhau, nếu ở lần gieo thứ nhất xuất hiện số chấm chẵn? Ở lần gieo thứ nhất xuất hiện số chấm chẵn, tức là một trong các số 2, 4, 6, gồm 3 khả năng. Ở lần gieo thứ hai có thể xuất hiện số chấm bất kì, nên có tất cả 3 · 6 = 18 khả năng.