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

Revision as of 05:31, 31 May 2017 by TuanminhBot (talk) (Hàm trung gian: replaced: 2 loại → hai loại using AWB)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

thumb|right|300px|Các phần số n với hạng lớn nhất k Template:Chú thích trong bài 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ố 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

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

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 hai 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ú

Tham khảo

Liên kết ngoài

Thể loại:Lý thuyết số Thể loại:Toán học tổ hợp Thể loại:Hàm số học Thể loại:Chuỗi số nguyên