0
$\begingroup$

Find the number of integral solutions for the equation $x_1+ x_2 + x_3 + x_4 + x_5 + x_6 = 31$

where $x_1 ≥ 1, x_2 ≥ 2, x_3 ≥ 2, x_4 ≥ 4, x_5 ≥ 6, x_6 ≥ 5?$

I have no idea how to proceed here ? I read somewhere that this question can also be done using generating function, an approach using generating function's will be appreciated.

|cite|improve this question
$\endgroup$
  • $\begingroup$ Call $x_1'=x_1-1, x_2'=x_2-2$ and so on. Then you have to solve how many solutions for $x_1'+ \dots + x_6' = 31-1-2-2-4-6-5$ for nonnegative integers $x_i'$. $\endgroup$ – Crostul Oct 27 '16 at 9:04
  • $\begingroup$ It isn't specified that $x_i's$ are integers. So how many solutions can then be there ? $\endgroup$ – true blue anil Oct 27 '16 at 9:08
  • $\begingroup$ @trueblueanil thanks for pointing out my mistake. Corrected now:) $\endgroup$ – mcjoshi Oct 27 '16 at 9:10
  • 1
    $\begingroup$ Just look around some and you will get your question answered plenty times. E.g math.stackexchange.com/questions/1171340/… $\endgroup$ – ctst Oct 27 '16 at 9:18
1
$\begingroup$

If it is given, $x_i \geq a_i,$ we may say $x_i=y_i+a_i(y\geq0). [i=1,2,...,r]$

So, $\sum x_i=n$ can be transformed to $\sum (y_i+a_i)=n\implies \sum y_i=n- \sum a_i=N.$

Now, you know that the number of solutions to this equation as $y \geq 0$ is $\binom{N+r-1}{r-1}.$

Hope this helps you solve the probelem yourslf as it's always more fun to do so.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ $(y_1 - 1) + (y_2 - 2) +(y_3 - 2) + (y_4 - 4) + (y_5 - 6) + (y_6 - 5) = 31$. So, $\sum_{i=1}^6 y_i = 11$ and number of non-negative solutions is equal to coefficient of $x^{11}$ in expansion of $(1-x)^{-6}$ which is equal to $\left(\begin{array}{c}16\\ 11\end{array}\right)$ $\endgroup$ – mcjoshi Oct 27 '16 at 9:24
  • $\begingroup$ what if we are required to find positive integral solutions only? can same be applied. $\endgroup$ – mcjoshi Oct 27 '16 at 9:27
  • $\begingroup$ @mcjoshi As you have been given bounds for $x_i$, see that they are positive integers only. $\endgroup$ – tatan Oct 27 '16 at 9:47
  • $\begingroup$ Ohh! i get it now I confused $y_i$ as the solution which includes $y_i = 0$ too, but the actual solutions are $x_i$ which are positive integrals. Thanks! $\endgroup$ – mcjoshi Oct 27 '16 at 9:51
  • 1
    $\begingroup$ @mcjoshi As $y_i$ are non-negative, we use $\binom{N+r-1}{r-1}$. If $y_i$ were positive then we would have used $\binom {N-1}{r-1}$. Do some research yourself, This is a very common problem. $\endgroup$ – tatan Oct 27 '16 at 9:52
2
$\begingroup$

Let $y_1 = x_1, y_2 = x_2-1, y_3 = x_3-1, y_4 = x_4-3, y_5 = x_5-5, y_6 = x_6 - 4$. Then $y_1+y_2+y_3+y_4+y_5+y_6 = 17$ and we have all $y_i$ positive integers. The number of solutions, by stars and bars method is $\binom{16}{5}$

|cite|improve this answer
$\endgroup$
  • $\begingroup$ here $y_i \geq 1$ right? $\endgroup$ – mcjoshi Oct 27 '16 at 9:30
  • $\begingroup$ Positive integer means $\geq 1$. $\endgroup$ – user348749 Oct 27 '16 at 9:37
  • $\begingroup$ Yes i know that, i mean to say $y_1+y_2+y_3+y_4+y_5+y_6 = 11$ when $y_i \geq 0$ gives $\left(\begin{array}{c}16\\ 5\end{array}\right)$ $\endgroup$ – mcjoshi Oct 27 '16 at 9:44
  • 1
    $\begingroup$ Yes, you are correct. $\endgroup$ – user348749 Oct 27 '16 at 9:46

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.