ONE MORE STEP TOWARD BETTER TOMORROW : CHAPTER 6

Tuesday, 5 August 2014

CHAPTER 6 - MORE Worked Out Examples

Example: 1

	(a) Consider the set of letters $\left\{ {a,a,a,b,c,d} \right\}.$ How many permutations of this set exist?
	(b) Consider the set of letters $\left\{ {a,a,a,b,b,c,d,e} \right\}.$ How many permutations of this set exist?
	(c) Generalise the results of the previous two parts. If we have a set of $\left( {m + n + p + \dots} \right)$ things where a particular thing, say $X$ , is repeated $m$ times, $Y$ is repeated $n$ times, $Z$ is repeated $p$ times, and so on, find the number of permutations of this set.

Solution: 1-(a)

The main issue now is that we have a repetition of things. If the things we have were all different, the number of permutations would have been easy to calculate. But now, with repetition of things, the number of permutations will change (it will actually decrease, if you think about it carefully). Let us calculate the permutations in this case from first principles

We have $3$ (repeated) “ $a$ ” letters, a “ $b$ ”, a “ $c$ ” and a “ $d$ ”. In all, $6$ letters. Consider, for a moment, that the $3$ “ $a$ ” s are all different. Let us denote the $3$ different “ $a$ ”s by ${a_1}, {a_2}$ and ${a_3}$ . Our set of letters is now $\left\{ {{a_1},{a_2}\,,{a_3},b,c,d} \right\}.$ The number of permutations of this set is simply $^6{P_6} = 6!$

If we list down all these $6!$ permutations, we will see that $6$ permutations from this list will correspond to only one permutation, had the “ $a$ ”s been all the same. Why?

Consider any particular permutation with the “ $a$ ” s all different, say $\left\{ {b,{a_1},{a_2},c,{a_3},d} \right\}.$ If we fix the letters “ $b$ ”, “ $c$ ” and “ $d$ ”, the $3$ different “ $a$ ” s can be permuted amongst themselves in $3! = 6$ ways. We now list down all the $6$ permutations so generated on the left hand side in the figure below, and see that these $6$ permutations correspond to a single permutation if the “ $a$ ” s were all the same:

Thus, the actual number of permutation with the “ $a$ ”s all same will be

$\dfrac{{6!}}{{3!}} = \dfrac{{6!}}{6} = 120$

Solution: 1-(b)

We now have $3$ repeated “ $a$ ” s and $2$ repeated “ $b$ ” s, and a total of $8$ letters. If we for a moment take the “ $a$ ” s and “ $b$ ” s as all different, the total number of permutations of this set of $8$ letters would be $^8{P_8} = 8!$

However, once we list down these $8!$ permutations, we will see that (as in the previous part) $3! = 6$ permutations in this list will correspond to a single permutation if the “ $a$ ”s were all the same. Similarly, $2!=2$ permutations in this list will correspond to a single permutation if both the “ $b$ ”s were the same. Thus, the actual number of permutations if “ $a$ ”s and “ $b$ ”s were the same would be $\dfrac{{8!}}{{3!2!}}$

Solution: 1-(c)

These results can now easily be generalised for this general set and the number of permutations will be

$\dfrac{{(m + n + p + \ldots)!}}{{m!n!p! \ldots}}$

From this example once again, the power of the fundamental principle of counting should be quite evident. Using a logical development/extension of this principle, we see that we’ve been able to solve non-trivial questions like the one above.

Tuesday, 5 August 2014

CHAPTER 6 - MORE Worked Out Examples

No comments:

https://www.youtube.com/TarunGehlot