Combination

There are different ways to select objects from a given set of objects to form subsets without replacing the objects. Two such common methods of selecting the objects from a set of objects are permutations and combinations. If the selection of objects is based on the order of selection, then such a selection is called a permutation and if the selection of the objects is independent of the order of selection, then the process of selection is called a combination.

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{23\times 22\times 21\times 20\times 19\times 18\times 17\times 16\times 15\times 14!}{14!\times 9\times 8\times 7\times 6\times 5\times 4\times 3\times 2\times 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{7\times 6\times 5\times 4!}{(7-3)!.3!}\]

\[C_{7}^{3}\] = \[\frac{7\times 6\times 5\times 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).