Combination Definition:
Combination is a process of selection of elements from a set of elements in which the order of selection does not matter. If the order of selection is a criterion in a selection process, then such a selection process is called the permutation. Combination is a special type of permutation selection in which the order does not matter. So, the number of permutations is always greater than the number of combinations for selecting ‘k’ elements out of ‘n’ elements.
Combination Examples v/s Permutation Examples:
Let us consider an example of a classroom with 20 students among which three are boys. Suppose 5 students are to be seated on each bench. The number of possible selections such that 5 students are seated in each bench is calculated as the number of combinations of choosing 5 out of 20. However, if all the three girls are to be seated together, then the example becomes a process of permutation.
Combination Formula:
Consider a set ‘A’ in which there are ‘n’ distinct elements out of which ‘p’ distinct elements are to be chosen. The number of ‘p’ combinations that can be formed out of a set with ‘n’ elements is given by its binomial coefficient.
nCp = [(n) (n – 1) ( n – 2) ……. (n – p + 1)] / [(p – 1) ( p – 2) ……. (1)]
This can be rewritten in terms of the factorial of terms as:
nCp = n! / (n – p)! p!
In the above equation, it is always true that n > p. If n < p, the value of nCp is equal to zero.
In the above equation,
‘C’ represents the combination of items
‘n’ is the total number of items available for selection
‘p’ is the number of items to be selected for the given combination
Relation Between Permutation and Combination Formula:
A combination is a special case of permutation. It is a permutation in which the order of choosing the elements is not considered. So, it is always true that the number of possible combinations is always less than that of the number of possible permutations. The formula for a number of permutations is:
nPq = [frac{n!}{(n – q)!}] → (1)
The number of combinations in which ‘q’ elements can be chosen out of ‘n’ elements is given as:
nCq = [frac{n!}{(n – q)!}] q! → (2)
Comparing equations (1) and (2), it is evident that the permutations and combinations can be related as follows:
nCq = nPq / q !
In the above equation,
nCq is the combination of ‘q’ items out of ‘n’ items
nPq is the permutation of ‘q’ out of ‘n’ items
‘n’ is the total number of items available for selection
‘q’ is the number of items selected during the selection process
Combination Properties:
-
nC0 = nCn = 1
-
nC1 = nCn-1 = n
-
nCr + nCr-1 = n+1Cr
-
nCr = nCn-r
-
nCr = nPr / r!
Problems on Combination Examples:
1. In how many ways can a coach choose 9 players out of 23 players? (Hint: Use the formula to solve combination examples)
Solution:
Total number of players (n) = 23
Number of players to be chosen (r) = 9
Total number of ways in which the players can be chosen is calculated in terms of combination definition as:
[C_{r}^{n}] = [frac{n!}{(n-r)!.r!}]
[C_{23}^{9}] = [frac{23!}{(23-9)!.9!}]
[C_{23}^{9}] = [frac{23!}{14!.9!}]
[C_{23}^{9}] = [frac{23times 22times 21times 20times 19times 18times 17times 16times 15times 14!}{14!times 9times 8times 7times 6times 5times 4times 3times 2times 1}]
[C_{23}^{9}] = 817190
There are 817190 ways to choose 9 players from a set of 23 players.
2. How many committees of 3 members can be formed out of a group of 7?
Solution:
Total number of members in a group (n) = 7
Number of members in each committee (r) = 3
Total number of committees possible is calculated as the combination of 3 out of 7.
It is computed using the combination formula as:
[C_{r}^{n}] = [frac{n!}{(n-r)!.r!}]
[C_{7}^{3}] = [frac{7!}{(7-3)!.3!}]
[C_{7}^{3}] = [frac{7times 6times 5times 4!}{(7-3)!.3!}]
[C_{7}^{3}] = [frac{7times 6times 5times 4!}{4!.3!}]
[C_{7}^{3}] = 35 ways
So, 3 members out of 7 members can be chosen in 35 different ways which means 35 choices are available to form a committee of 3 members.
Fun Facts About Combination Formula:
-
Permutations and combinations are widely used in problems involving selection and arrangement of things in probability, genetic engineering and life sciences.
-
A ‘Combination Lock’ should be called a ‘Permutation lock’ because here the order of numbers matters a lot. But if it is a combination lock the order of numbers should not be a concern at all. (Hint: Recall what is combination definition).