Separate a number into fixed part

Question

What is the algorithm to find the number way to separate number M to p part and no two part equal. Example: M = 5, P = 2 they are (1,4) (2,3). If P = 3 then no partition availabe, i.e not (1,2,2) because there two 2 in partition.

Answer 1

In the expanded product

(1+x)(1+x²)(1+x³)...(1+xⁿ)

find the coefficient of x^n. This gives the number of any possibility to represent n as sum of different numbers, i.e., a variable number of terms.

---

You want the number of possibilites to have

n = i₁+i₂+...+i_P with i₁ < i₂ < ... < i_P

which can be realized by setting

i₁=j₁, i₂=i₁+j₂=j₁+j₂, ...

i_P=i_P-1+j_P=j₁+j₂+...+j_P with all j_k > 0

so that the original task is the same as counting all the ways that one can solve

n = P * j₁+(P-1) * j₂+...+1 * j_P with all j_k > 0, but unrelated among each other.

The corresponding generator function is the product of the geometric series of the powers of x, omitting the constant term,

(x+x²+x³+...) * (x²+x⁴+x⁶+...) * (x³+x⁶+x⁹+...) * ... * (x^P+x^2*P+x^3*P+...)

= x^P*(P+1)/2 * (1+x+x²+...) * (1+x²+x⁴+...) * (1+x³+x⁶+...) * ... * (1+x^P+x^2*P+...)

Clearly, one needs n >= P*(P+1)/2 to get any solution at all. For P=3 that bound is n >= 6, so that n=5 has indeed no solutions in that case.

---

Algorithm

count = new double[N]
for k=0..N-1 do count[k] = 1
for j=2..P do
    for k=j..N-1 do
        count[k] += count[k-j]

Then count[k] contains the number of combinations for n=P*(P+1)/2+k.