Chuyen de BD HSG 4

§1. CÔNG THỨC TRUY HỒI
I. VÍ DỤ
Cho số tự nhiên n ( 100. Hãy cho biết có bao nhiêu cách phân tích số n thành tổng của dãy các số nguyên dương, các cách phân tích là hoán vị của nhau chỉ tính là một cách.
Ví dụ: n = 5 có 7 cách phân tích:
1. 5 = 1 + 1 + 1 + 1 + 1
2. 5 = 1 + 1 + 1 + 2
3. 5 = 1 + 1 + 3
4. 5 = 1 + 2 + 2
5. 5 = 1 + 4
6. 5 = 2 + 3
7. 5 = 5
(Lưu ý: n = 0 vẫn coi là có 1 cách phân tích thành tổng các số nguyên dương (0 là tổng của dãy rỗng))
Để giải bài toán này, trong chuyên mục trước ta đã dùng phương pháp liệt kê tất cả các cách phân tích và đếm số cấu hình. Bây giờ ta thử nghĩ xem, có cách nào tính ngay ra số lượng các cách phân tích mà không cần phải liệt kê hay không ?. Bởi vì khi số cách phân tích tương đối lớn, phương pháp liệt kê tỏ ra khá chậm. (n = 100 có 190569292 cách phân tích).
Nhận xét:
Nếu gọi F[m, v] là số cách phân tích số v thành tổng các số nguyên dương ( m. Khi đó:
Các cách phân tích số v thành tổng các số nguyên dương ( m có thể chia làm hai loại:
Loại 1: Không chứa số m trong phép phân tích, khi đó số cách phân tích loại này chính là số cách phân tích số v thành tổng các số nguyên dương < m, tức là số cách phân tích số v thành tổng các số nguyên dương ( m - 1 và bằng F[m - 1, v].
Loại 2: Có chứa ít nhất một số m trong phép phân tích. Khi đó nếu trong các cách phân tích loại này ta bỏ đi số m đó thì ta sẽ được các cách phân tích số v - m thành tổng các số nguyên dương ( m (Lưu ý: điều này chỉ đúng khi không tính lặp lại các hoán vị của một cách). Có nghĩa là về mặt số lượng, số các cách phân tích loại này bằng F[m, v - m]
Trong trường hợp m > v thì rõ ràng chỉ có các cách phân tích loại 1, còn trong trường hợp m ( v thì sẽ có cả các cách phân tích loại 1 và loại 2. Vì thế:
F[m, v] = F[m - 1, v] nếu m > v
F[m, v] = F[m - 1, v] + F[m, v - m] nếu m ( v
Ta có công thức xây dựng F[m, v] từ F[m - 1, v] và F[m, v - m]. Công thức này có tên gọi là công thức truy hồi đưa việc tính F[m, v] về việc tính các F[m`, v`] với dữ liệu nhỏ hơn. Tất nhiên cuối cùng ta sẽ quan tâm đến F[n, n]: Số các cách phân tích n thành tổng các số nguyên dương ( n. Ví dụ với n = 5, bảng F sẽ là:
F
0
1
2
3
4
5

0
1
0
0
0
0
0

1
1
1
1
1
1
1

2
1
1
2
2
3
3

3
1
1
2
3
4
5

4
1
1
2
3
5
6

5
1
1
2
3
5
7


Nhìn vào bảng F, ta thấy rằng F[m, v] được tính bằng tổng của:
Một phần tử ở hàng trên: F[m - 1, v]
và một phần tử ở cùng hàng, bên trái: F[m, v - m].
Ví dụ F[5, 5] sẽ được tính bằng F[4, 5] + F[5, 0], hay F[3, 5] sẽ được tính bằng F[2, 5] + F[3, 2]. Chính vì vậy để tính F[m, v] thì F[m - 1, v] và F[m, v - m] phải được tính trước. Suy ra thứ tự hợp lý để tính các phần tử trong bảng F sẽ phải là theo thứ tự từ trên xuống và trên mỗi hàng thì tính theo thứ tự từ trái qua phải.
Điều đó có nghĩa là ban đầu ta phải tính hàng 0 của bảng: F[0, v] = số dãy có các phần tử ( 0 mà tổng bằng v, theo