[Math] How to find the restricted partition of n into k *distincts* parts between a finite set [1;r]

combinatoricseuler-maclaurininteger-partitionsnumber theory

It seems to be an opened question.

Indeed, it is easy to find:

  • the number of partitions of n into k distinct parts
  • the number of partitions of n into k parts
  • the number of partitions of n into k parts, each of them less or equal than r and thus the k parts between a finite set [0;r].

However, I have not found any formula for partitions with three restrictions: k parts, k must be distinct, and k must belong to S (S=[1;r]).

To be concrete, what is the number of partition of 60 into 5 distinct parts all of them between [1;50] ?

Best Answer

Actually in your particular example you can remove the "all of them between [1;50]" requirement since any partition of $60$ into $5$ distinct positive parts cannot have a part greater than $50$ (the other four must be at least $1+2+3+4$). In your particular example, the answer is $2611$.

When Java applets worked on the internet, I would have pointed you at my page http://www.se16.info/js/partitions.htm which does the calculation by recursion.

The number of partitions of $n$ into exactly $k$ distinct positive parts each no greater than $r$ is same as the number of partitions of $n-\frac{k(k+1)}{2}$ into up to $k$ (not necessarily distinct) positive parts each no greater than $r-k$: you can subtract $1,2,\ldots,k$ from the smallest, second smallest, ..., largest terms respectively. So in your example the number of partitions of $45$ into up to $5$ positive parts each no greater than $45$ (you see again the point about an unnecessary constraint).

Let's use $f(x,y,z)$ for the number of partitions of $x$ into up to $y$ (not necessarily distinct) positive parts each no greater than $z$. You start with a lot of zeros but $f(0,0,0)=1$ and then use $$f(x,y,z)=f(x,y,z-1)+f(x-z,y-1,z).$$

Related Question