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

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm
Các phần số n với hạng lớn nhất k

Trong số học, sự phân tí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 tích có các số hạng giống nhau được coi là một cách phân tích. Số lượng cách phân tích số n được tính bởi hàm phân tích, kí hiệu là p(n).

Ví dụ[sửa | sửa mã nguồn]

Số 4 có 5 cách phân tí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 tí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 tích[sửa | sửa mã nguồn]

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

Hàm trung gian[sửa | sửa mã nguồn]

Một cách để tính hàm phân tích là thông qua hàm trung gian, kí hiệu p(k,n),(n, k là số nguyên dương). p(k,n) là hàm đếm số lượng cách phân tí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, cách phân tích được đếm bởi p(k,n) gồm 2 loại:

  • Cách phân tích có hạng tử nhỏ nhất bằng k.
  • Cách phân tí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 tích của p(k,n-k). Sau đó thêm "+k" vào mỗi cách phân tí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.

Một số giá trị p(k,n):

k
1 2 3 4 5 6 7 8 9 10
n 1 1
2 2 1
3 3 1 1
4 5 2 1 1
5 7 2 1 1 1
6 11 4 2 1 1 1
7 15 4 2 1 1 1 1
8 22 7 3 2 1 1 1 1
9 30 8 4 2 1 1 1 1 1
10 42 12 5 3 2 1 1 1 1 1

Ghi chú[sửa | sửa mã nguồn]

Tham khảo[sửa | sửa mã nguồn]

Liên kết ngoài[sửa | sửa mã nguồn]