Bài 24: Hoán vị, chỉnh hợp và tổ hợp
Tìm hiểu về ba khái niệm cơ bản của đại số tổ hợp: hoán vị, chỉnh hợp và tổ hợp, cùng các công thức tính và ứng dụng vào bài toán thực tế.
Lý thuyết
1. Hoán vị
Cho tập hợp $A$ gồm $n$ phần tử ($n \ge 1$). Mỗi kết quả của sự sắp xếp thứ tự $n$ phần tử của tập hợp $A$ được gọi là một hoán vị của $n$ phần tử đó.
Số các hoán vị của $n$ phần tử, kí hiệu là $P_n$, được tính bằng công thức:
$$P_n = n! = n(n-1)...2.1$$
Quy ước: $0! = 1$.
2. Chỉnh hợp
Cho tập hợp $A$ gồm $n$ phần tử ($n \ge 1$) và một số nguyên $k$ với $1 \le k \le n$. Mỗi kết quả của việc lấy ra $k$ phần tử từ $n$ phần tử của tập hợp $A$ và sắp xếp chúng theo một thứ tự nào đó được gọi là một chỉnh hợp chập $k$ của $n$ phần tử đã cho.
Số các chỉnh hợp chập $k$ của $n$ phần tử, kí hiệu là $A_n^k$, được tính bằng công thức:
$$A_n^k = \frac{n!}{(n-k)!} = n(n-1)...(n-k+1)$$
3. Tổ hợp
Cho tập hợp $A$ có $n$ phần tử ($n \ge 1$). Mỗi tập con gồm $k$ phần tử ($0 \le k \le n$) của $A$ được gọi là một tổ hợp chập $k$ của $n$ phần tử đã cho.
Số các tổ hợp chập $k$ của $n$ phần tử, kí hiệu là $C_n^k$, được tính bằng công thức:
$$C_n^k = \frac{n!}{k!(n-k)!} = \frac{A_n^k}{k!}$$
Tính chất của các số tổ hợp:
- $C_n^k = C_n^{n-k}$ ($0 \le k \le n$)
- $C_{n-1}^{k-1} + C_{n-1}^k = C_n^k$ ($1 \le k < n$) (Công thức Pascal)
Các dạng bài tập
Dạng 1: Dạng 1: Tính số hoán vị, chỉnh hợp, tổ hợp
Phương pháp giải:
Phương pháp giải
- Sử dụng trực tiếp các công thức tính $P_n, A_n^k, C_n^k$.
- Sử dụng máy tính cầm tay để tính toán nhanh các giá trị.
- Đối với các bài toán chứng minh hoặc rút gọn biểu thức, cần nắm vững các tính chất và công thức khai triển giai thừa.
Ví dụ:
Ta có:
- $P_3 = 3! = 3 \times 2 \times 1 = 6$.
- $A_5^2 = \frac{5!}{(5-2)!} = \frac{120}{6} = 20$.
- $C_6^4 = C_6^2 = \frac{6 \times 5}{2} = 15$.
Vậy $M = 6 + 20 - 15 = 11$.
Dạng 2: Dạng 2: Bài toán xếp hàng, chọn đội
Phương pháp giải:
Phương pháp giải
- Hoán vị: Dùng khi cần sắp xếp tất cả $n$ phần tử vào $n$ vị trí khác nhau.
- Chỉnh hợp: Dùng khi cần chọn ra $k$ phần tử từ $n$ phần tử và có sắp xếp thứ tự (ví dụ: bầu chức vụ, xếp vào vị trí khác nhau, lập số tự nhiên).
- Tổ hợp: Dùng khi chỉ cần chọn ra $k$ phần tử từ $n$ phần tử mà không quan tâm đến thứ tự sắp xếp (ví dụ: chọn một nhóm đi trực nhật, chọn tập con).
Ví dụ:
Vì mỗi người giữ một chức vụ khác nhau nên việc chọn ra 3 người và phân vào 3 chức vụ là một chỉnh hợp chập 3 của 40.
Số cách chọn là: $A_{40}^3 = 40 \times 39 \times 38 = 59.280$ cách.
Dạng 3: Dạng 3: Bài toán có điều kiện
Phương pháp giải:
Phương pháp giải
- Sử dụng quy tắc cộng, quy tắc nhân kết hợp với hoán vị, chỉnh hợp, tổ hợp.
- Đối với bài toán có điều kiện 'luôn đứng cạnh nhau': Ta coi nhóm phần tử đó là một phần tử 'siêu' và thực hiện hoán vị. Sau đó hoán vị nội bộ trong nhóm đó.
- Đối với bài toán có điều kiện 'không đứng cạnh nhau': Sử dụng phương pháp 'vách ngăn'.
Ví dụ:
Coi 2 học sinh nữ là một nhóm $X$.
Xếp nhóm $X$ và 3 học sinh nam (tổng cộng 4 đối tượng) vào hàng ngang: có $P_4 = 4! = 24$ cách.
Trong mỗi cách xếp đó, 2 học sinh nữ có thể đổi chỗ cho nhau: có $P_2 = 2! = 2$ cách.
Theo quy tắc nhân, số cách xếp thỏa mãn là: $24 \times 2 = 48$ cách.