After long and careful search on the web and in literature,(adsbygoogle = window.adsbygoogle || []).push({});

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) ?

**Physics Forums - The Fusion of Science and Community**

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Partitions with restrictions

Loading...

Similar Threads - Partitions restrictions | Date |
---|---|

Why do the conjugate classes of a group partition the group? | Jan 21, 2015 |

Cosets / Partitions | Dec 17, 2014 |

Partitioning a Group Into Disjoint Subgroups | Aug 29, 2014 |

Sum_{k=0n} p(k) where p(k) = number of partitions of k | Nov 5, 2012 |

Restriction of a Linear Transformation | May 16, 2011 |

**Physics Forums - The Fusion of Science and Community**