Quy tắc đếm | Lớp 10

Từ 4 chiếc áo, 3 chiếc quần và 2 đôi giày, bạn có thể phối được bao nhiêu bộ trang phục khác nhau? Bạn có thể liệt kê tất cả, nhưng danh sách sẽ dài và dễ nhầm. Các quy tắc đếm giúp bạn tìm ra con số bằng cách nghĩ về cấu trúc của việc chọn, thay vì viết ra từng khả năng. Chúng là nền tảng của hoán vị, tổ hợp và xác suất.

Quy tắc cộng

Giả sử bạn muốn đọc một cuốn sách trên giá. Có 5 cuốn sách toán và 4 cuốn tiểu thuyết. Bạn chọn hoặc một cuốn toán hoặc một cuốn tiểu thuyết, không thể chọn cả hai cùng lúc, nên có $5+4=9$ cách chọn.

Từ khoá là "hoặc" và "xung khắc": mỗi lựa chọn thuộc đúng một nhóm.

Quy tắc nhân

Bây giờ giả sử bạn muốn chọn một món ăn nhẹ và một đồ uống. Việc chọn diễn ra qua các bước liên tiếp. Sơ đồ hình cây cho thấy mọi khả năng: bắt đầu bạn chọn đồ uống (trà hoặc nước ép), và với mỗi đồ uống bạn chọn món ăn nhẹ (bánh, trái cây hoặc hạt).

Sơ đồ hình cây: 2 đồ uống, sau đó 3 món ăn nhẹ

Đếm các đầu nhánh bên phải của cây: $3+3=6$ , cũng bằng $2\times 3$ .

Từ khoá là "và": bạn làm bước 1 và rồi bước 2 và rồi bước 3.

Số, mật khẩu và lộ trình

Các số có điều kiện

Khi một chữ số bị ràng buộc, hãy điền vị trí bị ràng buộc nhiều nhất trước.

Ví dụ Số có ba chữ số khác nhau

Có bao nhiêu số có ba chữ số mà ba chữ số đó khác nhau? Trong đó có bao nhiêu số chẵn?

Lời giải.

Tất cả các số như vậy. Chữ số hàng trăm không thể là 0: có 9 cách. Chữ số hàng chục là chữ số bất kì khác chữ số đã dùng: có 9 cách (bây giờ được dùng 0). Chữ số hàng đơn vị khác cả hai chữ số trước: có 8 cách. Tổng cộng $9\cdot 9\cdot 8=648$ .
Các số chẵn. Chữ số hàng đơn vị quyết định, nên bắt đầu từ đó. Chia thành hai trường hợp (quy tắc cộng).
- Chữ số hàng đơn vị là 0: chữ số hàng trăm có 9 cách, hàng chục có 8 cách, cho $9\cdot 8=72$ số.
- Chữ số hàng đơn vị là 2, 4, 6 hoặc 8 (4 cách): chữ số hàng trăm không được là 0 hay chữ số hàng đơn vị, nên có 8 cách; chữ số hàng chục còn 8 cách. Cho $4\cdot 8\cdot 8=256$ số.
Cộng các trường hợp: $72+256=328$ .

Vậy có tất cả 648 số, trong đó 328 số là số chẵn.

Mật khẩu

Lộ trình

Cách đếm phần bù

Đôi khi đếm những gì ta không muốn lại dễ hơn. Nếu $N$ là tổng số khả năng và $M$ khả năng trong đó không thoả mãn điều kiện, thì số khả năng thoả mãn điều kiện là $N-M$ .

Kiểm tra bằng máy tính

Một chương trình ngắn có thể kiểm tra lập luận đếm bằng cách thử hết mọi khả năng. Đây là đoạn kiểm tra cho ví dụ đầu tiên ở trên:

count = 0
for n in range(100, 1000):
    if len(set(str(n))) == 3:
        count += 1
print(count)   # 648

Thuật ngữ

Tiếng Việt	English
quy tắc cộng	addition rule
quy tắc nhân	multiplication rule
xung khắc (không thể xảy ra đồng thời)	mutually exclusive
các bước liên tiếp	successive steps
sơ đồ hình cây	tree diagram
trường hợp	case
phần bù (đếm phần còn lại)	complement
điều kiện ràng buộc	restriction

Tóm tắt

Quy tắc cộng: các lựa chọn không thể xảy ra đồng thời, cộng các số lại ("hoặc").
Quy tắc nhân: các bước liên tiếp, nhân các số lại ("rồi").
Sơ đồ hình cây liệt kê mọi kết quả và cho thấy vì sao phép nhân đúng.
Với các số có điều kiện, điền vị trí bị ràng buộc nhiều nhất trước và chia trường hợp khi cần.
Cách đếm phần bù: (tất cả) $-$ (những khả năng không muốn).

Luyện tập

Một thực đơn có 3 món khai vị, 5 món chính và 2 món tráng miệng. Có bao nhiêu bữa ăn gồm một món khai vị, một món chính và một món tráng miệng?
Một giá sách thư viện có 6 cuốn sách tiếng Anh và 4 cuốn sách tiếng Pháp. Có bao nhiêu cách chọn (a) một cuốn sách; (b) một cuốn tiếng Anh và một cuốn tiếng Pháp?
Có bao nhiêu số có ba chữ số mà cả ba chữ số đều lẻ?
Một mã gồm hai chữ cái (mỗi chữ cái 26 cách chọn, được lặp lại) theo sau là ba chữ số (được lặp lại). Có bao nhiêu mã như vậy?
Có bao nhiêu số có ba chữ số khác nhau chia hết cho 5?
Có 3 con đường từ A đến B, 4 con đường từ B đến C và 2 con đường đi thẳng từ A đến C. Có bao nhiêu chuyến đi khứ hồi từ A đến C rồi quay về A, nếu mỗi con đường đều đi được theo cả hai chiều và đường về có thể là lộ trình bất kì?
Một xâu nhị phân có 8 kí hiệu, mỗi kí hiệu là 0 hoặc 1. Có bao nhiêu xâu (a) tất cả; (b) có ít nhất một chữ số 1; (c) bắt đầu bằng 1 và kết thúc bằng 0?
Có bao nhiêu số có bốn chữ số chứa ít nhất một chữ số 0?
Tìm số ước nguyên dương của 360.
Một lá cờ có 3 sọc ngang, mỗi sọc tô một trong 5 màu, và hai sọc kề nhau phải khác màu. Có bao nhiêu lá cờ như vậy?

Xem lời giải

Ba bước liên tiếp: $3\cdot 5\cdot 2=30$ bữa ăn.
(a) Một cuốn từ một trong hai nhóm, hai nhóm không giao nhau: $6+4=10$ . (b) Một cuốn mỗi loại, hai bước: $6\cdot 4=24$ .
Mỗi chữ số trong 3 chữ số được chọn từ $\{1;3;5;7;9\}$ : $5\cdot 5\cdot 5=125$ .
$26\cdot 26\cdot 10\cdot 10\cdot 10=676\,000$ .
Số chia hết cho 5 có tận cùng là 0 hoặc 5. Hàng đơn vị là 0: hàng trăm có 9 cách, hàng chục có 8 cách, được $72$ số. Hàng đơn vị là 5: hàng trăm không là 0 và không là 5 nên có 8 cách; hàng chục có 8 cách; được $64$ số. Tổng cộng $72+64=136$ .
Đi từ A đến C có $3\cdot 4+2=14$ lộ trình. Lộ trình về cũng là một trong 14 lộ trình đó, được chọn độc lập, nên có $14\cdot 14=196$ chuyến khứ hồi.
(a) $2^8=256$ . (b) Đếm phần bù: chỉ có xâu gồm toàn số 0 là không có số 1, nên $256-1=255$ . (c) Kí hiệu đầu và cuối đã cố định, 6 kí hiệu ở giữa tuỳ ý: $2^6=64$ .
Tổng cộng 9000 số. Số không có chữ số 0: $9^4=6561$ . Vậy $9000-6561=2439$ .
$360=2^3\cdot 3^2\cdot 5$ . Mỗi ước có dạng $2^a3^b5^c$ với $a\in\{0;1;2;3\}$ , $b\in\{0;1;2\}$ , $c\in\{0;1\}$ : $4\cdot 3\cdot 2=24$ ước.
Sọc đầu có 5 màu; mỗi sọc tiếp theo có 4 màu (khác màu của sọc kề nó): $5\cdot 4\cdot 4=80$ .