Bài 24: Hoán vị, chỉnh hợp và tổ hợp

1. HOÁN VỊ

Một hoán vị của một tập hợp có \(n\) phần tử là một cách sắp xếp có thứ tự \(n\) phần tử đó (với \(n\) là một số tự nhiên, \(n\ge1\)).

Số các hoán vị của tập hợp có \(n\) phần tử kí hiệu là \(P_n\), được tính bằng công thức

\(P_n=n.\left(n-1\right).\left(n-2\right)...2.1.\)

Chú ý: Kí hiệu \(n.\left(n-1\right).\left(n-2\right)...2.1\) là \(n!\) ( đọc là \(n\) giai thừa). Ta có \(P_n=n!.\)

Ví dụ. Từ các chữ số \(1,2,3,4,5,6\) có thể lập được bao nhiêu số có \(6\) chữ số khác nhau.

Giải

Mỗi cách sắp xếp sáu chữ số đã cho để lập thành một số có sáu chữ số khác nhau là một hoán vị của sáu chữ số đó.

Vậy số các số có bốn chữ số khác nhau có thể lập được là \(P_6=6!=720.\)

2. CHỈNH HỢP

Một chỉnh hợp chập \(k\) của \(n\) là một cách sắp xếp có thứ tự \(k\) phần tử từ một tập hợp \(n\) phần tử (với \(k,n\) là các số tự nhiên, \(1\le k\le n\)).

Số các chỉnh hợp chập \(k\) của \(n\), kí hiệu là \(A_n^k\), được tính bằng công thức:

\(A_n^k=n.\left(n-1\right)...\left(n-k+1\right)\) hay \(A_n^k=\dfrac{n!}{\left(n-k\right)!}\left(1\le k\le n\right).\)

Ví dụ. Từ các chữ số \(1,2,3,4,5,6\) có thể lập được bao nhiêu số tự nhiên có 3 chữ số khác nhau?

Giải

Mỗi cách chọn \(3\) chữ số trong \(6\) chữ số đã cho để lập thành một số tự nhiên có \(3\) chữ số khác nhau là một chỉnh hợp chập \(3\) của \(6\), vậy số các số tự nhiên có ba chữ số khác nhau có thể lập được là \(A^3_6=120.\)

3. TỔ HỢP

Một tổ hợp chập \(k\) của \(n\) là một cách chọn \(k\) phần tử từ một tập hợp \(n\) phần tử (với \(k,n\) là các số tự nhiên, \(0\le k\le n\)).

Số các tổ hợp chập \(k\) của \(n\), kí hiệu là \(C_n^k\), được tính bằng công thức:

  \(C_n^k=\dfrac{n!}{\left(n-k\right)!k!}\left(0\le k\le n\right).\)

Chú ý:

 \(C_n^k=\dfrac{A_n^k}{k!}\);

Chỉnh hợp và tổ hợp có điểm giống nhau là đều chọn một số phần tử trong một tập hợp nhưng khác nhau ở chỗ, chỉnh hợp là chọn có xếp thứ tự, còn tổ hợp là chọn không xếp thứ tự. 

Ví dụ. Cần phân công \(4\) bạn từ một tổ có \(12\) bạn để làm trực nhật. Hỏi có bao nhiêu cách phân công khác nhau?

Giải

Kết quả của sự phân công là một nhóm gồm bốn bạn, tức là một tổ hợp chập \(4\) của \(12\), vậy số cách phân công là \(C^4_{12}=495\) cách.

4. ỨNG DỤNG HOÁN VỊ, CHỈNH HỢP, TỔ HỢP VÀO BÀI TOÁN ĐẾM.

Ví dụ. Có bao nhiêu cách sắp xếp chỗ ngồi cho \(10\) bạn, trong đó có An và Bình vào \(10\) ghế hàng ngang sao cho:

a) An và Bình ngồi cạnh nhau.

b) An và Bình không ngồi cạnh nhau.

Giải

a) Có \(2.9=18\) cách xếp An và Bình ngồi cạnh nhau, \(8\) bạn kia xếp vào \(8\) chỗ còn lại có \(8!\) cách xếp.

Vậy có \(18.8!\) cách xếp chỗ thỏa mãn.

b) Có \(10!\) cách xếp chỗ ngồi cho \(10\) bạn, vậy có \(10!-18.8!=72.8!\) cách xếp chỗ cho \(10\) bạn mà An và Bình không ngồi cạnh nhau.