Basic counting principles

Nguyên lý thứ nhất (Quy tắc cộng). Giả sử có cách thực hiện việc , cách thực hiện việc ,…, cách thực hiện việc . Nếu việc này không thể làm đồng thời thì sẽ có cách thực hiện một trong các việc .

Ví dụ 1. Người ta có thể đi từ Hải Phòng đến Đà Nẵng bằng một trong ba phương tiện: tàu hoả, tàu thuỷ và máy bay. Nếu có hai cách đi bằng tàu hoả, ba cách đi bằng tàu thuỷ, và cách đi bằng máy bay thì sẽ có cách đi từ Hải Phòng đến Đà Nẵng.

Ví dụ 2. Tìm số các cặp có thứ tự các số nguyên thoả mãn .

Lời giải. Mỗi ta đặt , khi đó tập cần tính số phần tử sẽ là hợp rời rạc của các . Ta tính số phần tử của các bằng phương pháp liệt kê và cuối cùng được đáp số của bài toán là

Nguyên lý thứ hai (Quy tắc nhân). Giả sử rằng việc có thể được làm bằng cách thực hiện liên tiếp các việc ; và có cách thực hiện việc , cách thực hiện việc ,…, cách thực hiện việc . Khi đó số cách làm việc là .

Ví dụ 3. Đề đi từ thành phố đến thành phố người ta phải đi lần lượt qua hai thành phố và . Nếu có hai cách đi từ đến $B$, ba cách đi từ đến và một cách đi từ đến thì sẽ có cách đi từ đến

Ví dụ 4. Cho và là các số nguyên dương. Một dãy phân độ dài là một dãy với . Hỏi có bao nhiêu dãy này?

Lời giải. Đặt . Để hình thành một dãy phân, đầu tiên chúng ta cần chọn từ , sau đó chọn từ , và cứ như thế cho đến cuối cùng cần chọn từ . Bởi vì có cách để làm mỗi bước nên theo quy tắc nhân, số các dãy như vậy bằng

Ví dụ 5. Tìm số các ước dương của .

Lời giải. Ta có nên một số nguyên dương là một ước dương của khi và chỉ khi nó có dạng với là các số nguyên thoả mãn . Như vậy số các ước dương của bằng số các bộ ba thoả mãn , theo quy tắc nhân, số ước dương của bằng

Tổng quát hơn ta có: Nếu số nguyên dương có phân tích tiêu chuẩn thì số các ước dương của bằng .

Ví dụ 6. Cho và

Tính .

Lời giải. Với mỗi ta đặt . Khi đó là hợp rời rạc của các , mà theo quy tắc nhân ta có nên suy ra .

Để ý đến lời giải ví dụ thứ hai và thứ sáu, ta thấy chúng có một điểm chung là chia bài toán đã cho thành các bài toán con đơn giản hơn và giải chúng. Đây là cách cơ bản nhất để giải các bài toán đếm, có thể sẽ có cách khác ngắn gọn hơn, nhưng việc chia một bài toán thành các bài toán con mà chúng ta đã biết cách giải sẽ giúp ta ít gặp phải các sai lầm hơn.

Ví dụ 7. Có bao nhiêu số tự nhiên có ba chữ số được lấy từ tập nếu

(a) Các chữ số không cần phải khác nhau?

(b) Các chữ số phải khác nhau?

(c) Các chữ số phải khác nhau và chứa số ?

(d) Các chữ số không cần phải khác nhau và chứa số ?

Lời giải.

(a)

(b) .

(c) Đầu tiên ta chọn vị trí cho số , sau đó chọn hai số còn lại lần lượt. Đáp số là .

(d) Nếu tiếp tục làm như trên ta sẽ được kết quả là , đây là một kết quả không chính xác! Vì làm như vậy những số như sẽ được đếm hai lần. Vấn đề ở chỗ ta đã dùng sai quy tắc nhân, mỗi hai tổ hợp khác nhau cách thực hiện các công việc phải cho hai kết quả khác nhau thì ta mới áp dụng được quy tắc nhân. Bài này ta lại phải chia thành các bài toán con và giải chúng lần lượt.

Ta chia trường hợp theo vị trí của số nằm bên trái nhất. Nếu số này nằm ở vị trí hàng trăm thì số có ba chữ số phải có dạng , nếu nó nằm ở vị trí hàng chục thì số có ba chữ số phải có dạng với , và cuối cùng, nếu số này nằm ở vị trí hàng đơn vị thì số ba chữ số phải có dạng với . Giải các bài toán con ta được đáp số của bài toán là

Ví dụ 8. Một rổ bóng chứa quả bóng xanh giống nhau và quả bóng đỏ giống nhau. Hỏi có bao nhiêu cách bốc ít nhất quả bóng ra khỏi rổ?

Lời giải. Rõ ràng là có thể giải bài toán bằng cách chia thành các trường hợp: Bốc , bốc ,…,bốc quả bóng. Nhưng như thế hơi dài. Ở trên chia theo số bóng bốc ra, rõ ràng là số bóng khác nhau thì ta có hai lần bốc khác nhau. Liệu còn có cách khác phân biệt hai lần bốc? Ta thấy hai lần bốc cho hai kết quả giống nhau nếu và chỉ nếu số bóng xanh và số bóng đỏ như nhau, vậy hai lần bốc khác nhau nếu và chỉ nếu số bóng xanh hoặc số bóng đỏ khác nhau. Như vậy ta có lời giải sau.

Số cách bốc bằng số cặp trừ đi , ở đây là số quả bóng xanh và là số quả bóng đỏ. Như vậy ta có đáp số của bài toán là

Ví dụ 9. Tìm số các tập con của một tập có phần tử, ở đây là một số nguyên dương.

Lời giải. Gọi tập có phần tử trong đề bài là Mỗi tập con của sẽ được hình thành sau bước. Trong đó, ở bước ta quyết định xem có lấy làm phần tử của hay không, có hai cách để làm điều này. Vậy theo quy tắc nhân, đáp số của bài toán là .

Như vậy nếu chia được bài toán cần giải về các bài toán đếm đã biết cách giải thì mọi việc còn lại là đơn giản. Không may, trong đa số các bài toán đếm việc tìm ra một cấu trúc để chia bài toán thành các bài toán nhỏ hơn là việc làm khó khăn nhất. Hay nói khác đi, khó khăn nằm ở lúc bắt đầu. Sau khi chọn được cấu trúc rồi, bạn phải kiểm chia xem việc chia như vậy có đảm bảo đầu ra là các mô hình khác nhau hay không.

Hầu hết các bài toán đếm đều yêu cầu bạn phải thực sự hiểu mô hình mà mình cần đếm, hay cái mà bạn cần đếm. Biết lời giải một bài toán đếm sẽ giúp ích bạn một chút khi giải bài toán đếm khác, nhưng muốn thực sự giỏi thì bạn phải làm nhiều bài tập, việc đọc các ví dụ là không bao giờ đủ!