# Integer Partition and Ferrers Diagram

This article is intended to give introduction to **integer partitioning problem**, with numerous reading material, code and explanation aggregated from various Internet sources.

In number theory, a partition of a positive integer n, also called an integer partition, is a way of writing n as a sum of positive integers. Two sums that differ only in the order of their summands are considered to be the same partition; if order matters then the sum becomes a composition. A summand in a partition is also called a part. The number of partitions of n is given by the partition function p(n). – Wikipedia

Partition of number 4:

1. 4

2. 3 + 1

3. 2 + 2

4. 2 + 1 + 1

5. 1 + 1 + 1 + 1

A generating function for p(n) is given by the reciprocal of Euler’s function:

Expanding each term on the right-hand side as a geometric series, we can rewrite it as (1 + x + x^2 + x^3 + …)(1 + x^2 + x^4 + x^6 + …)(1 + x^3 + x^6 + x^9 + …) ….

The number of partitions p(n) is the coefficient of x^n in the expansion of

(1 + x + x^2 + x^3 + …)(1 + x^2 + x^4 + x^6 + …)(1 + x^3 + x^6 + x^9 + …) ….

The objective of this article is to look into the implementation of generating this ferrer’s diagram

Some more Additional Reading:

1 . From Numericana

2 . About Ferrers Diagram

3. An interesting paper that talks about fast algorithms for generating integer partitions.

Thus with these concepts code below displays a Ferrer’s diagram for a given input number and also generate the table using the generate function

#include<stdio.h> #include<stdlib.h> #define false 0; #define true 1; #define Min(x,y) ((x<y)?x:y) typedef struct partitionnode { int m; int numparts; int parts[101]; } partition; int Pn[40][40]; int P[50]; void output(partition a) /*print out the partition a*/ { int i,j; printf("%d = ",a.m); for(i=1;i<=a.numparts;i=i+1) { j = a.parts[i]; printf("%d",j); if (i != a.numparts) printf("+"); } } void RecPartition(partition a, int m, int B, int N) /** generate all partitions with largest part of size at most B ** recursive procedure used in other procedures */ { int i; if(m==0) { a.numparts = N; output(a); printf("\n"); } else { for (i=1;i<=Min(B,m);i=i+1) { a.parts[N+1] = i; RecPartition(a,m-i,i,N+1); } } } void GenPartitions(int m) /*generate all partitions of m*/ { partition a; a.m = m; RecPartition(a,m,m,0); } void EnumPartitions2(int m) /*compute the partition numbers P[i] for i <= m*/ { int i,j,sum,omega,omega2,sign; P[0] = 1; P[1] = 1; for (i=2;i<=m;i=i+1) { sign = 1; sum = 0; omega = 1; j = 1; omega2 = omega+j; while(omega <= i) { if(sign==1) sum = sum + P[i-omega]; else sum = sum - P[i-omega]; if(omega2 <= i) { if(sign==1) sum = sum + P[i-omega2]; else sum = sum - P[i-omega2]; } omega = omega + 3*j+1; j = j+1; omega2 = omega+j; sign = 0 - sign; } P[i] = sum; } } int main() { int m,n,i,j,r,s,num; int flag; partition a; char junk; printf("Enter the Number : \n"); scanf("%d",&m); printf("Ferrers Diagram with m=%d\n\n",m); GenPartitions(m); printf("\nEnd of Ferrers. Press enter to get the table\n"); scanf("%c",&junk); printf("Table with all possible combinations with m=%d \n\n",m); EnumPartitions2(m); printf(" i |"); for(i=1;i<=m;i=i+1) printf("%5d", i ); printf("\n"); printf("-----|"); for(i=1;i<=m;i=i+1) printf("-----"); printf("\n"); printf("P[i] |"); for(i=1;i<=m;i=i+1) printf("%5d",P[i]); printf("\n"); printf("\nPress Enter to Exit\n"); scanf("%c",&junk); return(0); }

I have made minor modification to code already available here . The main intention here is only educational. I was unable to identify the exact author here and give author due credit.

OUTPUT:

laptop:~/code$ ./a.out

Enter the Number :

4

Ferrers Diagram with m=4

4 = 1+1+1+1

4 = 2+1+1

4 = 2+2

4 = 3+1

4 = 4

End of Ferrers. Press enter to get the table

Table with all possible combinations with m=4

i | 1 2 3 4

—–|——————–

P[i] | 1 2 3 5

Press Enter to Exit

laptop:~/code$ ./a.out

Enter the Number :

7

Ferrers Diagram with m=7

7 = 1+1+1+1+1+1+1

7 = 2+1+1+1+1+1

7 = 2+2+1+1+1

7 = 2+2+2+1

7 = 3+1+1+1+1

7 = 3+2+1+1

7 = 3+2+2

7 = 3+3+1

7 = 4+1+1+1

7 = 4+2+1

7 = 4+3

7 = 5+1+1

7 = 5+2

7 = 6+1

7 = 7

End of Ferrers. Press enter to get the table

Table with all possible combinations with m=7

i | 1 2 3 4 5 6 7

—–|———————————–

P[i] | 1 2 3 5 7 11 15

For Perl coders:

There exists a Integer::Partition module. It implements two algorithms from this paper

For Python coders:

There exists an active state discussion

I had a good learning session , hope you did. Hope this article has provided a one stop resource on this topic.

Thanks for Reading !

Hello,

Its a nice work. I am also doing research in Theory of Partitions.

I have some doubts regarding this. Shall we share our ideas.

Please do communicate me through my e-mail: raghava.srinivasa@gmail.com

Regards,

SRINIVASA RAGHAVA. K

Sure i have sent test mail. Probably i can add to this article your ideas and doubts !

how to partition a number if the sequence of number should be in a increasing order i,e 7 into 3 parts 1,2,4 or 8 [1,2,5 ][1,3,4] just plz give me the recurrence relation f(n,k) where n is number k is the number of partition

Let f(n,k) denote the number of ways of partitioning n into exactly k distinct parts.

Then f(n,k) = P(n-

_{k}C_{2},k)where P(n,k) = P(n-1,k-1) + P(n-k,k)

with P(n,k)=0 for k>n and P(n,n) =1 and P(n,0) = 0

P(n,k) denotes the number of ways of writing n as a sum of exactly k terms or, equivalently, the number of partitions into parts of which the largest is exactly k

so for P(5,3) = 2 , since the partitions of 5 of length 3 are {3,1,1} and {2,2,1} and and the partitions of 5 with maximum element 3 are {3,2} and {3,1,1}

Thus let us take n = 8 and partition it into 3 parts in increasing order i.e distinct 3 parts

f(n,k) = P(8-(3), 3) = P(5,3) = 2

Note :

_{3}C_{2}= 3so u got the 2 parts with distinct increasing elements. We only got the count , you might want to find out the exact sets though

I think I was asked this theorem in a Google interview :O Given a number print all sequences of numbers which sum up to k.

k =1 , then {1}

k = 2, then {1+1}

k = 3. then {1+2, 2+1, 1+1+1}

k = 4, then {1+1+1+1, 1+3, 3+1, 2+2}

I could not give a solution which did not generate duplicates. The interviewer, suggested that there could be a bottom-up strategy of finding the # of partitions.