Bài 23. Quy tắc đếm

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

1. Quy tắc cộng và sơ đồ hình cây

Tình huống mở đầu Mỗi mật khẩu của một trang web là một dãy có từ 2 tới 3 kí tự, kí tự đầu tiên là một trong 26 chữ cái in thường (

a

–z), mỗi kí tự còn lại là một chữ số từ 0 đến 9. Hỏi tạo được bao nhiêu mật khẩu khác nhau?

Quy tắc cộng Giả sử một công việc có thể thực hiện theo một trong hai phương án khác nhau:

Phương án một có $n_{1}$ cách thực hiện;
Phương án hai có $n_{2}$ cách thực hiện (không trùng với bất kì cách nào của phương án một).

Khi đó số cách thực hiện công việc là

n_{1} + n_{2}

cách.
Chú ý: áp dụng khi các phương án phải rời nhau, không phụ thuộc vào nhau.

Sơ đồ hình cây Sơ đồ minh hoạ cách phân chia trường hợp gọi là sơ đồ hình cây; dùng để đếm thuận tiện và không bỏ sót trường hợp.

Ví dụ 1, 2 Từ Hà Nội vào Nghệ An: 7 chuyến tàu hoả, 2 chuyến máy bay

\Rightarrow 7 + 2 = 9

cách chọn chuyến đi. Quán sáng có 2 loại phở và 3 loại bún

\Rightarrow 2 + 3 = 5

cách chọn một món.
Bộ cờ vua 32 quân: lấy tất cả quân tốt

= 8

tốt trắng + 8 tốt đen

= 16

quân. Lấy tất cả quân trắng và tất cả quân tốt:

16 + 16 - 8 = 24

quân (vì 8 tốt trắng đã đếm hai lần).
Nhận xét: nếu

A

là tập các quân trắng,

B

là tập các quân tốt thì

A \cap B \neq = \emptyset

nên không áp dụng được quy tắc cộng

n (A \cup B) = n (A) + n (B)

(sẽ sai, ra 32).

2. Quy tắc nhân

Quy tắc nhân Giả sử một công việc phải hoàn thành qua hai công đoạn liên tiếp:

Công đoạn một có $m_{1}$ cách thực hiện;
Với mỗi cách thực hiện công đoạn một, có $m_{2}$ cách thực hiện công đoạn hai.

Khi đó số cách thực hiện công việc là

m_{1} \cdot m_{2}

cách.
Chú ý: áp dụng cho công việc có nhiều công đoạn nối tiếp nhau và các công đoạn này độc lập với nhau.

Ví dụ 3 và hai hoạt động HĐ3, HĐ4 (kết quả HĐ do người biên soạn tính) Mua vé tàu ngồi Hà Nội – Vinh: có 3 chuyến (SE5, SE7, SE35), mỗi tàu 2 loại vé (ngồi cứng, ngồi mềm)

\Rightarrow 3 \cdot 2 = 6

loại vé. (Cũng có thể dùng quy tắc cộng:

2 + 2 + 2 = 6

.)
Từ Hà Nội vào Huế có 3 cách đi, từ Huế vào Đà Nẵng có 2 cách

\Rightarrow 3 \cdot 2 = 6

cách chọn phương tiện. Nhãn ghế “chữ cái in hoa + số từ 1 đến 20”:

26 \cdot 20 = 520

ghế.

3. Kết hợp quy tắc cộng và quy tắc nhân

Phân biệt khi nào dùng quy tắc nào

Quy tắc cộng: công việc chia thành các phương án phân biệt (chỉ cần thực hiện một trong các phương án).
Quy tắc nhân: công việc có nhiều công đoạn nối tiếp (phải thực hiện tất cả các công đoạn).
Hầu hết bài toán đếm thực tế phải dùng cả hai quy tắc.

Ví dụ 4 – chọn thực đơn Thực đơn gồm một món khai vị (2 loại súp, 3 loại sa lát), một món chính (4 thịt, 3 cá, 3 tôm), một món tráng miệng (5 kem, 3 bánh). Ba công đoạn: khai vị

2 + 3 = 5

cách; món chính

4 + 3 + 3 = 10

cách; tráng miệng

5 + 3 = 8

cách. Số thực đơn:

5 \cdot 10 \cdot 8 =

400.

Ví dụ 5 – giải bài toán mở đầu (mật khẩu)

Mật khẩu 2 kí tự: $26 \cdot 10 = 260$ cách.
Mật khẩu 3 kí tự: $26 \cdot 1 0^{2} = 2600$ cách.
Hai trường hợp rời nhau nên theo quy tắc cộng: $260 + 2600 =$ 2 860 mật khẩu.

Vận dụng Khối lớp 10 gồm 10A (30 bạn), 10B (35 bạn), 10C (32 bạn); chọn 4 bạn thành lập đội cờ đỏ sao cho có đại diện đủ các lớp. (Sách chỉ nêu đề, không in đáp số.)

Mô phỏng tương tác: quy tắc đếm

Vẽ sơ đồ hình cây theo quy tắc cộng, quy tắc nhân; bấm vào từng ngọn để xem một cách thực hiện công việc, thử với các ví dụ trong SGK.

Mô phỏngSơ đồ hình cây – quy tắc cộng và quy tắc nhân

Mở ở trang riêng ↗

Bài 23. Quy tắc đếm

1. Quy tắc cộng và sơ đồ hình cây

2. Quy tắc nhân

3. Kết hợp quy tắc cộng và quy tắc nhân

Mô phỏng tương tác: quy tắc đếm

Sơ đồ tư duy