Linear algebraic equations are one of the simplest equations that we can solve. If there is only one variable, then the solutions are trivial to obtain, while for a system of linear equations, there are many ways to find unique solutions.

In this article, we are interested in a special linear equation, with many variables. It is well known that such an equation may have an infinite number of solutions. So, we are going to put certain restrictions, and bring down the number of solutions to a great extent.

The general form of the equation, that we are interested in, is given by

where n and m are positive integers.

Our task is to find the number of solutions of this equation, under the assumption that, xᵢ are whole numbers. This assumption drastically reduces the number of solutions of the given equation.

Need For A Method

Let us start by taking a special case of the general equation -

It’s not hard to find the number of solutions to this equation, by direct counting. The solutions are given by the pair (x₁, x₂) as -

We see that there are six solutions of this equation. It’s also not hard to visualize that if we replace the right hand side with a generic positive integer m , the solutions turn out to be

and we can count the number of solutions to be, m+1.

This was easy, right?

Now, we take a slightly more complicated case of three variables, say -

With a little more effort than before, we can find the solutions as a collection of three numbers (x₁, x₂, x₃), given by

The number of solutions for this case turns out to be 10.

We can imagine that this method of direct counting can become very tedious for an equation with more variables. It also becomes tedious if the integer on the right hand side of the equation gets bigger — for example, if we had, say 8 instead of 3 on the right side, the number of solutions turn out to be 45. Surely, we don’t want to find that many solutions by direct counting.

So, what we need is an efficient method of doing all this.

Developing The Method

There is another way in which we can solve the previous two equations. Let us begin with the first equation again -

One of the solutions that we obtained was (5, 0). Let us have a mapping of the kind,

Here we have decomposed the solution pair in terms of ones and zeroes, corresponding to each number. We have mapped the non zero part (5, in this case) with as many ones as the number itself, and zero is mapped to zero. Similarly, we can decompose another solution (4, 1) as

We have basically, switched the position of zero in the previous solution, to get the new one. So, the two numbers in the pairs (denoted in red and blue), are separated by a zero (in black), in the decomposed notation. Similarly, we can write all the remaining solutions as

By writing the solution in this weird way, a pattern emerges. It seems that all the solutions are just rearrangements of ones and zeroes. So, the question of how many solutions are there, becomes equivalent to the question of how many such rearrangements can be made out of ones and zeroes, starting from any one configuration.

In this case, we have 6 locations in the decomposed configuration, to put in ones and zeroes. We can choose the simplest solution as the initial configuration -

Now, all we need is to find the total number of ways in which we can fill 6 locations with 5 ones, and one location with a 0.

We can solve these kinds of counting problems by various methods, but the most efficient way is developed in the branch of mathematics called Combinatorics, which gives a neat formula for the number of ways to rearrange r objects in nlocations-

where n! (called “n factorial”) is defined as a product of all integers from 1 up to n, i.e. n! = 1 × 2 × 3 × ⋅ ⋅ ⋅ × n. We also define 0! = 1.

This formula is usually written in a compact form as

(We shall discuss the steps to obtain this formula in a future article)

So, now coming back to the problem, we can use this formula to find the number of ways in which we can rearrange 5 ones in 6 places as

That’s the same number we found by direct counting!

This looks promising, so let’s see if we can use this to find the number of solutions to our second linear equation,

Few of the solutions can be written in decomposed form as

This time, we need to fill up 3 ones and 2 zeroes in 5 locations. By using the formula, we can find that the number of ways of placing 3 ones in 5 locations is given by

which is same as obtained by direct counting. We can also find the number of solutions for the (previously unsolved) case when the right side of this equation is 8 instead of 3. One of the solutions will be-

and we need to find the number of ways of placing 8 ones in 10 places, which turns out to be

as claimed earlier.

If we believe that this method works well for all cases, we need a general formula. We recall that the general equation is given by

The simplest solution of this equation is given by

Since there are n variables, the number of zeroes in this solution is n-1. So, the decomposition looks like

It can be seen that there are m number of ones in the decomposed configuration, and n-1 number of zeroes (as mentioned earlier).

Therefore, the total number of locations that we have to fill is, (m+n-1). The only thing that remains is, to find the number of ways in which we can fill m ones into m+n-1 places, which is given by the formula as

That’s our final result.

Originally published at https://physicsgarage.com on April 26, 2020.