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

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.

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

Ghi chú

Tham khảo
George E. Andrews, The Theory of Partitions (1976), Cambridge University Press. ISBN 0-521-63766-X .
(See chapter 5 for a modern pedagogical intro to Rademacher's formula).

Provides the main formula (no derivatives), remainder, and older form for Ak(n).)
Gupta, Gwyther, Miller, Roy. Soc. Math. Tables, vol 4, Tables of partitions, (1962) (Has text, nearly complete bibliography, but they (and Abramowitz) missed the Selberg formula for Ak(n), which is in Whiteman.)
(See section I.1)

Ken Ono, Distribution of the partition function modulo m, Annals of Mathematics 151 (2000) pp 293–307. (This paper proves congruences modulo every prime greater than 3)
Sautoy, Marcus Du. The Music of the Primes. New York: Perennial-HarperCollins, 2003.
Richard P. Stanley, Enumerative Combinatorics, Volumes 1 and 2. Cambridge University Press, 1999 ISBN 0-521-56069-1
(Provides the Selberg formula. The older form is the finite Fourier expansion of Selberg.)
Hans Rademacher, Collected Papers of Hans Rademacher, (1974) MIT Press; v II, p 100–107, 108–122, 460–475.
(qn elementary introduction to the topic of integer partition, including a discussion of Ferrers graphs)

'A Disappearing Number', devised piece by Complicite, mention Ramanujan's work on the Partition Function, 2007

Liên kết ngoài
Partition and composition calculator
First 4096 values of the partition function
An algorithm to compute the partition function


Pieces of Number from Science News Online
Lectures on Integer Partitions by Herbert S. Wilf
Counting with partitions with reference tables to the On-Line Encyclopedia of Integer Sequences
Integer::Partition Perl module from CPAN
Fast Algorithms For Generating Integer Partitions
Generating All Partitions: A Comparison Of Two Encodings
Amanda Folsom, Zachary A. Kent, and Ken Ono, l-adic properties of the partition function. In press.
Jan Hendrik Bruinier and Ken Ono, An algebraic formula for the partition function. In press.