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)*
* [[Marcus du Sautoy|Sautoy, Marcus Du.]] The Music of the Primes. New York: Perennial-HarperCollins, 2003.
* [[Richard P. Stanley]], [http://www-math.mit.edu/~rstan/ec/ *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 ==
* [http://www.se16.info/js/partitions.htm Partition and composition calculator]
* [http://www.numericana.com/data/partition.htm First 4096 values of the partition function ]
* [http://www.numericana.com/answer/numbers.htm#partitions An algorithm to compute the partition function]
* 
* 
* [http://www.sciencenews.org/articles/20050618/bob9.asp Pieces of Number] from [[Science]] News Online
* [http://www.math.upenn.edu/%7Ewilf/PIMS/PIMSLectures.pdf Lectures on Integer Partitions] by Herbert S. Wilf
* [http://www.luschny.de/math/seq/CountingWithPartitions.html Counting with partitions] with reference tables to the On-Line Encyclopedia of Integer Sequences
* [http://metacpan.org/module/Integer::Partition Integer::Partition Perl module] from [[CPAN]]
* [http://www.site.uottawa.ca/~ivan/F49-int-part.pdf Fast Algorithms For Generating Integer Partitions] 
* [http://arxiv.org/abs/0909.2331 Generating All Partitions: A Comparison Of Two Encodings]
* Amanda Folsom, Zachary A. Kent, and Ken Ono, [http://www.aimath.org/news/partition/folsom-kent-ono.pdf *l''-adic properties of the partition function]. In press.
* Jan Hendrik Bruinier and Ken Ono, An algebraic formula for the partition function. In press.