# Number of Integral Solution of Linear Equation

### 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₃.