Welcome to our community

Be a part of something great, join today!

How many combinations of natural numbers add up to another?

mathmaniac

Active member
Mar 4, 2013
188
Given n numbers x1,x2.....xn belong to N.
x1+x2+x3....xn=m
How many different combinations of x1,x2,x3.....xn are there?Is there any formula useful here?
Note:x1,x2,x3.... need not be distinct and also can be 0.

Thanks
 

MarkFL

Administrator
Staff member
Feb 24, 2012
13,775
If we have a set of cardinality $n$:

\(\displaystyle A=\{x_1,x_2,x_2,\cdots,x_n\}\)

Then it can be shown that the number $N$ of subsets is:

\(\displaystyle N=2^n\)

However, this implies that the elements are distinct.
 

mathmaniac

Active member
Mar 4, 2013
188
If we have a set of cardinality $n$:

\(\displaystyle A=\{x_1,x_2,x_2,\cdots,x_n\}\)

Then it can be shown that the number $N$ of subsets is:

\(\displaystyle N=2^n\)

However, this implies that the elements are distinct.
I don't understand.What is N?And m is seen nowhere in your formula.And you also say the elements are distinct.So please tell me what did you mean to convey through the above post.

Thanks
 

MarkFL

Administrator
Staff member
Feb 24, 2012
13,775
...So please tell me what did you mean to convey through the above post.

Thanks
To be honest, I really wasn't sure what you are asking, so I took a stab at offering something that might help you. You state:

\(\displaystyle \sum_{k=1}^n x_k=m\)

Are you asking how many different ways the addends may be ordered? If this is the case, then it would simply be $n!$.

Can you give an example of what you are wishing to find?
 

chisigma

Well-known member
Feb 13, 2012
1,704
Given n numbers x1,x2.....xn belong to N.
x1+x2+x3....xn=m
How many different combinations of x1,x2,x3.....xn are there?Is there any formula useful here?
Note:x1,x2,x3.... need not be distinct and also can be 0.

Thanks
The number of combinations is given by the so called 'multinomial coefficient' and is...


$$ N= \frac{m!}{x_{1}!\ x_{2}!\ ...\ x_{n}!}\ (1)$$

Kind regards


$\chi$ $\sigma$
 

Jameson

Administrator
Staff member
Jan 26, 2012
4,043
All of the above posts are helpful and correct, but we really need to have more details to tell you which formula to use. It depends on if you must use all of the elements and if order matters.
 

mathmaniac

Active member
Mar 4, 2013
188
Example:

m=3,n=2
So the possible combinations are 03,12.

Clear?
n means the number of x1,x2....

And yes,order matters.
 

chisigma

Well-known member
Feb 13, 2012
1,704
One of the most remarkable application of multinomial coefficients is the 'polynomial formula'...

$$ (x_{1} + x_{2} + ... + x_{p})^{n} = \sum \frac{n!}{n_{1}!\ n_{2}!\ ...\ n_{p}!}\ x_{1}^{n_{1}}\ x_{1}^{n_{1}}\ ...\ x_{p}^{n_{p}}\ (1)$$

... where the sum is extended to any non negative integers for which is $n_{1} + n_{2} + ... + n_{p}=n$...

Kind regards

$\chi$ $\sigma$
 

mathmaniac

Active member
Mar 4, 2013
188
I am kind of asking how many terms with distinct coefficients will there be in the multinomial formula.
 

Jameson

Administrator
Staff member
Jan 26, 2012
4,043
Example:

m=3,n=2
So the possible combinations are 03,12.

Clear?
n means the number of x1,x2....

And yes,order matters.
If order matters then those are not all of the possible combinations. That would mean that 03 is different than 30. It sounds like there are $m+1$ elements and you are putting them into $n$ groups but it's hard to tell from your description.
 

Bacterius

Well-known member
MHB Math Helper
Jan 26, 2012
644
[JUSTIFY]The problem as stated is rather ambiguous. Do you mean to find the number of different combinations $(x_1, x_2, \cdots, x_n)$ such that their sum adds up to $m$? If so, you can use generating functions or statistics to attack this problem, I don't have time right now but the answer is a binomial coefficient, I believe $\binom{n - 1 + m}{m}$ from memory but it is a fairly simple problem.

But that is only true if zero is excluded. If it is, you can break down the problem by considering $n'$ integers to add up to $m$, with $0 < n' \leq n$, where each of these is nonzero, and add up the results.

If order matters, multiplying by $n!$ should do it, but I don't know. I am not very good at these kinds of statistics.[/JUSTIFY]
 

Ackbach

Indicium Physicus
Staff member
Jan 26, 2012
4,193
Given n numbers x1,x2.....xn belong to N.
x1+x2+x3....xn=m
How many different combinations of x1,x2,x3.....xn are there?Is there any formula useful here?
Note:x1,x2,x3.... need not be distinct and also can be 0.

Thanks
It looks to me like you are talking about either partitions, if order does not matter, or compositions, if order does matter. If so, then I would say this thread belongs in Number Theory.

MathWorld has another take on this problem. The number of partitions with a given number $S$ of parts is not a trivial problem, it seems.
 
Last edited:

mathmaniac

Active member
Mar 4, 2013
188
If order matters then those are not all of the possible combinations. That would mean that 03 is different than 30. It sounds like there are $m+1$ elements and you are putting them into $n$ groups but it's hard to tell from your description.
Sorry by order matters,I mean the other way,that you have to look out that an order is not repeated.

Not m+1 elements necessarily,it could be any n elements.that add up to m.
 
Last edited:

mathmaniac

Active member
Mar 4, 2013
188
It looks to me like you are talking about either partitions, if order does not matter, or compositions, if order does matter. If so, then I would say this thread belongs in Number Theory.

MathWorld has another take on this problem. The number of partitions with a given number $S$ of parts is not a trivial problem, it seems.
4=4=3+1=2+2=2+1+1=1+1+1+1

Here m=4,but there is no n.For eg:if n=2
Then the combinations I need are
(3,1),(4,0),(2,2)
 

Ackbach

Indicium Physicus
Staff member
Jan 26, 2012
4,193
4=4=3+1=2+2=2+1+1=1+1+1+1

Here m=4,but there is no n.For eg:if n=2
Then the combinations I need are
(3,1),(4,0),(2,2)
Right. As mentioned above, finding the number of partitions of a number with a given number of numbers is not a trivial task, apparently. There's not a nice neat formula for it.

In the MathWorld link, right around Equation 58, there's a section dealing with the computation of the numbers you're after.
 

mathmaniac

Active member
Mar 4, 2013
188
I have saved the page but it's a pretty big one and will take time to read.And I also don't think I will be able to understand it.

So there is no formula?:(I was looking for someway to assure whether I have written all combinations in the multinomial formula.

Thanks anyway.
 

mathworker

Active member
May 31, 2013
118
may the formula you asked is m+r-1Cr-1 for
x1+x2+....xr=m and the proof i am in a little mess about it right now i will surely come to it again my maths teacher used to prove this many a times
 

mathmaniac

Active member
Mar 4, 2013
188
Yaah,recently I am finding more connections of this problem to the r-multiset equation...
I will be waiting for your answer.
 

mathworker

Active member
May 31, 2013
118
okay the proof goes with prior knowledge in binomial theorem,
x1+x2+x3...xr=n(xi can be zero as given)
the question is an algebraic analogy dividing n identical objects among r different groups , that means,
coefficient of x^n in the expansion (x^0+x^1+.....x^n)^r (if you didn't understand this section report me (Wait))
multiplying with 1-x on numerator and denominator
we get
(1-x^(n+1))^r/(1-x)^r=(1-x^n+1)^r*(1-x)^-r,
hence coefficient x^n can only be found in (1-x)^-r
which is equal coefficient of x^n in sigma(n=0 to infinite) n+r-1Cr-1*x^n....:D
hence number of ways is n+r-1Cr-1
sorry that i didn't use latex(i have to learn) hope you understand the procedure
 

mathmaniac

Active member
Mar 4, 2013
188
multiplying with 1-x on numerator and denominator
we get
(1-x^(n+1))^r/(1-x)^r=(1-x^n+1)^r*(1-x)^-r,
hence coefficient x^n can only be found in (1-x)^-r
which is equal coefficient of x^n in sigma(n=0 to infinite) n+r-1Cr-1*x^n....:D
hence number of ways is n+r-1Cr-1
sorry that i didn't use latex(i have to learn) hope you understand the procedure
what you do with 1-x is not clear,mathworker.

Maybe I have to get myself a paper and pen.

Thanks anyway
 

mathworker

Active member
May 31, 2013
118
what you do with 1-x is not clear,mathworker.

Maybe I have to get myself a paper and pen.

Thanks anyway
1-x^n=(1-x)(1+x+x^2+...x^n-1):D
 

mathmaniac

Active member
Mar 4, 2013
188
n+r-1Cr-1
There is an easier proof with the numbers considered as writing r 1s and n 0s.For example for n=4 and r=3
we can write one of the combinations,say 130
as 1011100.The last zero is compulsory.

But if i order matters,the problem is bigger,each of the combination is permuted different times,which makes it harder to find a good formula.