Basics of Permutation & Combination
The moment I have used the term “Permutation and Combination” in front of my students, I have seen a huge bipolarity in the reactions that I get. There will always be one group of students who would absolutely hate this area of study, since they hated to mug up too many approaches and they always mix them up. The other group of students always have a smile on their faces when I mentioned the term. The latter group love this area and typically can understand the approaches and their meanings.
I promise you that regardless of which of the two groups you fall in, you will have some food for thought after you complete reading this article. When I was introduced this area of study for the first time, even I had inquiries on what these formulae (of nCr ; n! ; nPr) actually imply. Because ton understand any part of Mathematics, it’s important to understand the significance of the Operations that we can use in that area.
Like Multiplication (meaning repetitive addition), Division (repetitive subtraction), Exponents (repetitive multiplication), etc, even these nCr and n! have a meaning. In order to understand the area of Permutation and Combination, we need to understand these meanings. But that’s for another day. Today our task is much more Simple. Our task is to understand something more on Basic Foundation level.
So, let’s develop some Basic Foundations first. First of all, what is Combinatorics? Some of you must have heard this word, some you may not have. Combinatorics is an area of Mathematics which deals with Principles of Counting. Counting what? The number of ways of doing a certain amount of activity or the number of ways a certain incident might occur.
If it’s as simple as counting ways, then why do we need formulae for that? This might be a question in your mind at this moment. Agreed! We might not need it. But, if we count the number of ways one after another, it might take a long time to that (a very simple activity might have 210 = 1024 ways to happen).
Combinatorics revolves around finding Structured ways of Counting ways of doing an activity. These structures are developed from some Principles. These Counting Principles will be better understood if we understand Four Key Differences. In this article we have elaborated on these differences. Let us explore and understand them, one difference at a time.
Key Difference #1: When to Add vs When to Multiply
Everyone who has studied Permutation and Combination (in short P & C), have heard about this difference for sure. The alongside image should indicate what we have read in textbooks and been explained to in classes.
Whenever we have different cases, we should add the number of ways of these cases separately. In case of Independent and Correspondingly Occurring cases, we must multiply the number of ways.
But what is Dependency?
Let’s understand this with an example. (Check the image alongside)
Since the boy can wear any shirt with any trouser, we have 4 choices of wearing a trouser for each shirt. This means total cases should be 4 + 4 + 4 = 3 × 4. [Remember: Repetitive addition is simply multiplication]
Now, let’s add a constraint to the same question.
As shown in the image beside, the boy cannot wear the white shirt with the blue trouser. Say, each shirt and each trouser are of different colours. In this case, this adds a dependency: The choice of a shirt depends on the choice of the trouser and vice versa.
The cases that are explained in the image will be as follows:
Case 1: If he wears a blue trouser (1 choice), he can wear any one of the 2 non-white shirts.
Case 2: If he wears a non-blue trouser (3 choices), he can wear any of the 3 shirts he has.
Now, in each case the shirt and trouser are worn correspondingly, so we multiply as shown in the above image.
What is Correspondingly Occurring cases?
As explained in the image above, Correspondingly Occuring cases are situations in both the activities happen together. For our earlier example, the boy wears a shirt (activity 1) and wears a trouser (activity 2).
Key Difference #2: Selection vs Arrangement
One Word => “Ordering”. In simpler words, sequencing of the elements.
When we select few elements, the order in which we select them doesn’t matter. For example, say I have 10 dice of different colours in a basket and I pick 3 out of them randomly. If I pick Blue, Green and Yellow coloured dice, then that would be SAME as picking the Green, Blue and Yellow coloured dice.
On the other hand, if we arrange the 3 dice that I picked in a line or I hand two of them to two of my friends, then the order of the 3 dice suddenly matters. The placement of the 3 dice in the row or with the three people (including the one left with me) can now change among themselves.
This idea you Must have read in all your textbooks. But let us go a step forward and get some more clarity in this difference. Let’s take another example question. Check the image below.
All of us should get the answer accurately in this case. It would be 10C3 that is the first option. But why not the second option? It also uses ‘C’ right?
Let’s first gain some perspective. What is the meaning of the first option?
This is the first part one should focus their attention on. 10C3 doesn’t indicate selection of 3 items out of 10 items. Rather, it indicates the number of ways we can do that. So there are two key things to note in this expression. (Key note 1: “number of ways”)
There is another implicit idea that you should never forget. The selection, whenever done, must be for some purpose. In the example we took, the “purpose” was to form a team. The purpose could vary from question to question, but there will Always be a purpose associated with nCr.
If you understand the above two notes, you should now be able to understand EXACTLY why the second option is not correct.
Each of those 10C1 ; 9C1 ; 8C1 will have some purpose. Define the purpose of them as you wish to and look at the following two cases.
It should be evident from the above image, the 10C1 × 9C1 × 8C1 counts A, B, C and B, C, A as two separate cases. But since our objective was to select 3 people, the order in which they got selected automatically was taken into account.
So, remember the difference between Selection and Arrangement in the following manner.
- If we select the required number of items in a “bunch”, then Order is not included.
- If we select the required number of items “one at a time” from the same set of items, it implicity included the Order.
Key Difference #3: Identical Items vs Distinct Items
The meaning should be pretty obvious from the name itself. Identical are those items which are non-distiguishable among each other. Distinct items can be distinguished somehow, depending on the context of the question. Let’s say we have 10 blue coloured marbles and 8 green coloured marbles. The blue marbles should be identical to each other, so should the green marbles be. However, a blue marble should be distinct (or different) to a green marble.
But how does this impact in Permutation and Combination?
Let’s try and assign four marbles in two different bowls. Say initially, we have one marble green in colour, another blue in colour, the next red in colour and the fourth in yellow. Let us try some ways to assign these four marbles in the two bowls.
As it should be now, evident from the above images, that each of these cases should be different from each other. If we look at the first two distributions, then we can see that the Number of Marbles in each bowl does not change. However in the last distribution, that does change.
So, when it comes to Distinct items, both the NUMBER of ITEMS and WHICH ITEMS matter.
Now, let’s consider that each of the four marbles are green in colour and let’s again distribute them in the two bowls. Let us again look at three such distributions.
It should be obvious from the first two images, that which two marbles we place in the first two bowls doesn’t matter. But if we change the number of marbles in the bowls, it should be a different distribution. So, if the items are Identical to each other, the Only thing that matters is the NUMBER of ITEMS (Not Which Ones any more).
PS: Whenever we say 10C3 are the number of ways we can select 3 items out of 10 choices, we can only say that if the 10 items are distinct to each other. If the 10 items are identical to each other, then the number of ways you can pick 3 items out of these 10 is simply 1 way.
As a challenge, try to find the number of ways you can pick 3 marbles out of 10 marbles, out of which 5 are green, 2 are blue and 3 are white. Post your answers in the comments below.
Key Difference #4: Groups vs Boxes
We have a very good example to explain this idea to you all. Let’s take up two questions.
In the first question, let us consider A = 1, B = 9 vs A = 9, B = 1. Since, the assignments are into variables, they will be different to each other. So, A taking 1 and B taking 9 will be different from A taking 9 and B taking 1.
In the second question, we just need to find pairs of natural numbers which add up to 10. Counting 1 and 9 as one such pair is sufficient. We won’t need to count 9 and 1 as a pair again (it’s the same pair, afterall).
There’s a technical term to it (REMEMBER IT). Had the question said find the ORDERED Pairs of Natural numbers, it means the order of the numbers that we take in the pairs now matters. So, in (1, 9) we are taking 1 first and 9 next. However, in (9, 1) we are taking 9 first and 1 next. Since order matters, we will count them as different pairs.
To summarize, if the question uses the term “Boxes” (and doesn’t say identical boxes) or uses variable names, then by default you should count Ordered Solutions (unless otherwise specified). However, if the question uses the term “Groups” (and doesn’t say distinct groups), then by default you should count Unordered Solutions (unless otherwise specified).
Remember our previous example where we were distributing 4 marbles into two bowls. We would have considered the bowls to be distinct, even if the question didn’t explicitly mention that. But had the question explicitly said Identical Bowls, we would have simply considered them as Boxes. Check the two images below.
When the bowls are distinct (or the question simply says bowls), the above two distributions are different to each other. Because in the first distribution, the bowl in the left has the yellow and the red marbles, and the other bowl has the other two marbles. However in the second distribution, this has reversed. So, these two dsitributions will be treated differently.
However if the question says Identical Bowls (or simply groups), then all we care is the red and the yellow marbles are together, whereas the blue and the green marbles are together. That’s the same in both the images. So, they will be treated as the same distribution.
As another challenge, try another question. In how many ways can 6 people be divided into two groups of 3 people, such that they compete against each other in a quiz competition. Post your answers in the comments below.
Summary of the Basic study of Permutation and Combination
To end our discussion, we would like to re-emphasize on the understanding of the logic and reasoning in this area of study. Common sense plays a vital role in every Permutation and Combination problem. So, try to comprehend the questions properly and apply common sense before you reason out the problem. Try to use the 4 Differences that we discussed in this article in every P&C problem that you face from now on and watch how they interact with each other.
Hope you had fun reading the article. More of these are to follow. If you liked it, then do share among your friends and fellow CAT, GMAT aspirants. You can click here to watch a playlist of few videos on this topic uploaded in our YouTube channel. We have a plan of uploading many more in the upcoming days. Also Subscribe to our YouTube Channel if you like the playlist.
If you need conceptual clarity on these things and looking for a structured course for the same, you can purchase our Comprehensive CAT course by clicking here. We have put more 90 LESSONS for FREE TRIAL in the Comprehensive Course. You can simply Enroll for Free to avail the same.