2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Sorry, do you specifically want the sum of TWO natural numbers? Not general sums like $4=1+1+1+1$? $\endgroup$ – lulu Sep 24 '16 at 11:25
  • $\begingroup$ @lulu No.Not specifically two. $\endgroup$ – user220382 Sep 24 '16 at 11:26
  • $\begingroup$ So...why is your illustration for $4$ correct? $\endgroup$ – lulu Sep 24 '16 at 11:26
  • 1
    $\begingroup$ this article specifically discusses partitions of fixed length. $\endgroup$ – lulu Sep 24 '16 at 11:38
  • 2
    $\begingroup$ Partitions are extremely complicated! I agree, that's a bit unexpected. For pairs you can do better...they are just $\{i,n-i\}$ for $i\in [1,\lfloor \frac n2\rfloor]$. But for general collections, generating functions are really the best approach. $\endgroup$ – lulu Sep 24 '16 at 11:44
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Inserted "not" by mistake in that sentence.Pardon me _/\_!Thank you for the answer btw. $\endgroup$ – user220382 Sep 24 '16 at 14:15
  • $\begingroup$ nice answer and thank you for you review :) $\endgroup$ – user354674 Sep 27 '16 at 15:45

Your Answer

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