MHB How many combinations of r natural numbers add up to n?

  • Thread starter Thread starter mathworker
  • Start date Start date
  • Tags Tags
    Combinatorics
AI Thread Summary
The discussion centers on finding the number of combinations of r natural numbers that sum to n, a problem related to integer partitions. It highlights that while the partition function provides insights into the total number of partitions, it does not specify partitions of a particular cardinality. A suggestion is made to explore Ivan Niven's book for a deeper understanding, as well as a reference to a StackExchange page for additional insights. An example illustrates that the number of partitions of 6 into 3 summands is three, emphasizing the complexity of the problem when considering combinations versus permutations. The conversation concludes with a note on the distinction between combinations and compositions in this context.
mathworker
Messages
110
Reaction score
0
Find the number of different combinations of $$r$$ natural.numbers that add upto $$n$$

I tried this for quite a fair amount.of.time but.couldn't figure it out.(Punch)
 
Last edited:
Physics news on Phys.org
Re: a tough combonotrics problem

mathworker said:
Find the number of different combinations of $$r$$ natural.numbers that add upto $$n$$

I tried this for quite a fair amount.of.time but.couldn't figure it out.

This is known as the problem of Partitions of an Integer.
Here is a fair webpage on the topic.

If you want print material see Ivan Niven's Mathematics of Choice, chapter six.
 
Thanks for the link,I have gone through it.
But as far as I understood partition function doesn't give the number of partitions of specific cardinality.I mean if we want only the partitions that contains $$r$$ terms for example or can we define a restricted partition function that can do the job?If we can define how can we approximate such restricted $$p(x)$$
 
mathworker said:
Thanks for the link,I have gone through it.
But as far as I understood partition function doesn't give the number of partitions of specific cardinality.I mean if we want only the partitions that contains $$r$$ terms for example or can we define a restricted partition function that can do the job?If we can define how can we approximate such restricted $$p(x)$$

Well I did say that the webpage is only fair. I dislike its notation.
I suggest that you try to find Niven's book.

Example: The number of partitions of 6 into 3 summands is three:
\begin{align*} 6 &= 1+1+4\\ &=1+2+3\\ &=2+2+2\end{align*}

That is p_3(6)-p_2(6).

There is a clear recursive definition of p_k(n).
 
mathworker said:
Find the number of different combinations of $$r$$ natural.numbers that add upto $$n$$
There is a page in StackExchange about this. Of course, the problem is tricky if "combination" is used in its technical sense to mean a set. In contrast, permutations (i.e., ordered sequences) of summands are called compositions (rather than partitions). Their number is simple to figure out.
 
Back
Top