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.

$\endgroup$
4
  • $\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, 2016 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, 2016 at 9:08
  • $\begingroup$ @trueblueanil thanks for pointing out my mistake. Corrected now:) $\endgroup$
    – mcjoshi
    Oct 27, 2016 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, 2016 at 9:18

2 Answers 2

Reset to default
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}$

$\endgroup$
4
  • $\begingroup$ here $y_i \geq 1$ right? $\endgroup$
    – mcjoshi
    Oct 27, 2016 at 9:30
  • $\begingroup$ Positive integer means $\geq 1$. $\endgroup$
    – user348749
    Oct 27, 2016 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, 2016 at 9:44
  • 1
    $\begingroup$ Yes, you are correct. $\endgroup$
    – user348749
    Oct 27, 2016 at 9:46
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.

$\endgroup$
7
  • $\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, 2016 at 9:24
  • $\begingroup$ what if we are required to find positive integral solutions only? can same be applied. $\endgroup$
    – mcjoshi
    Oct 27, 2016 at 9:27
  • $\begingroup$ @mcjoshi As you have been given bounds for $x_i$, see that they are positive integers only. $\endgroup$
    – Soham
    Oct 27, 2016 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, 2016 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$
    – Soham
    Oct 27, 2016 at 9:52

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.