1
$\begingroup$

$$ \sum_{i = 1}^nx_i = m,\ x_i>=0,\ m >=0,\ x_i\in W,\ m \in W $$ OR $$ x_1 + x_2 + ...+x_n = m,\ x_1,x_2,..,x_n >= 0,\ m >= 0,\ x_i\in W,\ m \in W $$

I have the expression. I know how to find count of solutions, we can use the Combinations with Repetition: $$ C^m_{(n)} = \frac{(n+m-1)!}{m!(n-1)!} $$ But I don't really know how can I get all solutions. I have to create a program that prints all solutions, but I can't find the algorithm. May be math will help me. Sorry for english.

$\endgroup$
  • $\begingroup$ Actually the no. of solutions is $^{m-1}C_{n-1}$ and not $^{n+m-1}C_{n-1}$. $\endgroup$ – Doubtnut May 23 at 2:18
0
$\begingroup$

I don't know how to create a program but I can help you how to interpret it algebraically.

Now, the value of each variable is integer which lies between $[0, m]$. This is same as distribution of $m$ identical objects to $n$ persons. Here, the identical objects are $m$ $1$'s and persons are the $n$ different variables.

Consider $n$ brackets corresponding to $n$ persons. In each bracket, take an expression given by $(1+x+x^2+\dots+x^m)$. Here, the various powers of $x$ viz: $0,1, 2,\dots,m$ correspond to the number of items each person can have in the distribution.

Since the total number of items is $m$. So, the required number of ways is the coefficient of $x^m$ in the product $$(x^0+x^1 +x^2+...+x^m)(x^0+x^1+x^2+...+x^m)\dots\underbrace{(x^0+x^1+x^2+...+x^m)}_{n-brackets}$$

Thus the required no. of ways $\begin{align} &=\text{Coeff. of}\;x^m\;\text{in}\;(x^0+x^1+x^2+...+x^m)^n\\ &=\text{Coeff. of}\;x^m\;\text{in}\;\left(\frac{1-x^{n+1}}{1-x}\right)^n\\ &=\text{Coeff. of}\;x^m\;\text{in}\;(1-x^{n+1})^n(1-x)^{-n}\\ &=\text{Coeff. of}\;x^m\;\text{in}\;(1-x)^{-n}\\ &={n+m-1\choose n-1} \end{align}$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Pardon me. I had a mistake in my problem statement, and I edited it. Your answer will not change? $\endgroup$ – Wythuk May 23 at 10:01
  • $\begingroup$ Yes, it will change i.e what you mentioned in your questions is correct. I'm editing my solution. I've also made one edit more that $x\in W$ and not $N$, because $0$ doesn't come in $N$. $\endgroup$ – Doubtnut May 23 at 13:08
  • $\begingroup$ Thank you. I edited it. May be this is silly questions, but can you explain what is $ Coeff.\ of x^m\ in\ expression $, and I don't understand you actions of transformations after the string $ =\text{Coeff. of}\;x^m\;\text{in}\;(x^0+x^1+x^2+...+x^m)^n\\ $. Could you advise some resources where can I learn it? $\endgroup$ – Wythuk May 23 at 19:37
  • $\begingroup$ The transformation after the string is that I've wrote it as sum of GP. $\endgroup$ – Doubtnut May 24 at 1:37
  • $\begingroup$ Look, the $n$ bracket corresponds to $n$ persons and the powers of $x$ in each bracket corresponds to the number of objects the person can get in the distribution. Now, multiply the terms of each bracket with all terms in other brackets such that the power of $x$ by multiplying becomes $m$ because that's what max. no. of objects. We've to find all such multiplication combinations of $x$'s which can make the power of $x$ as $m$ i.e the coeff. of $x^m$ in the expansion. $\endgroup$ – Doubtnut May 24 at 1:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.