Công cụ này làm được gì?
Đây là công cụ trả lời câu hỏi cốt lõi của tổ hợp học: có bao nhiêu cách để chọn hoặc sắp xếp một mẫu gồm r phần tử lấy ra từ một tập hợp gồm n đối tượng phân biệt? Công cụ bao quát cả 4 trường hợp chọn mẫu được xác định bởi hai câu hỏi có/không — thứ tự có quan trọng không, và có cho phép lặp lại không — cùng với các phép đếm độc lập: giai thừa, hoán vị chẵn, hoán vị lẻ và hoán vị vòng. Mọi kết quả đều là một con số đếm thuần (không thứ nguyên), nên không liên quan đến đơn vị hay chuyển đổi nào cả.
Bốn trường hợp chọn mẫu
Tổ hợp (không xét thứ tự, không lặp): $${}_nC_r = \dfrac{n!}{r!\,(n-r)!}$$ Chỉnh hợp (có xét thứ tự, không lặp): $${}_nP_r = \dfrac{n!}{(n-r)!}$$ Tổ hợp có lặp (không xét thứ tự, có lặp): $$CR(n,r) = C(n+r-1, r)$$ Chỉnh hợp có lặp (có xét thứ tự, có lặp): $$PR(n,r) = n^r$$ Với các trường hợp không lặp, nếu \(r\) lớn hơn \(n\) thì kết quả bằng 0, vì bạn không thể chọn nhiều phần tử hơn số phần tử đang có.
Các phép đếm độc lập
Giai thừa \(n! = n(n-1)\cdots 2 \cdot 1\), với quy ước \(0! = 1\). Hoán vị chẵn \(= n!/2\) khi \(n\) lớn hơn hoặc bằng 2 (đây chính là số phần tử của nhóm thay phiên). Hoán vị lẻ \(= n!/2\) khi \(n\) lớn hơn hoặc bằng 2, và bằng 0 trong các trường hợp còn lại. Hoán vị vòng \(= (n-1)!\), là số cách sắp xếp phân biệt \(n\) đối tượng quanh một vòng tròn, trong đó các phép quay được coi là giống nhau.
Cách sử dụng
Nhập cỡ tập hợp \(n\) và cỡ mẫu \(r\), chọn loại phép chọn, rồi đọc số cách thu được. Các chế độ không dùng đến \(r\) (giai thừa, hoán vị chẵn, hoán vị lẻ, hoán vị vòng) chỉ cần giá trị \(n\).
Ví dụ minh họa
Chọn 3 người thắng cuộc từ 10 thí sinh mà không xét thứ tự: chọn chế độ Tổ hợp với \(n = 10\), \(r = 3\). Kết quả là $$C(10,3) = \frac{10 \cdot 9 \cdot 8}{3 \cdot 2 \cdot 1} = \frac{720}{6} = 120.$$ Nếu thứ tự lại quan trọng (giải nhất, nhì, ba), hãy chuyển sang Chỉnh hợp và bạn sẽ có $$P(10,3) = 10 \cdot 9 \cdot 8 = 720.$$
Câu hỏi thường gặp
Khi nào dùng tổ hợp, khi nào dùng chỉnh hợp? Dùng tổ hợp khi thứ tự chọn không quan trọng (ví dụ chọn thành viên ban tổ chức), và dùng chỉnh hợp khi thứ tự có ý nghĩa (xếp hạng, mật khẩu).
"Có lặp lại" nghĩa là gì? Sau khi chọn một phần tử, bạn trả nó lại vào tập hợp, nên phần tử đó có thể được chọn lại — hữu ích trong các bài toán lấy mẫu có lặp.
Vì sao kết quả rất lớn có thể bị sai số? Số cách tăng nhanh theo giai thừa và có thể vượt quá phạm vi biểu diễn chính xác của số dấu phẩy động; với \(n\) và \(r\) cực lớn, hãy xem con số hiển thị là một giá trị xấp xỉ gần đúng.
