Transcript Partitions of Integers - Department of Computer Science

Partitions of Integers
Prof. Sin-Min Lee
Department of Computer Science
San Jose State University
A numerical partition of an integer n is a
sequence p1 > p2 >· · ·> pk > 0, such that
p1+p2+ · · · +pk = n. Each pi is called a part.
For example, 7+4+4+1+1+1 is a partition of
18 into 6 parts. The number of partitions of n
is denoted p(n) and the number of partitions
of n into k parts is denoted p(n,k).
p(n,k) = p(n-1, k-1) + p(n-k,k)
p(n) = 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135,
176,…..
In 1740, German mathematician Naude wrote to Euler
to ask in how many ways a given positive integer can
be expressed as a sum of r distinct positive integers.
This problem was quickly solved by Euler.
First Euler introduced the idea of a partition of a
positive number n into r parts as a
sequence, n1<n2<…<nr, of positive integers such that
n= n1<n2<…<nr where the ni are the parts.
As an example, the partitions of 4 are:
1 + 1 + 1 + 1, 1 + 1 + 2, 1 + 3, 2 + 2, 4
Below we show a table of the numbers p(n,k) for 0
< k< n < 9.
The partitions on a number n correspond to the set of solutions
(j1,…,jn) to the Diophantine equation
For example, the partitions of four, given by (1, 1, 1, 1), (1, 1,
2), (2, 2), (4), and (1, 3) correspond to the solutions(j1,j2,j3,j4)=
(4,0,0,0) = 4 * 1,
(2, 1, 0, 0) = 2 * 1 + 1 * 2,
(0, 2, 0, 0) = 0 * 1 + 2 * 2,
(0, 0, 0, 1) = 0 * 1 + 0 * 2 + 0 * 3 + 1 * 4,
and
(1, 0, 1, 0).= 1 * 1 + 0 * 2 + 1 * 3
So, there are five different partitions of four.
Euler use p(n) denote the number of partitions of n into
any number of parts, where p(0) = 1.
Ex: p(4) = 5 because there are five different partitions of
four.
In order to study the sequence {p(n)}, he introduced the
concept of a generating function
, and showed that
The partitions of n can be enumerated by a simple recursive
routine:
function partition(n, limit, answer)
{ var i;
if(n > 0)
for(i = min(n, limit); i > 0; i --)
partition(n-i, i, answer now including
i);
else
process the answer }
//partition //initial call:
partition(n, n, initial empty answer);
(1) For each permutation (represented as ) ((1), (2),…., (p1), (p))
Create an array
A1[(1), (2),…., (p-1), (p)]
A2[(1)+ (2), (2)+ (3),…, (p-2)+ (p-1), (p-1)+ (p)]
A3[(1)+ (2)+ (3), (2)+ (3)+ (4),…, (p-3)+ (p-2)+ (p-1),
(p-2)+ (p-1)+ (p)]
…
until
…
Ap[(1)+ (2)+ (3)+…+(p)].
Now create a new array by appending the elements of==
A1,A2,…,Ap together, call this array B.
(2) Use any sorting algorithm sort the numbers in
array B .
(3)
If the sorted number of B is of the form :
1a,2b,3c,… we say the permutation is good, print this
permutation.
Example 1. For example n=4, p=3
The partition (2,1,1) is good.
Example 2.n=6,p=3.
(1,2,3) is not good but
(1,3,2) is good.
The partition (1,2,3) is
not good.
Turn in Thursday (2/26/2004) two separate envelopes containing
the following:
- A report-describing what you discovered from the program
(1) For p=3, what is the maximum n which will produce good
permutations.
(2) Do this for p=4,5,6,7,8.
In your report you should mention what kind of permutation
algorithms and sorting algorithm you are using.