A Method of Counting The Number of Solutions


5 min read
A Method of Counting The Number of Solutions

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

$$x_1 + x_2 + x_3 + \cdots x_n = m,$$

where $n$ and $m$ are positive integers.

Our task is to find the number of solutions of this equation, under the assumption that, $x_i$ 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 -

$$x_1 + x_2 = 5$$

It's not hard to find the number of solutions to this equation, by direct counting. The solutions are given by the pair $(x_1, x_2)$ as -

$$(5, 0), (4, 1), (3, 2), (2, 3), (1, 4), (0, 5)$$

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

$$(m, ~0), (m-1, ~1), (m-2, ~2), \cdots, (0, ~m),$$

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 -

$$x_1 + x_2 + x_3 = 3$$

With a little more effort than before, we can find the solutions as a collection of three numbers $(x_1, x_2, x_3)$, given by

$$(3, 0, 0), (2, 1, 0), (1, 2, 0), (0, 3, 0), \\ (0, 2, 1), (0, 1, 2), (0, 0, 3), (2, 0, 1), \\ (1, 0, 2), (1, 1, 1).$$

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 -

$$x_1 + x_2 = 5$$

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

$$(\red{5}, \blue{0}) \iff (\red{1, 1, 1, 1, 1}, \blue{0})$$

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

$$(\red{4}, \blue{1}) \iff (\red{1, 1, 1, 1}, 0, \blue{1})$$

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

$$(\red{3}, \blue{2}) \iff (\red{1, 1, 1}, 0, \blue{1, 1}) \\ (\red{2}, \blue{3}) \iff (\red{1, 1}, 0, \blue{1, 1, 1}) \\ (\red{1}, \blue{4}) \iff (\red{1}, 0, \blue{1, 1, 1, 1}) \\ (\red{0}, \blue{5}) \iff (\red{0}, \blue{1,1,1,1,1})$$

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 -

$$(\red{5}, \blue{0}) \iff (\red{1, 1, 1, 1, 1}, \blue{0})$$

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 $n$ locations-

$$\frac{n!}{(n-r)! \cdot r!},$$

where $n!$ (called "$n$ factorial") is defined as a product of all integers from $1$ up to $n$, ie. $n! = 1 \times 2 \times 3 \times \cdots \times n$. We also define $0! = 1$.

This formula is usually written in a compact form as

$$\frac{n!}{(n-r)! \cdot r!} \equiv C(n, r)$$

(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

$$C(6, 5) = \frac{6!}{5! \cdot 1!} = \frac{6\cdot5\cdot4\cdot3\cdot2\cdot1}{5\cdot4\cdot3\cdot2\cdot1\cdot1} = 6$$

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,

$$x_1 + x_2 + x_3 = 3$$

Few of the solutions can be written in decomposed form as

$$(\red{3}, \blue{0}, \green{0}) \iff (\red{1, 1, 1}, \blue{0}, \green{0}) \\ (\red{2}, \blue{1}, \green{0}) \iff (\red{1, 1}, 0, \blue{1}, \green{0}) \\ (\red{1}, \blue{2}, \green{0}) \iff (\red{1},0, \blue{1,1}, \green{0})$$

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

$$C(5, 3) = \frac{5!}{3! \cdot 2!} = \frac{5\cdot4\cdot3\cdot2\cdot1}{(3\cdot2\cdot1)\cdot(2 \cdot 1)} = 10,$$

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 is-

$$(\red{8}, \blue{0}, \green{0}) \iff (\red{1, 1, 1, 1, 1, 1, 1, 1}, \blue{0}, \green{0}),$$

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

$$C(10, 8) = \frac{10!}{8! \cdot 2!} = \frac{10\cdot9\cdot8\cdot7\cdot6\cdot5\cdot4\cdot3\cdot2\cdot1}{(8\cdot7\cdot6\cdot5\cdot4\cdot3\cdot2\cdot1)\cdot(2 \cdot 1)} = 45,$$

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

$$x_1 + x_2 + x_3 + \cdots x_n = m.$$

The simplest solution of this equation is given by

$$(m, 0, 0, \cdots 0).$$

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

$$(\red{m}, \blue{0}, \green{0}, \cdots, \pink{0}) \iff (\red{1, 1, 1, \cdots}, \blue{0}, \green{0}, \cdots, \pink{0}).$$

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 vacant places 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

$$C(m+n-1, m) = \frac{(m+n-1)!}{(n-1)!\cdot m!}$$

That's our final result.

Subscribe to the newsletter to receive more stories mailed directly to your inbox

Related Articles

A Derivation of Euler's Formula
4 min read
A Formula For Fibonacci Sequence
5 min read
Mighty Ruler Conquers Quadratic Equations
6 min read
A clever formula for Logarithm
2 min read

GO TOP

🎉 You've successfully subscribed to Physics Garage!
OK