Tóm tắt phương pháp: Kỹ thuật thiết lập công thức truy hồi là một trong những công cụ cực kỳ mạnh mẽ để giải quyết bài toán đếm tổ hợp. Thay vì đếm trực tiếp số cách chọn/số cấu hình \(f(n)\), ta xây dựng mối liên hệ truy hồi nối kết \(f(n)\) với các trường hợp quy mô nhỏ hơn như \(f(n-1), f(n-2), \dots\), từ đó suy ra đáp số tổng quát cho bài toán.
1. Các bài toán ứng dụng thiết lập hệ thức truy hồi
Bài toán 1 (Bungari - 1995). Cho số nguyên \(n \ge 2\). Hãy tìm số các hoán vị \((a_1, a_2, \dots, a_n)\) của \(1, 2, \dots, n\) sao cho tồn tại duy nhất một chỉ số \(i \in \{1, 2, \dots, n-1\}\) thỏa mãn \(a_i > a_{i+1}\).
Bài giải:
Gọi \(S_n\) là số các hoán vị thỏa mãn điều kiện bài toán. Để ý rằng số các hoán vị mà \(a_n = n\) là \(S_{n-1}\). Còn số các hoán vị \((a_1, a_2, \dots, a_n)\) với \(a_i = n\) (\(1 \le i \le n-1\)) là \(C_{n-1}^{i-1}\).
Do vậy:\[S_n = S_{n-1} + \sum_{i=1}^{n-1} C_{n-1}^{i-1} = S_{n-1} + 2^{n-1} - 1.\]Chú ý rằng \(S_2 = 1\), từ đó ta có: \(S_n = 2^n - n - 1\.
Gọi \(S_n\) là số các hoán vị thỏa mãn điều kiện bài toán. Để ý rằng số các hoán vị mà \(a_n = n\) là \(S_{n-1}\). Còn số các hoán vị \((a_1, a_2, \dots, a_n)\) với \(a_i = n\) (\(1 \le i \le n-1\)) là \(C_{n-1}^{i-1}\).
Do vậy:\[S_n = S_{n-1} + \sum_{i=1}^{n-1} C_{n-1}^{i-1} = S_{n-1} + 2^{n-1} - 1.\]Chú ý rằng \(S_2 = 1\), từ đó ta có: \(S_n = 2^n - n - 1\.
Bài toán 2. Giả sử \(F_k\) là tập hợp tất cả các bộ \((A_1, A_2, \dots, A_k)\) trong đó \(A_i\) (\(i = 1, 2, \dots, k\)) là một tập con của \(\{1, 2, \dots, n\}\) (Các tập \(A_1, A_2, \dots, A_k\) có thể trùng nhau). Hãy tính:\[S_n = \sum_{(A_1, A_2, \dots, A_k) \in F_k} |A_1 \cup A_2 \cup \dots \cup A_k|\](Trường hợp \(n = 1998\) là bài thi APMO 1998)
Bài giải:
Do có \(2^n\) tập con của \(\{1, 2, \dots, n\}\) nên có \(2^{nk}\) bộ \((A_1, A_2, \dots, A_k)\). Với mỗi \(k\)-bộ \((A_1, A_2, \dots, A_k)\) của tập \(\{1, 2, \dots, n-1\}\) ta có thể thêm hoặc không thêm \(n\) vào tập \(A_i\) để được \(k\)-bộ \((A_1, A_2, \dots, A_k)\) của \(\{1, 2, \dots, n\}\). Với chú ý rằng số \(k\)-bộ \((A_1, A_2, \dots, A_k)\) của tập \(\{1, 2, \dots, n-1\}\) là \(2^{(n-1)k}\) và có \(2^k - 1\) cách thêm \(n\) vào \(k\)-bộ \((A_1, A_2, \dots, A_k)\) của tập \(\{1, 2, \dots, n-1\}\) thì ta có:\[S_n = 2^k S_{n-1} + (2^k - 1) . 2^{k(n-1)}\]Dễ thấy: \(S_1 = 2^k - 1\). Từ đây bằng quy nạp ta chứng minh được:\[S_n = n . 2^{k(n-1)} (2^k - 1)\]
Do có \(2^n\) tập con của \(\{1, 2, \dots, n\}\) nên có \(2^{nk}\) bộ \((A_1, A_2, \dots, A_k)\). Với mỗi \(k\)-bộ \((A_1, A_2, \dots, A_k)\) của tập \(\{1, 2, \dots, n-1\}\) ta có thể thêm hoặc không thêm \(n\) vào tập \(A_i\) để được \(k\)-bộ \((A_1, A_2, \dots, A_k)\) của \(\{1, 2, \dots, n\}\). Với chú ý rằng số \(k\)-bộ \((A_1, A_2, \dots, A_k)\) của tập \(\{1, 2, \dots, n-1\}\) là \(2^{(n-1)k}\) và có \(2^k - 1\) cách thêm \(n\) vào \(k\)-bộ \((A_1, A_2, \dots, A_k)\) của tập \(\{1, 2, \dots, n-1\}\) thì ta có:\[S_n = 2^k S_{n-1} + (2^k - 1) . 2^{k(n-1)}\]Dễ thấy: \(S_1 = 2^k - 1\). Từ đây bằng quy nạp ta chứng minh được:\[S_n = n . 2^{k(n-1)} (2^k - 1)\]
Bài toán 3. Tìm số tập con của tập \(\{1, 2, \dots, n\}\) sao cho trong mỗi tập con chứa ít nhất 2 phần tử là hai số nguyên liên tiếp.
Bài giải:
Gọi \(S_n\) là tập hợp các tập con không rỗng của tập \(\{1, 2, \dots, n\}\) mà trong mỗi tập con không có hai phần tử nào là hai số nguyên liên tiếp. Chia các phần tử của \(S_n\) thành hai nhóm:
- Nhóm không chứa \(\{n\}\): số các tập con như vậy là \(|S_{n-1}|\)
- Nhóm chứa phần tử \(n\): \(\{n\}\) hoặc \(\{a_1, a_2, \dots, a_k, n\}\) (\(k \ge 1\)). Rõ ràng \(a_i \neq n-1\) (\(i = 1, 2, \dots, k\)) nên số các tập con như vậy là: \(|S_{n-2}| + 1\).
Do vậy:\[|S_n| = |S_{n-1}| + |S_{n-2}| + 1\]Với chú ý \(|S_2| = 2\), \(|S_3| = 4\) ta có:\[|S_n| = \frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^{n+2} - \left(\frac{1-\sqrt{5}}{2}\right)^{n+2}\right] - 1\]Mặt khác số tập con không rỗng của tập \(\{1, 2, \dots, n\}\) là \(2^n - 1\). Vậy số tập con mà trong mỗi tập con chứa ít nhất 2 phần tử là hai số nguyên liên tiếp là:\[2^n - \frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^{n+2} - \left(\frac{1-\sqrt{5}}{2}\right)^{n+2}\right]\]
Gọi \(S_n\) là tập hợp các tập con không rỗng của tập \(\{1, 2, \dots, n\}\) mà trong mỗi tập con không có hai phần tử nào là hai số nguyên liên tiếp. Chia các phần tử của \(S_n\) thành hai nhóm:
- Nhóm không chứa \(\{n\}\): số các tập con như vậy là \(|S_{n-1}|\)
- Nhóm chứa phần tử \(n\): \(\{n\}\) hoặc \(\{a_1, a_2, \dots, a_k, n\}\) (\(k \ge 1\)). Rõ ràng \(a_i \neq n-1\) (\(i = 1, 2, \dots, k\)) nên số các tập con như vậy là: \(|S_{n-2}| + 1\).
Do vậy:\[|S_n| = |S_{n-1}| + |S_{n-2}| + 1\]Với chú ý \(|S_2| = 2\), \(|S_3| = 4\) ta có:\[|S_n| = \frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^{n+2} - \left(\frac{1-\sqrt{5}}{2}\right)^{n+2}\right] - 1\]Mặt khác số tập con không rỗng của tập \(\{1, 2, \dots, n\}\) là \(2^n - 1\). Vậy số tập con mà trong mỗi tập con chứa ít nhất 2 phần tử là hai số nguyên liên tiếp là:\[2^n - \frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^{n+2} - \left(\frac{1-\sqrt{5}}{2}\right)^{n+2}\right]\]
Bài toán 4. Có \(n\) quả bóng \(b_1, b_2, \dots, b_n\) và \(2n\) hộp \(h_1, h_2, \dots, h_{2n}\). Biết rằng quả bóng \(b_i\) (\(i = 1, 2, \dots, n\)) chỉ bỏ vào được các hộp \(h_1, h_2, \dots, h_{2i}\). Hỏi có bao nhiêu cách bỏ \(k\) (\(1 \le k \le n\)) quả bóng vào các hộp biết rằng mỗi hộp chứa nhiều nhất một quả bóng. (Hai cách bỏ bóng được gọi là khác nhau khi ít nhất một quả bóng được bỏ vào hai hộp khác nhau trong hai cách đó).
Bài giải:
Đặt \(S_{n,k}\) là số cách bỏ \(k\) quả bóng vào các hộp. Giả sử \(2 \le k \le n\). Nếu một trong \(k\) quả bóng được chọn là \(b_n\) thì \((k-1)\) quả bóng còn lại có thể bỏ vào các hộp bằng \(S_{n-1, k-1}\) cách. Đồng thời, \(b_n\) có \(2n - (k-1) = 2n - k + 1\) cách chọn 1 hộp trong các hộp còn lại để bỏ. Do đó số cách bỏ bóng trong trường hợp này là: \((2n - k + 1) . S_{n-1, k-1}\).
Trường hợp quả \(b_n\) không được chọn. Để ý rằng \(k \le n-1\). Mọi quả bóng trong các quả bóng \(b_1, b_2, \dots, b_{n-1}\) đều có thể bỏ vào các hộp bằng \(S_{n-1, k}\) cách.
Suy ra:\[S_{n,k} = S_{n-1,k} + (2n - k + 1) S_{n-1,k-1} \quad (n \ge 3, 2 \le k \le n)\]Dễ thấy:\[S_{n,n} = (n+1) S_{n-1, n-1}, \quad S_{n,1} = n(n+1), \quad S_{1,1} = 2\]Từ đó bằng quy nạp ta chứng minh được:\[S_{n,k} = \frac{(n+1) . k! (C_n^k)^2}{n - k + 1}\]
Đặt \(S_{n,k}\) là số cách bỏ \(k\) quả bóng vào các hộp. Giả sử \(2 \le k \le n\). Nếu một trong \(k\) quả bóng được chọn là \(b_n\) thì \((k-1)\) quả bóng còn lại có thể bỏ vào các hộp bằng \(S_{n-1, k-1}\) cách. Đồng thời, \(b_n\) có \(2n - (k-1) = 2n - k + 1\) cách chọn 1 hộp trong các hộp còn lại để bỏ. Do đó số cách bỏ bóng trong trường hợp này là: \((2n - k + 1) . S_{n-1, k-1}\).
Trường hợp quả \(b_n\) không được chọn. Để ý rằng \(k \le n-1\). Mọi quả bóng trong các quả bóng \(b_1, b_2, \dots, b_{n-1}\) đều có thể bỏ vào các hộp bằng \(S_{n-1, k}\) cách.
Suy ra:\[S_{n,k} = S_{n-1,k} + (2n - k + 1) S_{n-1,k-1} \quad (n \ge 3, 2 \le k \le n)\]Dễ thấy:\[S_{n,n} = (n+1) S_{n-1, n-1}, \quad S_{n,1} = n(n+1), \quad S_{1,1} = 2\]Từ đó bằng quy nạp ta chứng minh được:\[S_{n,k} = \frac{(n+1) . k! (C_n^k)^2}{n - k + 1}\]