Consider the integral equation where . The non-negative solutions to this equation can be listed down as and . Thus, non-negative integral solutions exist for this equation.
We would like to solve the general case. How many non-negative, integral solutions exist for the equation
You might be surprised to know that this question can be solved using the general result obtained in the previous example. Can you think how?
Let us consider an arbitrary integral equation, say Consider any particular non-negative integral solution to this equation, say . We some how need to “tag” this solution in a new form; a form which is easily countable. This is how we do it. We break up the solution as shown below:
Similarly, would be written as
and would be written as
and would be written as
An alert reader must have realised the ‘trick’ by now. In each of and , we have on the left hand side “” symbols and “” symbols, in different orders. Any non-negative integral solution can thus be represented by a unique permutation of “” symbols and “” symbols. Conversely, every permutation of “” symbols and 2 “” symbols represents a unique non-negative integral solution to the equation .
Thus, the set of non-negative integral solutions to the equation and the set of permutations of “” symbols and “” symbols are in one-to-one-correspondence. To count the required number of solutions, we simply count the permutations of “” symbols and “” symbols, which as described in the last example would be
This beautiful artifice described about should make it clear to you the significance of (and the challenge of producing!) elegant proofs/solutions.
We now generalise this result. Any non-negative integral solutions to the equation can be represented using “” symbols and “” symbols. The total number of permutation of these symbols will be
and hence, this is the required number of solutions.
Consider a rectangular integral grid of size For example, a integral grid is drawn alongside:
A person has to travel from point to the diagonally opposite point . He moves one step at a time, towards the east or towards the north (that is, never moves towards the west or south at any time). How many distinct paths exist from the point to the point ?
Let us draw a random path on our grid in Fig. and think of some way to mathematically specify/describe this path
Suppose you had to describe this path to a blind person. If you use for a step towards the east and for a step towards the north, you’d tell the blind person that the travelling person took the following path.
This string that we just formed should immediately make you realise how to calculate the number all the possible paths. We have “” steps and “” steps. Any permutation of these steps gives rise to a different unique path. For example, the string “” is the path that goes straight east from to and then straight north from to . Thus, any path can be uniquely characterised by a permutation of these steps. The number of permutations of these letters, of which are “”s and are “”s, is . This is therefore the number of different paths that the travelling person can take from to . For an grid we will have total steps, of them being “” s and the remaining being “” s Thus, the number of possible paths is .