cjh@petsd.UUCP (Chris Henrich) (06/26/90)
In article <7529@ccncsu.ColoState.EDU> srimani@webber.CS.ColoState.Edu (pradip srimani) writes: >The problem is as follows : Given a positive integer n, let >P(n,m) be the number of ways we can partition them into m >parts. Also let P(n) = sum of all P(n,m) for all possible m. >Note m <= n. What are the closed form expressions for P(n) and >P(n,m) ? ... >Is there any way to compute P(n) efficiently other than >writing a program using the recurrence ? There is a more efficient way to compute P(n), namely a recurrence that involves only P(n) itself. I am not sure that this counts as a closed form, but there is a series expression for P(n) that looks as though it ought to be a divergent asymptotic series, but turns out to converge. The best reference is _Ramanujan_ by G. H. Hardy, in the chapters on Partitions. This book is a series of lectures on the work of the great Indian mathematician Srinavasa Ramanujan. It is in print, in a durable and inexpensive edition. Regards, Chris (201)758-7288 106 Apple Street, Tinton Falls,N.J. 07724
martins@rwthinf.UUCP (Martin Schoenert) (07/03/90)
In his article of 20-Jun-90, P. Srimani wrote about "Integer partitioning":
"The problem is as follows: Given a positive integer n, let P(n,m) be
the number of ways we can partition them into m parts. Also let P(n)
= sum of all P(n,m) for all possible m. Note m <= n. What are the
closed form expressions for P(n) and P(n,m)? Are they known? We
know that P(n,m) satisfies P(n+k,k) = P(n,1) + P(n,2) + ...+ P(n,k)
with P(n,1)=P(n,n)=1. Is there any way to compute P(n) efficiently
other than writing a program using the recurrence?"
And in his article of 22-Jun-90, Marcel Schoppers answered:
"The partitioning problem is well studied. The number P(n,m) is
called the Stirling number of the second kind. The number P(n) is
called the Bell number, and is the number of ways a set of N objects
can be partitioned. ..."
Sorry, but I think you misunderstood the original question. The Stirling
number of the second kind, S2(n,k), is the number of partitions of the
set {1,2,...,n} into k subsets. For example S2(4,2) = 7, corresponding
to the partitions:
{1} {2,3,4} {2} {1,3,4} {3} {1,2,4} {4} {1,2,3}
{1,2} {3,4} {1,3} {2,4} {1,4} {2,3}
The Stirling numbers of the second kind do not fullfill the relation
P(n+k,k) = P(n,1) + P(n,2) + ... + P(n,k), given in the original article.
Instead, the original question was how many ways there are to write the
positive number n as a sum of k positive integers. For example P(4,2) =
2, corresponding to the sums:
1 + 3 2 + 2
Note that there is a connection with Stirling numbers of the second kind;
P(n,k) is the number of partitions of the multi-set {1,1,...,1} into k
subsets. Again P(4,2) = 2, corresponding to {1} {1,1,1} and {1,1} {1,1}.
Is there a common name for those numbers? Note that P(n) is the number
of conjugacy classes of elements in the symetric group on n points. I am
pretty sure that there is no closed formula for P(n,k) and P(n).
The important relation that helps computing P(n,k) and P(n) is the
following:
P(n,k) = P(n-1,k-1) + P(n-k,k) with 1 < k < n
This can be seen by spliting the number of ways to write n as a sum of k
summands in two subsets; those sums that have 1 as a summand and those
that do not.
The number of ways to write n as a sum of k summands that have 1 as a
summand is P(n-1,k-1), because we can take away the 1 and obtain a new
sums with k-1 summands and value n-1.
The number of ways to write n as a sum of k summands such that no summand
is 1 is P(n-k,k), because we can subtract 1 from each summand and obtain
new sums that still have k summands but value n-k.
You can program a recursive function using this relation. However, this
function will call itself quite often with the same arguments. So it is
better to program it as follows:
for m in [1..n] do
P[m][1] := 1;
od;
for k in [2..n] do
for m in [1..k-1] do
P[m][k] := 0;
od;
P[k][k] := 1;
for m in [k+1..n] do
P[m][k] := P[m-1][k-1] + P[m-k][k];
od;
od;
If you are only interested in the value P(n), then you can make use of
the fact that at any time you only need two columns, P[*][m] and
P[*][m-1], to save space. The following program is a reasonably
straightforward transformation of the above program:
p := [];
for k from 1 to n do
p[k] := 1;
od;
s := 1;
for k from 2 to n do
for m from k+1 to n-k+1 do
p[m] := p[m] + p[m-k];
od;
s := s + p[n-k+1];
od;
This is pretty fast. On our MIPS M/120 the computation of P(1000) took
only 16 seconds. I do not think that you can do better than O(n^2)
asymptotically. I would be delighted, however, to be proved wrong.
Martin.
PS. The value of P(1000) is: 24061467864032622473692149727991
! Martin Schoenert, martins@rwthinf.uucp, fm@dacth51.bitnet, +49 241 804551 !
! Lehrstuhl D Mathematik, RWTH, Templergraben 64, D 51 Aachen, West Germany !