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

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

Tham khảo

• George E. Andrews, The Theory of Partitions (1976), Cambridge University Press. ISBN 0-521-63766-X .
• Template:Chú thích sách (See chapter 5 for a modern pedagogical intro to Rademacher's formula).
• Template:Hardy and Wright
• Lehmer, D. H. (1939). "On the remainder and convergence of the series for the partition function". Trans. Amer. Math. Soc. 46: 362–373. doi:10.1090/S0002-9947-1939-0000410-9. MR 0000410. Zbl 0022.20401.  Provides the main formula (no derivatives), remainder, and older form for A_k(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_k(n), which is in Whiteman.)
• Template:Chú thích sách (See section I.1)
• Template:Chú thích sách
• 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
• Template:Chú thích sách (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.
• Template:Chú thích sách (qn elementary introduction to the topic of integer partition, including a discussion of Ferrers graphs)
• Template:Chú thích sách
• '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
• Template:MathWorld
• Template:MathWorld
• 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.