For example $x_1+x_2=4$. The natural solutions are
$(1,3);(2,2);(3,1)$.The formula giving the number of ways for this is
$\binom{n-1}{r-1}=\binom{3}{1}=3$.But how to find a formula which will
return the number of ways as only ${\{1,3\}}$ or ${\{2,2\}}$?
Ok so let me explicitly write my question.
What is number of ways in which a natural number can be expressed as a
sum of natural numbers according to a equation like $x_1+x_2+…+x_r=n$?Is there any formula as such?I mean I don't want repeated solutions like $(1,2,3)$ and then again $(2,3,1)$.
I want a formula which neglects the arrangement of the numbers but only gives the set of numbers which add up to a certain natural number.
So what would be the necessary algorithm or formula?
Best Answer
Much depends on whether you want just the count of such arrangements or to list all of them.
If you were to "neglect" the arrangement of summands, as your example $4=3+1=1+3$ and $4=2+2$ suggests, then you are asking about integer partitions.
Efficient ways to count these are known, and it can even be said there exists an exact formula. The book The Theory of Partitions by George Andrews (1976) has the details. See the section Approximation formulas of the Wikipedia article for the convergent series called the Hardy–Ramanujan–Rademacher formula.
If instead you want to (say) write a program to list all the possible integer partitions, then this is an easier task (although such a program might run a long time for all but the smallest inputs). With the limitation of the largest summand to be allowed, one can express the task recursively:
If $M$ is the largest summand allowed to express $N$, choose some multiple $k$ of those summands $M$ to be used (descending from $\lfloor N/M \rfloor$ to 0).
For each such choice $k \ge 0$, recursively list all the possible integer partitions of $N - kM$ allowing summands at most $M-1$ to be used, prefixed by $k$ copies of summand $M$.