✨Phân hoạch (lý thuyết số)

thumb|Các phần số n với hạng lớn nhất k

Trong số học, sự phân hoạch một số nguyên dương n là cách viết số đó dưới dạng tổng của các số nguyên dương. Hai cách phân hoạch có các số hạng giống nhau nhưng thứ tự trong tổng khác nhau vẫn được coi chung là một cách phân hoạch. Số lượng các cách phân hoạch số n được tính bởi hàm phân hoạch, ký hiệu là p(n).

Ví dụ

Số 4 có 5 cách phân hoạch:

1. 4
2. 3 + 1
3. 2 + 2
4. 2 + 1 + 1
5. 1 + 1 + 1 + 1

Số 8 có 22 cách phân hoạch:

1. 8
2. 7 + 1
3. 6 + 2
4. 6 + 1 + 1
5. 5 + 3
6. 5 + 2 + 1
7. 5 + 1 + 1 + 1
8. 4 + 4
9. 4 + 3 + 1
10. 4 + 2 + 2
11. 4 + 2 + 1 + 1
12. 4 + 1 + 1 + 1 + 1
13. 3 + 3 + 2
14. 3 + 3 + 1 + 1
15. 3 + 2 + 2 + 1
16. 3 + 2 + 1 + 1 + 1
17. 3 + 1 + 1 + 1 + 1 + 1
18. 2 + 2 + 2 + 2
19. 2 + 2 + 2 + 1 + 1
20. 2 + 2 + 1 + 1 + 1 + 1
21. 2 + 1 + 1 + 1 + 1 + 1 + 1
22. 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

Hàm phân hoạch

Hàm phân hoạch dùng để tính số lượng cách phân hoạch một số nguyên n. Ví dụ có 5 cách phân hoạch số 4 như sau: 1 + 1 + 1 + 1, 1 + 1 + 2, 1 + 3, 2 + 2, 4, nên p(4)=5. Quy ước, p(0)=0 và p(n)=0 với mọi n nguyên âm. Hàm phân hoạch có thể được hình dung thông qua biểu đồ Young.

Thuật toán tính hàm phân hoạch

Một cách để tính hàm phân hoạch là thông qua các hàm trung gian được ký hiệu p(k,n),(n, k là số nguyên dương). p(k,n) là hàm đếm số số cách phân hoạch số n bằng các số tự nhiên lớn hơn hoặc bằng k. Với mọi giá trị k, số cách phân hoạch được đếm bởi p(k,n) gồm hai loại:

• Cách phân hoạch có hạng tử nhỏ nhất bằng k.
• Cách phân hoạch có hạng tử nhỏ nhất lơn hơn k.

Trường hợp thứ nhất có giá trị bằng p(k,n-k). Để hiểu điều này, hãy lập ra một bảng các cách phân hoạch của p(k,n-k). Sau đó thêm "+k" vào mỗi cách phân hoạch.

Trường hợp thứ hai có giá trị bằng p(k+1,n).

Vậy p(k,n)=p(k,n-k)+p(k+1,n).

Quy ước: nếu k>n thì p(k,n)=0. nếu k=n thì p(k,n)=1.