Tuesday, 5 August 2014

CHAPTER 3 - Introduction to Combinations

In the previous section, we encountered permutations, which correspond to arrangement of objects /things/ entities. In this section, we will encounter combinations which correspond to selection of things (and not their arrangement). We do no intend to arrange things. We intend to select them. For example, suppose we have a team of 15 cricket players. We intend to select a playing team of 11 out of these 15 players. Thus, we want the number of ways in which we can select 11 players out of 15 players. (We are not interested in arranging those 11 players in a row – only the group/ combination of those 11players matters).
Let us make this concept more specific. Suppose we have a set of 6 letters\left\{ {A,\,\,B,\,\,C,\,\,D,\,\,E,\,\,F} \right\}. In how many ways can we select a group of 3 letters from this set? Suppose we had to find the number of arrangements of 3 letters possible from those 6 letters. That number would be {}^{\rm{6}}{P_3}. Consider the permutations that contain the letters A, B and C. These are 3! = 6 in number, namely ABC, ACB, BAC, BCA, CAB and CBA.
Now, what we want is the number of combinations and not the number of arrangements. In other words, the 6 permutations listed above would correspond to a single combination. Differently put, the order of things is not important; only the group/combination matters. This means that the total number of combinations of 3 letters from the set of 6 letters available to us would be {}^{\rm{6}}{P_3}/3! since each combination is counted 3! times in the list of permutations. Thus, if we denote the number of combinations of 6 things taken3 at a time by {}^{\rm{6}}{C_3}, we have
{}^{\rm{6}}{C_3} = \dfrac{{{}^{\rm{6}}{P_3}}}{{3!}}
In general, suppose we have n  things available to us, and we want to find the number of ways in which we can select r things out of these n things.
We first find the number of all the permutations of these n things taken r at a time. That number would be {}^n{P_r}. Now, in this list of {}^n{P_r} permutations, each combination will be counted r! times since r things can be permuted amongst themselves in r! ways. Thus, the total number of combinations of these nthings, taken r at a time, denoted by {}^n{C_r}, will be
{}^n{C_r} = \dfrac{{{}^n{P_r}}}{{r!}} = \dfrac{{n!}}{{r!(n - r)!}}
You should now be able to appreciate the utility of the fundamental principle of counting. Using only a step-by-step application of this principle, we have been able to obtain an expression for ^n{C_r}. As we progress through the chapter, you’ll slowly realise that each and every concept that we discuss and each and every expression that we obtain follows logically as a consequence of this simple principle.
     Example: 1     

Consider the word EDUCATION.
(a) In how many ways can we select a pair of letters consisting of a vowel and a consonant ? Both vowels? Both consonants?
(b) In how many ways can a 5 – letter selection be made with more than 2 vowels?
Solution: 1-(a)

We have 5 vowels and 4 consonants available in the word EDUCATION. A vowel can be selected in 5 ways while a consonant can be selected in 4ways. Thus, a pair consisting of a vowel and a consonant can be selected in 5 \times 4 = 20 ways. Two vowels can be selected in ^5{C_2} ways while two consonants can be selected in ^4{C_2} ways.
Solution: 1-(b)

Since we want more than 2 vowels, we could have 3, 4 or 5 vowels in our 5-letter selection.
Suppose we select 3 vowels for our 5-letter group. This can be done in ^5{C_3}ways. The two remaining letters (consonants) can be selected in ^4{C_2} ways. Thus, 5-letter groups containing 3 vowels can be formed in ^5{C_3} \times {\,^4}{C_2}ways. Similarly, if we had 4 vowels, the possible number of groups would be^5{C_4} \times {\,^4}{C_1}. There’s only 1 group possible containing (all) the 5 vowels.
Thus, the number of required selections is
^5{C_3} \times {\,^4}{C_2}{ + ^5}{C_4} \times {\,^4}{C_1} + 1
Now that we’re done with the introductions, lets move on and see some really interesting and diverse applications of the basic concepts covered till now.
Post a Comment