Hoán vị, Chỉnh hợp, Tổ hợp

**NguoiDien** · 08-31-2009, 10:30 AM

HOÁN VỊ - TỔ HỢP - CHỈNH HỢP

1. Hoán Vị:

a. Ví dụ: Ba vận động viên An, Bình và Châu chạy thi. Nếu không kể trường hợp có hai hay ba vận động viên cùng về đích một lúc thì mọi khả năng đều có khả năng xảy ra.

Kết quả cuộc thi là một danh sách gồm $3$ người xếp theo thứ tự nhất, nhì, ba. Danh sách này là một Hoán vị của tập hợp {An, Bình, Châu}. Nếu kí hiệu tập hợp {An, Bình, Châu} là {a,b,c} thì tập hợp này có tất cả 6 Hoán vị là (a,b,c),(a,c,b),(b,a,c),(b,c,a),(c,a,b),(c,b,a).

Một cách tổng quát ta có:

Cho tập hợp $A$ có $n$ phần tử ( $n >0$ ). Khi sắp xếp $n$ phần tử này theo một thứ tự, ta được một Hoán vị các phần tử của tập $A$ .

b. Số các Hoán vị:

Định lí 1: Số các Hoán vị của một tập hợp có $n$ phần tử là: $P_{n}=n!=n(n-1)....2.1$

Ví dụ: Một đoàn khách du lịch dự định đến tham quan $7$ điểm du lịch $A,B,C,D,E,G$ và $H$ ở Hà Nội. Họ đi tham quan theo thứ tự nào đó, chẳng hạn

$A\rightarrow B\rightarrow C\rightarrow D\rightarrow E\rightarrow G\rightarrow H$ . Như vậy mỗi cách họ chọn thứ tự tham quan là một Hoán vị của tập ${A,B,C,D,E,G,H}$ . Do vậy đoàn khách có tất cả $7!=5040$ cách chọn.

2. Chỉnh hợp:

a. Ví dụ: Trong trận chung kết bóng đá phải phân định thắng thua bằng đá luân lưu $11m$ . Huấn luyện viên của mỗi đội cần trình với trọng tài một danh sách sắp thứ tự $5$ cầu thủ trong số $11$ cầu thủ của đội để tham gia đá.

Mỗi danh sách có xếp thứ tự $5$ cầu thủ được gọi là một chỉnh hợp chập [/I] $5$ của $11$ cầu thủ

Một cách tổng quát:

Cho tập $A$ gồm $n$ phần tử và số nguyên $k$ , $1\le k \le n$ . Khi lấy ra $k$ phần tử của $A$ và sắp xếp chúng theo một thứ tự ta được một Chỉnh hợp chập $k$ của $n$ phần tử của $A$ .

Nhận xét: Hai Chỉnh hợp khác nhau khi và chỉ khi hoặc có ít nhất một phần tử của Chỉnh hợp này không là phần tử của Chỉnh hợp kia hoặc các phần tử của $2$ Chỉnh hợp giống nhau nhưng được sắp xếp theo thứ tự khác nhau.

b. Số các Chỉnh hợp:

Xét ví dụ trên, ta tính xem có bao nhiều cách huấn luyện viên lập danh sách $5$ cầu thủ?

Giải: Ta có thể chọn $1$ trong $11$ cầu thủ để đá quả đầu tiên. Tiếp theo có $10$ cách chọn cầu thủ đá quả thứ hai, rồi $9$ cách chọn cầu thủ đá quả thứ ba, $8$ cách chọn cầu thủ đá quả thứ tư và cuối cùng có $7$ cách chọn cầu thủ đá quả thứ năm. Theo quy tắc nhân, mỗi đội sẽ có: $11.10.9.8.7 =55440$ cách chọn.

Định lí:

Số các Chỉnh hợp chập $k$ của một tập hợp có $n$ phần tử ( $1\leq k\leq n$ ) là:

$A_{n}^{k}=n.(n-1).(n-2)......(n-k+1)=\frac{n!}{(n-k)!\qquad (1)$

với quy ước $0!=1$

Ta quy ước: $A_{n}^{0}=1$ , do đó công thức $(1)$ đúng với mọi số nguyên $k$ thỏa mãn $0\leq k\leq n$

Chú ý: Một Hoán vị của một tập $n$ phần tử chính là một Chỉnh hợp chập $n$ của $n$ phần tử đó nên: $A_{n}^{n}=P_{n}=n!$

3. Tổ hợp:

Cho tập A có n phần tử vàsố nguyên $k$ với $1\leq k\leq n$ . Mỗi tập con của $A$ có $k$ phần tử gọi là một Tổ hợp chập $k$ của $n$ phần tử của $A$ ( gọi tắt là Tổ hợp chập $k$ của $A$ )

Như vậy, lập một Tổ hợp chập $k$ của $A$ chính là lấy ra $k$ phần tử của $A$ mà không quan tâm đến thứ tự.

Số các Tổ hợp:

[B]Định lí: Số các Tổ hợp chập $k$ của một tập hợp có $n$ phần tử ( $1\leq k\leq n$ ) là:

$C_{n}^{k}=\frac{A_{n}^{k}}{k!}=\frac{n!}{k!(n-k)!}\qquad (2)$

Với quy ước: $C_{n}^{0}=1$ thì $(2)$ cũng sẽ đúng với mọi số nguyên $k$ thỏa mãn $0\leq k\leq n$

Ví dụ: Trong $1$ lớp học có $20$ học sinh nam và $15$ học sinh nữ. Thầy giáo cần $4$ học sinh nam và $3$ học sinh nữ đi tham gia lao động. Hỏi có bao nhiêu cách?

Giải:

Ta có:

$C_{20}^{4}=\frac{20.19.18.17}{1.2.3.4}=4845$

cách chọn $4$ học sinh nam trong số $20$ học sinh nam và có

$C_{15}^{3}=\frac{15.14.13}{1.2.3}=455$

cách chọn $3$ HS nữ trong số $15$ HS nữ.

Theo quy tắc nhân, số cách chọn cần tìm là:

$4845.455=2204475$ cách chọn

4. Hai tính chất cơ bản của $C_{n}^{k}$ :

Tính chất 1: Cho các số nguyên $n,k$ thỏa mãn $0\leq k\leq n$ .

Khi đó:

$C_{n}^{k}=C_{n}^{n-k}$

Tính chất 2: Cho các số nguyên $n,k$ thỏa mãn $1\leq k\leq n$ .

Khi đó:

$C_{n+1}^{k}=C_{n}^{k}+C_{n}^{k-1}$