Đại số tổ hợp trả lời một câu hỏi duy nhất: có bao nhiêu cách? Toàn bộ chương chỉ có hai quy tắc gốc và ba công thức. Cái khó không nằm ở việc nhớ công thức mà ở việc chọn đúng công thức — và đề thi biết rõ điều đó, nên hầu hết bẫy đều nằm ở khâu nhận dạng chứ không ở khâu bấm máy.
Quy tắc cộng. Một công việc có thể làm theo phương án loại I ($m$ cách) hoặc theo phương án loại II ($n$ cách) thì có $m+n$ cách. Điều kiện bắt buộc: hai loại phương án phải rời nhau, không cách nào vừa thuộc loại I vừa thuộc loại II. Nếu chúng chồng lấn thì công thức hỏng và phải dùng $|A\cup B|=|A|+|B|-|A\cap B|$; cộng thẳng sẽ đếm hai lần phần giao.
Quy tắc nhân. Một công việc gồm hai công đoạn nối tiếp: công đoạn thứ nhất có $m$ cách, và ứng với mỗi cách đó, công đoạn thứ hai có $n$ cách thì tổng cộng có $m\cdot n$ cách. Điều kiện bắt buộc: số cách của công đoạn sau không đổi, dù công đoạn trước chọn thế nào. Khi số cách của công đoạn sau thay đổi theo lựa chọn trước (ví dụ lập số có chữ số đầu khác $0$), phải tách trường hợp rồi mới nhân.
Câu hỏi tự phân biệt hai quy tắc: «làm xong một việc là xong, hay còn phải làm tiếp việc nữa?» Chọn một học sinh trong lớp có $20$ nam và $15$ nữ là xong ngay — cộng, được $35$. Chọn một nam và một nữ là hai việc nối tiếp — nhân, được $300$.
| Tên | Công thức | Đếm cái gì |
|---|---|---|
| Hoán vị $P_n$ | $P_n=n!$ | Xếp toàn bộ $n$ phần tử khác nhau thành một dãy có thứ tự |
| Chỉnh hợp $A_n^k$ | $A_n^k=\dfrac{n!}{(n-k)!}=n(n-1)\dots(n-k+1)$ | Chọn $k$ trong $n$ rồi xếp thứ tự $k$ phần tử đó |
| Tổ hợp $C_n^k$ | $C_n^k=\dfrac{n!}{k!\,(n-k)!}$ | Chọn $k$ trong $n$, không phân biệt thứ tự |
Ba công thức này nối với nhau bằng một đẳng thức duy nhất cần nhớ: $A_n^k=C_n^k\cdot k!$. Đọc theo lời: muốn xếp thứ tự thì trước hết chọn ra nhóm ($C_n^k$ cách), rồi xếp thứ tự bên trong nhóm ($k!$ cách). Ai nhớ đẳng thức này thì chỉ cần thuộc một công thức là suy ra công thức kia.
Đừng cố nhớ danh sách các từ khoá. Chỉ cần hỏi một câu duy nhất:
«Đổi thứ tự các phần tử đã chọn thì có ra một kết quả khác không?»
Vài tình huống hay ra đề, xếp sẵn theo câu hỏi trên: lập số, xếp chỗ ngồi, trao giải nhất – nhì – ba, bầu ban gồm các chức vụ khác nhau đều là chỉnh hợp (hoặc hoán vị nếu lấy hết). Chọn tổ trực nhật, chọn đề thi, chọn ban gồm các thành viên ngang vai, số đường chéo, số tam giác, số cái bắt tay đều là tổ hợp.
$C_n^k=C_n^{n-k}$ — chọn ra $k$ phần tử cũng chính là chọn ra $n-k$ phần tử bị bỏ lại, nên hai cách đếm phải cho cùng một số. Và công thức Pascal $C_n^k+C_n^{k+1}=C_{n+1}^{k+1}$, chứng minh bằng cách xét một phần tử cố định: nhóm chứa nó hay không chứa nó. Tổng tất cả các tổ hợp $C_n^0+C_n^1+\dots+C_n^n=2^n$ chính là số tập con của một tập $n$ phần tử.
Khi đề có cụm «ít nhất» hoặc «không», đếm trực tiếp thường phải chia rất nhiều trường hợp. Đếm phần bù nhanh hơn nhiều: lấy tổng số cách trừ đi số cách của tình huống đối lập. Chọn $5$ người từ $12$ người sao cho có ít nhất một nữ thì lấy $C_{12}^5$ trừ đi số cách chọn toàn nam. Điều kiện dùng: hai tình huống phải phủ kín và không chồng lấn — mỗi phương án rơi vào đúng một trong hai. Nếu tách phần bù mà vẫn còn phương án nằm ngoài cả hai thì phép trừ sai.
Mẹo kiểm tra rẻ tiền: với bài nhỏ, hãy đếm trực tiếp bằng cách chia trường hợp rồi so với kết quả tính bằng phần bù. Hai con số phải trùng nhau; lệch nhau là một trong hai cách đã bỏ sót trường hợp.
Mỗi kết quả là một số hai chữ số, trong đó đổi chỗ hai chữ số cho nhau là ra một số khác ($12$ khác $21$). Vậy thứ tự có ý nghĩa, bài này thuộc dạng chỉnh hợp, không phải tổ hợp. Thêm nữa, đề bắt các chữ số đôi một khác nhau nên mỗi chữ số dùng tối đa một lần.
Chọn chữ số hàng chục trước: có $3$ nhánh, ứng với $1$, $2$, $3$. Với mỗi nhánh đó, chữ số hàng đơn vị chỉ còn $2$ lựa chọn vì một chữ số đã bị dùng. Cây có $3\times 2=6$ lá, mỗi lá là một số.
Chọn $2$ chữ số trong $3$ chữ số rồi xếp thứ tự chính là chỉnh hợp chập $2$ của $3$:
$$A_3^2=\dfrac{3!}{(3-2)!}=\dfrac{6}{1}=6.$$Trùng đúng số lá của cây.
Cách kiểm thứ nhất là liệt kê thẳng vì số nhỏ: $12$, $13$, $21$, $23$, $31$, $32$ — đúng $6$ số, không trùng, không sót. Cách kiểm thứ hai dùng quan hệ giữa hai công thức: số cách chọn hai chữ số mà không quan tâm thứ tự là $C_3^2=3$, gồm các cặp $\{1;2\}$, $\{1;3\}$, $\{2;3\}$; mỗi cặp xếp được $2!=2$ số. Vậy $3\times 2=6$, khớp với $A_3^2=C_3^2\cdot 2!$.
Lập được $6$ số tự nhiên có hai chữ số đôi một khác nhau từ ba chữ số $1$, $2$, $3$.
Nếu đề bỏ điều kiện «đôi một khác nhau» thì đáp số đổi hẳn: mỗi vị trí đều có $3$ lựa chọn, cho $3^2=9$ số, thêm $11$, $22$, $33$. Bẫy ngược lại là dùng $C_3^2=3$ vì thấy chữ «chọn hai chữ số» — cách này bỏ mất một nửa kết quả do không tính đến việc đổi chỗ.
Ý thứ nhất: hai người cùng đi dự hội thảo, không ai có vai trò gì khác ai. Đổi thứ tự không tạo ra kết quả mới, nên đây là tổ hợp. Ý thứ hai: một người làm trưởng đoàn, một người làm thư ký. Đổi vai hai người là một phương án hoàn toàn khác, nên đây là chỉnh hợp. Cùng một tập ba người, cùng lấy ra hai, nhưng hai câu hỏi thuộc hai dạng khác nhau — đó chính là điểm mấu chốt của bài.
Ba nhóm đó là $\{A;B\}$, $\{A;C\}$, $\{B;C\}$.
Sáu phương án là $AB$, $BA$, $AC$, $CA$, $BC$, $CB$, trong đó chữ đứng trước chỉ trưởng đoàn.
Liệt kê trực tiếp vì số nhỏ: ý thứ nhất có đúng ba nhóm như đã kể; ý thứ hai có sáu phương án như đã kể, và mỗi nhóm ở ý thứ nhất sinh ra đúng hai phương án ở ý thứ hai. Tỉ số $6:3=2$ chính là $2!$, đúng như đẳng thức $A_3^2=C_3^2\cdot 2!$. Nếu tính ra hai số mà tỉ số của chúng không phải $k!$ thì chắc chắn một trong hai kết quả sai.
Có $3$ cách chọn hai người đi dự hội thảo và $6$ cách chọn hai người có phân vai trưởng đoàn – thư ký.
Bẫy lớn nhất là đọc thấy chữ «chọn» ở cả hai ý rồi dùng chung một công thức. Từ khoá không quyết định dạng bài; thứ quyết định là các phần tử được lấy ra có phân vai hay không. Bẫy thứ hai là cộng hai đáp số lại thành $9$ khi đề hỏi cả hai ý — đó là hai câu hỏi độc lập, mỗi câu một đáp số riêng.
Đội văn nghệ gồm năm người ngang vai, không phân công nhiệm vụ, nên đây là bài tổ hợp. Điều kiện «ít nhất $2$ nữ» gợi ngay tới kỹ thuật đếm phần bù: lấy tổng số cách chọn năm người bất kỳ, trừ đi các trường hợp vi phạm là «không có nữ nào» và «có đúng một nữ». Tổng số học sinh là $8+6=14$.
Trường hợp không có nữ nào, tức chọn cả năm người từ tám nam: $C_8^5=56$. Trường hợp có đúng một nữ, tức chọn một nữ trong sáu và bốn nam trong tám: $C_6^1\cdot C_8^4=6\cdot 70=420$.
Hai trường hợp bị loại không chồng lấn nhau (một bên có $0$ nữ, một bên có đúng $1$ nữ) và cùng với «ít nhất $2$ nữ» thì phủ kín mọi khả năng, nên phép trừ hợp lệ.
Đếm trực tiếp theo số học sinh nữ trong đội:
Tổng bốn dòng: $840+560+120+6=1526$. Hai con đường độc lập cho cùng một số, nên đáp án đứng vững. Kiểm thêm một lớp nữa: cộng cả hai trường hợp bị loại vào, $1526+420+56=2002$, đúng bằng tổng số cách chọn năm người.
Có $1\,526$ cách chọn đội văn nghệ thoả yêu cầu.
Bẫy quen thuộc nhất là «chọn trước hai nữ rồi chọn tuỳ ý ba người còn lại», cho $C_6^2\cdot C_{12}^{3}=15\cdot 220=3300$ — con số này lớn hơn cả tổng số cách chọn năm người, dấu hiệu rõ ràng là đã đếm trùng: cùng một đội bị đếm nhiều lần theo từng cặp nữ được coi là «hai nữ chọn trước». Bẫy thứ hai là chỉ trừ trường hợp không có nữ mà quên trường hợp đúng một nữ, cho $2002-56=1946$.