Câu trả lời ngắn gọn
Sự sắp xếp số hoán vị trong đó thứ tự quan trọng (P(n,r) = n! ÷ (n−r)!); các kết hợp đếm các lựa chọn trong đó thứ tự không (C(n,r) = n! ÷ (r!(n−r)!)). Chọn bục đua 3 vị trí trong số 10 vận động viên chạy là một hoán vị - P(10,3) = 720 thứ tự khác nhau. Chọn một ủy ban gồm 3 người từ 10 người giống nhau là một sự kết hợp - C(10,3) = 120, vì các thành viên trong ủy ban không quan tâm đến trật tự.
Bài học chính
- Các kết hợp luôn nhỏ hơn (hoặc bằng) hoán vị phù hợp, vì C(n,r) = P(n,r) `r! — chia ra mọi cách để sắp xếp lại cùng một nhóm.
- C(n,r) = C(n, n−r) — việc chọn r mục nào để đưa vào tương đương với việc chọn n−r mục nào cần loại bỏ.
- Khi r = n, cả hai đều giảm xuống việc đếm tất cả n mục: P(n,n) = n! và C(n,n) = 1.
- Giai thừa tăng cực kỳ nhanh, do đó P(n,r) và C(n,r) có thể trở nên lớn về mặt thiên văn ngay cả đối với các giá trị khiêm tốn của n và r.
Công thức hoán vị và tổ hợp
| Ý tưởng | Công thức | Vấn đề đặt hàng? |
|---|---|---|
| Hoán vị | P(n,r) = n! / (n−r)! | Đúng |
| Sự kết hợp | C(n,r) = n! / (r!(n−r)!) | KHÔNG |
Ví dụ hoạt động: thứ tự cuộc đua so với lựa chọn ủy ban
Với 10 vận động viên (n=10), chọn 3 (r=3):
P(10,3) = 10 × 9 × 8 = 720 (thứ tự vàng/bạc/đồng)
C(10,3) = 720 3! = 720 6 = 120 (ủy ban 3 người)
Mỗi nhóm 3 người chạy tương ứng với 3! = 6 thứ tự bục khác nhau (người nhận vàng, bạc, đồng), đó chính xác là lý do tại sao số lượng hoán vị (720) gấp 6 lần số lượng kết hợp (120).
Quy tắc đối xứng cho sự kết hợp
C(8,2) = C(8,6) = 28
Việc chọn 2 trong số 8 người để đưa vào một nhóm sẽ tạo ra số lượng giống hệt như việc chọn 6 người để loại trừ - đó là hai cách mô tả cùng một sự phân chia. Sự đối xứng này, C(n,r) = C(n, n−r), có thể tiết kiệm công sức tính toán: nếu r lớn hơn một nửa n, thì thay vào đó, việc tính C(n, n−r) thường nhanh hơn.
Những lỗi thường gặp cần tránh
- Sử dụng công thức hoán vị khi thứ tự thực sự không quan trọng - điều này làm tăng số đếm thực sự lên hệ số r!.
- Quên rằng r không thể vượt quá n - không có cách nào để sắp xếp hoặc chọn nhiều mục hơn số mục tồn tại trong nhóm.
- Confusing the standard (no-repetition) formulas with "with repetition" versions, which apply to different problems, like a 4-digit PIN where digits can repeat.
- Mất dấu r trong các vấn đề lựa chọn nhiều giai đoạn - quên giảm nhóm còn lại sau mỗi giai đoạn đã được chọn.
Máy tính liên quan
- Máy tính xác suất — biến một hoán vị hoặc số kết hợp thành một xác suất thực tế.
- Máy tính số lớn — xử lý các giai thừa khổng lồ mà các giá trị n và r lớn có thể tạo ra.
- Máy tính ký hiệu khoa học — thể hiện kết quả hoán vị hoặc tổ hợp rất lớn một cách cô đọng.
- Máy tính thống kê — áp dụng kết quả đếm để phân tích thống kê rộng hơn.