Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

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 parition 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 disctinct 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 parition 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).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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