Lý thuyết quy tắc đếm

Lý thuyết quy tắc đếm

Đóng vai trò quan trọng trong Đại số tổ hợp và trong nhiều ứng dụng

A. Tóm tắt kiến thức:

Đóng vai trò quan trọng trong Đại số tổ hợp và trong nhiều ứng dụng của nó là quy tắc cộng và quy tắc nhân. Trong thực hành ứng dụng, hai quy tắc này thường được phát biều như sau:

1. Quy tắc cộng:

Giả sử để hoàn thành một công việc, phải thực hiện một hành động trong (k) hành động loại trừ nhau từng đôi một và giả sử  có:

(n_1) cách để thực hiện hành động thứ nhất,

(n_2) cách để thực hiện hành động thứ hai,

…

(n_k) cách để thực hiện hành động thứ (k).

Khi đó ta có: Số cách để hoàn thành công việc kể trên là (n_1) + (n_2) + ...+ (n_k).

2. Quy tắc nhân:

2.1 Quy tắc nhân:

Giả sử để hoàn thành một công việc, phải thực hiện liên tiếp (k) hành động (sau khi kết thúc hành động này thì thực hiện tiếp hành động khác) và giả sử có:

(n_1) cách để thực hiện hành động thứ nhất,

 (n_2)ách để thực hiện hành động thứ hai,

…

(n_k) cách để thực hiện hành động thứ (k).

Khi đó ta có: Số cách để hoàn thành công việc kể trên là (n_1) . (n_2) ... (n_k) .

2.2 Chú ý:

Khi vận dụng quy tắc nhân, nên thực hiện theo những lời khuyền sau đây:

a) Nếu có hành động nào đặc biệt hơn các hành động khác thì nên thực hiện hành động khác thì thực hiện hành động nào trước cũng được.

b) Khi có nhiều hành động đặc biệt cần thực hiện trước, thì nên lựa chọn thứ tự thực hiện những hành động này để tìm ra được lời giải đơn giản nhất có thể được.

Nếu không thực hiện theo những lời khuyên ở trên thì vẫn giải được, nhưng lời giải sẽ phức tạp hơn và do đó sẽ khó hiểu hơn.