How many combinations of natural numbers add up to another?

[mathmaniac1]

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]

If we have a set of cardinality $n$:

$$A=\{x_1,x_2,x_2,\cdots,x_n\}$$

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

$$N=2^n$$

However, this implies that the elements are distinct.

 

[mathmaniac1]

If we have a set of cardinality $n$:

$$A=\{x_1,x_2,x_2,\cdots,x_n\}$$

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

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

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

$$\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]

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]

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.

 

[mathmaniac1]

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]

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$

 

[mathmaniac1]

I am kind of asking how many terms with distinct coefficients will there be in the multinomial formula.

 

[Jameson]

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.

 

[Nono713]

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

 

[Ackbach]

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.

 

[mathmaniac1]

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.

 

[mathmaniac1]

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]

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.

 

[mathmaniac1]

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]

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

 

[mathmaniac1]

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

 

[mathworker]

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

 

[mathmaniac1]

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]

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

 

[mathmaniac1]

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.