Partitions with restrictions


by oleg-mary
Tags: partition
oleg-mary
oleg-mary is offline
#1
Nov4-11, 05:23 PM
P: 3
After long and careful search on the web and in literature,
I could not find the solution of the following problem.

I need calculate p(N,K,L) - the number of partitions of N into
no more than K parts not exceeding L.

Example: N = 7, K = 4, L = 5

1) 2+5
2) 3+4
3) 1+1+5
4) 1+2+4
5) 1+3+3
6) 2+2+3
7) 1+1+1+4
8) 1+1+2+3
9) 1+2+2+2

So, here is p(7,4,5)=9

I found the different formulas for the partitions with different restrictions,
but not both for quantity and size of parts.
May be I was bad looking, but might be the solution has not yet been found?

Of course, it is not a problem to write search algorithms, to solve this problem,
as in Pascal:

*********************************************************************

var K,L,M,i,i1,i2,itog:longint; b:real;
Code:integer;

procedure Box(pr:longint;ostatok:longint;nbox:longint);
var j1,j2,j:longint;
a: real;
begin
a:=ostatok/nbox;
if frac(a)>0
then j1:=trunc(a)+1
else j1:=trunc(a);
if pr>ostatok then j2:=ostatok else j2:= pr;
for j:=j1 to j2 do
if nbox>1 then Box(j,ostatok-j,nbox-1) else itog:=itog+1
end;

begin

val(ParamStr(1),K,Code);
val(ParamStr(2),L,Code);
val(ParamStr(3),M,Code);
{
writeln(K);
writeln(L);
writeln(M);
}
itog:=0;
If L*M<K Then writeln('It is impossible')
Else
begin
If M>K Then i2:=K Else i2:=M;
b:=K/L;
If frac(b)>0 Then i1:=trunc(b)+1 Else i1:=trunc(b);

For i:=i1 to i2 do Box(i,K-i,L-1)

end;
writeln (Itog)
end.

**********************************************************

but it bogged down with a slight increase of parameters.
Roughly speaking, if the value of parameters begins to run into the hundreds,
then modern computer begins to squeak.

Is there some "nice" formula to calculate p(N,K,L) ?
Phys.Org News Partner Science news on Phys.org
Review: With Galaxy S5, Samsung proves less can be more
Making graphene in your kitchen
Study casts doubt on climate benefit of biofuels from corn residue
Ulam
Ulam is offline
#2
Nov5-11, 05:10 AM
P: 5
Nobody knows, but it seems unlikely that a formula exists.
Guffel
Guffel is offline
#3
Nov5-11, 09:26 AM
P: 29
Not really answering your question, but a generating function should not be very hard to find.

Also, check out http://www.btinternet.com/~se16/js/partitionstest.htm if you haven't done that already.

Ulam
Ulam is offline
#4
Nov5-11, 11:31 AM
P: 5

Partitions with restrictions


The question was if there is a "nice" formula, not a "nice" algorithm. The formula, for now, isn't discovered, maybe it doesn't exists, but the algorithm to calculate p(n,l,k) is easy to make.
oleg-mary
oleg-mary is offline
#5
Nov5-11, 03:08 PM
P: 3
Easy-to-make algorithms will go into deep-deep recursion, so it is not easy to make really fast one.
For example, shown code in Pascal will fall even on low parameters like p(200,20,20).
After some thinking I wrote algorithm wich gives result in suitable time for p(125000,500,500).
It uses arbitrary length integer arithmetics and gives result of near thousand bits.
But I need about p(millions,thousands,thousands) job.
Ulam
Ulam is offline
#6
Nov5-11, 06:13 PM
P: 5
In this case the problem is a P problem in information theory, in other words the time to calculate p(n,l,k) is Polynomial, so it will spend more time to calculate p(millions,thousands,thousands). Only a formula will give you a gift, but it is not discovered yet, and maybe it's likely that it doesn't exist.


Register to reply

Related Discussions
Restrictions commutativity General Math 6
Restrictions of compact operators Calculus 1
Number of partitions of [n] with block restrictions Calculus & Beyond Homework 0
Restrictions on Riemann components Special & General Relativity 2