Bài 2. Hoán vị, chỉnh hợp và tổ hợp
Chương 8. Đại số tổ hợp
1. Hoán vị
Cho tập hợp A có 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ự gọi là một hoán vị các phần tử đó (gọi tắt là hoán vị của A hay của n phần tử).
Kí hiệu Pn là số hoán vị của n phần tử.
Pn = n(n - 1)(n - 2)…2 .1. (n ≥ 1)
Chú ý:
• Kí hiệu n! = n(n - 1)(n - 2)…2 .1 đọc là n giai thừa hoặc giai thừa của n. Khi đó, Pn = n!.
• Quy ước: 0! = 1.
Ví dụ
Một nhóm bạn gồm sáu thành viên cùng đi xem phim, đã mua sáu vé có ghế ngồi cùng dãy và kế tiếp nhau (như Hình 3). Có bao nhiêu cách sắp xếp chỗ ngồi cho các thành viên của nhóm?
Giải
Mỗi cách sắp xếp chỗ ngồi cho 6 thành viên vào 6 ghế là một hoán vị của 6 thành viên. Vậy số cách sắp xếp chỗ ngồi cho 6 thành viên của nhóm là:
P6 = 6! = 6.5.4.3.2.1 = 720 (cách).
2. Chỉnh hợp
Cho tập hợp A có n phần tử (n ≥ 1) và số nguyên k với 1 ≤ k ≤ n.
Mỗi cách lấy k phần tử của A và sắp xếp chúng theo một thứ tự gọi là một chỉnh hợp chập k của n phần tử đó.
Kí hiệu ${\color{Blue}A_n^k}$ là số chỉnh hợp chập k của n phần tử.
$A_n^k=n(n-1)(n-2)…(n-k+1)=\frac{n!}{(n-k)!}$.
Nhận xét: Mỗi hoán vị của n phần tử cũng chính là chỉnh hợp chập n của n phần tử đó.
Ta có Pn = $A_n^n$ , n ≥ 1.
Ví dụ
Từ bảy chữ số 1; 2; 3; 4; 5; 6; 7, lập các số có ba chữ số đôi một khác nhau.
a) Có thể lập được bao nhiêu số như vậy?
b) Trong các số đó có bao nhiêu số lẻ?
Giải
a) Việc chọn ra 3 chữ số trong 7 chữ số đã cho và lập thành một số có ba chữ số đôi một khác nhau là một chỉnh hợp chập 3 của 7.
Vậy ta lập được $A_7^3$ = 7.6.5 = 210 số có ba chữ số đôi một khác nhau.
b) Gọi số có ba chữ số là $\overline{abc}$ với a, b, c ∈ { 1; 2; 3; 4; 5; 6; 7 }.
Để $\overline{abc}$ là số lẻ thì c ∈ { 1; 3; 5; 7} nên ta có 4 cách chọn c.
Để a, b, c đôi một khác nhau thì b ∈ { 1; 2; 3; 4; 5; 6; 7 } \ { c }, ta có 6 cách chọn b,
a ∈ { 1; 2; 3; 4; 5; 6; 7 } \ { c ; b }, ta có 5 cách chọn a.
Vậy theo quy tắc nhân ta có 4.6.5 = 120 số lẻ có ba chữ số đôi một khác nhau.
3. Tổ hợp
Cho tập hợp A có n phần tử (n ≥ 1).
Mỗi tập con gồm k phần tử (1 ≤ k ≤ n) của A được gọi là một tổ hợp chập k của n phần tử.
Kí hiệu ${\color{Blue}C_n^k}$ là số tổ hợp chập k của n phần tử.
$C_n^k=\frac{n!}{k!(n-k)!}$.
Quy ước ${\color{Blue}C_n^0=1}$.
Nhận xét: Ta có hệ thức ${\color{Blue}C_n^k=C_n^{n-k}}$ (0 ≤ k ≤ n).
Ví dụ
Nội dung thi đấu đôi nam nữ của giải bóng bàn cấp trường có 7 đội tham gia. Các đội thi đấu vòng tròn một lượt.
a) Nội dung này có tất cả bao nhiêu trận đấu?
b) Sau giải đấu, ba đội có thành tích tốt nhất sẽ được chọn đi thi đấu liên trường. Có bao nhiêu khả năng có thể xảy ra về ba đội được chọn đi thi đấu cấp liên trường?
Giải
a) Mỗi trận đấu vòng tròn một lượt là là một cách chọn ra 2 đội trong 7 đội. Do đó số trận đấu là số tổ hợp chập 2 của 7, ta có
$C_7^2=\frac{7!}{2!.(7-2)!}$ = 21 (trận đấu).
b)Chọn ra ba đội có thành tích tốt nhất đi thi đấu cấp liên trường là tổ hợp chập 3 của 7 nên ta có $C_7^3=\frac{7!}{3!.(7-3)!}$ = 35 khả năng có thể xảy ra về ba đội được chọn đi thi đấu cấp liên trường.
Xem thêm các bài học khác :