Chọn đúng công thức: thứ tự và sự lặp lại
Có bốn công thức đếm khác nhau, tùy theo hai câu hỏi có/không độc lập: thứ tự có quan trọng không, và có cho phép lặp không?
| Thứ tự có quan trọng? | Có cho phép lặp? | Công thức | Tình huống ví dụ |
|---|---|---|---|
| Có | Không | nPr = n! ÷ (n − r)! | Trao giải nhất/nhì/ba cho 7 vận động viên |
| Có | Có | nʳ | Tạo mã PIN 3 chữ số từ các chữ số 0–6, cho phép trùng |
| Không | Không | nCr = n! ÷ (r!(n−r)!) | Chọn ban gồm 3 người từ 7 người |
| Không | Có | C(n+r−1, r) | Chọn 3 viên kem từ 7 vị, cho phép trùng vị |
- nCr luôn nhỏ hơn hoặc bằng nPr với cùng n và r (cụ thể nCr = nPr ÷ r!), vì tổ hợp gộp mọi nhóm gồm r! cách sắp thứ tự của cùng các phần tử thành một kết quả duy nhất.
- Khi r = 0, cả nPr và nCr đều bằng 1 theo quy ước — có đúng một cách chọn không phần tử nào (phép chọn rỗng).
- Khi r = n (không lặp), nPr = n! và nCr = 1 — chỉ có một cách 'chọn' toàn bộ n phần tử thành một tập không thứ tự, nhưng có n! cách sắp xếp tất cả chúng theo thứ tự.
Chỉnh hợp và tổ hợp là gì?
Chỉnh hợp là một cách sắp xếp các phần tử trong đó thứ tự có ý nghĩa. Số chỉnh hợp chập r của n phần tử phân biệt (không lặp) được viết là nPr và đếm những cách sắp xếp kiểu 'hạng nhất, hạng nhì, hạng ba', trong đó việc hoán đổi hai phần tử đã chọn tạo ra một kết quả khác, phân biệt.
Tổ hợp là một cách chọn các phần tử trong đó thứ tự không có ý nghĩa. Số tổ hợp chập r của n phần tử phân biệt được viết là nCr (còn gọi là 'n chọn r' hay hệ số nhị thức) và đếm những nhóm như một ban đại diện hay một bộ bài trên tay, trong đó cùng một tập phần tử theo thứ tự khác nhau vẫn được coi là cùng một kết quả.
Câu hỏi mấu chốt để phân biệt là: việc sắp xếp lại chính những phần tử đã chọn có tạo ra kết quả khác không? Nếu có (ví dụ trao huy chương vàng/bạc/đồng, hay xếp sách trên giá), dùng chỉnh hợp. Nếu không (ví dụ chọn một ban gồm 3 người, hay rút một bộ bài trên tay), dùng tổ hợp. Công cụ này cũng đưa ra các biến thể 'có lặp', áp dụng khi cùng một phần tử có thể được chọn nhiều lần (ví dụ chọn các chữ số cho mã PIN, hay các viên kem theo vị khi được phép trùng vị).
Cách dùng máy tính chỉnh hợp và tổ hợp này
- Nhập n — tổng số phần tử phân biệt có sẵn để chọn.
- Nhập r — số phần tử được chọn hoặc được sắp xếp. r phải nhỏ hơn hoặc bằng n: nếu r lớn hơn n, công cụ sẽ không trả về kết quả nào cả, kể cả các kết quả cho phép lặp.
- Đọc số chỉnh hợp (nPr) nếu thứ tự chọn có ý nghĩa và không cho phép lặp, hoặc số tổ hợp (nCr) nếu thứ tự không có ý nghĩa và không cho phép lặp.
- Với các tình huống cho phép chọn cùng một phần tử nhiều lần, hãy dùng các kết quả 'có lặp' thay cho giá trị nPr/nCr tiêu chuẩn.
Công thức chỉnh hợp và tổ hợp
Số chỉnh hợp chập r của n phần tử, không lặp, là nPr = n! ÷ (n − r)!, tương đương với tích của r số nguyên liên tiếp giảm dần bắt đầu từ n. Ví dụ minh họa với n = 7, r = 3: 7P3 = 7 × 6 × 5 = 210 — số cách trao ba giải phân biệt hạng nhất, nhì và ba cho 7 thí sinh.
Số tổ hợp chập r của n phần tử, không lặp, là nCr = n! ÷ (r! × (n − r)!) = nPr ÷ r!. Phép chia này loại bỏ r! cách sắp thứ tự trong mỗi nhóm đã chọn, vì tổ hợp không phân biệt thứ tự. Ví dụ minh họa với n = 7, r = 3: 7C3 = 210 ÷ 3! = 210 ÷ 6 = 35 — số ban gồm 3 người phân biệt có thể lập từ 7 người.
Chỉnh hợp có lặp (mỗi vị trí trong r vị trí đều có thể nhận độc lập bất kỳ phần tử nào trong n phần tử) đơn giản là nʳ. Với n = 7, r = 3: 7³ = 343 — chẳng hạn, số mã 3 chữ số phân biệt dùng các chữ số 0–6 khi cho phép trùng. Tổ hợp có lặp dùng công thức 'sao và vạch' C(n + r − 1, r). Với n = 7, r = 3: C(9, 3) = 84 — chẳng hạn, số cách chọn 3 viên kem từ 7 vị khi được phép trùng vị và thứ tự không quan trọng.
Những lỗi thường gặp
- Dùng công thức chỉnh hợp trong khi thứ tự thực ra không quan trọng (hoặc ngược lại) — hãy kiểm tra xem việc hoán đổi hai phần tử đã chọn có làm thay đổi kết quả không trước khi chọn công thức.
- Quên kiểm tra xem có cho phép lặp hay không — 'chọn mã PIN' (chữ số có thể trùng) cần công thức khác với 'chia bài từ một bộ bài' (không lặp, lá bài không quay lại bộ).
- Áp dụng nPr hay nCr với r lớn hơn n khi không cho phép lặp — điều này không xác định, vì bạn không thể chọn nhiều phần tử phân biệt hơn số phần tử có trong tập nếu không lặp lại một phần tử nào đó.
- Nhầm 'tổ hợp có lặp' (công thức sao và vạch) với nCr thông thường — hai công thức cho kết quả rất khác nhau và áp dụng cho những tình huống khác nhau (có lặp so với không lặp).
Câu hỏi thường gặp
Chỉnh hợp và tổ hợp khác nhau như thế nào?
Chỉnh hợp đếm các cách sắp xếp trong đó thứ tự có ý nghĩa (nPr = n! ÷ (n−r)!) — ví dụ, xếp hạng nhất, nhì và ba. Tổ hợp đếm các cách chọn trong đó thứ tự không có ý nghĩa (nCr = n! ÷ (r!(n−r)!)) — ví dụ, chọn một ban đại diện. Với n = 7 và r = 3: 7P3 = 210 (có thứ tự), nhưng 7C3 = 35 (không thứ tự), vì mỗi nhóm 3 người có thể được sắp theo 3! = 6 thứ tự khác nhau, và 210 ÷ 6 = 35.
Tính nCr (n chọn r) như thế nào?
Dùng công thức nCr = n! ÷ (r! × (n − r)!). Với n = 7, r = 3: 7C3 = 7! ÷ (3! × 4!) = 5.040 ÷ (6 × 24) = 5.040 ÷ 144 = 35. Tương đương, tính nPr trước (7 × 6 × 5 = 210) rồi chia cho r! (3! = 6): 210 ÷ 6 = 35.
Tính nPr như thế nào?
Dùng công thức nPr = n! ÷ (n − r)!, rút gọn thành tích của r số nguyên liên tiếp giảm dần bắt đầu từ n. Với n = 7, r = 3: 7P3 = 7 × 6 × 5 = 210.
Khi nào nên cho phép lặp trong bài toán chỉnh hợp hoặc tổ hợp?
Cho phép lặp khi cùng một phần tử có thể được chọn nhiều lần trong một kết quả — ví dụ, các chữ số trong mã PIN, hay các vị kem khi khách có thể chọn cùng một vị cho nhiều viên. Không cho phép lặp khi mỗi phần tử chỉ được dùng một lần — ví dụ, chia các lá bài phân biệt, hay phân công những người khác nhau vào các vai trò.
nPr bằng bao nhiêu khi r bằng n?
Khi r = n (sắp xếp toàn bộ n phần tử, không lặp), nPr rút gọn thành n! ÷ (n − n)! = n! ÷ 0! = n! ÷ 1 = n!. Đây chính là tổng số cách sắp xếp toàn bộ n phần tử phân biệt thành một hàng — ví dụ, 5 phần tử có thể được sắp xếp đầy đủ theo 5! = 120 cách.
'Sao và vạch' nghĩa là gì đối với tổ hợp có lặp?
'Sao và vạch' (stars and bars) là kỹ thuật tổ hợp chuẩn để đếm các tổ hợp có lặp, cho ra công thức C(n + r − 1, r). Kỹ thuật này biểu diễn r phần tử được chọn thành các 'ngôi sao' ngăn cách bởi các 'vạch' đánh dấu ranh giới giữa n loại, rồi đếm số cách sắp xếp các ngôi sao và vạch. Với n = 7, r = 3: C(9, 3) = 84.
Tài liệu tham khảo
- Rosen KH. Discrete Mathematics and Its Applications. 8th ed. McGraw-Hill, 2018. (Permutations, combinations, and the stars-and-bars method.)
- NIST Digital Library of Mathematical Functions (DLMF), §26.1–26.3 Combinatorial Analysis. dlmf.nist.gov.
- Feller W. An Introduction to Probability Theory and Its Applications, Vol. 1. 3rd ed. Wiley, 1968. (Classic treatment of permutations and combinations.)