ONE MORE STEP TOWARD BETTER TOMORROW : CHAPTER 10

Tuesday 5 August 2014

CHAPTER 10 - MISCELLANEOUS EXAMPLES

Example: 1

A composition of a natural number $N$ is a sequence of non-zero integers $\{ {a_1},{a_2},\ldots ,{a_k}\}$ which add up to $N$ . How many compositions of $N$ exist?

Solution: 1

Let us make the question more clear by taking a particular example for $N$ , say $N = 4$ .

As described in the question, the compositions of $N = 4$ will be $\left\{ 4 \right\},\,\,\left\{ {1,\,\,3} \right\},\,\left\{ {2,2} \right\},\,\,\left\{ {3,1} \right\},\,\,\left\{ {1,1,2} \right\},\left\{ {1,2,1} \right\},\,\,\left\{ {2,\,1,1} \right\}\,\,{\rm{and}}\,\,\left\{ {1,\,1,\,1,1} \right\}$ which are $8$ in number.

Observe carefully the compositions listed out. How can we characterize each of these compositions mathematically? Recall the problem of finding the number of non-negative solutions of the integral equation ${x_1} + {x_2} +\ldots + {x_n} = r$ where each solution corresponded to a unique permutation of $r$ “ $1$ “symbols and $n - 1$ “

” symbols. Can we do something like that here? In other words, can we represent each composition in another form whose permutations are easier to count?

It turns out that we can, as follows:

$\begin{array}{l} \{ 4\} \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, = \,\,\,\,1\,\,\,\,\,\,\,\,\,\,\,1\,\,\,\,\,\,\,\,\,\,\,1\,\,\,\,\,\,\,\,\,\,\,1\\ \{ 1,3\} \,\,\,\,\,\,\,\,\,\,\, \,= \,\,\,\,1\,\, + \,\,1\,\,\,\,\,\,\,\,\,\,\,1\,\,\,\,\,\,\,\,\,\,\,1\\ \{ 3,1\} \,\,\,\,\,\,\,\,\,\,\, \,= \,\,\,\,1\,\,\,\,\,\,\,\,\,\,\,1\,\,\,\,\,\,\,\,\,\,\,1\,\, + \,\,1\\ \{ 2,2\} \,\,\,\,\,\,\,\,\,\,\,\, = \,\,\,\,1\,\,\,\,\,\,\,\,\,\,\,1\,\, + \,\,1\,\,\,\,\,\,\,\,\,\,\,1\\ \{ 1,1,2\} \,\,\,\,\,\,\, = \,\,\,\,1\,\, + \,\,1\,\, + \,\,1\,\,\,\,\,\,\,\,\,\,\,1\\ \{ 1,2,1\} \,\,\,\,\,\,\, = \,\,\,\,1\,\, + \,\,1\,\,\,\,\,\,\,\,\,\,\,1\,\, + \,\,1\\ \{ 2,1,1\} \,\,\,\,\,\,\, = \,\,\,\,1\,\,\,\,\,\,\,\,\,\,\,1\,\, + \,\,1\,\, + \,\,1\\ \{ 1,1,1,1\} \,\, = \,\,\,\,1\,\, + \,\,1\,\, + \,\,1\,\, + \,\,1 \end{array}$

On the right hand side, we have $4$ “ $1$ ”s and thus $3$ blank spaces between the $4$ “ $1$ ” s. We can insert “ $+$ ” signs in these blank spaces; each different arrangement of “ $+$ ” signs in these blank spaces will correspond to a different composition.

To count the number of these arrangements, we proceed as follows: For each blank space, we have $2$ options, we can either insert or not insert a “ $+$ ” sign into that space. There are $3$ blank spaces; so the total number of all arrangements of “ $+$ ” signs in the $3$ blank spaces is $2 \times 2 \times 2 = 8$ (which is the number of compositions we already listed out).

In the general case, we will have $(N - 1)$ blank spaces and $2$ options for each such blank space. Thus, the total number of ways in which we can arrange “ $+$ ” signs in these blank spaces, and therefore, the total number of compositions, will be $\underbrace{2 \times 2 \times 2 \times \ldots 2}_{\rm{Comment:1}} = {2^{N - 1}}$

Comment:1 $(N-1)$ times

Example: 2

Prove logically the following assertion:

$\sum\limits_{k = 0}^n {{2^k} \cdot {\,^n}{C_k} = {3^n}}$

Solution: 2

Suppose that we have to form a string of length $n$ , consisting of only letters from the set ${A, B, C}$ . Thus, we have $3$ options to fill any particular place in the string: We fill that place with either $A$ , $B$ or $C$ . Thus the total number of different strings of length $n$ would be

	$\underbrace{3 \times 3 \times 3 \times \ldots \times 3}_{\rm{Comment:1}} = {3^n}$
	Comment:1 $n$ times

We now approach the task of formation of these strings from a different perspective.

Suppose that our string contains a total of $r$ “ $A$ ” s. How many such strings will exist? We first select $r$ places out of $n$ which we will fill with “ $A$ ”. This can be done in ${}^n{C_r}$ ways. For each of the remaining $(n - r)$ places, we have two options; we either fill it with “ $B$ ” or “ $C$ ”. Thus, the number of strings containing $r$ “ $A$ ” s will be ${}^n{C_r}{.2^{n - r}}$ .

Now we vary $r$ from $0$ to $n$ and thus get the total number of strings as

	$\sum\limits_{r = 0}^n {{\,^n}{C_r} \cdot {2^{n - r}}} = \sum\limits_{k = 0}^n {{\,^n}{C_{n - k}} \cdot {2^k}\,\,\,\,\,\,} \left( {{\rm{where}}\,\,k = n - r} \right)$
	$= \sum\limits_{k = 0}^n {{\,^n}{C_k} \cdot {2^k}}$ $\left( {{\rm{since}}\,{\,^n}{C_{n - k}} = {\,^n}{C_k}} \right)$

Thus $\sum\limits_{k = 0}^n {{\,^n}{C_k} \cdot {2^k}} = {3^n}$

Example: 3

$5$ balls are to be placed in $3$ boxes. Each box can hold all the $5$ balls. In how many ways can we place the balls into the boxes so that no box remains empty, if

	(a) balls and boxes are all different
	(b) balls are identical but boxes are different
	(c) balls are different but boxes are identical
	(d) balls as well as boxes are identical
	(e) balls as well as boxes are identical, but the boxes are kept in a row.

Solution:3-(a)

One of the constraints that should always be satisfied is that no box should remain empty. Thus, each box should get at least one ball. This means that the distribution of balls can have the configuration $( 1, 1, 3)$ or $(1, 2, 2)$ . Only in these two configurations does no box remain empty.

In this case, the balls and the boxes are all different. If you observe carefully, you will note that this case is equivalent to dealing cards to players. Here, we are dealing balls (all different) into boxes (all different). In the card game, we were dealing cards (all different) to players (all different).

Suppose we distribute the balls in the configuration $(3, 1, 1)$ . We first divide the group of balls into this configuration. This can be done in $^5{C_3}$ ways since we just need to select a group of $3$ balls and our division will be accomplished. Once the division of the group of balls into $3$ -subgroups in the configuration $(3, 1, 1)$ has been done, we can permute the $3$ sub-groups among the $3$ different boxes in $3!$ ways.

Thus, the number of ways to achieve the $(3, 1, 1)$ configuration is $^5{C_3} \times 3! = 60$

We now find the number of ways to achieve the $(1, 2, 2)$ configuration .

We first select $2$ balls out of the $5$ which can be done in $^5{C_2}$ ways. We then select $2$ balls from the remaining $3$ , which can be done in $^3{C_2}$ ways. Thus simple division into the configuration $(2, 2, 1)$ can be achieved in $\dfrac{{^5{C_2} \times {\,^3}{C_2}}}{{2!}}$ ways. Division by $2!$ is required since two subgroups are of the same size and right now we are just dividing into sub groups so the order to the sub-groups doesn’t matter. Once division has been accomplished, we permute the $3$ subgroups so formed amongst the $3$ different boxes is $3!$ ways.

Thus, the number of ways to achieve the $(2, 2, 1)$ configuration is $\dfrac{{^5{C_2} \times {\,^3}{C_2}}}{{2!}} \times 3!\,\, = \,\,90$

The total number of ways is $60 + 90 = 150$

To make things more clear, let us list down in detail the various configurations possible for the $3$ different boxes, $A$ , $B$ $\&$ $C$ :

Box - $A$	Box - $B$	Box - $C$	Number of ways
$1$	$1$	$3$	$20$
$1$	$3$	$1$	$20$
$3$	$1$	$1$	$20$
$1$	$2$	$2$	$30$
$2$	$1$	$2$	$30$
$2$	$2$	$1$	$30$
			Total : $150$

Solution: 3-(b)

The balls are now identical so it doesn’t matter which ball goes into which box. What matters is only the configuration of the distribution.

By simple enumeration, only $6$ configurations exist for this case. (The notation $[a, b, c]$ implies that Box – $A$ has a balls, Box – $B$ has $b$ balls and Box – $C$ has $c$ balls.)

	$\left[ {1,\,1,3} \right] \,\,\,\,\,\,\,\,\,\,\, \left[ {1,\,3,1} \right] \,\,\,\,\,\,\,\,\,\,\, \left[ {3,1,1} \right]$
	$\left[ {1,\,2,2} \right] \,\,\,\,\,\,\,\,\,\,\,\, \left[ {2,\,1,2} \right] \,\,\,\,\,\,\,\,\,\, \left[ {2,2,1} \right]$

Thus, $6$ possible ways exist for this case

Solution:3-(c)

The boxes are identical. This means that it does not matter which sub-group of balls you put in which box. What matters is only the division of the group of balls. This case is akin to the one where you have to divide a deck of cards into sub-groups. (you aren’t required to distribute those sub-groups to players).

For the configuration $(1, 1, 3)$ , the number of ways of division is ${\,^5}{C_3} = 10$ (we just choose $3$ balls out the $5$ and the division is automatically accomplished. For the configuration $(1, 2, 2),$ the number of ways of division is $\dfrac{{^5{C_2} \times {\,^3}{C_2}}}{{2!}} = 15$ (division by $2!$ is required since two sub-groups are of the same size, and here the order of the group doesn’t matter)

Thus, the total number of ways is $10 + 15 = 25$

Solution: 3-(d)

This case is quite straightforward. The balls are identical. The boxes are identical too. The only $2$ possible configuration are $(1, 1, 3)$ and $(1, 2, 2)$ . There can be no permutation of these configurations since the boxes are indistinguishable. Thus, only $2$ ways of division exist.

Solution: 3-(e)

If we keep the boxes in a row, we have inherently ordered them and made them non-identical, since the boxes can be numbered now.

Therefore, in this case, the balls are identical but the boxes are different so this question becomes the same as the one in part – (b)

Example: 4

We have $21$ identical balls available with us which we need to be distributed amongst $3$ boys $A$ , $B$ and $C$ such that $A$ always gets an even number of balls. How many ways of doing so are possible?

Solution: 4

The only constraint is that $A$ should get an even number of balls. There’s no constraint on the minimum number of balls a boy should get. This means that a boy can also not be given any ball.

We can represent the number of balls given to $A$ by $2 x$ since $A$ must get an even number of balls. If we represent the number of balls given to $B$ and $C$ by $y$ and $z$ , we should have

$2x + y + z = 21$

$\ldots (1)$

This means that to find the number of distributions possible, we find the number of non-negative integral solutions to the equation $(1)$ .

Note that $x$ can take a maximum value of $10$ and a minimum value of $0$ .

We rearrange $(1)$ so that we get an integral equation with $y$ and $z$ as variables, treating $x$ as a constant

$y + z = 21 - 2x$

$\ldots (2)$

The number of non-negative integer solutions of $(2)$ is

$^{21 - 2x + 2\, - 1}{C_1} = \,\,\,\,\,{\,^{22 - 2x}}{C_1} = 22 - 2x$

We now add the number of solutions so obtained for all the possible values of $x$ . The total number of solutions is therefore $\sum\limits_{x = \,0}^{10} {\left( {22 - 2x} \right) = 132.}$

Note:

An alert reader must have noticed that we can form arbitrarily complex integer equations. For example, what do we do if we intend to find out the number of non-negative integer solutions to the equation

${\alpha _1}{x_1} + {\alpha _2}{x_2} + \ldots {\alpha _n}{x_n} = r$

where the ${\alpha _i}'s$ are integers that are not necessarily equal to unity.

In addition, what if we impose constraints on the $x_i'\,s$ themselves say, we define an upper and lower bound for ${x_i}$ , i.e

${l_i} \le {x_i} \le {u_i}$

For example, how do we distribute $20$ apples among $4$ boys such that each boy gets more than $2$ apples but less that $8$ apples, in addition to the constraint that one of the boys, say $A$ , must always get an even number of apples? Think about it. We will revisit the problem of such general integral equations in example – $39$ and in the chapter on Binomial Theorem. There we’ll learn to solve such problems using the Multinomial theorem.

Example: 5

Find the sum of the divisors of $120$ . Generalise the result for an arbitrary natural number $N$ .

Solution: 5

The divisors of $120$ are listed out below:

${\rm{ \{ 1, \,2,\, 3,\, 4,\, 5,\, 6,\, 8,\, 10,\, 12,\, 15,\, 20,\, 24,\, 30,\, 40,\, 60,\, 120\,\} }}$

The sum of these divisors is $360$ . We have to determine an elegant way to deduce this sum because we cannot repeat everytime the procedure of listing down all the factors and summing them.

For this purpose, we again resort to the use of the prime factorization form.

$120 = {2^3} \cdot {3} \cdot {5^1}$

The sum of the divisors will be

$S = \sum\limits_{\scriptstyle 0\, \le \,\,i\,\, \le \,3\hfill\atop {\scriptstyle 0\, \le \,j\, \le \,1\hfill\atop \scriptstyle 0\, \le \,k\, \le \,1\hfill}} {{2^i} \cdot {3^j} \cdot {5^k}}$

This notation is simply a shorthand which implies that we vary the integral indices $i$ , $j$ and $k$ (in their respective allowed ranges) and this way we will have listed down all the factors and hence evaluated the required sum.

To generate the expression for the sum $S$ , we can alternatively use the following method:

$S = \left( {1 + {2^1} + {2^2} + {2^3}} \right)\left( {1 + {3^1}} \right)\left( {1 + {5^1}} \right)$

Did you realize the trick? Writing $S$ this way also gives rise to all the factors. You are urged to convince yourself about this by expanding this expression and observing that all possible factors will be generated.

Thus, $S$ can now be simply evaluated as follows:

	$S = \left( {1 + {2^1} + {2^2} + {2^3}} \right)\,\,\left( {1 + {3^1}} \right)\,\,\left( {1 + {5^1}} \right)$
	$= 15 \times 4 \times 6$
	$= 360$

This is the same result that we got earlier!

To do the general case, assume that the prime factorization form of $N$ is

$N = p_1^{{\alpha _1}}p_2^{{\alpha _2}}\ldots p_n^{{\alpha _n}}$

where the $\alpha _i'$ are all positive integers and the $p_i'$ s are all primes. The sum ${S_f}$ of all the factors will be

${S_f} = \left( {1 + {p_1} + p_1^2 + \ldots p_1^{{\alpha _1}}} \right)\,\,\left( {1 + {p_2} + p_2^2 + \ldots + p_2^{{\alpha _2}}} \right)\ldots \left( {1 + {p_n} + p_n^2 + \ldots p_n^{{\alpha _n}}} \right)$

Example: 6

Find the sum of all the five-digit numbers that can be formed using the digits $1$ , $2$ , $3$ , $4$ and $5$ if no digit is repeated.

Solution: 6

This problem can be solved very easily if we view it from an individual digit’s perspective. Suppose that we only consider the digit “ $4$ ”. How many numbers will there be with “ $4$ ” in the units place?

From these $24$ numbers, what is the total contribution of the digit “ $4$ ” to the sum we are required to calculate? Since “ $4$ ” is at the units place and it occurs $24$ times, its contribution will be $4 \times 24 = 96$

Similarly, there will be $24$ numbers where “ $4$ ” is at the tens place. The total contribution of “ $4$ ” from these $24$ numbers will be $4 \times 240 = 960$

Proceeding in this way, we see that the total contribution of the digit “ $4$ ” from all the $120$ numbers that can be possibly formed is:

	$4\left( {24 + 240 + 2400 + 24000 + 240000} \right)$
	$= 4 \times 24 \times \left( {1 + 10 + 100 + 1000 + 10000} \right)$
	$= 4 \times 24 \times \,\,11111$

This is the contribution to the sum from only the digit “ $4$ ”. To calculate the entire sum $S$ , we calculate the contributions from all the five digits. Thus, the sum is

$S = \left( {1 + 2 + 3 + 4 + 5} \right) \times 24 \times 11111$ = 3999960

ONE MORE STEP TOWARD BETTER TOMORROW

Tuesday 5 August 2014

CHAPTER 10 - MISCELLANEOUS EXAMPLES

No comments:

https://www.youtube.com/TarunGehlot