3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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).$$

$\endgroup$
  • $\begingroup$ Can you elaborate on that equivalence from distinct to non-distinct partitions please? $\endgroup$ – Joffan Jan 13 '15 at 21:09
  • 1
    $\begingroup$ I have added "you can subtract $1,2,…,k$ from the smallest, second smallest, ..., largest terms respectively" $\endgroup$ – Henry Jan 13 '15 at 21:18
  • $\begingroup$ OK, thanks, I get it, you are transforming the distinct partition into the, um, indistinct case. To me it would be clearer to describe the reverse process, which is (presumably) to add 1, 2, 3 etc to the partitions in ascending order of size. $\endgroup$ – Joffan Jan 13 '15 at 21:30
  • $\begingroup$ Exactly what you add/subtract depends on the question and whether you can. If your "indistinct case" had an exact number of terms you would instead add $0,1,2,\ldots$. Enjoy the first half of the code at se16.info/js/PartitionChoice.java which turns $36$ formulations of the question into $13$ recurrences; I suspect fewer is possible. $\endgroup$ – Henry Jan 13 '15 at 21:38
  • $\begingroup$ OK thanks, I am afraid I don't understand it entirely. Your idea is that the number of partition of 60 into exactly 5 distinct integers taken into [1;50] is the same as the number of partitions of 45 into up to 5 (i.e partition with two terms exactly + three terms exactly + four...terms) not specifically distinct term taken into [1;45]. When I compute this with a little code since I know the formulae to get the number of partition with non distinct terms, I finally find 135 751 partitions which far most important than 2611. $\endgroup$ – Eddy Jan 15 '15 at 11:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.