Đếm bằng phương pháp truy hồi

ĐẾM BẰNG PHƯƠNG PHÁP TRUY HỒI
Đếm bằng truy hôi là một phương pháp khá hiệu quả trong việc giải các bài toán đếm. Nội dung của phương pháp đếm bằng truy hồi là để tính ta tìm một hệ thức giữa và các giá trị Do đó, để tính ta chỉ cần đi tính . Để thiết lập hệ thức truy hồi, ta thường đi phân hoạch một tập hợp thành các tập con, rồi đi tính phần tử của các tập con đó.
Ví dụ 1. Cho tập hợp có phần tử. Hãy tính số tập con của tập .
Lời giải.
Gọi là tập hợp gồm tập con của tập và . Ta phân hoạch tập thanh hai tập gồm các tập con chứa và gồm các tập con không chứa . Khi đó .
 Tính 
Với mỗi tập con , ta có , trong đó là một tập con của tập .
Khi đó, ánh xạ là một song ánh.
Do đó .
 Tính 
Vì mỗi tập con thuộc , ta có không chứa nên là một tập con của tập và ngược lại. Do đó, .
Suy ra .
Nhận xét: Mẫu chốt của lời giải trên là ta đi phân hoạch tập thành 2 tập. Một tập gồm các tập con chứa và một tập gồm các tập con không chứa , rồi đi tính số phần tử của mỗi tập đã được phân hoạch đó.
Ví dụ 2. Cho là số nguyên dương. Có bao nhiêu xâu kí tự độ dài với kí tự lấy trong các số mà số lần xuất hiện của số trong xâu kí tự là số chẵn.
Lời giải. Đặt là số xâu kí tự có độ dài mà số lần xuất hiện của số 0 là số chẵn và 
Ta thấy . 
Vì có xâu kí tự có độ dài nên số xâu kí tự độ dài mà trong đó số xuất hiện của chữ số 0 là số lẻ bằng .
Ta phân hoạch tập thành hai tập rời nhau như sau :
 và 
Ta tính 
Với thì xâu kí tự có độ dài và số xuất hiện của chữ số 0 trong xâu là số lẻ. Do đó ta có .
Ta tính 
Với thì xâu có độ dài và số lần xuất hiện của số 0 là số chẵn. Do đó, có xâu như vậy. Với mỗi xâu ta có cách chọn .
Suy ra .
Do đó .
Từ đây, ta tìm được . 
Ví dụ 3. Có bao nhiêu hoán vị của tập sao cho tồn tại duy nhất một chỉ số sao cho .
Lời giải. Gọi là tập các hoán vị của tập sao cho tồn tại duy nhất một chỉ số sao cho và đặt . Rõ ràng với mỗi thì chỉ có thể xảy ra ba dạng sau
+) , gọi tập các hoán vị thuộc dạng này là tập 
+) , còn , gọi tập các hoán vị thuộc dạng này là 
+) và , gọi tập các hoán vị thuộc dạng này là . 
Khi đó tập được phân hạch thành ba tập nên . 
Dễ thấy 
Với mỗi hoán thuộc tập , khi ta bỏ thì ta thư được một hoán vị thuộc và ngược lại mỗi hoán vị thuộc ta chèn thêm vào giữa và (với ) ta được một hoán vị thuộc tập . Suy ra 
Với mỗi hoán vị thuộc tập ta rút ra thì ta thu được hoán vị và với mỗi hoán vị này, ta có cách chèn vào. Do đó .
Do đó và .
Từ đây ta tìm được . 
Ví dụ 4. Cho tập , ta định nghĩa . Hỏi có bao nhiêu tập con của tập sao cho (THTT số 400 bài T10).
Lời giải.
Đặt và 
Ta có .
Vì nên và . Do đó, ta chia tập thành hai tập rời nhau và .
+) Tính 
Với , ta đặt , khi đó nên . 
+) Tính 
Với , ta đặt , khi đó . Suy ra .
Do đó, ta có . Từ đây ta tìm được 
.
Ví dụ 5. Có tấm thẻ được đánh số từ đến . Có bao nhiêu cách chọn ra một số thẻ (ít nhất 1 tấm) sao cho tất cả các số viết trên các tấm thẻ này đều lớn hơn hoặc bằng số tấm thẻ được chọn.
Lời giải.
Gọi là số cách chọn một số thẻ từ thẻ sao cho tất cả các số viết trên thẻ đều không nhỏ hơn số thẻ được chọn. Ta có các trường hợp sau
Thẻ ghi số không được chọn, khi đó các thẻ được chọn từ các thẻ được ghi từ số 1 đến và tất cả các số viết trên các tấm thẻ đều không nhỏ hơn số thẻ được chọn. Số cách chọn trong trường hợp này là .
Thẻ ghi số được chọn
+) Nếu chỉ chọn 1 thẻ ghi số thì có 1 cách chọn
+) Nếu chọn ít nhất hai thẻ thì thẻ ghi số sẽ không được chọn và các thẻ được chọn còn lại (khác thẻ ghi số ) gồm các thẻ ghi số từ đến , ta trừ đi mỗi số ghi trên các thẻ này 1 đơn vị thì ta được các thẻ ghi từ số 1 đến . Do đó, trường hợp này có cách chọn.
Từ đó, ta suy ra và .
Do đó ta tìm được .
Ví dụ 6. Cho tập . Tìm số bộ thỏa:
1) thuộc với mọi 
2) thuộc với mọi .
Lời giải.
Gọi là tập các bộ thỏa bài toán. Ta phân hoạch tập thành ba tập rời nhau
.
Đặt .
Xét một bộ , khi đó . Do đó, khi bỏ phần tử ta thu được một bộ thuôc hoặc . Ngược lại với mỗi bộ thuộc hoặc ta có thể thêm vào cuối số 1 hoặc số 0 để thu được một bộ thuộc . Do đó, ta có 
Tương tự, ta có và 
Do đó .
Từ đó, ta tìm được . 
 Chú ý: Trong một số bài toán, chúng ta cần xây dựng thêm đối tượng phụ để giúp giải quyết bài toán đếm.
Ví dụ 7. Từ các chữ số lập được bao nhiêu số có chữ số và số đó chia hết cho .
Lời giải. Gọi là tập các số tự nhiên có chữ số được lập từ các chữ số . Ta có .
Vì một số tự nhiên khi chi cho 3 chỉ có 3 số dư là 0,1,2 nên ta chia tập A thành 3 tập rời nhau theo thứ tự là gồm các mà số dư của khi chia cho 3 là 0, 1, 2.
Ta cần tìm , đặt , ta có .
Xét một số và có chữ số. 
+) Nếu hoặc , khi ta bỏ ta thu được số có chữ số và số này chia hết cho , ngược lại với mỗi số có chữ số chia hết cho 3 thì khi ta thêm vào cuối chữ số 3 hoặc 6 ta được một số chia hết cho 3 và có chữ số. Nên trường hợp này có số.
+) Nếu , khi ta bỏ , ta thu được một số có chữ số thuộc tập và mỗi số thuộc , ta thêm vào cuối chữ số 5 ta thu được một số thuộc . Trường hợp này có số.
+) Nếu . Tương tự như trên ta có số.
Do đó, ta có . 
Suy ra . 
Trong bài toán trên, việc đưa thêm hai tập và vào để giúp chúng ta tìm được quan hệ truy hồi giữa ba đại lượng . Trong một số bài toán, việc làm xuất hiện các bài toán phụ không còn là việc đơn giản nữa.
Ví dụ 8. Một bộ gồm số được gọi là “đẹp” nếu thỏa mãn hai điều kiện sau
i) với 
ii) với và .
Hỏi có tất cả bao nhiêu bộ cô đẹp?
Lời giải.
Đặt thỏa .
 thỏa .
Và .
Ta có với mọi . Do đó, ta chỉ xét với .
Với thì ta có .
+) Nếu thì bộ 
+) Nếu thì bộ .
Ngược lại với mỗi bộ thì ta có 
Và mỗi bộ thì .
Do đó, ta có (1).
Với , ta có .
+) Nếu thì 
+) Nếu thì .
 Ngược lại với mỗi bộ thì ta có ; 
Và mỗi bộ thì .
Suy ra (2).
Từ (1) và (2) ta có và 
Nên ta có .
Ví dụ 9 (VMO 2009). Cho số nguyên dương . Kí hiệu là tập hợp số nguyên dương đầu tiên. Hỏi có tất cả bao nhiêu tập con của có tính chất: Trong không tồn tại các số mà . ( Tập rỗng được coi là một tập có tính chất trên).
Lời giải.
(hình 1)
Xét bảng hình chữ nhật và đánh các số từ đến như hình trên (hình 1) và ta gọi hai ô chứa n và là hai ô đặc biệt.
Số tập con thỏa yêu cầu bài toán chính bằng số cách chọn một số số từ bảng sao cho hai ô kề nhau không được chọn và cả hai ô đặc biệt không cùng được chọn và số cách chọn này ta kí hiệu là .
Gọi là số cách chọn một số ô sao cho hai ô kề nhau không được chọn (*)
 là số cách chọn một số ô sao cho hai ô kề nhau không được chọn và hai ô đặc biệt được chọn.
Khi đó .
 Tính 
Gọi là số cách chọn một số ô thỏa (*) từ bảng chữ nhật khuyết đơn (ở hình 2)
(Hình 2)
Ta có các cách chọn thỏa (*) gồm:
+) cách chọn mà ô ở cột thứ nhất không được chọn.
+) cách chọn mà trong mỗi cách chọn thì ô thuộc cột thứ nhất được chọn.
Do đó, ta có (1)
Mặt khác, tất cả các cách chọn một số ô thỏa (*) từ bảng chữ nhật khuyết đơn gồm:
+) cách chọn mà mỗi cách chọn ô chứa không được chọn
+) cách chọn mà mỗi cách chọn ô chứa được chọn.
Do đó, ta có (2).
Từ (1) và (2) ta suy ra và ta có nên
.
 Tính 
Ta có 
(hình 3)
Gọi là số cách chọn một số ô thỏa (*) từ hình chữ nhật khuyết kép (hình 3)
Khi đó, ta có . Nên ta có và ta tính được 
Ta thấy tất cả các cách chọn thỏa (*) từ hình chữ nhật kép gồm
+) cách chọn mà mỗi cách chọn thì cả và đều không được chọn.
+) cách chọn mà mỗi cách chọn thì một trong hai ô A, B được chọn.
+) cách chọn mà mỗi cách chọn thì ccar hai ô A và B đều được chọn.
Do đó 
Suy ra 
Do đó .
Vậy với .
Bài tập vận dụng
Bài 9. Trong mặt phẳng cho đường thẳng phân biệt, hai đường thẳng bất kì luôn cắt nhau và không có 3 đường thẳng nào đồng quy. Hỏi đường thẳng trên chia mặt phẳng thành bao nhiêu miền.
Lời giải.
Gọi là số phần mặt phẳng được chia bởi đường thẳng 
Khi đó là số phần mặt phẳng được chia bởi đường thẳng .
Vì đường thẳng cắt đường thẳng tại điểm và điểm này chia đường thẳng thành phần gồm 2 tia và đoạn thẳng.
Mỗi phần bị chia đó sẽ nằm trong một miền của mặt phẳng bị chia bởi đường thẳng và phần này chia miền đó thành hai miền. Do đó, số phần mặt phẳng được chia bởi đường thẳng nhiều hơn số phần mặt phẳng được chia bởi đường thẳng là . 
Chẳng hạn, ta xét 3 đường thẳng chia mặt phẳng thành miền, đường thẳng bị chia thành phần, phần nằm trong miền và chia miền này thành 2 miền 
Do đó, ta có (*).
Suy ra
.
Bài 10. Có bao nhiêu xâu nhị phân độ dài trong đó không có hai bit 1 đứng cạnh nhau?
Lời giải.
Giả sử có là tập hợp các xâu nhị phân có độ dài và trong đó không có hai bit 1 đứng cạnh nhau và . Ta phân hoạch tập thành hai tập rời nhau và như sau
 và .
Khi đó .
 Với , ta có . 
Do đó, ánh xạ biến thành là một song ánh
Nên .
Xét ánh xạ được xác định bởi với là một song ánh. 
Do đó 
Do vậy, ta có .
Vì nên ta tìm được .
Bài 11. ( IMO-2011) Giả sử là một số nguyên. Cho một cái cân đĩa và quả cân có trọng lượng
. Ta muốn đặt lên cái cân mỗi một trong quả cân, lần lượt từng quả một, theo cách để đảm bảo đĩa cân bên phải không bao giờ nặng hơn đĩa cân bên trái . Ở mỗi bước ta chọn một trong các quả cân chưa được đặt lên rồi đặt nó lên đĩa bên phải, hoặc đĩa bên trái, cho đến khi tất cả các quả cân đều được đặt lên đĩa. Hỏi có bao nhiêu cách để thực hiện việc đặt cân theo đúng mục đích đề ra?
Lời giải
Gọi là số cách thực hiện việc đặt quả cân lên đĩa thỏa mãn yêu cầu đề ra.
Xét cách đặt quả cân có trọng lượng .
Do nên trong mọi cách đặt cân thỏa mãn thì quả cân có trọng lượng luôn được đặt ở đĩa cân bên trái. 
Nếu quả cân được chọn để đặt cuối cùng ( chỉ có một cách đặt, vì quả chỉ đặt lên đĩa bên trái ) và số cách đặt quả cân còn lại là .
Nếu quả cân được đặt ở bước thứ ( ). Do có cách chọn , và trong trường hợp này quả cân có trọng lượng có 2 cách đặt ( đặt lên đĩa bên phải hay đĩa bên trái đều thỏa mãn) , do đó số cách đặt quả cân trong trường hợp này là . 
Vậy ta có hệ thức truy hồi .
Ta có nên .
Bài 12. Cho số nguyên dương . Có bao nhiêu số tự nhiên có chữ số được lập từ các
số thuộc tập và chia hết cho 3?.
Lời giải
Gọi là tập tất cả các số tự nhiên có chữ số lần lượt chia hết cho 3 và không chia hết cho 3 được lập từ các số .
Xét một phần tử thuộc thì có 2 cách thêm vào chữ số cuối để được một phần tử của và có 2 cách thêm vào chữ số cuối để được một phần tử của .
Xét một phần tử thuộc thì có 1 cách thêm vào chữ số cuối để được một phần tử của và có đúng 3 cách thêm vào chữ số tận cùng để được một phần tử của .
Vậy 
Đặt thì từ suy ra thay vào ta được 
Từ suy ra ( do ).
.
. Vậy có số tự nhiên thỏa mãn yêu cầu bài toán.
Bài 13. Từ các số thuộc tậpcó thể lập được bao nhiêu số tự nhiên có chữ số mà trong mỗi số đó đều chứa một số lẻ chữ số 1 và một số chẵn chữ số 2 ( là số nguyên dương cho trước).
Lời giải
Kí hiệu là tập tất cả các số tự nhiên có chữ số được lập từ các số của tập và lần lượt là tập tất cả các số tự nhiên có chữ số được lập từ các số của tập mà trong mỗi số đó lần lượt chứa ( lẻ các chữ số 1, chẵn các chữ số 2);( lẻ các chữ số 1, lẻ các chữ số 2); ( chẵn các chữ số 1, lẻ các chữ số 2);( chẵn các chữ số 1, chẵn các chữ số 2).
Dễ thấy đôi một rời nhau và do đó .
Ta có .Dễ thấy .
Xét một phần tử thuộc , ta thực hiện phép biến đổi: giữ nguyên các chữ số khác 1 và 2, các chữ số 1( nếu có) đổi thành 2 và các chữ số 2( nếu có) đổi thành 1 ta được một phần tử của , nếu lấy một phần tử thuộc và cũng thực hiện phép biến đổi trên ta được một phần tử của . Phép biến đổi này là một song ánh từ tập vào tập nên , do đó từ suy ra 
Kí hiệu 
Từ ta có được 
 ( do ).Vậy .
Bài 14. .(BRVT-2010) Cho số nguyên dương . Có bao nhiêu số tự nhiên có chữ số, trong mỗi số đó các chữ số đều lớn hơn 1 và không có hai chữ số khác nhau cùng nhỏ hơn 7 đứng liền nhau.
Lời giải
Kí hiệu là tập tất cả các số tự nhiên có chữ số thỏa mãn đề bài, là các tập con của theo thứ tự các số có tận cùng nhỏ hơn 7; các số có tận cùng lớn hơn 6.
Ta có .
Lấy một phần tử thuộc bỏ đi chữ số tận cùng ta được một phần tử của , ngược lại lấy một phần tử của .
Nếu tận cùng nhỏ hơn 7 ( thuộc) thì chỉ có một cách thêm vào chữ số cuối để được một phần tử của và có đúng 3 cách thêm vào chữ số cuối để được một phần tử của .
Nếu tận cùng lớn hơn 6 ( thuộc ) thì có 5 cách thêm vào chữ số cuối để được một phần tử của và đúng 3 cách thêm vào chữ số cuối để được một phần tử của .
Từ các lập luận trên ta có .
Từ và suy ra 
Kí hiệu ta có .
Ta có
.
Dễ thấy, ta tìm . Xét .
Nếu thì có 4 cách chọn .
Nếu thì có 8 cách chọn . 
Vậy ,do đó .
Bài 15. Có người ngồi thành một hàng ngang vào chiếc ghế. Hỏi có bao nhiêu cách lập hàng mới cho người đó mà trong mỗi cách lập hàng mới: mỗi người hoặc giữ nguyên vị trí của mình, hoặc đổi chỗ cho người liền bên trái, hoặc đổi chỗ cho người liền bên phải.
Lời giải
Đánh số thứ tự vị trí các ghế từ trái qua phải là 
Gọi là số cách lập hàng mới cho người thỏa mãn đề bài.
Dễ thấy .
Với 
Xét một cách lập hàng mới thỏa mãn điều kiện. Có hai loại hàng được lập:
Loại 1: Người ở vị trí số 1 giữ nguyên vị trí. Rõ ràng số hàng được lập loại này là cách.
Loại 2: Người ở vị trí số 1 đổi chỗ, khi đó người ở vị trí số 1 chỉ có thể xếp vào vị trí số 2 và người ở vị trí 2 phải chuyển sang vị trí 1. Số hàng loại này là .
Từ đó ta có .
Vậy .
Từ đây dễ dàng tìm được .
Bài 16. Cho số nguyên dương . Xét tập . Tìm số các tập con của tập mà mỗi tập con đó có tính chất: Nếu là hai phần tử khác nhau của và có tổng là một lũy thừa của 2 thì đúng một trong hai phần tử này thuộc .
Lời giải
Ta gọi một tập thỏa yêu cầu bài toán là một tập tốt.
Với mỗi số nguyên , gọi là tập hợp gồm tất cả các tập tốt thỏa mãn yêu cầu bài toán.
Chẳng hạn với ta có , trong chỉ có hai số và 3 thỏa nên .
Kí hiệu , ta có .
 Xét một tập tốt , khi đó với là một tập tốt của và là một tập con nào đó của tập .
Ta đếm số tập tốt không chứa phần tử của bằng cách đếm số khả năng thêm mỗi phần tử của tập vào . Ta viết các phần tử này dưới dạng .
Nếu thì không thể thêm phần tử vào ( do là một tập tốt).
Nếu thì chắc chắn phải thêm phần tử vào ( do là một tập tốt).
Do đó mỗi phần tử của chỉ có một khả năng duy nhất để thêm vào một tập nào đó của . Từ đây suy ra số tập tốt của không chứa là .
Dễ thấy là một tập tốt thuộc trong đó là một tập tốt của không chứa phần tử , do đó số tập tốt có chứa phần tử của cũng là .
Vậy ; kết hợp với ta có 
Bài 17. Tìm số hoán vị của tập sao cho và với mọi .
Lời giải. Kí hiệu là tập các hoán vị thỏa yêu cầu bài toán và .
Ta có hoặc .
Ta phân hoạch tập thành hai tập rời nhau 
 và 
 , khi đó ánh xạ biến là một song ánh. Nên .
 , khi đó . Nên ta có các trường hợp sau
+) , ta có và khi đó ánh xạ 
Biến bộ là một song ánh
Nên trường hợp này có bộ
+) với , khi đó từ vô lí.
+) , khi đó và và trong trường hợp này chỉ có 1 hoán vị thỏa bài toán.
Do vậy, ta có . Từ đây ta tìm được .