Tổ hợp, chỉnh hợp, hoán vị
Tài liệu học tập: Tổ hợp, Chỉnh hợp, Hoán vị - Chọn và Sắp xếp
1. Các khái niệm cơ bản
1.1. Hoán vị
Định nghĩa: Cho tập hợp A gồm n phần tử (n ≥ 1). Mỗi cách sắp xếp n phần tử của A theo một thứ tự được gọi là một hoán vị của n phần tử.
Số lượng hoán vị: Số các hoán vị của n phần tử, kí hiệu P<sub>n</sub>, được tính bởi công thức:
P<sub>n</sub> = n! = n × ( n - 1 ) × ( n - 2 ) × ... × 2 × 1
Ví dụ:
- Cho tập A = { 1, 2, 3 }. Các hoán vị của A là: (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1). Vậy P<sub>3</sub> = 3! = 6.
1.2. Chỉnh hợp
Định nghĩa: Cho tập hợp A gồm n phần tử (n ≥ 1). Chỉnh hợp chập k của n (1 ≤ k ≤ n) là một cách chọn k phần tử từ n phần tử của A và sắp xếp chúng theo một thứ tự.
Số lượng chỉnh hợp: Số các chỉnh hợp chập k của n phần tử, kí hiệu A<sup>k</sup><sub>n</sub>, được tính bởi công thức:
A<sup>k</sup><sub>n</sub> = (\frac{n!}{(n-k)!}) = n × (n - 1) × ... × (n - k + 1)
Ví dụ:
- Cho tập A = { 1, 2, 3, 4 }. Các chỉnh hợp chập 2 của 4 là: (1, 2), (1, 3), (1, 4), (2, 1), (2, 3), (2, 4), (3, 1), (3, 2), (3, 4), (4, 1), (4, 2), (4, 3). Vậy A<sup>2</sup><sub>4</sub> = (\frac{4!}{(4-2)!}) = (\frac{4!}{2!}) = 12.
1.3. Tổ hợp
Định nghĩa: Cho tập hợp A gồm n phần tử (n ≥ 1). Tổ hợp chập k của n (0 ≤ k ≤ n) là một cách chọn k phần tử từ n phần tử của A, không quan tâm đến thứ tự.
Số lượng tổ hợp: Số các tổ hợp chập k của n phần tử, kí hiệu C<sup>k</sup><sub>n</sub> hoặc (\binom{n}{k}), được tính bởi công thức:
C<sup>k</sup><sub>n</sub> = (\binom{n}{k}) = (\frac{n!}{k!(n-k)!}) = (\frac{A^k_n}{k!})
Ví dụ:
- Cho tập A = { 1, 2, 3, 4 }. Các tổ hợp chập 2 của 4 là: {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}. Vậy C<sup>2</sup><sub>4</sub> = (\frac{4!}{2!(4-2)!}) = (\frac{4!}{2!2!}) = 6.
Tính chất của tổ hợp:
- C<sup>0</sup><sub>n</sub> = C<sup>n</sup><sub>n</sub> = 1
- C<sup>1</sup><sub>n</sub> = n
- C<sup>k</sup><sub>n</sub> = C<sup>n-k</sup><sub>n</sub> (0 ≤ k ≤ n)
- C<sup>k</sup><sub>n</sub> + C<sup>k+1</sup><sub>n</sub> = C<sup>k+1</sup><sub>n+1</sub> (0 ≤ k < n)
2. Phân biệt và ứng dụng
2.1. Bảng so sánh Hoán vị, Chỉnh hợp, Tổ hợp
| Tính chất | Hoán vị (P<sub>n</sub>) | Chỉnh hợp (A<sup>k</sup><sub>n</sub>) | Tổ hợp (C<sup>k</sup><sub>n</sub>) |
|---|---|---|---|
| Định nghĩa | Sắp xếp n phần tử | Chọn k phần tử từ n, sắp xếp | Chọn k phần tử từ n, không sắp xếp |
| Thứ tự | Quan trọng | Quan trọng | Không quan trọng |
| Số lượng | n! | (\frac{n!}{(n-k)!}) | (\frac{n!}{k!(n-k)!}) |
| Điều kiện | 1 ≤ k ≤ n | 0 ≤ k ≤ n | |
| Ví dụ | Sắp xếp học sinh vào bàn | Chọn ban cán sự lớp (có chức vụ) | Chọn đội tuyển thể thao (không chức vụ) |
2.2. Các dạng bài tập thường gặp
Dạng 1: Bài toán đếm số cách thực hiện một công việc
- Xác định công việc cần thực hiện gồm các giai đoạn nào.
- Tính số cách thực hiện mỗi giai đoạn.
- Áp dụng quy tắc cộng hoặc quy tắc nhân để tính số cách thực hiện công việc.
Dạng 2: Bài toán liên quan đến Hoán vị
- Khi một bài toán yêu cầu sắp xếp tất cả các phần tử của một tập hợp, ta sử dụng hoán vị.
Dạng 3: Bài toán liên quan đến Chỉnh hợp
- Khi một bài toán yêu cầu chọn một số phần tử từ một tập hợp và sắp xếp chúng theo thứ tự, ta sử dụng chỉnh hợp.
Dạng 4: Bài toán liên quan đến Tổ hợp
- Khi một bài toán yêu cầu chọn một số phần tử từ một tập hợp mà không quan tâm đến thứ tự, ta sử dụng tổ hợp.
2.3. Ví dụ minh họa
Ví dụ 1 (Hoán vị): Có bao nhiêu cách xếp 5 quyển sách khác nhau lên một giá sách?
Giải:
- Đây là bài toán sắp xếp 5 quyển sách, nên ta sử dụng hoán vị.
- Số cách xếp là P<sub>5</sub> = 5! = 120 cách.
Ví dụ 2 (Chỉnh hợp): Một lớp có 30 học sinh. Cần chọn ra 3 bạn để bầu vào ban cán sự lớp (lớp trưởng, lớp phó, bí thư). Hỏi có bao nhiêu cách chọn?
Giải:
- Đây là bài toán chọn 3 bạn từ 30 bạn và sắp xếp theo thứ tự chức vụ, nên ta sử dụng chỉnh hợp.
- Số cách chọn là A<sup>3</sup><sub>30</sub> = (\frac{30!}{(30-3)!}) = (\frac{30!}{27!}) = 30 × 29 × 28 = 24360 cách.
Ví dụ 3 (Tổ hợp): Một tổ có 10 học sinh. Cần chọn ra 3 bạn để tham gia đội tuyển của trường. Hỏi có bao nhiêu cách chọn?
Giải:
- Đây là bài toán chọn 3 bạn từ 10 bạn, không quan tâm đến thứ tự, nên ta sử dụng tổ hợp.
- Số cách chọn là C<sup>3</sup><sub>10</sub> = (\frac{10!}{3!(10-3)!}) = (\frac{10!}{3!7!}) = (\frac{10 × 9 × 8}{3 × 2 × 1}) = 120 cách.
Ví dụ 4 (Bài toán tổng hợp): Một đội văn nghệ có 8 người, cần chọn ra 5 người để biểu diễn, trong đó có 1 người hát, 2 người múa và 2 người chơi nhạc cụ. Hỏi có bao nhiêu cách chọn?
Giải:
- Giai đoạn 1: Chọn 1 người hát từ 8 người: C<sup>1</sup><sub>8</sub> = 8 cách.
- Giai đoạn 2: Chọn 2 người múa từ 7 người còn lại: C<sup>2</sup><sub>7</sub> = 21 cách.
- Giai đoạn 3: Chọn 2 người chơi nhạc cụ từ 5 người còn lại: C<sup>2</sup><sub>5</sub> = 10 cách.
- Theo quy tắc nhân, số cách chọn là: 8 × 21 × 10 = 1680 cách.
3. Bài tập tự luyện
- Có bao nhiêu cách sắp xếp 7 người vào một hàng ghế?
- Từ 5 chữ số 1, 2, 3, 4, 5 có thể lập được bao nhiêu số có 3 chữ số khác nhau?
- Một hộp có 12 quả bóng, trong đó có 5 quả màu đỏ. Lấy ngẫu nhiên 3 quả bóng. Hỏi có bao nhiêu cách lấy được ít nhất 2 quả bóng màu đỏ?
- Một lớp học có 25 học sinh, trong đó có 15 học sinh nam và 10 học sinh nữ. Cần chọn ra một đội gồm 5 học sinh, sao cho có ít nhất 2 học sinh nữ. Hỏi có bao nhiêu cách chọn?
- Từ các chữ số 0, 1, 2, 3, 4, 5 có thể lập được bao nhiêu số tự nhiên chẵn có 4 chữ số khác nhau?
4. Lời khuyên
- Nắm vững định nghĩa và công thức của hoán vị, chỉnh hợp, tổ hợp.
- Phân biệt rõ sự khác nhau giữa hoán vị, chỉnh hợp và tổ hợp.
- Luyện tập nhiều bài tập để làm quen với các dạng bài khác nhau.
- Khi giải bài, cần đọc kỹ đề bài, xác định rõ yêu cầu và phân tích bài toán.
- Vận dụng linh hoạt các công thức và quy tắc để giải bài toán.