Combinations are the selection of items from a group of items where the order of selection does not matter. It is contrary to permutations which deal with arranging those items/objects in a definite order.
Counting problems in the mathematical field is known as combinatorics. In simple words, combinations deal with selection while permutations deal with the 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 as follows:
1. Fundamental principle of counting: Let 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 events cannot occur together, then the occurrence of events X or Y is m + n.
Permutation and Combinations Formulas
Permutation: Arrangement of objects in a definite sequence or order, where the order of arrangement matters.
The number of permutations of n objects taken n at a time is
^{n}P_{n }= n! |
The number of permutations of n objects taken r at a 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 this. 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 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) The first person can choose any one bed among the 5 beds available. Similarly, the second person will be left with 4 choices, and the third will be having 3 choices.
The 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 by using these points?
b) How many triangles can be formed using these points?
Solution:
a) To form one line, two points are required. Suppose that all the points are non-collinear, then 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. }
The number of triangles formed using 3 non-collinear lines will be ^{3}C_{3}.
Hence, the number of triangles formed when out of 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, there are three possible combinations.
i. 18 – Family (At most 2 children) and 2 – Family (Other)
ii. 19 – Family (At most 2 children) and 1 – Family (Other)
iii. 20 – Family (At most 2 children).
Therefore, the possible ways of making a choice are = ^{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 certain elements in such a way that no element of that set appears in its original position. It is given by the following formula:
Let us have a look at the solved examples to have a clear idea.
Example: In how many ways can you put 9 letters in respective envelopes such that exactly 4 go to the correct address?
Solution: The number of selecting 4 correct envelopes is ^{9}C_{4, }i.e., 126.
The derangement of the 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, the required arrangement = 4! × 2 = 24 × 2 = 48 ways.
b) Among the 5 boys, the total number of permutations will be = 5! = 120.
The arrangement in which two boys are always together is 48 ways.
In the remaining, 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 a number of combinations, i.e., atleast 1 of each category among birds, amphibians and reptiles,
The 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 of 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) permutations 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, there are 8
distinct words in letters.
For combination, a selection has to be made; 4 letter words can be selected in 3 different ways, and they are listed below:
i) All 4 are different letters: There are 8 distinct letters hence selection can be made in = ^{8}C_{4 }= 70.
ii) 2 are the 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, the selection can be made in = ^{3}C_{1 }×^{7}C_{3 }= 63.
iii) 2 are the same, and the other 2 are also the same letters: From the three pairs, the 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 the same, and the other 2 are also the same letters = ^{3}C_{2 }× 4!/(2! × 2!) = 18.
Therefore, the 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 sets 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 the 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 and (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, the 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 ^{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?
A permutation is used when order matters, and a 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.
Comments