Trong các phương pháp kể trên thì phương pháp dùng hàm sinh là một phương pháp khá đa năng, tuy nhiên nó đòi hỏi phải sử dụng đến một số kiến thức toán cao cấp nhất định. Trong bài viết này tôi sẽ giới thiệu cho các bạn một phương pháp đếm sơ cấp hơn và cũng khá hiệu quả: Phương pháp Truy hồi - Quy nạp.
Để hiểu thêm về phương pháp này ta sẽ tìm hiểu qua một số ví dụ quen thuộc sau đây:
Ví dụ 1: Có bao nhiêu cách chia $m$ cái kẹo cho $n$ đứa trẻ (có thể có đứa không có cái nào!)
Hay hiểu theo một cách khác là phương trình:
$m=k_1+k_2+...+k_n\;\;\;(1)$
Có bao nhiêu nghiệm nguyên không âm?
Lời giải:
Gọi $S(m,n)$ là số nghiệm của (1). Ta có:
$(1)\Leftrightarrow m-k_1=k_2+...+k_n\;\;\;(2)$
Như vậy, tương ứng với mỗi giá trị $k_1;\;(0\le k_1 \le m)$, ta có số nghiệm của (2) là $S(m-k_1,n-1)$
Do đó:
$S(m,n)=\sum\limits_{k=0}^m S(m-k,n-1)$ (Truy hồi)
- Với $n=1$, dễ thấy $S(m,1)=1$
- Với $n=2$, ta có: $S(m,2)=\sum\limits_{k=0}^m S(m-k,1)=\sum\limits_{k=0}^m 1 = m+1$
- Với $n=3$, ta có: $S(m,3)=\sum\limits_{k=0}^m S(m-k,2)=\sum\limits_{k=0}^m (m+1-k) = \dfrac{(m+2)(m+1)}{2}$
- Qua 3 trường hợp trên, ta dự đoán rằng: $\boxed{S(m,n)=C_{m+n-1}^{n-1}}\;\;\;(3)$
- Bây giờ ta sẽ chứng minh (3) bằng quy nạp theo $n$.
- Rõ ràng (3) đúng với $n=1,2,3$. Giả sử (3) đúng với $n$ ta sẽ chứng minh (3) cũng đúng với $(n+1)$. Ta có:
$S(m+1,n)=\sum\limits_{k=0}^m S(m-k,n)=\sum\limits_{k=0}^m C_{m-k+n-1}^{n-1}$ (giả thiết quy nạp)
$S(m+1,n)=\sum\limits_{k=0}^m C_{k+n-1}^{n-1}$ (đảo chiều biến k)
$S(m+1,n)=\sum\limits_{k=0}^m \left(C_{k+n}^n-C_{k-1+n}^n\right)=C_{m+n}^n$
Như vậy (3) đúng với $(n+1)$, theo nguyên lý quy nạp ta có điều phải chứng minh.
Vậy (3) là đáp số của bài toán.
Ví dụ 2: Các bạn có thể tham khảo ở đây
Cho tập $E=\{1,2,...,n\};\;\;\;(n\le 9)$ Mỗi tổ hợp gồm $i;\;\;(1\le i\le n)$ phần tử của $E$ là $\{a_1,...,a_i\}$ được sắp tăng dần $(a_1<...<a_i)$ để tạo thành số $\overline{a_1...a_i}$
Gọi $S(i,n)$ là tổng của tất cả các số đó. Tính $S(i,n)$
Lời giải:
Ta tính tổng $S(i,n)$ bằng cách phân ra các số có tận cùng là $k,\;\;(i\le k\le n)$
Nếu số có tận cùng là $k$ thì $i-1$ chữ số đầu sẽ có các chữ số nhỏ hơn $k$, nghĩa là nó là một tổ hợp $i-1$ phần tử của tập $\{1,...,k-1\}$ được sắp thứ tự tăng dần.
Có $C_{k-1}^{i-1}$ số như vậy.
Do đó ta có:
$\Rightarrow S(i,n)=\sum\limits_{k=i}^n\left(10S(i-1,k-1)+kC_{k-1}^{i-1}\right)$
$\Rightarrow S(i,n)=\sum\limits_{k=i}^n\left(10S(i-1,k-1)+iC_k^i\right)$
$\Rightarrow S(i,n)=iC_{n+1}^{i+1}+10\sum\limits_{k=i}^n S(i-1,k-1)$ (Truy hồi)
- Với $i=1$, ta có $S(1,n)=1+...+n=C_{n+1}^2$
- Với $i=2$, ta có $S(2,n)=2C_{n+1}^3+10\sum\limits_{k=2}^n S(1,k-1)=2C_{n+1}^3+10\sum\limits_{k=2}^n C_k^2$
$\Rightarrow S(2,n)=2C_{n+1}^3+10\sum\limits_{k=2}^n \left(C_{k+1}^3-C_k^3\right)=2C_{n+1}^3+10C_{n+1}^3=12C_{n+1}^3$
- Qua 2 trường hợp trên, ta dự đoán được: $\boxed{S(i,n)=\overline{1...i}.C_{n+1}^{i+1}}\;\;\;(*)$
- Ta sẽ chứng minh (*) bằng quy nạp theo $i$
Rõ ràng (*) đúng với $i=1,2$. Giả sử (*) đúng với $(i-1)$ ta sẽ chứng minh nó cũng đúng với $i$
Ta có:
$S(i,n)=iC_{n+1}^{i+1}+10\sum\limits_{k=i}^n S(i-1,k-1)$
$S(i,n)=iC_{n+1}^{i+1}+10.\overline{1...(i-1)}\sum\limits_{k=i}^n C_k^i$ (theo giả thiết quy nạp)
$S(i,n)=iC_{n+1}^{i+1}+\overline{1...(i-1)0}\sum\limits_{k=i}^n \left( C_{k+1}^{i+1}-C_{k+1}^i \right)$
$S(i,n)=iC_{n+1}^{i+1}+\overline{1...(i-1)0}.C_{n+1}^{i+1}$
$S(i,n)=\overline{1..i}.C_{n+1}^{i+1}$
Vậy (*) cũng đúng với $i$, theo nguyên lý quy nạp ta có điều phải chứng minh.
Kết luận: (*) là đáp số cần tìm!
Bài viết đã được chỉnh sửa nội dung bởi hxthanh: 01-11-2011 - 15:53