The relation between Integer Partition and Pentagonal Numbers

A partition of an integer n is defined as a way of representing n as a sum of positive integers where the order of the summands does not matter ([1]). The partition function p(n) denotes the number of possible partitions of n. For example, 5 can be represented in 7 different ways:

5
4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

So, p(5) = 7. The value of p(n) grows very quickly as n grows. For example:

p(10) = 42
p(50) = 204226
p(100) = 190569292
p(500) = 2300165032574323995027
p(1000) = 24061467864032622473692149727991
p(5000) = 169820168825442121851975101689306431361757683049829233322203824652329144349
p(10000) = 36167251325636293988820471890953695495016030339315650422081868605887952568754066420592310556052906916435144
p(25000) = 795153665211854316623270592370059262051214684698263936645288037606040374321677412443089599487464373732598268996277510779455269671090533346705889153124159897638140712684550
p(50000) = 3626186097141667844592140891595633728165383082527785049015872755414109904256712082718122747316610565824630881772910217544261659239432670671532413858378256188987333877121891586607957389750538447474712592979263719012461858719791627302489739548263

Though there is a very easy recursive solution to find p(n) by using an intermediate function ([4]), this method is not much suitable for large values of n.

Surprisingly, p(n) can be calculated by using a simple recursive function: ([3])

p(n) = 0 for n < 0
p(0) = 1
p(n) = p(n - 1) + p(n - 2) - p(n - 5) - p(n - 7) + p(n - 12) + p(n - 15) - p(n - 22) - p(n - 26) + ...

At first this equation looks like a total chaos due to the sequence 1, 2, 5, 7, 12, 15, 22, 26, ..., but that is generalized Pentagonal Number sequence([2]) which is defined by:

f(k) = k(3k - 1) / 2 for k = 0, 1, -1, 2, -2, 3, -3, 4, -4, ...

Well, I am not going to prove this relation between integer partition function and pentagonal numbers here, but if anyone is really really interested then try Google and good number theory books.

Thus p(n) can be written simply as:
p(n) = \sum_{k=1}^{\infty} (-1)^{k+1}\{p(n - f(k)) + p(n - f(-k))\}

Finally here is a simple (read it, stupid and not optimized) Python program that exploits the relation between partition function and pentagonal numbers and generates partition values.

import sys

p = [1]

def generate(n):
	for i in range(1, n + 1):
		s = 0
		k = 1
		
		while True:
			f = i - k * (3 * k - 1) / 2
			if f < 0:
				break
			if k % 2:
				s += p[f]
			else:
				s -= p[f]
			
			f = i - k * (3 * k + 1) / 2
			if f < 0:
				break
			if k % 2:
				s += p[f]
			else:
				s -= p[f]
			
			k += 1
		
		p.append(s)
		

def main():
	generate(int(sys.argv[1]))
	
	for i in range(len(p)):
		print i, p[i]

if __name__ == '__main__':
	main()
$ python partition.py 20
0 1
1 1
2 2
3 3
4 5
5 7
6 11
7 15
8 22
9 30
10 42
11 56
12 77
13 101
14 135
15 176
16 231
17 297
18 385
19 490
20 627

Here is a file containing the partition values upto 50000. You can have a look if you are interested (warning: the file is big).

Like always, any feedback is welcome.

[1] Integer Partition
[2] Pentagonal Number
[3] Playing with Partitions on the Computer
[4] Intermediate function

About these ads
This entry was posted in Algorithm and tagged . Bookmark the permalink.

2 Responses to The relation between Integer Partition and Pentagonal Numbers

  1. Pingback: Integer Partition in Java | Off Topic…Sharing stuffs

  2. Thanks Taskinoor for this post. Here goes one supplementary post in response of this: http://azimbabu.wordpress.com/2011/11/21/integer-partition-java/ ;)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s