Bài 2: Hoán Vị, Chỉnh Hợp, Tổ Hợp - Hoc24

1. Hoán vị

a) Định nghĩa:

Cho tập hợp A có n \(\left(n\ge1\right)\) phần tử.

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 một hoán vị của \(n\) phần tử đó.

- Nhận xét: Hai hoán vị của \(n\) phần tử chỉ khác nhau ở thứ tự sắp xếp.

Chẳng hạn, hai hoán vị \(abc\) và \(acb\) của ba phần tử \(a,b,c\) là khác nhau.

b) Số các hoán vị:

Ví dụ 1: Có bao nhiêu cách sắp xếp 4 bạn An, Bình, Chi, Dung ngồi vào một bàn học gồm bốn chỗ ngồi?

Giải:

Mỗi cách sắp xếp bốn bạn vào một bàn bốn chỗ là một hoán vị của 4 phần tử. Ta tính số hoán vị bằng 2 cách như sau:

- Cách 1: Liệt kê: Để cho gọn, ta viết A, B, C, D thay cho tên bốn bạn: An, Bình, Chi, Dung. Ta có tất cả các cách sắp xếp là:

ABCD , ABDC, ACBD, ACDB, ADBC, ADCB

BACD, BADC, BCAD, BCDA, BDAC, BDCA

CABD, CADB, CBAD, CBDA, CDAB, CDBA

DABC. DACB, DBAC, DBCA, DCAB, DCBA

Có tất cả 24 cách.

- Cách 2: Sử dụng qui tắc nhân: Để chọn được một cách sắp xếp thì ta thực hiện liên tiếp 4 hành động sau:

+ Chọn người vào vị trí đầu tiên của bàn: Có 4 cách chọn (A, B, C, D)

+ Sau khi chọn người vào vị trí đầu, ta chọn tiếp người vào vị trí thứ hai: có 3 cách chọn (vì không chọn người đã ngồi vị trí thứ nhất)

+ Sau khi chọn hai người vào vị trí thứ nhất và thứ hai, ta chọn tiếp ngườ vào vị trí thứ ba: Có 2 cách chọn (vì không chọn lại hai người ở vị trí thứ nhất và vị trí thứ hai)

+ Sau khi chọn ba người vào ba vị trí đầu tiên, vị trí thứ tư chỉ còn 1 lựa chọn.

Vậy số cách chọn là: \(4.3.2.1=24\) cách.

Qua ví dụ trên, ta có công thức tính số hoạn vị của n phần tử như sau:

Định lí 1:

Số các hoán vị của một tập hợp có n phần tử, kí hiệu là \(P_n\):

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

Ví dụ 2: Một đoàn khách du lịch dự định tham quan bảy địa điểm \(A,B,C,D,E.G\) và \(H\) ở thủ đô Hà Nội. Họ đi thăm quan theo một thứ tự nào đó, chẳng hạn B→A→C→E→D→G→H.

Hỏi đoàn khách có bao nhiêu cách chọn thứ tự tham quan du lịch?

Giải:

Mỗi cách chọn thứ tự các địa điểm tham quan trên là một hoán vị của tập \(\left\{A,B,C,D,E,G,H\right\}\).

Do đó, đoàn khách có tất cả \(7!=5040\) cách chọn.

@27381@

2. Chỉnh hợp

a) Định nghĩa:

Cho tập hợp \(A\) gồm \(n\) phần tử (\(n\ge1\)) và số nguyên \(k\) với \(1\le k\le n\).

Kết quả của việc lấy \(k\) phần tử khác nhau 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.

- Nhận xét: Hai chỉnh hợp khác nhau khi và chi khi có một phần tử của chỉnh hợp này mà không phải của chỉnh hợp kia, hoặc phần tử của hai chỉnh hợp giống nhau nhưng được sắp xếp theo thứ tự khác nhau.

b) Ví dụ và cách tính số các chỉnh hợp:

Ví dụ 1: Một nhóm học tập có năm bạn \(A,B,C,D,E\). Hãy tính số cách phân công ba bạn làm trực nhật: một bạn quét nhà, một bạn lau bảng và một bạn sắp xếp bàn ghế?

Giải:

Ta kí hiệu \(ABC\) là một phân công trực nhật: \(A\) - quét nhà, \(B\) - lau bảng, \(C\) - sắp xếp bàn ghế.

Và như vậy: \(BAC\) là một phân công: \(B\) - quét nhà, \(A\) - lau bảng, \(C\) - sắp xếp bàn ghế.

Ta thấy \(ABC\) và \(BAC\) tuy cùng là ba bạn \(A,B,C\) nhưng đó là hai cách phân công khác nhau (vì khác nhau ở chỗ nhiệm vụ mỗi người khác nhau).

Như vậy mỗi một cách phân công là một chỉnh chập 3 của 5 phần tử.

Ta tính số cách phân công (hay số chỉnh hợp chập 3 của 5 phần tử) bằng hai cách sau:

- Cách 1: Liệt kê:

\(ABC\), \(ABD\), \(ABE\), \(ACB\), \(ACD\), \(ACE\), \(ADB\), \(ADC\), \(ADE\), \(AEB\), \(AEC\), \(AED\), \(BAC\), ....

Số cách là: 60 cách

- Cách 2: Sử dụng qui tắc nhân:

Mỗi cách phân công trực nhật là việc chọn liên tiếp 3 vị trí: quét nhà, lau bảng, sắp xếp bàn ghế.

+ Có 5 cách chọn người quét nhà

+ Khi đã chọn người quét nhà, có 4 cách chọn người lau bảng (phải trừ người quét nhà)

+ Khi đã chọn được người quét nhà và người lau bảng, có 3 cách chọn người sắp xếp bàn ghế (vì còn 3 bạn sau khi không tính hai người quét nhà và lau bảng)

Như vậy số cách phân công trực nhật là: 5 x 4 x 3 = 60 cách.

Qua ví dụ trên ta có cách tính số chỉnh hợp chập k của n phần tử như sau:

Định lí 2:

Số các chỉnh hợp chập k của một tập hợp có n phần tử, kí hiệu \(A_n^k\)\(\left(1\le k\le n\right)\) \(A_n^k=n.\left(n-1\right)\left(n-2\right)...\left(n-k+1\right)\) (1)

Chú ý: Với \(0< k< n\) , với quy ước \(0!=1\) thì ta có thể viết công thức (1) dưới dạng:

\(A_n^k=\dfrac{n!}{\left(n-k\right)!}\) (2)

Khi đó công thức (2) đúng cho cả \(k=0\) và \(k=n\). Vậy công thức (2) đúng với mọi số nguyên \(k\) thỏa mãn \(0\le k\le n\).

Nhận xét: Một chỉnh hợp chập n của n phần tử chính là một hoán vị của n phần tử.

Do vậy: \(A^n_n=P_n=n!\)

Ví dụ 2: Trong mặt phẳng cho một tập hợp gồm 6 điểm phân biệt. Có bao nhiêu vectơ khác vectơ có điểm đầu và điểm cuối thuộc tập hợp điểm này?

Giải:

Mỗi cặp sắp xếp thứ tự gồm hai điểm \(\left(A,B\right)\) cho ta một vectơ có điểm đầu \(A\), điểm cuối \(B\). Như vậy, mỗi vectơ có thể xem là một chỉnh hợp chập 2 của tập hợp 6 điểm đã cho. Vậy số vectơ cần tìm là:

\(A^2_6=6.5=30\) (vectơ)

Hay \(A^2_6=\dfrac{6!}{\left(6-2\right)!}=\dfrac{6!}{4!}=\dfrac{720}{24}=30\) (vectơ)

@38434@

3. Tổ hợp

a) Định nghĩa:Cho tập \(A\) có \(n\) phần tử \(\left(n\ge1\right)\) và số nguyên \(k\). Một tập con của \(A\) có \(k\) phần tử được 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à một 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\) (không quan tâm đến thứ tự).

Chú ý: Số \(k\) trong định nghĩa cần thoả mãn điều kiện \(1\le k\le n\). Tuy nhiên tập hợp không có phần tử nào là tập rỗng nên 1a quy ước gọi tổ hợp chập 0 của \(n\) phần tử là tập rỗng.

b) Ví dụ và cách tính số các tổ hợp:

Ví dụ 1: Trên mặt phẳn cho 4 điểm phân biệt \(A,B,C,D\) sao cho không có ba điểm nào thẳng hàng. Hỏi có thể tạo được bao nhiêu tam giác mà các đỉnh thuộc tập 4 điểm đã cho?

Giải:

Mỗi một tam giác ứng với tập có 3 đỉnh lấy ra từ tập 5 điểm đã cho (thứ tự các đỉnh không quan trọng, ví dụ các tam giác \(ABC\), \(ACB\), \(BAC\), \(BCA\), \(CAB\), \(CBA\) đều là một tam giác và chỉ đếm 1 lần). Hay nói cách mỗi tam giác là một tổ hợp chập 3 của 4 phần tử \(A,B,C,D\).

Ta tính số tổ hợp chập 3 của 4 phần tử bằng 2 cách sau:

- Cách 1: Liệt kê:

\(ABC\), \(ABD\), \(BCD\)

Như vậy có 3 tam giác.

- Cách 2: Tính theo số chỉnh hợp chập \(k\) của \(n\) phần tử:

Số chỉnh hợp chập \(k\) của \(n\) phần tử là: \(A_n^k=\dfrac{n!}{\left(n-k\right)!}\)

Tuy nhiên trong các chỉnh hợp chập \(k\), thứ tự các phần tử là quan trọng. Nếu thứ tự là không quan trong, thì số phần tử sẽ giảm đi (\(k!\)) lần.

Hay nói cách khác, so với số chỉnh hợp chập \(k\) thì số tổ hợp chập \(k\) chỉ tính mỗi tập con là 1 lần còn số chỉnh hợp phải tính \(k!\) lần tương ứng với số hoán vị của \(k\) phần tử.

Vậy số tổ hợp chập \(k\) của \(n\) phần từ bằng số chỉnh hợp chập \(k\) của \(n\) phần tử chia cho \(k!\).

Kí hiệu số tổ hợp chập \(k\) của \(n\) phần tử là \(C^k_n\) hoặc \(\left(\dfrac{n}{k}\right)\)thì ta có:

\(C_n^k=\dfrac{A^k_n}{k!}=\dfrac{n!}{k!\left(n-k\right)!}\)

Số các tổ hợp chập \(k\) của một tập hợp có n phần tử là

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

Ví dụ 2: Một tổ có 10 người gồm 6 nam và 4 nữ. Cần lập một đoàn đại biểu gồm 5 người. Hỏi

a) Có tất cả bao nhiêu cách lập?

b) Có bao nhiêu cách lập trong đó có 3 nam và 2 nữ?

Giải:

a) Mỗi cách lập là một tổ hợp chập 5 của 10 phần tử (vì 10 người). Số cách lập là:

\(C^5_{10}=\dfrac{10!}{5!\left(10-5\right)!}=252\) cách

b) Số cách lập đoàn 5 người trong đó có 3 nam và 2 nữ:

- Số cách chọn 3 nam từ 6 nam là: \(C^3_6\)

- Số cách chọn 2 nam từ 4 nữ là: \(C^2_4\)

Theo qui tắc nhân, số cách chọn 5 người trong đó có 3 nam và 2 nữ là: \(C^3_6.C^2_4=20.6=120\) cách.@27411@

4. Hai tính chất cơ bản của số \(C^k_n\)

a) Tính chất 1:

Cho số nguyên dương \(n\) và số nguyên \(k\) với \(0\le k\le n\). Khi đó:

\(C^k_n=C^{n-k}_n\)

Chẳng hạn: \(C^3_7=C^4_7=35\).

b) Tính chất 2 (hằng đẳng thức Pa-xcan):

Cho các số nguyên \(n\) và \(k\) với \(1\le k\le n\). Khi đó :

\(C^{k-1}_{n-1}+C^k_{n-1}=C^k_n\)

Chẳng hạn: \(C^3_7+C^4_7=C^4_8=70\)

Chú ý: Để phân biệt sự khác nhau giữa số chỉnh hợp với số tổ hợp, ta chỉ cần lưu ý đển nhận xét sau :

-Tổ hợp là cách chọn k phần tử trong n phần tử mà "không quan tâm" đến thứ tự sắp xếp

- Chỉnh hợp là cách chọn k phần tử trong n phần tử và "có quan tâm" đến thứ tự sắp xếp. Việc phân biệt lúc nào sử dụng số chỉnh hợp, lúc nào sử dụng số tổ hợp là rất quan trọng.

5. Vài tính chất quan trọng của số chỉnh hợp, số tổ hợp

Cho \(0\le k\le n\) với \(k,n\) là các số tự nhiên (trong đó \(n>0\)). Khi đó ta có :

1) \(C_n^k=\dfrac{A_n^k}{P_k}\)

2) \(C_n^k=C_n^n=1;A_n^0=1\)

3) \(C_n^k=C_n^{n-k}\)

4) \(C_n^k=C_{n-1}^k+C_{n-1}^{k-1}\), (đúng với mọi \(n\ge k\ge1\))

Ví dụ 1 : Tính giá trị biểu thức :

\(M=\dfrac{A_{n+1}^4+3A^3_n}{\left(n+1\right)!}\)

Nếu \(C_{n+1}^2+2C_{n+2}^2+2C_{n+3}^2+C_{n+4}^2=149\)

Giải:

Xét phương trình :

\(C_{n+1}^2+2C_{n+2}^2+2C_{n+3}^2+C_{n+4}^2=149\left(1\right)\)

Chú ý : khi \(n+1\ge2\) thì rõ ràng \(n+2>2;n+3>3;n+4>4\), vì thế điều kiện để (1) có nghĩa là \(n\in N\)*

Ta có :

(1) \(\Leftrightarrow\dfrac{\left(n+1\right)!}{\left(n-1\right)!2!}+2\dfrac{\left(n+2\right)!}{n!2!}+2\dfrac{\left(n+3\right)!}{\left(n+1\right)!2!}+\dfrac{\left(n+4\right)!}{\left(n+2\right)!2!}=149\)

\(\Leftrightarrow\dfrac{n\left(n+1\right)}{2}+\left(n+1\right)\left(n+2\right)+\left(n+2\right)\left(n+3\right)+\dfrac{\left(n+3\right)\left(n+4\right)}{2}=149\)

\(\Leftrightarrow n^2+4n+6+2n^2+8n+8=149\)

\(\Leftrightarrow3n^2+12n-135=0\)

\(\Leftrightarrow n^2+4n-45=0\)

\(\Leftrightarrow n=5\) hoặc \(n=-9\) (loại do \(n\ge1\))

Vậy \(M=\dfrac{A_6^4+3A_5^3}{6}=\dfrac{\dfrac{6!}{2!}+3\dfrac{5!}{2!}}{6!}=\dfrac{3}{4}\)

Ví dụ 2 : Cho tập hợp \(A\) gồm \(n\) phần tử (\(n\ge4\)). Biết rằng số tập hợp con gồm 4 phần tử bằng 20 lần số tập hợp con gồm 2 phần tử của A. Tìm \(n\) ?

Giải:

Số tập hợp con có 4 phần tử của A là \(C^4_n\)

Số tập hợp con có 4 phần tử của A là \(C^2_n\)

Theo bài ra ta có phương trình : \(C^4_n=20C^2_n\left(n\ge4\right)\)

\(\Leftrightarrow\dfrac{n!}{\left(n-4\right)!4!}=20\dfrac{n!}{\left(n-2\right)!2!}\)

\(\Leftrightarrow\dfrac{n\left(n-1\right)\left(n-2\right)\left(n-3\right)}{3.4}=20n\left(n-1\right)\)

\(\Leftrightarrow\left(n-2\right)\left(n-3\right)=240\)

\(\Leftrightarrow n^2-5n-234=0\)

\(\Leftrightarrow n=18\) hoặc \(n=-13\) (loại do \(n\ge4\))

Vậy tập hợp \(A\) có 18 phần tử

Ví dụ 3 : Cho đa giác đều \(A_1A_2....A_{2n};n\ge2\), (n là nguyên dương) nội tiếp đường tròn (O). Biết rằng số tam giác có 3 đỉnh trong 2n điểm \(A_1,A_2,....,A_{2n}\) gấp 20 lần số hình chữ nhật có 4 đỉnh trong 2n điểm \(A_1,A_2,....,A_{2n}\). Tìm \(n\) ?

Giải:

Số tam giác là \(C^3_{2n}\). Một đa giác đều \(2n\) đỉnh thì có \(n\) đường chéo xuyên tâm. Cứ hai đường chéo xuyên tâm có 1 chữ nhật theo yêu cầu. Vậy số hình chữ nhật là \(C^2_{2n}\).

Theo bài ta có phương trình :

\(C_{2n}^3=20C_n^2\left(n\ge2\right)\)

\(\Leftrightarrow\dfrac{\left(2n\right)!}{\left(2n-3\right)!3!}=20\dfrac{n!}{\left(n-2\right)!2!}\)

\(\Leftrightarrow\dfrac{\left(2n-2\right)\left(2n-1\right)2n}{3}=20\left(n-1\right)n\)

\(\Leftrightarrow2\left(n-1\right)\left(2n-1\right)2n=60\left(n-1\right)n\)

\(\Leftrightarrow2n-1=15\) (do \(n\ge2\))

\(\Leftrightarrow n=8\)

Vậy đa giác đều có 16 cạnh (thập lục giác đều).