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

VẤN ĐỀ 2. HOÁN VỊ - CHỈNH HỢP - TỔ HỢP

A. Kiến thức cần nhớ

1. Hoán vị

Cho tập hợp A có n phần tử. Khi sắp xếp n phần tử này theo một thứ tự ta được một hoán vị của tập A. Số các hoán vị của một tập hợp có n phần tử là n!.

2. Chỉnh hợp

Cho tập hợp A gồm n phần tử và k là một số nguyên dương với 1 $\leq$ k $\leq$ n. Khi lấy ra một tập con gồm 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 tập hợp A (gọi tắt là một chỉnh hợp chập k của A)

Số chỉnh hợp chập k của một tập hợp n phần tử, kí hiệu là $A_{n}^{k}$, được cho bởi công thức

$A_{n}^{k}$ = n(n - 1)...(n - k + 1). Quy ước $A_{n}^{0}$ = 1

3. Tổ hợp

Cho tập A có n phần tử và số tự nhiên k với 0 $\leq$ k $\leq$ n. 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 A.

Số tổ hợp chập k của một tập hợp có n phần tử, kí hiệu là $C_{n}^{k}$, được cho bởi công thức

B. Giải bài tập sách giáo khoa

Bài 1

Từ các chữ số 1, 2, 3, 4, 5, 6, lập các số tự nhiên gồm sáu chữ số khác nhau. Hỏi:

a) Có tất cả bao nhiêu số?

b) Có bao nhiêu số chẵn, bao nhiêu số lẻ?

c) Có bao nhiêu số bé hơn 432000?

Giải

a) Mỗi số gồm sáu chữ số khác nhau được đồng nhất với một hoán vị của sáu chữ số 1, 2,..., 6. Vậy có 6! số.

b) Để tạo nên một số chẵn, ta cần chọn chữ số hàng đơn vị là số chẵn. Có 3 cách chọn

5 chữ số còn lại (sau khi đã chọn chữ số hàng đơn vị được sắp theo thứ tự sẽ tạo nên một hoán vị của 5 phần tử). Có 5! cách chọn.

Vậy theo quy tắc nhân có

3.5! = 360

số các số chẵn có sáu chữ số tạo nên từ sáu chữ số 1, 2, 3, 4, 5, 6

Tương tự, số các số lẻ có sáu chữ số tạo nên từ sáu chữ số 1, 2, 3, 4, 5, 6 cũng là 360.

c) Các số trong câu a) bé hơn 432000 bao gồm:

* Các số có chữ số hàng trăm nghìn nhỏ hơn 4

- Có 3 cách chọn chữ số hàng trăm nghìn, đó là các chữ số 1, 2, 3.

- Sau khi đã chọn chữ số hàng trăm nghìn, ta phải chọn tiếp năm chữ số còn lại và sắp thứ tự chúng để ghép với chữ số hàng trăm nghìn tạo thành số có sáu chữ số. Mỗi một lần chọn là một hoán vị của 5 phần tử (5 chữ số). Có 5! cách chọn.

Vậy theo quy tắc nhân, các số có chữ số hàng trăm nghìn nhỏ hơn 4 là

3.5! = 360 (số).

* Các số có chữ hàng trăm nghìn là 4 và chữ số hàng chục nghìn nhỏ hơn 3.

- Có 2 cách chọn chữ số hàng chục nghìn, đó là các chữ số 1, 2

- Sau khi đã chọn chữ số hàng chục nghìn phải chọn tiếp bốn chữ số nữa và sắp thứ tự chúng để ghép với hai chữ số hàng trăm nghìn và hàng chục nghìn tạo thành số có sáu chữ số. Có 4! cách chọn.

Vậy theo quy tắc nhân có tất cả

2.4! = 48 số như vậy.

* Các số có chữ số hàng trăm nghìn là 4, hàng chục nghìn là 3, hàng nghìn là 1 (nhỏ hơn 2)

Vậy có 1. 3! = 6 (số).

Từ đó theo quy tắc cộng, số các số trong câu a) bé hơn 432000 là

360 + 48 + 6 = 414 (số).

Bài 2

Có bao nhiêu cách sắp xếp chỗ ngồi cho mười người khách vào mười ghế kê thành một dãy

Giải

Mỗi cách sắp xếp chỗ ngồi của 10 người khách theo hàng ngang cho một hoán vị của 10 và ngược lại.

Vậy có 10! cách sắp xếp.

Bài 3

Giả sử có bảy bông hoa màu khác nhau và ba cái lọ khác nhau. Hỏi có bao nhiêu cách cắm ba bông hoa vào ba cái lọ đã cho (mỗi lọ cắm một bông)?

Giải

Vì bảy bông hoa màu khác nhau và ba lọ cắm hoa khác nhau nên mỗi lần chọn ra ba bông hoa để cắm vào ba lọ, ta có một chỉnh hợp chập 3 của 7 phần tử. Vậy số cách cắm hoa bằng số các chỉnh hợp chập 3 của 7 (bông hoa).

Do đó, kết quả cần tìm là

$A_{7}^{3}$ = $\large \frac{7!}{4!}$ = 210.

Bài 4

Có bao nhiêu cách mắc nối tiếp 4 bóng đèn được chọn từ 6 bóng đèn khác nhau?

Giải

Kết quả cần tìm là:

Có $A_{6}^{4}$ = $\large \frac{6!}{(6-4)!}$ = 360 cách mắc nối tiếp 4 bóng đèn chọn từ 6 bóng.

Bài 5

Có bao nhiêu cách cắm 3 bông hoa vào 5 cái lọ khác nhau (mỗi lọ cắm không quá 1 bông) nếu:

a) Các bông hoa khác nhau?

b) Các bông hoa như nhau?

Giải

a) Đánh số 3 bông hoa 1, 2, 3. Chọn 3 trong 5 lọ để cắm hoa. Mỗi cách cắm là một chỉnh hợp chập 3 của 5. Vậy số cách cắm là

$A_{5}^{3}$ = 5.4.3 = 60 (cách).

b) Nếu các bông hoa là như nhau thì mỗi cách cắm là một tổ hợp chập 3 của 5 (lọ). Vậy số cách cắm là

$C_{5}^{3}$ = $\large \frac{5.4.3}{3!}$ = 10 (cách).

Bài 6

Trong mặt phẳng, cho sáu điểm phân biệt sao cho không có ba điểm nào thẳng hàng. Hỏi có thể lập được bao nhiêu tam giác mà các đỉnh của nó thuộc tập điểm đã cho?

Giải

Số tam giác bằng số các tổ hợp chập 3 của 6 điểm. Từ đó, ta có số tam giác là $C_{6}^{3}$ = 20.

Bài 7

Trong mặt phẳng có bao nhiêu hình chữ nhật được tạo thành từ bốn đường thẳng song song với nhau và năm đường thẳng vuông góc với bốn đường thẳng song song đó?

Giải

Để tạo một hình chữ nhật từ chín đường thẳng đã cho, ta tiến hành hai hành động:

- Hành động 1: Chọn hai đường thẳng từ bốn đường thẳng song song. Vì các đường thẳng đã cố định nên mỗi lần chọn cho ta một tổ hợp chập 2 của 4 phần tử (đường thẳng). Vậy có $C_{4}^{2}$ cách.

- Hành động 2: Chọn hai trong năm đường thẳng vuông góc với bốn đường thẳng song song với nhau. Tương tự, ta có $C_{5}^{2}$ cách.

Từ đó theo quy tắc nhân, ta có số hình chữ nhật là

$C_{4}^{2}$.$C_{5}^{2}$ = 60 (hình chữ nhật).

C. Bài tập bổ sung

Bài 1

Một tổ gồm 8 nam và 6 nữ. Cần lấy một nhóm 5 người trong đó có 2 nữ. Hỏi có bao nhiêu cách chọn?

Giải

Việc lấy một nhóm 5 người trong đó có 2 nữ và 3 nam có thể chia làm hai giai đoạn:

- Giai đoạn 1: chọn 2 nữ trong số 6 nữ. Mỗi cách chọn là một tổ hợp chập 2 của 6 phần tử, do đó số cách chọn 2 nữ là $C_{6}^{2}$.

- Giai đoạn 2: chọn 3 nam trong số 8 nam, số cách chọn là $C_{8}^{3}$.

Vậy có tất cả $C_{6}^{2}$.$C_{8}^{3}$ = 15.56 = 840 cách chọn ra một nhóm gồm 5 người trong đó có 2 nữ.

Bài 2

Cho hai đường thẳng song song ($d_{1}$), ($d_{2}$). Trên ($d_{1}$) lấy 17 điểm phân biệt, trên ($d_{2}$) lấy 20 điểm phân biệt. Tính số tam giác có các đỉnh là 3 điểm trong số 37 điểm đã chọn trên ($d_{1}$) và ($d_{2}$).

Giải

Các tam giác có 3 đỉnh là 3 điểm trong số 37 điểm đã chọn thuộc một trong hai loại sau đây:

- Loại 1: Một đỉnh nằm trên ($d_{1}$) và 2 đỉnh nằm trên ($d_{2}$) có 17 cách chọn một đỉnh trên ($d_{1}$). Với một cách chọn một đỉnh trên ($d_{1}$) luôn luôn có $C_{20}^{2}$ cách chọn 2 đỉnh trên ($d_{2}$). Vậy có 17.$C_{20}^{2}$ tam giác loại 1.

- Loại 2: Một đỉnh nằm trên ($d_{2}$) và 2 đỉnh nằm trên ($d_{1}$). Lập luận tương tự như trên ta có 20.$C_{17}^{2}$ tam giác loại 2. Vậy tổng cộng có tất cả:

17.$C_{20}^{2}$ + 20.$C_{17}^{2}$ = 3230 + 2720 = 5950 tam giác thỏa mãn yêu cầu bài toán.

Bài 3

Cho mười chữ số 0, 1,..., 9. Có bao nhiêu số lẻ có 6 chữ số khác nhau, nhỏ hơn 600000 xây dựng từ 10 chữ số đã cho?

Giải

Kí hiệu A = {0, 1, 2, 3,..., 9}.

Số phải tìm có dạng x = $\overline{a_{1}a_{2}a_{3}a_{4}a_{5}a_{6}}$

Vì x < 600000 nên $a_{1}$ $\in$ B = {1, 2, 3, 4, 5}. Chúng ta xét hai trường hợp:

- TH1: $a_{1}$ $\in$ {2, 4}. Đương nhiên, có hai cách chọn $a_{1}$. Với mỗi cách chọn $a_{1}$ luôn luôn có 5 cách chọn $a_{6}$ vì $a_{6}$ $\in$ C = {1, 3, 5, 7, 9}. Khi đã chọn các số $a_{1}$ và $a_{6}$ thì mỗi cách chọn $a_{2}a_{3}a_{4}a_{5}$ là một chỉnh hợp chập 4 của 8 phần tử thuộc tập A \ {$a_{1}$, $a_{6}$}. Do đó có $A_{8}^{4}$ cách chọn $a_{2}a_{3}a_{4}a_{5}$. Vậy có 2.5.$A_{8}^{4}$ số x mà $a_{1}$ $\in$ {2, 4}.

- TH2: $a_{1}$ $\in$ {1, 3, 5}. Lúc này có 3 cách chọn $a_{1}$, do $a_{1}$ là số lẻ nên với mỗi cách chọn $a_{1}$ ta chỉ có 4 cách chọn $a_{6}$ ($a_{6}$ $\in$ C \ {$a_{1}$}).

Với mỗi cách chọn $a_{1}$ và $a_{6}$ ta cũng có $A_{8}^{4}$ cách chọn $a_{2}a_{3}a_{4}a_{5}$. Do đó có 3.4.$A_{8}^{4}$ số x mà $a_{1}$ $\in$ {1, 3, 5}.

Tổng cộng có 2.5.$A_{8}^{4}$ + 3.4.$A_{8}^{4}$ = 36960 số lẻ có 6 chữ số khác nhau từng đôi, nhỏ hơn 600000.

Bài 4

Từ một tập thể gồm 12 học sinh ưu tú, người ta cần cử một đoàn đi dự trại hè quốc tế trong đó có 1 trưởng đoàn, 1 phó đoàn và 3 đoàn viên. Hỏi có bao nhiêu cách cử?

Giải

Từ 12 học sinh cử ra một nhóm gồm 5 người: có $C_{12}^{5}$ cách.

Với mỗi cách cử ra một nhóm 5 người có $A_{5}^{2}$ cách cử trưởng đoàn và phó đoàn.

Vậy có $C_{12}^{5}$.$A_{5}^{2}$ = 15 840 cách cử đoàn gồm một trưởng đoàn, một phó đoàn và một đoàn viên.

Bài 5

Có bao nhiêu số tự nhiên khác nhau, nhỏ hơn 10000 được tạo thành từ 5 chữ số 0; 1; 2; 3; 4?

Giải

Số nhỏ hơn 10000 là số có dạng: $\overline{a_{1}a_{2}a_{3}a_{4}}$ trong đó $a_{1}$, $a_{2}$, $a_{3}$, $a_{4}$ $\in$ {0, 1, 2, 3, 4}.

Có 5 cách chọn $a_{1}$.

Với mỗi cách chọn $a_{1}$ có 5 cách chọn $a_{2}$.

Với mỗi cách chọn $a_{2}$ có 5 cách chọn $a_{3}$.

Với mỗi cách chọn $a_{1}a_{2}a_{3}$ có 5 cách chọn $a_{4}$.

Với 5.5.5.5 = 625 số thỏa mãn yêu cầu bài toán.

Bài 6

Cho tập hợp A = {1, 2, 3, 4, 5, 6, 7, 8}. Có bao nhiêu tập hợp con X của tập A thỏa điều kiện chứa 1 và không chứa 2?

Giải

Mỗi tập con X của tập A chứa 1 và không chứa 2 có dạng:

X = {1} $\cup$ Y trong đó Y là tập con của tập B = {3, 4, 5, 6, 7, 8}. Do đó số các tập con X thỏa yêu cầu bài toán bằng số các tập con Y của B. Mà tập B có 6 phần tử nên B có $2^{6}$ = 64 tập con. Vậy có 64 tập con X của A chứa 1 và không chứa 2.

Bài 7

Một học sinh có 12 cuốn sách đôi một khác nhau, trong đó có 2 cuốn sách môn Toán, 4 cuốn sách môn Văn và 6 cuốn sách môn Anh văn. Hỏi có bao nhiêu cách xếp tất cả các cuốn sách lên một kệ sách dài, nếu mọi cuốn sách cùng môn được xếp kề nhau?

Giải

Trước hết, đặt 3 nhóm sách (Toán, Văn, Anh văn) lên kệ dài có 3! cách. Trong mỗi nhóm sách ta có thể thay đổi cách xếp đặt sách.

- Nhóm sách Toán có 2! cách xếp.

- Nhóm sách Văn có 4! cách xếp.

- Nhóm sách Anh văn có 6! cách xếp.

Vậy có 3!2!4!6! = 6.2.24.720 = 207360 cách.

Bài 8

Có bao nhiêu số có 6 chữ số được chọn từ các chữ số thuộc {1, 2, 3, 4, 5, 6, 7, 8} sao cho các chữ số đôi một khác nhau, chữ số đầu tiên phải là số 4 và chữ số cuối cùng phải là số chẵn?

Giải

Ta tìm các số dạng $\overline{4a_{1}a_{2}a_{3}a_{4}a_{5}}$

Có 3 cách chọn $a_{5}$ vì $a_{5}$ $\in$ {2, 6, 8}.

Có $A_{6}^{4}$ cách chọn $a_{1}a_{2}a_{3}a_{4}$ vì mỗi cách chọn $a_{1}a_{2}a_{3}a_{4}$ ứng với một chỉnh hợp chập 4 của 6 phần tử thuộc {1, 2, 3, 4, 5, 6, 7, 8} \ {$a_{5}$}.

Vậy có 3. $A_{6}^{4}$ = 3.6.5.4.3 = 1080 số thỏa yêu cầu bài toán.

Bài 9

Một đội văn nghệ có 20 người, trong đó có 10 nam và 10 nữ. Hỏi có bao nhiêu cách chọn ra 5 người sao cho

a) Có đúng 2 nam trong 5 người đó.

b) Có ít nhất 2 nam và ít nhất 1 nữ trong 5 người đó.

Giải

a) • Số cách chọn 2 nam từ 10 nam là $C_{10}^{2}$ (cách)

• Số cách chọn 3 nữ từ 10 nữ là $C_{10}^{3}$ (cách)

Do đó số cách chọn theo yêu cầu bài toán là $C_{10}^{2}$.$C_{10}^{3}$ = 5400 (cách)

b) • Số cách chọn 5 người trong 20 người là $C_{20}^{5}$

• Các trường hợp không thỏa mãn yêu cầu bài toán là:

- Không có nam nào, chọn 5 nữ trong số 10 nữ: có $C_{10}^{5}$ (cách)

- Chọn 1 nam và 4 nữ: có $C_{10}^{1}$.$C_{10}^{4}$ (cách).

- Không có nữ nào, chọn 5 nam trong số 10 nam: $C_{10}^{5}$ (cách).

Vậy số cách cử thỏa mãn yêu cầu bài toán là

$C_{20}^{5}$ - (2$C_{10}^{5}$ + $C_{10}^{1}$.$C_{10}^{4}$) = 15504 - (504 + 2100) = 12900 cách

Bài 10

Có bao nhiêu số gồm 7 chữ số khác nhau đôi một được lập bằng cách dùng 7 chữ số 1, 2, 3, 4, 5, 7, 9 sao cho hai chữ số chẵn không liền nhau?

Giải

- Số các số có 7 chữ số khác nhau đôi một được lập bằng cách dùng 7 chữ số đã cho là 7! (số)

- Số các số có 7 chữ số khác nhau từng đôi mà hai chữ số chẵn 2, 4 đứng kề nhau là 2.6!

Do đó số các số có 7 chữ số khác nhau từng đôi (lấy từ các chữ số đã cho) sao cho 2 số chẵn không đứng kề nhau là

7! - 2.6! = (7 - 2).6! = 3600.

D. Bài tập đề nghị

Bài 1

Cho tập hợp A = {1, 2, 3, 5, 7, 9}.

a) Có bao nhiêu số tự nhiên gồm có 4 chữ số đôi một khác nhau?

b) Bao nhiêu số tự nhiên chẵn gồm có 5 chữ số đôi một khác nhau?

Bài 2

Cho tập hợp A = {0, 1, 2, 3, 4, 5, 6, 7, 8}

a) Từ tập hợp A có thể lập được bao nhiêu số tự nhiên gồm có 5 chữ số đôi một khác nhau và các số này lẻ chia hết cho 5.

b) Từ tập hợp A có thể lập được bao nhiêu số tự nhiên gồm có 6 chữ số đôi một khác nhau sao cho chữ số đứng cuối chia hết cho 4.

Bài 3

Cho tập hợp A = {0, 1, 2, 3, 4, 5, 6}.

a) Từ tập A có thể lập được bao nhiêu số tự nhiên có sáu chữ số đôi một khác nhau sao cho các số này không bắt đầu bằng 246.

b) Từ tập A có thể lập được bao nhiêu số tự nhiên có năm chữ số đôi một khác nhau sao cho chữ số 1 có mặt đúng một lần.

Bài 4

Có bao nhiêu số tự nhiên có năm chữ số trong đó các chữ số cách đều số đứng giữa thì giống nhau.

Bài 5

Một tổ học sinh gồm 9 học sinh nam và 3 học sinh nữ. Giáo viên chọn 4 học sinh để đi trực thư viện. Có bao nhiêu cách chọn nếu

a) Chọn học sinh nào cũng được.

b) Trong đó có đúng một nữ sinh được chọn.

c) Trong đó có ít nhất một nữ sinh được chọn.

Bài 6

Một đoàn tàu có bốn toa đỗ sân ga. Có bốn hành khách bước lên tàu. Hỏi

a) Có bao nhiêu trường hợp có thể xảy ra

b) Có bao nhiêu trường hợp mà mỗi toa có một người lên.

c) Có bao nhiêu trường hợp mà một toa có ba người lên, một toa có một người lên và hai toa còn lại không có ai lên.

Bài 7

Có bao nhiêu số tự nhiên lẻ trong khoảng (2000, 3000) có thể tạo nên bằng các chữ số 1, 2, 3, 4, 5, 6 nếu

a) Các chữ số không nhất thiết khác nhau.

b) Các chữ số của nó khác nhau.

Bài 8

Có bao nhiêu số có ba chữ số được tạo thành từ các chữ số 2, 3, 4, 5, 6 nếu

a) Các chữ số này không nhất thiết khác nhau.

b) Các chữ số này khác nhau.

c) Các chữ số này hoàn toàn như nhau.

Bài 9

Có bao nhiêu số tự nhiên lớn hơn 4000 có bốn chữ số được tạo thành từ các chữ số 1, 3, 5, 7 nếu

a) Các chữ số này không nhất thiết khác nhau.

b) Các chữ số này khác nhau.

Bài 10

Một tập hợp có 100 phần tử. Hỏi nó có bao nhiêu tập con có nhiều hơn 2 phần tử?

Bài 11

Một tổ bộ môn của một trường có 10 giáo viên nam và 15 giáo viên nữ. Có bao nhiêu cách thành lập một hội đồng gồm 6 ủy viên của tổ bộ môn, trong đó số ủy viên nam ít hơn số ủy viên nữ?

Bài 12

Có bao nhiêu số tự nhiên gồm năm chữ số, biết rằng hai chữ số đứng kề nhau phải khác nhau?

Bài 13

Có bao nhiêu cách sắp xếp chỗ cho 6 người khách ngồi quanh một bàn tròn (Hai cách sắp xếp được xem là như nhau nếu cách này nhận được từ cách kia bằng cách xoay bàn đi một góc nào đó).

Bài 14

Cho năm chữ số 1, 2, 3, 4, 5. Hãy tính số các số tự nhiên

a) Có 5 chữ số đôi một khác nhau và bắt đầu bởi chữ số khác chữ số 1.

b) Có 5 chữ số đôi một khác nhau và bắt đầu bởi 24.

c) Có 5 chữ số đôi một khác nhau và không bắt đầu bởi 241.