This is our part 1 on tricky GMAT permutation and combination questions and how to solve them efficiently
Let’s start with an example:
John has to form a management team from 10 candidates. He can choose to include any number of members from the candidates all the way from 0 to 10. If 0 candidates are chosen, John is the sole member in the management team. Each candidate has a unique skill and their inclusion in the management team would change the nature of the management team. How many different management teams can John form?
E. None of the above
We may be tempted to say John can form 11 management teams (i.e., with 0 candidates chosen, 1 candidate chosen,.10 candidates chosen).
However, the question throws a twist saying each candidate has a unique skill – i.e., if John chooses only 1 candidate – he can choose 10 types of candidates – and hence 10 different types of management teams.
Hence, the solution we are after is :
Total management teams possible = (# of choosing 0 candidates) + (# of ways of choosing 1 candidate) + (# of ways of choosing 2 candidates) + … + (# of ways of choosing 10 candidates)
Total management teams possible = 10C0 + 10C1 + 10C2 + 10C3 + 10C4 + 10C5 …+ 10C10
Now, nCr = (n!)/(r!(n-r)!)… we know this from basics of permutations and combinations
Using the above formula to compute 10C0 + 10C1 + 10C2 + 10C3 + 10C4 + 10C5 …+ 10C10 is going to be a nightmare J
Trick : nC0 + nC1 + nC2 + nC3 + nC4 + nC5 …+ nCn = 2n
So, the solution is 210 = 1024
We go with option (B)
Why does this formula work?
Imagine the 10 candidates standing in a line and you could go from left to right and while passing each candidate – either decide yes or no. Yes means they are included and no means not.
yes yes yes yes yes yes yes no yes yes is a possibility. And so are :
yes yes yes no no yes yes no yes yes
yes no no no no yes yes no yes yes
…. many others….
# of overall possibilities = 2 (can be yes or no) x 2 x 2 ….x 2 (10 times) = 210
If we generalize this, then for n candidates/items, we are left with :
nC0 + nC1 + nC2 + nC3 + nC4 + nC5 …+ nCn = 2n
This is quite a powerful formula and worth remembering.
Another example of a question :
John is making a cake for his sister’s birthday. He has a box of 7 ingredients – he has to use at least 1 ingredient and can choose as many ingredients as he wants. How many different combinations of ingredients can he use for the cake?
Answer : 27 – 1
Why did we take the 1 out of 27 ? This is because he has to use at-least 1 ingredient so the 1 case with no no no no no no no is not possible and has to be subtracted from the total # of possibilities 🙂