Permutation and combination

Subject of arrangements and selection

Permutation and combination are two of the important topics covered in high school that have wide applications in many areas of mathematics and other activity areas. Together, these deal with such questions as,

• How many ways three letters can be arranged out of the first six letters of English alphabet?
• How many ways 4 out of 9 students can be seated in the first row of a class where seats are numbered?
• How many ways a captain and vice captain can be selected out of 11 players in a cricket team?
• How many 13 card hands are possible out of a standard pack of 52 playing cards?

In permutation ordering of the objects selected is important whereas in combination it is not - selection of the objects only is important. Essentially, these two together form the subject of arrangements.

Looking closely we find arrangements all around us.

Permutation

Permutation of distinct objects

Permutation is - creating an arrangement of a set of specific number of distinct objects from another set of distinct objects in which the ordering of the objects is meaningful. For example, If we make 3 letter permutations of the 4 letters $\left[a, b, c, d \right]$, the letter arrangement $abc$ will form a permutation that is different from the arrangement of same three letters, $bca$. This second arrangement is another unique 3 letter permutation of the 4 letters $\left[a, b, c, d \right]$.

Problem 1:

In how many ways can the three letters a, b and c be permuted ?

Solution 1: Among all the possible 3 letter permutations of three letters, the first position can have any of the three letters. There are 3 possible ways a letter in the first position can be selected - either a, b or c.

---

Method of enumerating set of all the ordered arrangements or permutations

So the first place can be occupied by the three letters in 3 possible ways.

For each of these 3 possible arrangements now, the first place has already been decided and we have 2 remaining letters that can be arranged in only 2 distinct ways in the second position.

When we decide the letter for the second position, the letter for the third position is automatically decided as remaining letter is only 1.

---

Thus, the total number of 3 letter permutations or distinctly ordered arrangements possible for the three letters a, b, c is,

$^3P_{3}= 3\times{2} = \text{factorial}(3)\space=3\text{!}$

$\hspace{9mm}=3\times{2}\times{1}=6$

All possible 3 letter permutations or distinct arrangements of 3 letters a, b, c are,

$\text{abc, acb, bca, bac, cab, cba}$

If there were 4 distinct letters $\left[a, b, c, d \right]$ instead of three, the total number of different ways to arrange the letters or permutations will be,

$^4P_4=4\text{!}=24$

Case 2: Let us now consider another case of all possible permutations of 3 letters out of 4 letters $\left[a, b, c, d \right]$. This is permutation of 3 distinct objects out of 4.

---

Method of enumerating the ordered arrangements or permutations

In this case, first let us fix the first position. We can put any of the 4 letters in the first position. After fixing the 1st position, now we are left with 3 letters and in the second position we can put any of these 3 letters. Lastly after fixing each of the first two positions we will have 2 possibilities for the 3rd position.

---

So total number of permutations,

$^4P_{3}= 4\times{3}\times{2} = 24 = \displaystyle\frac{4\text{!}}{(4-3)\text{!}}$

Similarly, number of permutation of 3 objects out of 5 different objects is,

$^5P_{3}= 5\times{4}\times{3} = 60 = \displaystyle\frac{5\text{!}}{(5-3)\text{!}}$

In general, number of permutations of $n$ distinct objects out of $m$ distinct objects is,

$^mP_{n}= m\times{(m-1)}\times{(m-2)}...\times(m - n + 1) $

$\hspace{10mm}=\displaystyle\frac{m\text{!}}{(m-n)\text{!}}$

The expression $m\times{(m-1)}\times{(m-2)}...\times(m - n + 1)$ is multiplied and divided by ${(m-n)\text{!}}$ to get ${m\text{!}}$ in the numerator and ${(m-n)\text{!}}$ in the denominator.

This is how the well known formula for permutation is derived. But more importantly, it is vital to understand how the number of $m\times{(m-1)}\times{(m-2)}...\times(m - n + 1)$ arrangements or permutations are formed following a systematic method.

Take note: Number of permutations of $m$ out of $m$ distinct objects is same as $(m - 1)$ out of $m$ distinct objects.

$^mP_{m}= \displaystyle\frac{m\text{!}}{(m-m)\text{!}} = \displaystyle\frac{m\text{!}}{0\text{!}} $

$\hspace{10mm}= \displaystyle\frac{m\text{!}}{1\text{!}} = \displaystyle\frac{m\text{!}}{\left[m-(m - 1)\right]\text{!}} =  ^mP_{m-1}$

That means 4 out of 4 object permutations, that is $4\text{!}=24$ is same as 3 out of 4 permutations, which is also 24.

By definition, $0{!} = 1$.

Problem 2:

How many 3 digit numbers can be formed using the digits 1, 2, 3, 4, 5 with no digit repeating?

Solution 2: The total number of 3 out of 5 permutations of the given digits are,

$^5P_3=\displaystyle\frac{5\text{!}}{(5-3)\text{!}}$

$\hspace{9mm}=\displaystyle\frac{5\text{!}}{2\text{!}}=5\times{4}\times{3}=60$

Problem 3:

How many 3 digit numbers greater than 300 can be formed using the digits 1, 2, 3, 4, 5 and 6 with no digit repeating?

Solution 3: Here the possible digits in the first position of the resultant numbers will be 3, 4, 5 or 6. The digits 1 or 2 in the first position will make the resultant number less than 300.

After deciding the digit in the first position in 4 possible ways we are left with 2 positions and 5 digits. So the desired number of permutations is,

$4\times{^5P_2}= 4\times{\displaystyle\frac{5\text{!}}{(5-2)\text{!}}}$

$\hspace{16mm}=4\times{\displaystyle\frac{5\text{!}}{3\text{!}}}=4\times{5}\times{4}=80$

Problem 4:

How many two digit numbers can be formed out of the digits 2, 3, 4 and 0 without repeating digits?

Solution 4: The desired number of permutations may at first seem to be a 2 out of 4 permutation, which is 12. But if you are careful you would remember that in the first position of a number (which is the most significant position) placing a 0 is ignored. If we place a 0 in the first position, the resultant number will then become a single digit number.

So we can place only 3 digits 2, 3 and 4 in the first position. Rest of the digits are then 3 and number of positions 1. This second position can then be filled in 3 ways.

So the desired number of numbers is $3\times{3}=9$ instead of 12.

It will be 3 less than 12 for the prohibition of 0 in the first position.

---

Important note:

If you are clear about the concept of how ordered arrangements or permutations are formed, you should always be able to approach a problem of permutation in this way and should use the formula of permutation only when its application is absolutely straightforward without any complication.

As the formula of permutation comes only after you enumerate the permutations systematically and exhaustively following this method in general, the method forms the basic concept layer that is to be understood very clearly. The formula is trivial and will follow immediately out of the results of the method.

A big advantage of the systematic method of enumeration of ordered arrangements is its ability to generate the actual arrangements along with the number of arrangements, while the formula would give you only the number of arrangements but not the actual permuted arrangements.

---

Permutation of objects that are not distinct

In this case, we have some of the objects that are alike. Let us consider a $m$ out of $m$ permutation in which $p$ objects are alike. We must form the arrangements that are distinct considering the order of the objects. Otherwise an arrangement will not be a distinct permutation.

Let us assume that the desired number of permutations is $x$. In each of these permutations, there are $p$ objects in various positions of the arrangements. Let us take one of these $x$ arrangements. In this arrangement, if we make these $p$ objects all distinct now, we will have $p\text{!}$ ways to rearrange these now different $p$ objects among the particular positions of the specific arrangement of $x$ chosen.

Thus if we make the $p$ objects distinct, for each of the $x$ arrangements we will have $p\text{!}$ new arrangements and we will reach the $m$ out of $m$ distinct object permutations. This means,

$^{m}P_m=m{!}=x\times{p{!}} \qquad \text{or,  } x=\displaystyle\frac{m{!}}{p{!}}$

Ultimately it is a simple relationship - for $p$ alike objects in $m$ objects, the $m$ out of $m$ permutation is $m{!}$ divided by $p{!}$.

If there are $q$ more alike objects in $m$ in addition to $p$ alike objects, we just need to divide our previous permutation by $q{!}$. Thus, for $p$, $q$ and $r$ alike objects in $m$ objects the number of $m$ out of $m$ permutations is,

$\displaystyle\frac{m\text{!}}{p\text{!}q\text{!}r\text{!}}$

Problem 5:

How many 6 digit numbers can you form from the digits 1, 2, 3, 4, and 5 with 1 repeating in each number twice?

Solution 5:

The desired number would be 6 out of 6 permutations from the digits, 1, 1, 2, 3, 4 and 5. Here 1 is repeated twice. So the desired number of permutations is,

$\displaystyle\frac{6{!}}{2{!}}=\displaystyle\frac{6\times{5}\times{4}\times{3}\times{2}\times{1}}{2\times{1}}=360$

Problem 6:

In how many ways a person can invite his 6 friends by sending invitation cards through 2 of his servants?

Solution 6: This is a different type of problem from permutation. In this case, the person is free to send any of the two servants to each of the six friends. Thus, each friend can receive his card in two possible ways from two servants. As there are six friends, the required number is,

$2\times{2}\times{2}\times{2}\times{2}\times{2}=2^6 = 64$

Combination

Basic concepts

Combination is selection of $r$ objects from a set of $n$ distinct objects. In this case, there is no importance attached to the order of selection. Each unique set of $r$ objects selected form one combination.

As in each such combination the $r$ objects selected can be ordered among themselves in $r{!}$ unique ways, if we order all the combinations in this way we would get the permutation of $r$ out of $n$ distinct objects. Thus, number of combinations multiplied with $r{!}$ gives us number of permutations.

So,

Number of combinations,

$^nC_{r} = \displaystyle\frac{\text{Number of Permutations}}{r{!}} $

$\hspace{9mm}=\displaystyle\frac{n{!}}{r{!}(n-r){!}}$

Problem examples

Problem 1:

In how many ways can you select 3 books out of 5 available books?

Solution 1:

The number of ways 3 books can be selected out of 5 books is,

$^5C_{3}=\displaystyle\frac{5{!}}{3{!}(5-3){!}}=\displaystyle\frac{5{!}}{3{!}2{!}}=10$

Problem 2:

In how many ways 4 members can be selected out of 8 members to form a committee such that 1 member is always selected?

Solution 2:

If 1 member is always selected in the committee then the combination choice problem is changed to selecting $(4 - 1)=3$ members out of $(8 - 1)=7$ members. The required number of ways then,

$^7C_{3}=\displaystyle\frac{7{!}}{3{!}(7-3){!}}=\displaystyle\frac{7{!}}{3{!}4{!}}=35$

Problem 3:

In how many ways 4 members can be selected out of 8 members to form a committee such that 2 members are always excluded?

Solution 3:

If two members are always excluded, the number of members to choose from reduces to $(8 - 2)=6$ and the required number of combinations is,

$^6C_{4} = \displaystyle\frac{6{!}}{4{!}(6-4){!}}=\displaystyle\frac{6{!}}{4{!}2{!}}=15$

---

Problem Exercise:

Recommended time limit: 30 minutes.

Problem 1. How many 5 letter words (may not be meaningful) out of the first eight letters of the English alphabet can be formed with the vowels always included?

1. 1600
2. 900
3. 4800
4. 2400

Problem 2. How many 3 digit even numbers greater than 500 can be formed out of the digits 6, 0, 3, 5 and 4?

1. 9
2. 12
3. 15
4. 18

Problem 3. The sum of all the numbers that can be formed by using all the four digits 1, 2, 3 and 4 is,

1. 65666
2. 66660
3. 66550
4. 56650

Problem 4. How many 3 letter words (may not be meaningful) can be formed with the letters of the word PENUMBRA each with at least one vowel?

1. 388
2. 276
3. 150
4. 212

Problem 5. In how many ways can the letters of the word METRIC be arranged so that the two vowels are never together?

1. 480
2. 960
3. 560
4. 280

Problem 6. How many straight lines can be drawn from 15 non-collinear points?

1. 110
2. 105
3. 115
4. 120

Problem 7. In how many different ways 5 boys and 5 girls can sit in a circular table so that the boys and the girls are alternately placed?

1. 2800
2. 2880
3. 2400
4. 2280

Problem 8. In how many ways a committee of 2 men and 3 women be formed out of a total of 4 men and 4 women?

1. 15
2. 20
3. 16
4. 24

Problem 9. If there are 10 stations on a railway line, the number of different journey tickets to be printed by the railway authorities is,

1. 45
2. 91
3. 90
4. 93

Problem 10.  A team of six is to be formed by taking two from each of three groups of boys of numbering 5, 6 and 7. How many such teams are possible?

1. 3150
2. 3350
3. 3250
4. 4500

The detailed explanatory solutions of these questions are available in,

Permutation and Combination Solution Set 1.

Answers:

1. d: 2400.

2. c: 15.

3. b: 66660.

4. b: 276.

5. a: 480.

6. b: 105

7. b: 2880.

8. d: 24.

9. c: 90.

10. a: 3150.

---

Further reading resources

Tutorial on Permutation and Combination with exercise problems

Solutions to the exercise problems on Permutation and combination

Bank PO level Solution set 2 on Permutation and Combination 2

Bank PO level Question set 2 on Permutation and Combination 2

Bank PO level Solutions 1 on Permutation combination 1

Bank PO level Question set 1 on Permutation combination 1

---