Integer solutions using coefficient method


Suppose there are 20 intermediary stations between two stations A and B.  A train can stop at 3 of these stations but there must be minimum 3 stop between any two consecutive stoppings. In how many ways the train can reach its destination.
To solve questions of these type, we should learn a important method called coefficient method.

The number of non - negative integer solutions for the equation ${x_1} + {x_2} + {x_3} + ...{x_r} = n$ is the number of ways of distribution n identical things among r persons. , when each person can get zero, one or more things.  
This is nothing but Coefficient of ${x^n}$ in ${\left[ {1 + x + {x^2} + ......{x^n}} \right]^r}$
The terms in the bracket are in geometric progression with common ratio of x. And they are (n+1) terms.  Applying the geometric progression sum rule
= Coefficient of ${x^n}$ in ${\left( {\displaystyle\frac{{1 - {x^{n + 1}}}}{{1 - x}}} \right)^r}$
= Coefficient of ${x^n}$ in ${\left( {1 - {x^{n + 1}}} \right)^r}{\left( {1 - x} \right)^{ - r}}$
In the first expression, $\left[ {1{ + ^r}{C_1}{x^{n + 1}}{ + ^r}{C_2}{{\left( {{x^{n + 1}}} \right)}^2} + ...} \right]{\left( {1 - x} \right)^{ - r}}$ = ${\left( {1 - x} \right)^{ - r}}$
[first term in the first expression only gives a power of n, all other terms have powers are in the multiples of n+1]
\({\left( {1 - x} \right)^{ - r}} = 1 + {}^r{C_1}\left( x \right) + {}^{r + 1}{C_2}{x^2} + {}^{r + 2}{C_3}{x^3} + ... + \)
Coefficient of ${x^n}$ in the above expansion  = \({}^{n + r - 1}{C_n}\)

How to apply the above formula:
${\left( {1 - x} \right)^{ - 18}} = 1 + {}^{18}{C_1}x + {}^{19}{C_2}{x^2} + {}^{20}{C_3}{x^3} + .......\infty $
 The coefficient of  ${x^3}$ will be calculated by using the formula = ${}^{(n + r - 1)}{C_{n}}$ = ${}^{(3 + 18 - 1)}{C_{3}} = {}^{20}{C_3}$
The coefficient of  ${x^{17}}$ will be calculated by using the formula = ${}^{(n + r - 1)}{C_{n}}$ = ${}^{(17 + 18 - 1)}{C_{17}} = {}^{34}{C_{17}}$

Solved Examples


1. Find the number of positive number of solutions of x + y + z + w = 20 (a)  if "0" is allowed (b) if "0" is not allowed. 
Solution:
This equation is nothing but distributing 20 similar articles to 4 persons. Here n = 20 and r = 4
Applying the formula ${}^{(n + r - 1)}{C_{r - 1}} = {}^{20 + 4 - 1}{C_{4 - 1}} = {}^{23}{C_3} = 1771$.
If 0 is not allowed, the let us give one article each to x, y , z , w. Now assume $x = {x^1} + 1$, $y = {y^1} + 1$, $z = {z^1} + 1$, $w = {w^1} + 1$
So our equation becomes, $({x^1} + 1) + ({y^1} + 1) + ({z^1} + 1) + ({w^1} + 1) = 20$
Now ${x^1},{y^1},{z^1},{w^1}$ can take zero.
So ${x^1} + {y^1} + {z^1} + {w^1} = 16$ and number of intezer solutions for this equation become ${}^{(n + r - 1)}{C_{r - 1}} = {}^{16 + 4 - 1}{C_{4 - 1}} = {}^{19}{C_3} = 969$
Note: When we give r articles each one to r persons we left with (n-r) articles. Now distributions these articles to r persons = ${}^{(n - r) + r - 1}{C_{r - 1}} = {}^{n - 1}{C_{r - 1}}$
If x, y, z , w are graeter than equal to 1, we apply above formula.

2. How many integral solutions exist for x + y + z + w = 29 where $x \ge 1,y \ge 1,z \ge 3$ and $w \ge 0$
Solution:
x + y + z + w = 29
Take $x = {x^1} + 1$, $y = {y^1} + 1$, $z = {z^1} + 3$
Substituting these values in our equation makes it as $({x^1} + 1) + ({y^1} + 1) + ({z^1} + 3) + w = 29$
${x^1} + {y^1} + {z^1} + w = 23$
Number of intezer solutions for the above equation = $^{(n + r - 1)}{C_{r - 1}}{ = ^{23 + 4 - 1}}{C_{4 - 1}}{ = ^{26}}{C_3} = 2600$

3. How many integral solutions are there to the system of equations a+b+c+d+e = 20 and a + b = 15 where "0" is allowed. 
Solution: 
a + b + c + d + e = 20 -----(1)
a + b = 15 ----(2)
From the above two equations, c + d + e = 5 -----(3)
Number of integer solutions for (2) is $^{15 + 2 - 1}{C_{2 - 1}}{ = ^{16}}{C_1} = 16$ and for (3) is $^{5 + 3 - 1}{C_{3 - 1}}{ = ^7}{C_2} = 21$
So total solutions are 16 x 21 = 336

4. Find the number of integer solutions for the equation x + y + z + 4t = 20
Solution:
The values for 4t are 0, 4, 8, 12, 16, 20
By substituting the above values in the given equation, we get x + y + z = 20, x + y + z =  16, x + y + z = 12, x + y + z = 8, x + y + z = 4, x + y + z = 0
Now the solutions for the above equations are $^{20 + 3 - 1}{C_{3 - 1}}{ = ^{22}}{C_2}$, $^{16 + 3 - 1}{C_{3 - 1}}{ = ^{18}}{C_2}$, $^{12 + 3 - 1}{C_{3 - 1}}{ = ^{14}}{C_2}$, $^{8 + 3 - 1}{C_{3 - 1}}{ = ^{10}}{C_2}$, $^{4+ 3 - 1}{C_{3 - 1}}{ = ^{6}}{C_2}$, and 1
So total solutions = $^{22}{C_2}{,^{18}}{C_2}{,^{14}}{C_2}{,^{10}}{C_2}{,^6}{C_2},1$ = 231 + 153 + 91 + 45 + 15 + 1 = 536

5. There are 20 intermediary stations between two stations A and B.  A train can stop at 3 of these stations but there must be minimum 3 stop between those intermediary stoppings. In how many ways the train can reach its destination.
Solution: 
$A,{S_1},{S_2}......{S_K},........{S_L},..........{S_M},..........{S_{20}},B$
Assume that there are P stations between A and ${S_K}$, Q stations between ${S_K}$ and ${S_L}$, R stations between ${S_L}$ and ${S_M}$ and S stations between ${S_M}$ and B.
Now there must be 3 stoppings between ${S_K},{S_L},{S_M}$ but there need not be any stopping between A and the first intermediry and B and the last intermediary stations.
This gives us, P + Q + R + S = 17 (As we have to substract 3 stations from  the sum of intermediary stations)
Here P $ \ge $ 0, Q $ \ge $ 3, R $ \ge $ 3 and S $ \ge $ 0
Substituting $Q = {Q^1} + 3$ and $R = {R^1} + 3$ we get $P + {Q^1} + {R^1} + S = 11$
Now number of intezer solutions for this equation = $^{11 + 4 - 1}{C_{4 - 1}}{ = ^{14}}{C_3}$

Integer solutions when an integer has some minimum and maximum limit:
We have seen already that, how to find integer solutions x + y + z + w = 20 where x, y, z, w may take values from 0 to 20.  But what if when x, y, z, w has a minimum of 3 and maximum limit of 10.  ie., We may not substitute values more than 10 in this equation. So how do we attempt to solve this equation?
Suppose, we have n similar articles may be distributed to 1 person. In how many ways we can distribute 3 articles to this person? In how many ways we can distribute 5 articles to this person? In how many ways n articles to be distributed to this person?
For all above questions, the answer is 1 as all articles are similar there is only 1 ways to choose, 2, 5, n articles from n articles.
So number of ways of distributing K articles to 1 person is the coefficient of ${x^k}$ = $1 + x + {x^2} + {x^3} + ......{x^n}$ which is 1.
Now assume He will get a minimum of 3 and maximum of 6, then we have to consider this equation. ${x^3} + {x^4} + {x^5} + {x^6}$

6. How many integers between 1 to 1000000 have the sum of the digits 18?
Solution:

Any number between 1 to 10000000 has 7 digits. Let us say they are ${a_1},{a_2},{a_3}.....{a_7}$. Now ${a_1} + {a_2} + {a_3} + {a_4} + {a_5} + {a_6} + {a_7} = 18$
Here these variables take a minimum value of 0 but a maximum value of 9.  18, 0, 0, 0, 0, 0, 0 is a solution of the above but this is violating our condition as all the digits are single digit numbers of maximum 9
We have to consider, ${x^{18}}$ coefficient in the expansion of ${({x^0} + {x^1} + {x^2} + {x^3} + {x^4}......{x^9})^6}$
The required number is ${x^{18}}$ coefficient in the expansion of ${\left( {\displaystyle\frac{{1 - {x^{10}}}}{{1 - x}}} \right)^6}$
${x^{18}}$ coefficient in the expansion of ${\left( {1 - {x^{10}}} \right)^6}{\left( {1 - x} \right)^{ - 6}}$
${x^{18}}$ coefficient in the expansion of $\left( {1{ - ^6}{C_1}{x^{10}} + ...} \right){\left( {1 - x} \right)^{ - 6}}$
${x^{18}}$ coefficient in the second expression multiplied by 1 will give us one ${x^{18}}$  and ${x^{8}}$ coefficient in the second expression multiplied by ${x^{10}}$ will give us another ${x^{18}}$ coefficient.
= Coefficient of ${x^{18}}$ in ${\left( {1 - x} \right)^{ - 6}}$ - ${}^6{C_1}$. Coefficient of ${x^{8}}$ in ${\left( {1 - x} \right)^{ - 6}}$
= $^{6 + 18 - 1}{C_{6 - 1}}{ - ^6}{C_1}.{}^{6 + 8 - 1}{C_{6 - 1}} = {}^{23}{C_5} - 6.{}^{13}{C_5} = 25927$

7.  In how many ways can we get a sum of 12 throwing 3 dice. 
Solution:

A single dice shows from 1 to 6. So we have to find the integer solutions for A + B + C = 12 where A, B, C represent the numbers of dice subject to the condition that they take values form 1 to 6.
So we have to find coefficient of ${x^{12}}$ in the expansion ${({x^1} + {x^2} + {x^3} + {x^4} + {x^5} + {x^6})^3}$
= Coefficient of ${x^{12}}$ in ${x^3}{(1 + x + {x^2} + {x^3} + {x^4} + {x^5})^3}$
= Coefficient of ${x^{9}}$ in ${\left( {\displaystyle\frac{{1 - {x^6}}}{{1 - x}}} \right)^3}$
= Coefficient of ${x^{9}}$ in ${\left( {1 - {x^6}} \right)^3}{\left( {1 - x} \right)^{ - 3}}$
= Coefficient of ${x^{9}}$ in $\left( {1 - {}^3{C_1}{x^6} + {}^3{C_2}{x^{12}}...} \right){\left( {1 - x} \right)^{ - 3}}$
Required coefficient is coefficient of ${x^{9}}$ in ${\left( {1 - x} \right)^{ - 3}}$ - ${}^3{C_1}$. Coefficient of ${x^{3}}$ in ${\left( {1 - x} \right)^{ - 3}}$
= $^{9 + 3 - 1}{C_{3 - 1}} - 3.{}^{3 + 3 - 1}{C_{3 - 1}} = {}^{11}{C_2} - 3.{}^5{C_2} = 25$

8. Find the number of non negative integer solutions of the inequality x + y + z $ \le $ 20
Solution:

We add another variable K to this equation to make it an equality
Now x + y + z + K = 20 where K can take any value from 0 to 20 so that we get different solutions for the above equation from 20 to 0.
Now number of solutions for the above equation = $^{(n + r - 1)}{C_{r - 1}}{ = ^{20 + 4 - 1}}{C_{4 - 1}} = {}^{23}{C_3}$

9. If 3 dice are rolled, The number of ways so that the sum of the numbers on them is atleast 9 is
Solution:

We first consider that the maximum sum on the dice is 8.
Now A + B + C $ \le $ 8
Add a variable K to this equation to make it an equality
A + B + C + K = 8 Subjected to the condition A, B, C takes values from 1 to 6 and K take any value from 0 to 8 for the sum of the numbers ranges from 8 to 0
We have to find the coefficient of ${x^{8}}$ in ${({x^1} + {x^2} + {x^3} + {x^4} + {x^5} + {x^6})^3}(1 + x + {x^2} + ...)$
= ${x^3}{(1 + {x^1} + {x^2} + {x^3} + {x^4} + {x^5})^3}(1 + x + {x^2} + ...)$
= Cofficient of ${x^{5}}$ in ${(1 + {x^1} + {x^2} + {x^3} + {x^4} + {x^5})^3}(1 + x + {x^2} + ...)$
= Cofficient of ${x^{5}}$ in ${\left( {\displaystyle\frac{{1 - {x^6}}}{{1 - x}}} \right)^3}{(1 - x)^{ - 1}}$
= Cofficient of ${x^{5}}$ in ${(1 - {x^6})^3}{(1 - x)^{ - 4}}$
= Cofficient of ${x^{5}}$ in  $\left( {1 - {}^6{C_1}{x^{10}} + ...} \right){(1 - x)^{ - 4}}$
= Cofficient of ${x^{5}}$ in ${(1 - x)^{ - 4}}$
= $^{(n + r - 1)}{C_{r - 1}}{ = ^{5 + 4 - 1}}{C_{4 - 1}} = {}^8{C_3} = 56$
Now total number of ways of throwing 3 dice = ${6^3}$ of which we get a sum of 8 or less in 56 ways.  Now to get a sum more than 8 or above = 216 - 56 = 160