Combinations
Just like permutations, combination is also a way of selecting objects from a larger group, but without considering the order of objects. A combination is thus a selection of r items from a total of n items where order hasn’t got any importance. The formula used for this computation is
Combinations can be of two types:
- Combinations in which there is no repetition
- Combinations in which repetition is allowed
Combinations with repetition are a bit confusing and so we first consider the case of combinations without repetition which are comparatively simple.
Selection of objects without repetition:
The number of selections (combinations or groups) that can be formed from n different objects taken r (0 < r < n) at a time is ^{n}C_{r} = n!/(r!(n-r))!.
Explanation: Let the total number of selection (or groups) = x. Each group contains r objects, which can be arranged in r! ways. Hence number of arrangements of r objects = x × (r!).
But the number of arrangements = ^{n}p_{r}
=> x × (r!) = ^{n}P_{r}
=> x = ^{n}P_{r}/ r!
=> x = n!/(r!(n-r)!) = ^{n}C_{r}.
Selection of objects with repetition:
If we need to compute the combination of n different items taken r at a time wherein the possibility of occurrence of any item may be once, twice or thrice….. up to r times, then it is calculated with the help of the formula ^{n+r-1}C_{r}.
Explanation: Let us consider n objects a_{1}, a_{2}, a_{3}, ...... , a_{n}. Now suppose we have a collection of r objects in which
a_{1} occur x_{1} times,
a_{2} occur x_{2} times,
a_{3} occur x_{3} times,
.................................
.................................
a_{n} occur x_{n} times,
such that x_{1} + x_{2} + x_{3} + ......... + x_{n} = r ......... (1)
0 < x_{i} < r ∀ i ∈ {1, 2, 3, ......, n}.
Now the total number of selections of r objects, out of n
= number of non-negative integral solution of equation (1)
= ^{n+r-1}C_{n-1}
= ^{n+r-1}C_{r}.
Let us refer some of the examples to see what kind of questions can be asked from these sections:
Illustration: Let 15 toys be distributed among 3 children subject to the condition that any child can take any number of toys. Find the required number of ways to do this if
(i) toys are distinct (ii) if toys are identical
Solution:
(i) Toys are distinct
Here we have 3 children and we want the 15 toys to go to the 3 children with repletion. In other words it is same as selecting and arranging children 15 times out of 3 children with the condition that any children can be selected any no. of time which can be done in 315 ways (n = 3, r = 15).
(ii) Toys are identical
Here we only have to select children 15 times out of 3 children with the condition that any children can be selected any number of times which can be done in
^{3+5-1}C_{15} = ^{17}C_{2} way (n = 3, r = 5).
Illustration: in how many ways can a pack of 52 cards be divided equally amongst four players in order? Also find the ways of dividing it into four groups of 13 cards each.
Solution: Let A, B, C and D be the four players and since the 52 cards are to be distributed equally amongst these players, then each will get 13 cards.
Now, 13 cards can be given to A in ^{52}C_{13} ways. Out of the remaining 39 cards, 13 cards can be given to B in ^{39}C_{13} ways. Hence, similarly C will get 13 cards in ^{26}C_{13 }ways.
The remaining 13 cards will be given to D. Hence, the total number of ways in which a pack of 52 cards can be distributed equally amongst 4 players in order is given by
= ^{52}C_{13} x ^{39}C_{13} x ^{26}C_{13} x ^{13}C_{13}
= 52! /39! 13! x 39!/26!13! x 26!/13!13! x 1
= 52!/(13!)4
Similarly, the number of ways in which a pack of 52 cards can be divided equally into 4 groups of 13 cards each
= 1/4! x ^{52}C_{13} x ^{39}C_{13} x ^{26}C_{13} x ^{13}C_{13}
= 52!/4! (13!)^{3}
View the video for more on the topic
Illustration: Find the total number of ways in which six ‘+’ and four ‘-‘ signs can be arranged in a line such that no two ‘-‘ signs occur together.
Solution: Six ‘+’ can be arranged in a line in just one way and in that case they create 7 places shown in the form of dots below:
.+.+.+.+.+.+.
These dots are negative signs and 4 out of these 7 dots may be chosen in ^{7}C_{4 }ways
= 7.6.5.4/ 1.2.3.4.
= 35 ways
askIITians is a unique platform which offers you the benefit of getting answers to your queries on concepts like circular permutations with restrictions, combinations and permutations.
Related resources: