Combination — Order doesn’t Matter!
This Article will help you Understand concepts of Combination in a way that you will always remember
Before getting into this Article, make sure you have checked out, my Article on Permutation :-
Recap :-
In a sequence order matters
cat != act (!= means doesn’t equal)
even though both words have the same letters: {t, c, a}
Collection :-
Unlike Sequences(Permutation), In a collection order does not matter
cat = cta = act = atc = tac = tca , all these 3! permutation of these 3 letters mean the same in the collection, we can think sequence(permutation) as something which we are arranging in a line, one after other, hence order matters.
But we can think of collection as something which we are putting in a pouch, once we put things in a pouch order doesnt matters, there is just a pouch of things with you, and thats a collection.
all these 6 words means the same: {t, c, a}
Before moving further, make sure, you have understand the analogy of order matters and order doesnt matter, clearly!
Earlier we have looked at the problems where we are trying to form a sequence of length k from a given n objects:-
Question:- How many sequences of 3 letters can you form(no repetition)?
and we know how to do it, this is just(if repetitions is not allowed) -
Now instead of sequences, what if i asked you
Question :- How many collections of 3 letters can you form(no repetition)?
so remember in a sequences we are counting act, cat,.. all of them seperately, couting them 3! times, but in a collection, you will not do that, all of these will be counted as 1. So the question then is, how many collections of 3 letters can you form, if you just put the letters in a pouch and not arrange them in a sequence?
So, We don’t know that yet!
But me know how to count sequences! Can we reuse that knowledge?
so, to do that, let’s break down the problem of creating sequences, it’s a 2 step procedure
But now we are interested in only 1st step which is Making a collection. step 2 is something we don’t care about while making collection.
Number of Sequences = N * k! =
Therefore, N =
This formula does makes an intuitive sense, if it doesnt make sense yet, Lets understand this with an example:-
Quest:- What is the number of ways of selecting 3 vowels from 5 vowels?
There are total 10 collections possible. And each collection has 6 sequences(i.e. 3!)
The number of sequences = 10 * 3! = Number of collections * k!
=> Number of collections = Number of Sequences/k!
=>Number of Collections = n!/(n-k)!*k! =
Acc. to Question and by putting it in Formula :-
Number of Sequences = 60 = 5!/2!
Number of choices, k = 6 = 3!
Number of Collections = 60/6 = 5!/2!*3! = 10 (Which is actually the number of collections, so that’s the intuition behind the formula)
Exercise :- Consider 10 people in a meeting. If each person shakes hand with every other person in the room what is the total number of handshakes?
Collections with Repetitions :-
Question :- Consider, you are in a restaurant which serves 10 different kinds of dishes and now you want to find a combo where you can select any of these 5 items, not just that you are also allowed to repeat the item i.e. you can have 2 servings of idli 2 servings of dosa and then 1 coffee and these would be the collection of 5 items where certain items are repeated. So the question is, How many breakfast combos can you form?
So just imagine this as a restaurant scenario, where all these items are placed in a counter and to begin with there is only 1 serving of each of these items, based on the counter.
So now you have decided to have the first item as idli,and now that counter is empty, because there is only one idli becuase there is only 10 items in your collection of which one has been taken now.
But now you want to order one more idli, so then what will you do, because there is no counter serving idli now. So, now the restaurant need to know this, that you are allowed to repeat the items, so it cannot have only these many counters, the moment you select the idli the manager will have to open the new counter, which also serves idli.
So now you are allowed to select second idli.
So from your point of view, you can think of it that there were these 10 original counters and the moment you selected one idli, there were magical counters which opened up, which serves the same item which you have selected. Since, that counter is serving the same item which you have selected, you have the choice of repeating it.
Now we again have selected one more plate of idli and that counter is empty, the way which we can look at it as, there were 11 counters out of which 2 are serving idli and you have selected 2 idlis.
But now what, the manager have to again realise that if you want you can choose all the 5 dishes to be idli, the moment you have selected another idli there will be another magical counter which opens up and will serve idli, and now you have choice of selecting it again, but this time you have decided to not to select idli, you have selected poha, the moment you select poha the manager has to open up new counter, that will serve poha, so if you want you can select poha again.
And now again you have selected poha and you have one more dish left and if you could choose poha again, so manager has to open the another counter which will serve poha, but now you have decided to select vada, so now the vada has gone from the counter and now the manager wont have to do anything becasue you are served, all the 5 dishes are served.
It doesn’t matter which item you select, there will be only k-1 magic counters that will open, in our case k=5 so k-1 magic counter had opened up i.e. 4
This brings us to our Principle :-
The number of ways of selecting k objects from given n objects with repetitions is
Collections-Multiplication Principle :-
Consider a scenario, you are a captain of a cricket team and the team of course consists of batsmen, keepers, pacers and spinners, there are 16 players available, 7 batsmen, 2 keepers, 4 pacers and 3 spinners. and you want to select a team of 11, as a captain you would desire that there will be 5 batsmen, 1 keeper, 3 pacers and 2 spinners, how you can form a team of 11 players out of 16 players.
The answer to this is definetly not 16C11
Collection-Substraction Principle :-
In how many ways can you form a 4-member committee containing at least one gynaecologist?
We have Learned Substraction principle in well detailed in Permutation Article, where we have studies in a question having atleast restriction it easier to solve using substraction principle. So,
A = all possible committees of 4 members.
B = all possible committees containing at least one gynaecologist.
C = all possible committees containing no gynaecologist.
Summary :-
This is all about Collections(Combinations). Have Any Doubts? Let me know in the comments below! Any Suggestions/Feedbacks are always Appreciated.
Thanks for Reading!
Cheers :)
