- Thread starter
- #1

#### mathmaniac

##### Active member

- Mar 4, 2013

- 188

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

- Thread starter mathmaniac
- Start date

- Thread starter
- #1

- Mar 4, 2013

- 188

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

- Admin
- #2

- Thread starter
- #3

- Mar 4, 2013

- 188

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

Thanks

- Admin
- #4

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:...So please tell me what did you mean to convey through the above post.

Thanks

\(\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?

- Feb 13, 2012

- 1,704

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

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

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

Kind regards

$\chi$ $\sigma$

- Admin
- #6

- Jan 26, 2012

- 4,055

- Thread starter
- #7

- Mar 4, 2013

- 188

m=3,n=2

So the possible combinations are 03,12.

Clear?

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

And yes,order matters.

- Feb 13, 2012

- 1,704

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

- Thread starter
- #9

- Mar 4, 2013

- 188

- Admin
- #10

- Jan 26, 2012

- 4,055

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.

m=3,n=2

So the possible combinations are 03,12.

Clear?

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

And yes,order matters.

- Jan 26, 2012

- 644

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]

- Admin
- #12

- Jan 26, 2012

- 4,198

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.

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

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:

- Thread starter
- #13

- Mar 4, 2013

- 188

Sorry by order matters,I mean the other way,that you have to look out that an order is not repeated.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.

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

Last edited:

- Thread starter
- #14

- Mar 4, 2013

- 188

4=4=3+1=2+2=2+1+1=1+1+1+1It 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.

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)

- Admin
- #15

- Jan 26, 2012

- 4,198

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

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

- Thread starter
- #16

- Mar 4, 2013

- 188

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

Thanks anyway.

- May 31, 2013

- 119

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

- Thread starter
- #18

- Mar 4, 2013

- 188

I will be waiting for your answer.

- May 31, 2013

- 119

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 )

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

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

- Thread starter
- #20

- Mar 4, 2013

- 188

what you do with 1-x is not clear,mathworker.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....

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

Maybe I have to get myself a paper and pen.

Thanks anyway

- May 31, 2013

- 119

1-x^n=(1-x)(1+x+x^2+...x^n-1)what you do with 1-x is not clear,mathworker.

Maybe I have to get myself a paper and pen.

Thanks anyway

- Thread starter
- #22

- Mar 4, 2013

- 188

There is an easier proof with the numbers considered as writing r 1s and n 0s.For example for n=4 and r=3n+r-1Cr-1

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.