ONE MORE STEP TOWARD BETTER TOMORROW : CHAPTER 9

Tuesday 5 August 2014

CHAPTER 9 - Worked Out Examples

Example: 1

Give a combinatorial (logical) justification for this assertion:

${}^n{C_0} + {}^{n + 1}{C_1} + {}^{n + 2}{C_2} +\ldots + {}^{n + r}{C_r} = {}^{n + r + 1}{C_r}$

Solution: 1

The right hand side tells us that we have to select $r$ persons out of a group of $n + r + 1$ persons. To do so, we consider any particular group of $r$ persons from these $n + r + 1$ persons. Specify these $r$ persons by the symbols ${A_1},{A_2} \ldots {A_r}$ .

Now, to count all the possible r-groups from this group of $n + r + 1$ , we consider the following mutually exclusive cases:

(1) The $r$ -group does not contain ${A_1}$

Such r-groups can be formed in ${}^{n + r}{C_r}$ ways since we have to select $r$ people out of $n + r$ .

(2) The $r$ -group contains ${A_1}$ but not ${A_2}$

We have to select $(r - 1)$ people out of $(n + r - 1)$ because we already have selected ${A_1}$ so we need only $(r - 1)$ more people and since we are not taking ${A_2}$ , we have $(n + r - 1)$ people to choose from. This can be done ${\,^{n + r - 1}}{C_{r - 1}}$ ways.

(3) The $r$ -group contains ${A_1}$ , ${A_2}$ but not ${A_3}$

	We now have to select $(r - 2)$ people out of $(n + r - 2)$ . This can happen in ${}^{n + r - 2}{C_{r - 2}}$ ways. Proceeding in this way, we arrive at the last two possible cases.
	$\vdots$

(r) The $r$ -group contains ${A_1},\,\,{A_2}\ldots {A_{r - 1}}$ but not ${A_r}$ .

We need to select only $1$ person out of $(n + 1)$ available for selection. This can be done in ${}^{n + 1}{C_1}$ ways.

(r+1) The $r$ -group contains ${A_1},\,\,{A_2}\ldots {A_r}$

In this case, our $r$ -group is already complete. We need not select any more person. This can be done in ${}^n{C_0}$ or equivalently $1$ way.

Convince yourself that these $(r + 1)$ cases cover all the possible cases that can arise in the formation of the $r$ – groups. Also, all these cases are mutually exclusive. Thus, adding the number of possibilities of each case will give us the total number of $r$ -groups possible, i.e.

${}^n{C_0} + {}^{n + 1}{C_1} + {}^{n + 2}{C_2} + \ldots + {}^{n + r - 1}{C_{r - 1}} + {}^{n + r}{C_r} = {}^{n + r + 1}{C_r}$

Example: 2

How many distinct throws are possible with a throw of $n$ dice which are identical to each other, i.e. indistinguishable among themselves ?

Solution: 2

The important point to be realised here is that the dice are totally identical. Suppose we had just $2$ dice, say die $A$ and die $B$ . Suppose that, upon throwing these dice, we get a “two” on $A$ and a “three” on $B$ . This case would be the same as the one where we get a “three” on $A$ and a “two” on $B$ because we cannot distinguish between $A$ and $B$ . What we are concerned with is only what numbers show up on the top of the dice. We are not concerned with which die shows what number. This means that if we have $n$ dice and we throw them, we are only concerned with how many “ones”, “twos”, “threes” etc show on the top faces of the dice; we are not at all interested in which die throws up what number.

If we denote the number of “ones” we get by ${x_1}$ , number of “twos” we get by ${x_2}$ and so on, we will have

${x_1} + {x_2} + \ldots + {x_6} = n$

Thus, the total number of distinct throws will be simply the number of non-negative solutions to this integral equation.

As discussed earlier, this number will be ${}^{n + 6 - 1}{C_{6 - 1}} = {}^{n + 5}{C_5}$ .

What would be the number of distinct throws if the $n$ dice were not identical?

Example: 3

Give combinatorial arguments to prove that

$\sum\limits_{r = 1}^n r \cdot {}^n{C_r} = n \cdot {2^{n - 1}}$

Solution: 3

Let us first interpret what the left hand side of this assertion says.

Suppose we have a group of $n$ people. We select a sub-group of size $r$ from the group of $n$ people. This can be done in ${}^n{C_r}$ ways. Once the sub-group has been formed, we select a leader of that sub-group, and send that sub-group on an excursion. The leader can be selected in $r$ ways. Thus, the total number of different ways in which an $r$ – group can be formed with a unique leader is $r \times {\,^n}{C_r}$ .

Now $r$ can take any integer value from $1$ to $n$ , i.e. $1 \le r \le n$ . Thus, the total number of all possible sub-groups, each sub-group being assigned a unique leader, will be $\sum\limits_{r = 0}^n r \cdot {}^n{C_r}$ which is the left hand side of our assertion.

To prove this equal to the right hand side, we count the sub-groups from a different angle. We count all those sub-groups in which a particular person, say $A$ , is the leader.

Since $A$ is the leader, $A$ is fixed in our sub-group. For each of the remaining $(n - 1)$ people, we have two options. We either put the person in the group led by $A$ or we don’t. Thus, the total number of sub-groups in which $A$ is the leader will be

	$\underbrace{2 \times 2 \times 2 \times\ldots \times 2 }_{\rm{Comment:1}}= {2^{n - 1}}$
	Comment:1 $(n - 1)$ times

Since any of the $n$ persons can be the leader, and under each person’s leadership, ${2^{n - 1}}$ groups can be formed, the total number of sub-groups, each sub-groups under some unique person’s leadership is $n \cdot {2^{n - 1}}$ . This proves our assertion that

ONE MORE STEP TOWARD BETTER TOMORROW

Tuesday 5 August 2014

CHAPTER 9 - Worked Out Examples

No comments:

https://www.youtube.com/TarunGehlot