Câu hỏi cốt lõi: thứ tự có quan trọng không?
Chỉnh hợp và tổ hợp đều đếm số cách chọn r phần tử từ một nhóm gồm n phần tử phân biệt, nhưng chúng trả lời hai câu hỏi khác nhau. Chỉnh hợp đếm số cách vừa chọn vừa sắp xếp r phần tử, nên hai lựa chọn chứa đúng những phần tử giống nhau nhưng xếp khác thứ tự được tính thành hai kết quả riêng biệt. Tổ hợp chỉ đếm số cách chọn ra r phần tử, nên hai lựa chọn chứa cùng những phần tử ấy được tính là một kết quả duy nhất, bất kể chúng được lấy ra theo thứ tự nào.
Một cách nhanh để quyết định dùng công thức nào: hãy hình dung hai lựa chọn dùng đúng cùng các phần tử nhưng liệt kê hoặc sắp xếp khác nhau. Nếu hai lựa chọn ấy phản ánh hai kết quả thực tế khác nhau — hai bảng xếp hạng, hai mật khẩu, hai thứ tự về đích trong một cuộc đua — thì thứ tự có ý nghĩa và chỉnh hợp là phép đếm đúng. Nếu chúng phản ánh cùng một kết quả thực tế — cùng một ban đại diện, cùng một bộ bài trên tay, cùng một bộ số xổ số — thì thứ tự không có ý nghĩa và tổ hợp mới là phép đếm đúng.
Công thức nPr và nCr, kèm một ví dụ đã kiểm chứng
Số chỉnh hợp chập r của n phần tử phân biệt là nPr = n! / (n − r)!, còn số tổ hợp là nCr = n! / [r! (n − r)!] — công thức tổ hợp chính là công thức chỉnh hợp chia cho r!, vì phép chia cho r! loại bỏ r! cách sắp xếp khác nhau của cùng một nhóm phần tử mà phép đếm chỉnh hợp vốn tính riêng.
Ví dụ minh họa: chọn 3 phần tử từ nhóm 7 phần tử. Chỉnh hợp: 7P3 = 7! / (7−3)! = 7 × 6 × 5 = 210. Tổ hợp: 7C3 = 7! / (3! × 4!) = (7 × 6 × 5) / (3 × 2 × 1) = 210 / 6 = 35. Số tổ hợp đúng bằng số chỉnh hợp chia cho 3! = 6, khẳng định quan hệ nCr = nPr / r!.
| Đại lượng | Công thức | Giá trị khi n=7, r=3 |
|---|---|---|
| Chỉnh hợp (thứ tự có ý nghĩa) | nPr = n! / (n − r)! | 7P3 = 7 × 6 × 5 = 210 |
| Tổ hợp (thứ tự không có ý nghĩa) | nCr = n! / [r!(n − r)!] | 7C3 = 210 / 3! = 35 |
Có lặp lại và không lặp lại
Cả hai công thức trên đều giả định mỗi phần tử trong n phần tử chỉ được chọn nhiều nhất một lần — tức lấy mẫu không lặp. Khi phần tử được dùng lại (lấy mẫu có lặp, còn gọi là lấy mẫu có hoàn lại), công thức đếm thay đổi. Chỉnh hợp có lặp đơn giản là nâng n lên lũy thừa r, vì mỗi vị trí trong r vị trí đều có đủ n lựa chọn một cách độc lập, bất kể trước đó đã chọn gì: n^r.
Tổ hợp có lặp dùng một công thức khác, C(n + r − 1, r), đếm số cách chọn r phần tử từ n loại khi được phép trùng lặp mà thứ tự vẫn không có ý nghĩa — đây là trường hợp ít gặp hơn nhưng vẫn xuất hiện, chẳng hạn khi chọn các viên kem từ n vị mà cùng một vị có thể chọn nhiều lần.
| Trường hợp | Công thức | Ví dụ điển hình |
|---|---|---|
| Chỉnh hợp, không lặp | n! / (n − r)! | Xếp hạng 3 người thắng trong 7 thí sinh chung kết |
| Chỉnh hợp, có lặp | n^r | Mã PIN 4 chữ số cho phép trùng chữ số |
| Tổ hợp, không lặp | n! / [r!(n − r)!] | Chọn 6 số cho một vé xổ số |
| Tổ hợp, có lặp | (n + r − 1)! / [r!(n − 1)!] | Chọn 3 viên kem từ 5 vị, được phép trùng vị |
Ví dụ minh họa: mã PIN và vé xổ số
Mã PIN 4 chữ số, trong đó mỗi vị trí trong 4 vị trí có thể là chữ số bất kỳ từ 0 đến 9 và các chữ số được phép trùng nhau (quy tắc thường thấy ở mã PIN ngân hàng), là ví dụ của chỉnh hợp có lặp: thứ tự có ý nghĩa (1234 và 4321 là hai mã khác nhau) và được phép lặp, cho 10^4 = 10.000 mã PIN khả dĩ. Nếu không cho phép trùng chữ số, con số này tụt xuống giá trị chỉnh hợp không lặp, 10P4 = 10 × 9 × 8 × 7 = 5.040 — ít khả năng hơn, vì mỗi chữ số đã dùng sẽ bớt đi một lựa chọn cho các vị trí còn lại.
Một thể thức xổ số kinh điển bốc 6 số từ dải 49 số, không số nào lặp lại và thứ tự bốc không ảnh hưởng đến việc vé có trúng hay không, là ví dụ của tổ hợp không lặp: C(49, 6) = 49! / (6! × 43!) = 13.983.816. Chính con số khổng lồ này giải thích vì sao các thể thức xổ số như vậy được mô tả là trò chơi tỉ lệ trúng cực thấp — số tổ hợp tăng rất nhanh khi n lớn so với r, bởi nó đang đếm các nhóm không thứ tự lấy từ một dải rộng chứ không phải một tập sắp xếp nhỏ và cố định.
Một mẹo nhanh để nhớ nên dùng công thức nào
Trong tiếng Anh, «permutation» và «position» cùng bắt đầu bằng âm P, và mẹo ghi nhớ là chỉnh hợp quan tâm đến vị trí — mỗi phần tử rơi vào chỗ nào trong dãy. Còn «combination» gợi đến một nhóm được gộp lại, như đồ trong một chiếc túi hay thành viên một ban đại diện, nơi chỉ tư cách thành viên mới quan trọng chứ không phải trình tự thêm vào.
Mật khẩu, mã PIN, thứ hạng cuộc đua, cùng mọi cách xếp chỗ ngồi hay xếp lịch đều là bài toán chỉnh hợp, vì đổi thứ tự là đổi kết quả. Bộ bài trên tay, bộ số xổ số, thành phần một ban đại diện, cùng mọi phép chọn nhóm không xét thứ tự đều là bài toán tổ hợp, vì chỉ danh sách thành viên mới đáng kể, không phải trình tự chọn ra chúng.
Câu hỏi thường gặp
Chỉnh hợp và tổ hợp khác nhau ở điểm nào?
Chỉnh hợp đếm các cách sắp xếp có phân biệt thứ tự, nên chọn cùng các phần tử theo thứ tự khác nhau được tính là kết quả khác nhau. Tổ hợp đếm các cách chọn không phân biệt thứ tự, nên cùng các phần tử xếp kiểu nào cũng chỉ tính một lần. Cả hai đều xuất phát từ nhóm n phần tử và chọn ra r phần tử, nhưng số chỉnh hợp luôn lớn hơn hoặc bằng số tổ hợp tương ứng với cùng n và r.
7P3 bằng bao nhiêu và tính thế nào?
7P3 bằng 210, tức số cách chọn và sắp xếp 3 phần tử từ nhóm 7 phần tử phân biệt khi thứ tự có ý nghĩa. Cách tính: 7P3 = 7! / (7 − 3)! = 7 × 6 × 5 = 210, tức nhân ba thừa số lớn nhất của 7! với nhau, vì các thừa số nhỏ hơn đã triệt tiêu với (7−3)! ở mẫu.
7C3 bằng bao nhiêu và tính thế nào?
7C3 bằng 35, tức số cách chọn 3 phần tử từ nhóm 7 phần tử phân biệt khi thứ tự không có ý nghĩa. Cách tính: 7C3 = 7! / (3! × 4!) = (7 × 6 × 5) / (3 × 2 × 1) = 210 / 6 = 35 — đúng bằng số chỉnh hợp 7P3 = 210 chia cho 3! (số cách xếp lại mỗi nhóm 3 phần tử), vì tổ hợp gộp mọi thứ tự của cùng một nhóm thành một kết quả.
Vì sao mã PIN dùng chỉnh hợp còn xổ số dùng tổ hợp?
Mã PIN coi 1234 và 4321 là hai mã khác nhau, tức thứ tự các chữ số làm đổi kết quả, nên đây là bài toán chỉnh hợp — với PIN 4 chữ số cho phép trùng, ta có 10^4 = 10.000 khả năng. Vé xổ số trúng chỉ dựa trên những số nào được bốc, không phụ thuộc trình tự bốc, nên hai lần quay ra cùng bộ số theo thứ tự khác nhau vẫn là một kết quả trúng, tức bài toán tổ hợp — với thể thức 6 chọn từ 49, C(49,6) = 13.983.816 bộ số khả dĩ.
«Có lặp lại» trong công thức chỉnh hợp hay tổ hợp nghĩa là gì?
Nghĩa là một phần tử có thể được chọn nhiều hơn một lần trong cùng một kết quả. Chỉnh hợp có lặp dùng n^r (mỗi vị trí trong r vị trí đều có đủ n lựa chọn một cách độc lập), còn tổ hợp có lặp dùng (n + r − 1)! / [r!(n − 1)!]. Khi không lặp, mỗi phần tử chỉ được dùng nhiều nhất một lần, đúng như giả định của hai công thức nPr và nCr chuẩn.
Tài liệu tham khảo
- NIST Digital Library of Mathematical Functions (DLMF), §26 Combinatorial Analysis. dlmf.nist.gov.
- Rosen KH. Discrete Mathematics and Its Applications. 8th ed. McGraw-Hill, 2018 (permutations, combinations, and counting with repetition).
- Ross SM. A First Course in Probability. Pearson (combinatorial counting methods).
- Weisstein EW. "Permutation" and "Combination." MathWorld — A Wolfram Web Resource. mathworld.wolfram.com.