Welcome to our community

Be a part of something great, join today!

a tough combinatorics problem

mathworker

Well-known member
May 31, 2013
119
Find the number of different combinations of \(\displaystyle r\) natural.numbers that add upto \(\displaystyle n\)
[HR][/HR]I tried this for quite a fair amount.of.time but.couldn't figure it out.(Punch)
 
Last edited:

Plato

Well-known member
MHB Math Helper
Jan 27, 2012
196
Re: a tough combonotrics problem

Find the number of different combinations of \(\displaystyle r\) natural.numbers that add upto \(\displaystyle n\)
[HR][/HR]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.
 

mathworker

Well-known member
May 31, 2013
119
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 \(\displaystyle 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 \(\displaystyle p(x)\)
 

Plato

Well-known member
MHB Math Helper
Jan 27, 2012
196
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 \(\displaystyle 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 \(\displaystyle 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:
[TEX] \begin{align*} 6 &= 1+1+4\\ &=1+2+3\\ &=2+2+2\end{align*}[/TEX]

That is [TEX]p_3(6)-p_2(6).[/TEX]

There is a clear recursive definition of [TEX]p_k(n). [/TEX]
 

Evgeny.Makarov

Well-known member
MHB Math Scholar
Jan 30, 2012
2,528
Find the number of different combinations of \(\displaystyle r\) natural.numbers that add upto \(\displaystyle 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.