Combinations are selection of items from a group of items where the order of selection does not matter. Contrary to permutations which deals with arranging those items/objects in definite order.
Counting problems in the mathematical field known as combinatorics. In simple words, combinations deals with selection while permutations deals with arrangement of objects without actually listing them. In combinations, we can select items in any order. In this article we come across basic principles of counting, combinations formula, permutation and combination and solved examples.
Basic Principles of Counting
Two basic principles of counting are:
1. Fundamental principle of counting: Let the event X occurs in n different ways and another event Y occurs in m different ways. The total number of occurrences of two events is = m x n.
2. Addition principle: Let event X occurs in m different ways and event Y occurs in n different ways and both the event cannot occur together, occurrence of events X or Y is m + n.
Permutation and Combinations Formulas
Permutation: Arrangement of objects in a definite sequence or order and the order of arrangement matters.
Number of permutation of n objects taken n at time is
^{n}P_{n }= n! |
Number of permutation of n objects taken r at time is
\(\begin{array}{l}^nP_r = \frac{n!}{(n-r)!}\end{array} \) |
Combinations: Selection of objects from a group of objects where the order of selection does not matter.
Combinations Formula
Selection of r objects from n objects is given by:
\(\begin{array}{l}^nC_r = \frac{n!}{r!(n-r)!}\end{array} \) |
Important results
2. The number of combinations of n different items taken nothing at all is considered as 1. Counting combinations is counting the number of ways in which all or some of the objects are selected at a time. Selecting no item is the same as leaving behind all the objects . There is only one way of doing that. Thus we define ^{n}C_{0} = 1
⇒ a = b or a = n – b
i.e., n = a+b
Related articles:
Problems on Permutations and combinations
Video Lesson:
How to Calculate the Probability of Combinations
Let us understand the concept with the help of some of the examples:
Example 1:
a) In how many ways can you allot 5 beds to 3 people?
b) In how many ways can the letters of the word ‘MOBILE’ be arranged?
c) How many four digit numbers can be formed with digits 5, 6, 7 and 9 and with distinct digits?
Solution:
a) First person can choose any one bed among the 5 beds available. Similarly, 2^{nd} person will be left with 4 choices and 3^{rd} will be having 3 choices.
Number of ways of allotting = 5 × 4 × 3 = 60 ways
b) Letters of the word ‘MOBILE’ can be arranged in 5! Ways i.e.120 ways.
c) Number of distinct ways of forming 4 digit numbers with distinct digits is 4!, which is 24 words.
Example 2: There are 10 points out of which 3 are collinear. Find
a) How many lines can be formed from by using these points?
b) How many triangles can be formed using these points?
Solution:
a) Since to form one line two points are required. Let’s suppose all the points are non-collinear, the number of lines formed using these points will be ^{10}C_{2 }.
And the number of lines formed using collinear points will be ^{3}C_{2}.
Therefore, the number of lines formed will be ^{10}C_{2} – ^{3}C_{2 }+ 1 (where 1 is for the one line that is being formed using those 3 points).
b) Number of triangles formed if all the 10 points are non-collinear will be ^{10}C_{3. }
Number of triangles formed using 3 non-collinear lines ^{3}C_{3}.
Hence the number of triangles formed when out 10 points 3 are collinear will be ^{10}C_{3 }– ^{3}C_{3.}
Example 3: In a locality there are 87 families, among which 52 families have at most 2 children. In an annual locality quiz competition 20 families are chosen to participate, of which 18 families have at most 2 children. In how many can the choice be made.
Solution: Since the 20 families are to be selected out of which at least 18 families have at most 2 children. Therefore there are three possible combinations
i. 18 – Family (At most 2 child) and 2 – Family (Other)
ii. 19 – Family(At most 2 child) and 1 – Family(Other)
iii. 20 – Family (At most 2 child).
Therefore the possible ways of making the choice is = ^{52}C_{18 }× ^{35}C_{2 }× ^{52}C_{19 }× ^{35}C_{1 }+ ^{52}C_{20 .}
De-arrangement: It can be defined as the permutation arrangement of elements of a certain in such a way that no element of that set appears in original positions. It is given by the formula given below.
Let us have a look into the below solved example to have a clear idea.
Example: In how many can you put 9 letters in respective envelopes such that exactly 4 go into the correct address?
Solution: Number of selecting 4 correct envelopes is ^{9}C_{4, }i.e., 126_{.}.
Derangement of remaining 5 envelopes is D_{5} = 44.
Hence the total number of ways of arrangement = 44 × 126 = 5544.
Problems on Combination
Example 1: In how many ways 5 boys can be arranged in a queue such that
a) Two particular boys of them are always together
b) Two particular boys of them are never together
Solution:
a) If two boys are always together, then they will be treated as one entity. Hence it can be arranged in 4! ways. Again two as one entity can also arrange among themselves in 2 ways.
Therefore required arrangement = 4! × 2 = 24 × 2 = 48 ways.
b) Among the 5 boys total number of permutation will be = 5! = 120.
The arrangement in which two boys are always together is 48 ways.
The remaining in no two boys are never together will be = 120 – 48 = 72 ways.
Example 2: How many combinations can be made up of 4 birds, 5 amphibians and 3 reptiles so that each combination has birds, amphibians and reptiles?
Solution: Since it asks the case of number of combinations i.e atleast 1 of each category among birds, amphibians and reptiles.
So combination of birds is given by 2^{4 }– 1.
Similarly, the combination of amphibians is given by = 2^{5 }– 1.
So the combination of reptiles is 2^{3 }– 1.
Therefore, the total combination at least one of each category will be = (2^{4 }– 1) × (2^{5 }– 1) × (2^{3 }– 1) = 3255.
Example 3: How many different (1) combination (2) permutation can be made by using four letters of the word “COMBINATION”.
Solution:
1. Since in the word “COMBINATION” there are 2-O’s, 2-I’s and 2-N’s. Hence, there are 8
distinct words in letters.
For combination selection has to be made. 4 letter words can be selected in 3 different
ways which are :-
i) All 4 are different letters: There are 8 distinct letters hence selection can be made in = ^{8}C_{4 }= 70
ii) 2 are same letters and 2 are different letters: There are 3 pairs of two same letters from which 1 pair has to be selected, and the remaining two are selected from 7 remaining.
Thus selection can be made in = ^{3}C_{1 }×^{7}C_{3 }= 63.
iii) 2 are same and other 2 are also same letters: From the three pairs selection of two pairs has to be made, i.e., ^{3}C_{2 }= 3.
Total combinations: = 70 + 63 + 3 = 136.
2. Now permutations of these selected 4 letter words will be again 3 cases:
i) 4 different letters: Selection as well as arrangement of these will be ^{8}C_{4 }× 4! = 1680
ii) 2 are same letters and 2 are different letters = ^{3}C_{1 }× ^{7}C_{3 }× 4!/2! = 756
iii) 2 are same and other 2 are also same letters = ^{3}C_{2 }× 4!/(2! × 2!) = 18.
Therefore, Total permutations: = 1680 + 756 + 18 = 2454.
Example 4:
Solution:
Example 5: If ^{2n}C_{3} : ^{n}C_{2} = 44 : 3, then for which values of r, the value of ^{n}C_{r} will be 15?
Solution:
Example 6: In a city no two persons have identical set of teeth and there is no person without a tooth. Also no person has more than 32 teeth. If we disregard the shape and size of tooth and consider only the positioning of the teeth, then what is the maximum population of the city?
Solution:
We have 32 places for teeth. For each place, we have two choices either there is a tooth or there is no tooth. Therefore the number of ways to fill up these places is 2^{32}. As there is no person without a tooth, the maximum population is 2^{32} – 1.
Example 7: If ^{n}C_{9} = ^{n}C_{8}, find ^{n}C_{17}.
Solution:
Given ^{n}C_{9} = ^{n}C_{8}
1/9 = 1/(n – 8)
n – 8 = 9
n = 8 + 9 = 17
Hence,
Example 8: A class consists of 6 girls and 7 boys. In how many ways can a group of 5 members be selected if the team has (i) no girl (ii) at least 3 girls.
Solution:
(i)Only boys need to be selected since the team has no girls.
Therefore 5 out of 7 boys can be selected in ^{7}C_{5} ways.
i.e., 7!/(5! 2!) = 21
(ii) Since the team has to consist of at least 3 girls, it will consist of 3 girls and 2 boys or 4 girls and 1 boy.
3 girls and 2 boys can be selected in ^{5}C_{3} × ^{7}C_{2} ways.
4 girls and 1 boy can be selected in ^{5}C_{4} × ^{7}C_{1} ways.
So required number = ^{5}C_{3} × ^{7}C_{2} + ^{5}C_{4} × ^{7}C_{1} = 210 + 35 = 245
Frequently Asked Questions
Give the Combination formula.
The Combination formula is given by ^{n}C_{r} = n!/r!(n-r)!.
What is the value of ^{n}C_{n}?
The value of ^{n}C_{n} = 1.
When do we use Combination and Permutation?
Permutation is used when order matters and Combination is used when order doesn’t matter.
What do you mean by Derangement?
A derangement is a permutation of the elements of a set, so that no element appears in its original position.