Path: utzoo!utgpu!news-server.csri.toronto.edu!mailrus!uwm.edu!rpi!crdgw1!ge-dab!tarpit!peora!petsd!cjh
From: cjh@petsd.UUCP (Chris Henrich)
Newsgroups: comp.theory
Subject: Re: Integer partitioning
Message-ID: <1821@petsd.UUCP>
Date: 25 Jun 90 17:11:36 GMT
References: <7529@ccncsu.ColoState.EDU>
Reply-To: cjh@petsd.UUCP (Chris Henrich)
Organization: Perkin-Elmer DSG, Tinton Falls, N.J.
Lines: 25

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