In first part of this series, we discussed about the importance of Permutation and Combination and about Permutation topic. In this part, we are going to discuss about Combination.
Combinations are simpler as order doesn't matter. Going by the example given in Permutation, we have 8 participants: A, B, C, D, E, F, G and H for a swimming competition. Let us assume, instead of medals I am to distribute one pencil each to the first 3 winners.
In how many ways, can you distribute 3 pencils to 8 people?
In this case the order does not matter. If I give a pencil first to A, then to B and then to C, it's same as giving it to C first, followed by A and B.
So, if we have 3 pencils to distribute, there are 3! or 6 variations for every choice we pick. If we want to know how many combinations we have, calculate all the permutations and divide them by all the redundancies. In our case, we have 336 (=8 x 7 x 6) permutations and we divide it by the 6 redundancies for each permutation to get 336/6 = 56.
The general formula is C(n,k) = P(n,k) / k!
which means "Find all the ways to pick k people from n, and divide by the k! variants". So the combination formula, or the number of ways to combine k items from a set of n is:
C(n,k) = n! / [(n-k)! x k!]
There are always fewer combinations than permutations.
The Multiplication Theorem:
If a task can be performed in x different ways, following which a second task can be performed iny different ways, then the two operations in succession can be performed in x × y different ways.
Our cricket team has 3 shirts and 4 pants, how many different kits can be made.
For the shirt we have 3 choices. Similarly for pants we have 4 choices. Just multiply the choices to get the answer. That is 3 x 4 = 12. With first shirt you can choose one from the 4 pants. With second shirt you again can choose any one from the 4 pants and so on.
The Addition Theorem:
If a task can be performed in x different ways and another independent operation can be performed in y different ways, either of the two operations can be performed in (x+y) ways.
You have to arrange n things and you have n choices everytime.
(In other words, there are n possibilities for the first choice, THEN there are n possibilities for the second choice, and so on, multiplying each time.) If we have to put in r places
n × n × ... (r times) = nr
Suppose we have a number lock with 3 dials. Here the number of ways you can arrange 10 digits (0 1 2 3 4 5 6 7 8 9) in 3 dials will be 103
This is because the correct combination can have same number in all the 3 dials. So repetition is allowed.
Don't assume repetition unless mentioned in the question.
Solving a permutation or combination problem is a two-step process,
1. Recognizing the problem type: permutation or combination.
2. Using formulas or models to count the possibilities.
The problem students face is how to identify whether the problem is for permutation or for combination?
The best way to do is switch the items of the question and checking is the result the same?
If you need to pick a Captain and Vice-captain, then switching them changes the result. So, picking a Captain and Vice-captain from a set of candidates is permutation.
If you want to choose 2 players for a fight, then switching the order doesn't change the result: either way, they are fighting each other. Hence, it's a combination.
The second question to ask is whether repetition is allowed or not.
Formula and Shortcuts
- Number of permutations of n different things, taken r at a time, when a particular thing is to be always included in each arrangement is: rn-1Pr-1
- Number of permutations of n different things, taken r at a time, when a particular thing is never taken in each arrangement is: n-1Pr
- Number of permutations of n different things, taken all at a time, when m specified things always come together is: m!×(n-m+1)!
- Number of permutations of n different things, taken all at a time, when m specified never come together is: n!-[m!×(n-m+1)!]
- The number of permutations of n dissimilar things taken r at a time when k(n-kPr-k]×[rPk]
- The number of permutations of n dissimilar things taken r at a time when k particular things never occur is: n-kPr
- The number of permutations of n dissimilar things taken r at a time when repetition of things is allowed any number of times is: nr
- The number of permutations of n different things, taken not more than r at a time, when each thing may occur any number of times is: n+n2+n3+....+nr=n(nr-1) / n-1
- The number of permutations of n different things taken not more than r at a time:
- nCr=nC n-r
The article is written by Vaibhav Mehta, Education Consultant at www.MockBank.com, a Bengaluru based online Test Preparation Company for government/PSU jobs