Welcome to our community

Be a part of something great, join today!

a tough combinatorics problem

mathworker

Active member
May 31, 2013
118
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

Active member
May 31, 2013
118
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,492
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.