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:

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

== 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:

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

== 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 A(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 A(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.