Number of Integral Solution of Linear Equation
Consider the equation x₁ + x₂ + x₃ + … + xr = n … (1)
Where x₁, x₂, x₃, … x and n are non-negative integer.
This equation may be interpreted as that n identical objects are to be divided into r groups where a group may contain any number of objects. Therefore,
Total number of solutions of equation (1)
= coefficient of xⁿ in (x⁰ + x¹ + … + xⁿ)²
= n + r – 1cr₋₁
Now let us consider the equation
x₁ + x₂ + x₃ + … + xm = n … (2)
Where x₁ + x₂ + … + xm are integers such that aᵢ ≤ xᵢ ≤ bᵢ; 1 = 1, 2, … m.
Proceeding as above, we find that
Total number of solution of equation (2)
= coefficient of xⁿ in
\(\left[ \left( {{x}^{{{a}_{1}}}}+{{x}^{{{a}_{1}}+1}}+{{x}^{{{a}_{1}}+2}}+…..+{{x}^{{{b}_{1}}}} \right)\left( {{x}^{{{a}_{2}}}}+{{x}^{{{a}_{2}}+1}}+{{x}^{{{a}_{2}}+2}}+….+{{x}^{{{b}_{2}}}} \right)…\left( {{x}^{{{a}_{m}}}}+{{x}^{{{a}_{m}}+1}}+….+{{x}^{{{b}_{m}}}} \right) \right]\).
Let us consider the equation ax₁ + bx₂ + cx₃ = n where x₁, x₂, x₃ are integers such that aᵢ ≤ xᵢ ≤ bᵢ; 1 = 1, 2, 3.
Total number of solution of this equation is equal to coefficient of xⁿ in
\(\left[ \left\{ {{\left( {{x}^{a}} \right)}^{{{a}_{1}}}}+{{\left( {{x}^{a}} \right)}^{{{a}_{1}}+1}}+…+{{\left( {{x}^{{{a}_{1}}}} \right)}^{{{b}_{i}}}} \right\}\left\{ {{\left( {{x}^{b}} \right)}^{{{a}_{2}}}}+{{\left( {{x}^{b}} \right)}^{{{a}_{2}}+1}}+…+{{\left( {{x}^{b}} \right)}^{{{b}_{2}}}} \right\}\left\{ {{\left( {{x}^{c}} \right)}^{{{a}_{3}}}}+{{\left( {{x}^{c}} \right)}^{{{a}_{3}}+1}}+….+{{\left( {{x}^{c}} \right)}^{{{b}_{3}}}} \right\} \right]\).
The total number of non-negative integral solution of the equation x₁ + x₂ + … + xr = n is n + r – 1cr₋₁ and the number of solution of the same equation in the set N of natural numbers is n – 1cr₋₁.
If the upper limit of a variable in solving an equation of the form x₁ + x₂ + x₃… + xm = n subject to the condition aᵢ ≤ xᵢ ≤ bᵢ; i = 1, 2, … m is more than or equal to the sum required and lower limit of all the variable are non-negative, then upper limit of that variable can be taken as infinite.
In order to solve in equations of the form x₁ + x₂ + … + xm ≤ n … (1)
We introduce a dummy variable xm₊₁ such that x₁ + x₂ + … + xm + xm₊₁ = n where xm₊₁ ≥ 0.
Example: Determine the total number of non-negative integral solution of x₁ + x₂ + x₃ + x₄ = 100.
Solution: Here the upper limit of variables x₁, x₂, x₃ is more than 100 and the lower limit of non-negative. Therefore, required number of solution.
= coefficient of x¹⁰⁰ in (1 + x + x² + …)⁴
= coefficient of x¹⁰⁰ in (1 – x)⁻⁴
= 100 + 4 – 1c₄₋₁
= 100c₃
Method 2: Total number of non-negative integral solution of the given equation is same as the number of ways of distributing 100 item among 4 persons such that each person can receive any number of items.
Hence, total number of solutions = 100 + 4 – 1c₄₋₁
= 100c₃.