I know how to find the number of partition into distinct parts, which is necessarily equal to the number of ways to divide a number into odd parts. I also know how to partition n into exactly k parts. However, combining the two restrictions, if you limit the number of summands and also say that each summand is unique, then I cannot find a method to either evaluate/approximate this quantity. Please give me some hints or links for the solution.
[Math] Partition an integer $n$ into exactly $k$ distinct parts
combinatoricsinteger-partitions
Related Solutions
In the "Update" (the day after the Question itself was posted), the OP mentions a recursion for counting the partitions of $n$ into $k$ distinct parts, each part at most $M$:
$$ p_k(\leq M, \mathcal{D},n) = p_{k-1}(\leq M-1, \mathcal{D},n-k) + p_k(\leq M-1, \mathcal{D},n-k) $$
and asks "How can I prove this?".
To see this, separate the required partitions on the basis of whether $1$ appears as a summand. If it does, then subtracting $1$ from each summand produces a partition of $n-k$ with exactly $k-1$ distinct parts (since the original summand $1$ disappears), each part at most $M-1$. These partitions are counted by the first term on the right-hand side of the recursion. Otherwise the summand $1$ does not appear, and subtracting $1$ from each part resulting in a partition of $n-k$ with exactly $k$ distinct parts, each part at most $M-1$. These cases are counted by the second term.
Note that a partition of $n$ with $k$ distinct parts exists if and only if $n \ge \binom{k+1}{2}$, because the ascending summands $m_1 + \ldots + m_k = n$ must satisfy $m_i \ge i$. If $n = \binom{k+1}{2}$, then there is just one such partition with $k$ distinct parts, the largest of which is $k$. Repeated application of the recursion will culminate with terms which we can evaluate "by inspection" as either zero or one.
By itself this recursion doesn't seem to give us an especially attractive way of evaluating $p_k(\leq M, \mathcal{D},n)$. Like the recursion for Fibonacci numbers, as a top-down method it suffers from recalculating terms multiple times (giving exponential complexity), so we would be better off working with it as a bottom-up method (giving polynomial complexity).
Better for large parameters is to close the circle with the ideas presented by @NikosM. by showing how the evaluation of $p_k(\leq M, \mathcal{D},n)$ can be reduced to counting restricted partitions without requiring distinct summands.
Prop. Suppose that $n \gt \binom{k+1}{2}$. Then the following are equal:
$(i)$ the number of partitions of $n$ into exactly $k$ distinct parts, each part at most $M$, i.e. $p_k(\leq M, \mathcal{D},n)$
$(ii)$ the number of partitions of $n - \binom{k}{2}$ into exactly $k$ parts, each part at most $M$
$(iii)$ the number of partitions of $n - \binom{k+1}{2}$ into at most $k$ parts, each part at most $M$
Sketch of proof: Once we know the ordered summands of partitions in $(i)$ satisfy $m_i \ge i$, it is easy to visualize their equivalents in $(ii)$ and $(iii)$ by Young tableaux, also called Ferrers diagrams. We remove a "base triangle" of dots corresponding to the first $i$ dots in the $i$th summand (since $m_i \ge i$) to get case $(iii)$, and remove one fewer dot in each summand to preserve exactly $k$ summands in case $(ii)$. These constructions are reversible, and the counts are equal.
Remark 1 If $n \le \binom{k+1}{2}$, $p_k(\leq M, \mathcal{D},n)=1$ if $n=\binom{k+1}{2}$ and $k \le M$ and otherwise $p_k(\leq M, \mathcal{D},n)=0$.
Remark 2 For fixed $k,n$, suppose $M_0 = n - \binom{k}{2} \gt 0$. Then for all $M \ge M_0$, $p_k(\leq M, \mathcal{D},n) = p_k(\leq M_0, \mathcal{D},n)$. That is, further increasing the upper bound $M$ on the size of parts will not yield additional partitions of $n$ with exactly $k$ distinct parts.
Recommended Reading
Andrews, George E. The Theory of Partitions (Cambridge University Press, 1998)
A modern classic for theory of integer partitions, reviewed by Richard Askey in BAMS.
[Math] How to find the restricted partition of n into k *distincts* parts between a finite set [1;r]
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
- [Math] Integer partitions of $N$ into three distinct parts
- How do you find the number of unique parts in a partition of an integer $n$ into $k$ parts
- A question about integer partitions
- Partitions into distinct even summands and partitions into (not necessarily distinct) summands of the form $4k-2,k\in\Bbb N$
Best Answer
If you partition $n$ into exactly $k$ distinct parts, then the $i$-th smallest part must be at least $i$, therefore strictly larger than $i-1$. So you can start reserving $i-1$ units for the $i$-th smallest part, which amount to a total of $\binom k2$ reserved units. Then (assuming $n\geq\binom{k+1}2$ without which no solution is of course possible) you can find a partition of $n-\binom k2$ into exactly $k$ parts, and then add the $i-1$ reserved units to the $i$-th smallest part of that partition (it may be ex-aequo with another part, but after these additions it will be distinct from any other parts, and exactly $i$-th smallest among them). This gives every partition of $n$ into exactly $k$ distinct parts exactly once.
The reason for not reserving $i$ parts is than you would then need a partition of $n-\binom{k+1}2$ into at most $k$ parts, and this case did not occur in the list of cases you said you knew how to handle. But in any case, the number of ways to partition any $m$ into at most $k$ parts is equal to the number of ways to partition $m+k$ into exactly $k$ parts, by a similar argument (reserve one unit for each part).