ONE MORE STEP TOWARD BETTER TOMORROW : CHAPTER 7

Tuesday 5 August 2014

CHAPTER 7 - SOME MORE Worked Out Examples

Example: 1

Consider the integral equation ${x_1} + {x_2} = 4$ where ${x_1},{x_2} \in \mathbb{Z}$ . The non-negative solutions to this equation can be listed down as $\left\{ {0,4} \right\},\;\left\{ {1,3} \right\},\left\{ {2,2} \right\},\;\left\{ {3,1} \right\}$ and $\left\{ {4,0} \right\}$ . Thus, $5$ 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

${x_1} + {x_2} + \dots + {x_n} = r$

Solution: 1

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 ${x_1} + {x_2} + {x_3} = 8.$ Consider any particular non-negative integral solution to this equation, say $\left\{ {2,3,3} \right\}$ . 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 $2 + 3 + 3 = 8$ as shown below:

Similarly, $1 + 6 + 1 = 8$ would be written as

and $0 + 1 + 7 = 8$ would be written as

and $0 + 0 + 8 = 8$ would be written as

An alert reader must have realised the ‘trick’ by now. In each of $(1), (2), (3)$ and $(4)$ , we have on the left hand side $8$ “ $1$ ” symbols and $2$ “

” symbols, in different orders. Any non-negative integral solution can thus be represented by a unique permutation of $8$ “ $1$ ” symbols and $2$ “

” symbols. Conversely, every permutation of $8$ “ $1$ ” 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 $8$ “ $1$ ” symbols and $2$ “

” symbols are in one-to-one-correspondence. To count the required number of solutions, we simply count the permutations of $8$ “ $1$ ” symbols and $2$ “

” symbols, which as described in the last example would be $\dfrac{{(8 + 2)!}}{{8!2!}} = \dfrac{{10!}}{{8!2!}} = 45$

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 ${x_1} + {x_2} + \dots + {x_n} = r$ can be represented using $r$ “ $1$ ” symbols and $n - 1$ “

” symbols. The total number of permutation of these symbols will be

$\dfrac{{(n + r - 1)!}}{{r!(n - 1)!}} = {\,^{n + r - 1}}{C_r}$

and hence, this is the required number of solutions.

Example: 2

Consider a rectangular integral grid of size $m \times n.$ For example, a $4 \times 5$ integral grid is drawn alongside:

A person has to travel from point $A(0, 0)$ to the diagonally opposite point $C(m, n)$ . 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 $A$ to the point $C$ ?

Solution: 2

Let us draw a random path on our grid $4\times 5$ in Fig. $6$ 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 $E$ for a step towards the east and $N$ for a step towards the north, you’d tell the blind person that the travelling person took the following path.

“ $E\,E\,N\,E\,N\,E\,E\,N\,N\,$ ”

This string that we just formed should immediately make you realise how to calculate the number all the possible paths. We have $5$ “ $E$ ” steps and $4$ “ $N$ ” steps. Any permutation of these $9$ steps gives rise to a different unique path. For example, the string “ $E\,E\,E\,E\,E\,N\,N\,N\,N\,$ ” is the path that goes straight east from $A$ to $B$ and then straight north from $B$ to $C$ . Thus, any path can be uniquely characterised by a permutation of these $9$ steps. The number of permutations of these $9$ letters, $5$ of which are “ $E$ ”s and $4$ are “ $N$ ”s, is $\dfrac{{9!}}{{5!4!}}$ . This is therefore the number of different paths that the travelling person can take from $A$ to $C$ . For an $m \times n$ grid we will have $(m + n)$ total steps, $m$ of them being “ $E$ ” s and the remaining $n$ being “ $N$ ” s Thus, the number of possible paths is $\dfrac{{(m + n)!}}{{m!\, \times \,n!}}$ .

ONE MORE STEP TOWARD BETTER TOMORROW

Tuesday 5 August 2014

CHAPTER 7 - SOME MORE Worked Out Examples

No comments:

https://www.youtube.com/TarunGehlot