Ba khái niệm khác nhau thế nào?
Cả ba đều nói về cách chọn/sắp xếp các phần tử từ một tập n phần tử. Chìa khóa phân biệt là hai câu hỏi: Lấy tất cả hay chỉ lấy k? và Thứ tự có quan trọng không? Trả lời được hai câu này là chọn đúng công thức.
Ba công thức
- Hoán vị P(n) = n! — sắp xếp cả n phần tử theo một thứ tự. Ví dụ xếp n bạn thành một hàng.
- Chỉnh hợp A(n, k) = n!/(n−k)! — chọn k trong n phần tử có để ý thứ tự. Ví dụ trao huy chương Vàng–Bạc–Đồng.
- Tổ hợp C(n, k) = n!/[k!·(n−k)!] — chọn k trong n phần tử không kể thứ tự. Ví dụ chọn một đội k người.
- Quan hệ: A(n, k) = C(n, k)·k!, nên C(n, k) = A(n, k)/k!.
Vì sao tổ hợp chia cho k!?
Khi đếm chỉnh hợp A(n, k), một nhóm k phần tử cụ thể được đếm nhiều lần — mỗi lần ứng với một cách sắp thứ tự k phần tử đó, tức k! lần. Tổ hợp không phân biệt thứ tự, nên ta chia A(n, k) cho k! để gộp tất cả các thứ tự của cùng một nhóm về một. Kết quả C(n, k) = A(n, k)/k! chính là số nhóm không kể thứ tự.
Ứng dụng thực tế
Đại số tổ hợp xuất hiện khi:
- 🎟️ Đếm số kết quả xổ số, mã PIN, mật khẩu.
- 🏅 Xếp giải thưởng, lập đội hình, chia nhóm.
- 🎲 Tính xác suất: số trường hợp thuận lợi trên tổng số trường hợp.
- 🧬 Sinh học, mật mã, mạng máy tính đếm số cấu hình khả dĩ.