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

Chương VIII. Đại số tổ hợp

1. Hoán vị

Tình huống mở đầu Đội tuyển bóng đá có 23 cầu thủ (3 thủ môn, 7 hậu vệ, 8 tiền vệ, 5 tiền đạo) đá theo sơ đồ 3 – 4 – 3 (3 hậu vệ, 4 tiền vệ, 3 tiền đạo, 1 thủ môn). Nếu đối thủ đã đoán trước vị trí thủ môn thì họ phải xét bao nhiêu đội hình có thể?

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ử đó

(n \geq 1)

.
Số các hoán vị của tập hợp có

n

phần tử, kí hiệu

P_{n} : P_{n} = n \cdot (n - 1) \cdot (n - 2) \cdot

··

2 \cdot 1 = n!

(đọc n! là

n

giai thừa; ví dụ

P_{3} = 3! = 6

.) Quy ước $0! = 1$ .

Ví dụ 1 Từ các chữ số 6, 7, 8, 9 lập được

P_{4} = 4! = 24

số có bốn chữ số khác nhau. (Xếp bốn bạn thành một hàng:

4 \cdot 3 \cdot 2 \cdot 1

cách.)

2. Chỉnh hợp

Chỉnh hợp chập

k

của

n

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ử

(1 \leq k \leq n)

.
Số các chỉnh hợp chập

k

của

n

, kí hiệu

A_{n}^{k}

A_{n}^{k} = n \cdot (n - 1) \cdot

··

(n - k + 1) = \frac{n !}{( n - k )!} (1 \leq k \leq n)

.
Để tính, dùng quy tắc nhân (chọn lần lượt từng phần tử).

Chú ý Hoán vị sắp xếp tất cả các phần tử; chỉnh hợp chọn ra một số phần tử và sắp xếp chúng. Mỗi hoán vị của

n

phần tử là một chỉnh hợp chập

n

của

n : P_{n} = A_{n}^{n}

Ví dụ 2 Lớp có 30 học sinh, chọn lần lượt 4 học sinh trồng bốn cây khác nhau:

A_{30}^{4} = 657720

cách. Chọn hai bạn làm nhóm trưởng, nhóm phó từ bốn bạn: chỉnh hợp chập 2 của

4 (4 \cdot 3 = 12

cách).

3. Tổ hợp

Tổ hợp chập

k

của

n

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ử (không xếp thứ tự;

0 \leq k \leq n

).
Số các tổ hợp chập

k

của

n

, kí hiệu

C_{n}^{k}

C_{n}^{k} = \frac{n !}{( n - k )! \cdot k !} (0 \leq k \leq n)

Chú ý – phân biệt chỉnh hợp và tổ hợp

$C_{n}^{k} = \frac{A _{n}^{k}}{k !}$ (không cần xếp thứ tự nên số cách giảm đi $k!$ lần).
Chỉnh hợp và tổ hợp đều chọn một số phần tử của một tập hợp; chỉnh hợp có xếp thứ tự, tổ hợp không xếp thứ tự.

Ví dụ 3 Chọn 4 bạn trong 7 bạn chơi cờ cá ngựa:

C_{7}^{4} = \frac{7 !}{4 ! \cdot 3 !} = 35

cách.

4. Ứng dụng vào các bài toán đếm

Ví dụ 4 – lịch trình tham quan Anh Hưng đi tham quan 5 địa điểm (Đền Hùng, Ninh Bình, Hạ Long, Sơn Tây, Bát Tràng), mỗi ngày một nơi.
a) Xếp lịch trình cả 5 địa điểm:

P_{5} = 5! = 120

cách.
b) Chỉ có 3 ngày để đi 3 địa điểm: chỉnh hợp chập 3 của

5 : A_{5}^{3} = \frac{5 !}{2 !} = 60

cách.

Ví dụ 5 – giải bài toán mở đầu (đội hình) Đã biết vị trí thủ môn, chọn đội hình qua 3 công đoạn: chọn 3 hậu vệ trong

7 : C_{7}^{3} = 35

; chọn 4 tiền vệ trong

8 : C_{8}^{4} = 70

; chọn 3 tiền đạo trong

5 : C_{5}^{3} = 10

. Theo quy tắc nhân:

35 \cdot 70 \cdot 10 =

24 500 đội hình.

Vận dụng (câu lạc bộ 20 học sinh) a) Chọn 6 thành viên vào Ban quản lí:

C_{20}^{6}

; b) chọn Trưởng ban, 1 Phó ban, 4 thành viên khác: chọn có thứ tự hai vị trí đầu rồi chọn tổ hợp bốn thành viên còn lại. (Sách chỉ nêu đề; người biên soạn tính: a) 38 760 cách; b) $20 \cdot 19 \cdot C_{18}^{4} = 1162800$ cách.)

5. Sử dụng máy tính cầm tay

Các phím

Hoán vị $n!$ : nhập $n$ , bấm SHIFT, $x!$ , rồi “=”. Ví dụ $9! = 362880$ .
Chỉnh hợp $A_{n}^{k}$ : nhập $n$ , bấm SHIFT, nPr (phím $\times$ ), nhập $k$ , “=”. Ví dụ $A_{15}^{2} = 210$ .
Tổ hợp $C_{n}^{k}$ : nhập $n$ , bấm SHIFT, nCr (phím $\div$ ), nhập $k$ , “=”. Ví dụ $C_{20}^{5} = 15504$ .

Em có biết Leonardo Fibonacci (thế kỉ XIII) là người đầu tiên đưa các bài toán tổ hợp vào châu Âu, giới thiệu dãy số Fibonacci

F_{0} = 0, F_{1} = 1, F_{n + 1} = F_{n} + F_{n - 1}

. Bằng lập luận tổ hợp chứng minh được số cách xếp hình chữ nhật

1 \times n

từ hai loại gạch

1 \times 1

và

1 \times 2

chính là

F_{n + 1}

. Về lí thuyết, một ván cờ vua có tối đa 5 950 nước đi (sách nêu).

Mô phỏng tương tác: hoán vị, chỉnh hợp, tổ hợp

Duyệt lần lượt từng cách sắp xếp, từng cách chọn để thấy số hoán vị, chỉnh hợp, tổ hợp và mối liên hệ giữa chúng.

Mô phỏngLiệt kê hoán vị, chỉnh hợp và tổ hợp

Mở ở trang riêng ↗