recategorized by
804 views
1 votes
1 votes
  • How many solutions are there to the equation x1+x2+x3+x=17 where xi is non negative?

  • Please explain how this problem has 1 to 1 correspondence with the solution of reordering of 17     1's   and 3  0's.

 

  • How many solutions are there to the equation x1+x2+x3+x4+x5+x6  =29 where xi is non negative such that x1<=5?

recategorized by

2 Answers

1 votes
1 votes
a)

 xi  can take value from 0 to 17

so required slution is ---

coeff of x17 in the given expression

 (x0+x1+x2+..... +x15+x16+x17)(x0+x1+x2+..... +x15+x16+x17)(x0+x1+x2+..... +x15+x16+x17)(x0+x1+x2+..... +x15+x16+x17)

which is $\binom{17+4-1}{17}$ 

b) here xi can take value from 0 to 5

so required slution is ---

coeff of x29 in the given expression

 (x0+x1+x2+x3+x4+x5)(x0+x1+x2+x3+x4+x5)(x0+x1+x2+x3+x4+x5)(x0+x1+x2+x3+x4+x5)(x0+x1+x2+x3+x4+x5)(x0+x1+x2+x3+x4+x5)  [6 times because variable is 6(x1 to x6)]

= coeff of x29 in expression $\frac{ (x6 -1)^{6}}{x-1}$

= $\binom{6}{4}*1 + \binom{6}{3}*1 + \binom{6}{2}*1 + \binom{6}{1}*1 + \binom{6}{0}*1$  [$\binom{6}{6} + \binom{6}{5}$ is not in ans because x6*6 and x6*5 is greater than x29 and all power of x in (x-1)-1 is 1

0 votes
0 votes

1: No. of solutions

= $\binom{4+17-1}{17} = \binom{20}{17}$

2: Total solutions with no upper limit on $x_1$ - No. of solutions with lower limit on x1 as $6 \leq x_1$

= $\binom{29+6-1}{29} - \binom{23+6-1}{23}$ = 278256 - 98280 = 179976

Or, if you are interested in solving with generating functuions :

https://gateoverflow.in/?qa=blob&qa_blobid=11255772522350385173

2. solution using generating function :

Upper bound is given on x1

Generating function: (answer is  = coefficient of $x^{29}$)

$\\ => G(x) = (1+x+x^2+x^3+x^4+x^5)(1+x+x^2+x^3+.....\infty )^5 \\ \\ => G(x) = (1+x+x^2+x^3+x^4+x^5)\frac{1}{(1-x)^5} \\ \\ => G(x) = (1+x+x^2+x^3+x^4+x^5)\left [ \sum_{r=0}^{\infty}\binom{5+r-1}{r}x^r \right ]$

Collecting the coefficients of $x^{29}$ = $\binom{33}{29} + \binom{32}{28} + \binom{31}{27} +\binom{30}{26} + \binom{29}{25} + \binom{28}{24} = 179976$

edited by

Related questions