CBSE Class 11 Mathematics Permutations and Combinations Notes Set 01

Important Notes and Formulas

Fundamental Principle of Multiplication

If an event can occur in m different ways following which another event can occur in n different ways following which another event can occur in p different ways, then the total number of ways of simultaneous happening of all these events in a definite order is m × n × p.

Fundamental Principle of Addition

If there are two jobs such that they can be performed independently in m and n ways respectively, then either of the two jobs can be performed in (m + n) ways.

Combinations

Each of the different selections made by taking some or all of a number of distinct objects or items, irrespective of their arrangements or order in which they are placed, is called a combination.

Permutations

Each of the different arrangements which can be made by taking some or all of a number of distinct objects is called a permutation.

Important Results on Permutations and Combinations

1. Let r and n be positive integers such that 1 ≤ r ≤ n. Then, the number of all permutations of n distinct items or objects taken r at a time is
\( {}^{n}P_{r} = {}^{n}C_{r} \times r! \)
Proof: Total ways = n(n − 1)(n − 2) … (n − r + 1)
\( = \frac{n(n-1)(n-2)\ldots(n-r+1)(n-r)!}{(n-r)!} = \frac{n!}{(n-r)!} = {}^{n}P_{r} \)
So, the total number of arrangements (permutations) of n distinct items, taking r at a time, is \( {}^{n}P_{r} \) or P(n, r).

2. The number of all permutations (arrangements) of n distinct objects taken all at a time is n!.

3. The number of ways of selecting r items or objects from a group of n distinct items or objects is \( \frac{n!}{(n-r)!\,r!} = {}^{n}C_{r} \).

Geometric Applications of \( {}^{n}C_{r} \)

(i) Out of n non-concurrent and non-parallel straight lines, the number of points of intersection is \( {}^{n}C_{2} \).
(ii) Out of n points, the number of straight lines (when no three are collinear) is \( {}^{n}C_{2} \).
(iii) If out of n points m are collinear, then the number of straight lines = \( {}^{n}C_{2} - {}^{m}C_{2} + 1 \).
(iv) In a polygon, the total number of diagonals out of n points (no three collinear) = \( {}^{n}C_{2} - n = \frac{n(n-3)}{2} \).
(v) The number of triangles formed from n points (when no three points are collinear) is \( {}^{n}C_{3} \).
(vi) The number of triangles out of n points in which m are collinear is \( {}^{n}C_{3} - {}^{m}C_{3} \).
(vii) The number of parallelograms in two systems of parallel lines (when the 1^st set contains m parallel lines and the 2^nd set contains n parallel lines) is \( {}^{n}C_{2} \times {}^{m}C_{2} \).

Permutations under Certain Conditions

The number of all permutations (arrangements) of n different objects taken r at a time:
(i) when a particular object is always to be included in each arrangement, is \( {}^{n-1}C_{r-1} \times r! \).
(ii) when a particular object is never taken in each arrangement, is \( {}^{n-1}C_{r} \times r! \).

Permutations of Alike Objects

1. The number of mutually distinguishable permutations of n things, taken all at a time, of which p are alike of one kind and q alike of a second kind such that p + q = n, is \( \frac{n!}{p!\,q!} \).

2. The number of permutations of n things, of which p are alike of one kind, q are alike of a second kind and the remaining are all distinct, is \( \frac{n!}{p!\,q!} \). Here p + q ≠ n.

3. The number of permutations of n things, of which \( p_1 \) are alike of one kind, \( p_2 \) are alike of a second kind, \( p_3 \) are alike of a third kind, …, \( p_r \) are alike of the r^th kind such that \( p_1 + p_2 + \ldots + p_r = n \), is \( \frac{n!}{p_1!\,p_2!\,p_3!\ldots p_r!} \).

4. Suppose there are r things to be arranged, allowing repetitions. Let further \( p_1, p_2, \ldots, p_r \) be integers such that the first object occurs exactly \( p_1 \) times, the second occurs exactly \( p_2 \) times, etc. Then the total number of permutations of these r objects under the above condition is \( \frac{(p_1 + p_2 + \ldots + p_r)!}{p_1!\,p_2!\,p_3!\ldots p_r!} \).

Selection of One or More Objects

The number of ways of selecting one or more items from a group of n distinct items is \( 2^n - 1 \).
Proof: Out of n items, 1 item can be selected in \( {}^{n}C_{1} \) ways, 2 items can be selected in \( {}^{n}C_{2} \) ways, 3 items can be selected in \( {}^{n}C_{3} \) ways and so on.
Hence, the required number of ways
\( = {}^{n}C_{1} + {}^{n}C_{2} + {}^{n}C_{3} + \ldots + {}^{n}C_{n} \)
\( = ({}^{n}C_{0} + {}^{n}C_{1} + {}^{n}C_{2} + \ldots + {}^{n}C_{n}) - {}^{n}C_{0} \)
\( = 2^n - 1 \)
(Equivalently, each of the n items can either be selected or left out, giving \( 2^n \) choices, out of which the case of selecting nothing is excluded.)

Solved Examples

Example 1. The flag of a newly formed forum is in the form of three blocks, each to be coloured differently. If there are six different colours on the whole to choose from, how many such designs are possible?
Answer:
Since there are six colours to choose from, the first block can be coloured in 6 ways. After choosing the first block, the second and third can be chosen in 5 and 4 ways respectively.
Hence, by the fundamental principle of multiplication, the number of flag-designs is 6 × 5 × 4 = 120.

Example 2. Find the number of 4 letter words, with or without meaning, which can be formed out of the letters of the word ROSE, when
(i) the repetition of the letters is not allowed.
(ii) the repetition of the letters is allowed.
Answer:
(i) The total number of words is the same as the number of ways of filling 4 vacant places by the 4 letters. The first place can be filled in 4 different ways by any one of the 4 letters R, O, S, E. Since the repetition of letters is not allowed, the second, third and fourth places can be filled by any one of the remaining 3, 2, 1 letters respectively.
Thus, by the fundamental principle of counting, the required number of ways is 4 × 3 × 2 × 1 = 24.
Hence, required number of words = 24.
(ii) If the repetition of the letters is allowed, then each of the 4 vacant places can be filled in succession in 4 different ways.
Hence, required number of words = 4 × 4 × 4 × 4 = 256.

Example 3. Find the number of different signals that can be generated by arranging at least 2 flags in order (one below the other) on a vertical staff, if five different flags are available.
Answer:
A signal may consist of either 2 flags, 3 flags, 4 flags or 5 flags. Therefore,
Total number of signals = Number of 2-flag signals + Number of 3-flag signals + Number of 4-flag signals + Number of 5-flag signals
= 5 × 4 + 5 × 4 × 3 + 5 × 4 × 3 × 2 + 5 × 4 × 3 × 2 × 1
= 20 + 60 + 120 + 120 = 320

Example 4. Find the total number of ways of answering 5 objective type questions, each question having 4 choices.
Answer:
Since each question can be answered in 4 ways, the total number of ways of answering 5 questions is 4 × 4 × 4 × 4 × 4 = 4⁵ = 1024.

Example 5. How many numbers are there between 100 and 1000 such that at least one of their digits is 7?
Answer:
Clearly, a number between 100 and 1000 has 3 digits.
∴ Total number of 3-digit numbers having at least one of their digits as 7 = (3-digit numbers) − (3-digit numbers in which 7 does not appear)
Total number of 3-digit numbers = 9 × 10 × 10 = 900
Total number of 3-digit numbers in which 7 does not appear at all: we have to form 3-digit numbers by using the digits 0 to 9 except 7. So, the hundred's place can be filled in 8 ways and each of the ten's and one's places can be filled in 9 ways.
So, required ways = 8 × 9 × 9 = 648
Hence, the total number of 3-digit numbers having at least one of their digits as 7 is 900 − 648 = 252.

Example 6. How many three-digit numbers more than 600 can be formed by using the digits 2, 3, 4, 6, 7?
Answer:
Clearly, repetition of digits is allowed. Since a three-digit number greater than 600 will have 6 or 7 at the hundred's place, the hundred's place can be filled in 2 ways. Each of the ten's and one's places can be filled in 5 ways.
Hence, total number of required numbers = 2 × 5 × 5 = 50.

Example 7. How many numbers divisible by 5 and lying between 4000 and 5000 can be formed from the digits 4, 5, 6, 7 and 8?
Answer:
Clearly, a number between 4000 and 5000 must have 4 at the thousand's place. Since the number is divisible by 5, it must have 5 at the unit's place. Now, each of the remaining places (viz. hundred's and ten's) can be filled in 5 ways.
Hence, total number of required numbers = 1 × 5 × 5 × 1 = 25.

Example 8. Find the number of ways of selecting 9 balls from 6 red balls, 5 white balls and 7 blue balls if each selection consists of 3 balls of each colour.
Answer:
The number of ways of selecting 9 balls from 6 red balls, 5 white balls and 7 blue balls containing 3 balls of each colour = \( {}^{6}C_{3} \times {}^{5}C_{3} \times {}^{7}C_{3} \)
\( = \frac{6!}{3!\,(6-3)!} \times \frac{5!}{3!\,(5-3)!} \times \frac{7!}{3!\,(7-3)!} = 20 \times 10 \times 35 = 7000 \)

Example 9. In how many ways can a team of 3 boys and 2 girls be selected from 6 boys and 5 girls?
Answer:
Required number of ways = \( {}^{6}C_{3} \times {}^{5}C_{2} \)
\( = \frac{6!}{3!\,(6-3)!} \times \frac{5!}{2!\,(5-2)!} = 20 \times 10 = 200 \)

Example 10. Find the number of triangles obtained by joining 10 points on a plane if
(i) no three of them are collinear
(ii) four points are collinear
Answer:
(i) Since no three points are collinear, any three non-collinear points can be selected to form a triangle.
Number of triangles required = \( {}^{10}C_{3} = 120 \)
(ii) If four points are collinear,
Required number of triangles = \( {}^{10}C_{3} - {}^{4}C_{3} = 120 - 4 = 116 \)
(because a selection of 3 collinear points does not make a triangle.)

Example 11. Among 22 cricket players, there are 3 wicketkeepers and 6 bowlers. In how many ways can a team of 11 players be chosen so as to include exactly one wicketkeeper and at least 4 bowlers?
Answer:
We have to choose 11 players which include exactly 1 wicketkeeper and at least 4 bowlers. The other 13 players are neither wicketkeepers nor bowlers.
Possible combinations: 1 wicketkeeper – 4 bowlers, 1 wicketkeeper – 5 bowlers and 1 wicketkeeper – 6 bowlers.
Total number of combinations
\( = {}^{3}C_{1} \times {}^{6}C_{4} \times {}^{13}C_{6} + {}^{3}C_{1} \times {}^{6}C_{5} \times {}^{13}C_{5} + {}^{3}C_{1} \times {}^{6}C_{6} \times {}^{13}C_{4} \)
= 77220 + 23166 + 2145 = 102531

Example 12. In how many ways can 5 students be selected out of 11 students if
(i) 2 particular students are included?
(ii) 2 particular students are not included?
Answer:
There are 11 students and we have to select 5 students.
(i) If 2 particular students are included, we select the remaining 3 from the other 9 students. Required number of ways
\( = {}^{11-2}C_{5-2} = {}^{9}C_{3} = \frac{9!}{3!\,6!} = \frac{9 \times 8 \times 7}{3 \times 2} = 84 \)
(ii) If 2 particular students are not included, we select all 5 from the other 9 students. Required number of ways
\( = {}^{9}C_{5} = \frac{9!}{5!\,4!} = \frac{9 \times 8 \times 7 \times 6}{4 \times 3 \times 2} = 126 \)

Example 13. How many different signals can be made by 5 flags from 8 flags of different colours?
Answer:
The total number of signals is the number of arrangements of 8 flags taking 5 flags at a time.
Hence, required number of signals = \( {}^{8}C_{5} \times 5! = 56 \times 120 = 6720 \)

Example 14. How many different signals can be given using any number of flags from 5 flags of different colours?
Answer:
The signals can be made by using at a time one or two or three or four or five flags.
Hence, by the fundamental principle of addition,
Total number of signals = \( {}^{5}P_{1} + {}^{5}P_{2} + {}^{5}P_{3} + {}^{5}P_{4} + {}^{5}P_{5} \)
= 5 + 20 + 60 + 120 + 120 = 325

Example 15. How many 4-letter words, with or without meaning, can be formed out of the letters of the word 'LOGARITHMS', if repetition of letters is not allowed?
Answer:
There are 10 different letters in the word 'LOGARITHMS'.
So, the number of 4-letter words = \( {}^{10}C_{4} \times 4! = {}^{10}P_{4} = 5040 \)

Example 16. How many different words can be formed with the letters of the word EQUATION so that
(i) the words begin with E?
(ii) the words begin with E and end with N?
Answer:
Clearly, the given word contains 8 letters, out of which 5 are vowels and 3 are consonants.
(i) Since all words must begin with E, we fix E at the first place. So, total number of words = \( {}^{7}P_{7} = 7! = 5040 \)
(ii) Since all words must begin with E and end with N, we fix E at the first place and N at the last place.
Hence, the required number of words = \( {}^{6}P_{6} = 6! = 720 \)

Example 17. In how many ways can 5 boys and 3 girls be seated in a row so that no two girls are together?
Answer:
The 5 boys can be seated in a row in \( {}^{5}P_{5} = 5! \) ways. In each of these arrangements 6 places are created, shown by the cross-marks, as given below:
× B × B × B × B × B ×
Since no two girls are to sit together, we may arrange the 3 girls in the 6 places. This can be done in \( {}^{6}P_{3} \) ways.
Hence, the total number of seating arrangements = \( {}^{5}P_{5} \times {}^{6}P_{3} \) = 5! × 6 × 5 × 4 = 14400.

Example 18. Find the number of ways in which 5 boys and 5 girls can be seated in a row so that
(i) no two girls may sit together.
(ii) all the girls sit together and all the boys sit together.
(iii) all the girls are never together.
Answer:
(i) 5 boys can be seated in a row in \( {}^{5}P_{5} = 5! \) ways. Now, in the 6 gaps between and around them, the 5 girls can be arranged in \( {}^{6}P_{5} \) ways.
Hence, the number of ways in which no two girls sit together = \( 5! \times {}^{6}P_{5} = 5! \times 6! \) = 86400.
(ii) The two groups of girls and boys can be arranged in 2! ways. The 5 girls can be arranged among themselves in 5! ways. Similarly, the 5 boys can be arranged among themselves in 5! ways. Hence, by the fundamental principle of counting, the total number of requisite seating arrangements = 2!(5! × 5!) = 2(5!)² = 28800.
(iii) The total number of ways in which all the girls are never together = Total number of arrangements − Total number of arrangements in which all the girls are always together
= 10! − 5! × 6! = 3628800 − 86400 = 3542400

Example 19. Five boys and five girls form a line with the boys and girls alternating. Find the number of ways of making the line.
Answer:
5 boys can be arranged in a line in \( {}^{5}P_{5} = 5! \) ways. Since the boys and girls are alternating, corresponding to each of the 5! ways of arrangement of the 5 boys we obtain 5 places marked by crosses as shown below:
(i) \( B_1 \times B_2 \times B_3 \times B_4 \times B_5 \times \)    (ii) \( \times B_1 \times B_2 \times B_3 \times B_4 \times B_5 \)
Clearly, the 5 girls can be arranged in the 5 places marked by crosses in (5! + 5!) ways.
Hence, the total number of ways of making the line = 5! × (5! + 5!) = 2(5!)² = 28800.

Example 20. How many five-letter words containing 3 vowels and 2 consonants can be formed using the letters of the word 'EQUATION' so that the two consonants occur together?
Answer:
There are 5 vowels and 3 consonants in the word 'EQUATION'. 3 vowels out of 5 and 2 consonants out of 3 can be chosen in \( {}^{5}C_{3} \times {}^{3}C_{2} \) ways. As the consonants occur together, considering the 2 consonants as one letter, we have 4 letters which can be arranged in 4! ways. But the two consonants can be put together in 2! ways. Therefore, the 5 letters in each group can be arranged in 4! × 2! ways.
The required number of words = \( ({}^{5}C_{3} \times {}^{3}C_{2}) \times 4! \times 2! \) = 30 × 48 = 1440.

Example 21. How many words, with or without meaning, each of 2 vowels and 3 consonants can be formed from the letters of the word DAUGHTER?
Answer:
There are 3 vowels and 5 consonants in the word DAUGHTER, out of which 2 vowels and 3 consonants can be chosen in \( {}^{3}C_{2} \times {}^{5}C_{3} \) ways. These selected five letters can now be arranged in 5! ways.
Hence, required number of words = \( {}^{3}C_{2} \times {}^{5}C_{3} \times 5! \)
= 3 × 10 × 120 = 3600

Example 22. (i) How many different words can be formed with the letters of the word HARYANA?
(ii) How many of these begin with H and end with N?
(iii) In how many of these are H and N together?
Answer:
(i) There are 7 letters, of which 3 are alike (A, A, A).
So, total number of words = \( \frac{7!}{3!\,1!\,1!\,1!\,1!} = \frac{7!}{3!} = 840 \)
(ii) After fixing H at the first place and N at the last place, we have 5 letters out of which three are alike.
So, total number of words = \( \frac{5!}{3!} = 20 \)
(iii) If H and N are together, treating them as one letter we have 6 letters out of which 3 are alike. These 6 letters can be arranged in \( \frac{6!}{3!} \) ways. But H and N can be arranged amongst themselves in 2! ways.
Hence, the requisite number of words = \( \frac{6!}{3!} \times 2! = 120 \times 2 = 240 \)

Example 23. How many different words can be formed by using all the letters of the word 'ALLAHABAD'?
(i) In how many of them do the vowels occupy the even positions?
(ii) In how many of them do both L's not come together?
Answer:
There are 9 letters in the word 'ALLAHABAD', out of which 4 are A's, 2 are L's and the rest are all distinct.
So, the requisite number of words = \( \frac{9!}{4!\,2!} = 7560 \)
(i) The four A's (the only vowels) will occupy the four even places in 1 way. Now, we are left with 5 places and 5 letters, of which two are alike (2 L's) and the others are distinct; these can be arranged in \( \frac{5!}{2!} \) ways.
Total number of required words = \( \frac{4!}{4!} \times \frac{5!}{2!} = 60 \)
(ii) Treating both L's as one letter, the number of words in which both L's come together = \( \frac{8!}{4!} = 1680 \)
Hence, the number of words in which both L's do not come together = Total number of words − Number of words in which both L's come together = 7560 − 1680 = 5880.

Example 24. How many four-letter words can be formed using the letters of the word INEFFECTIVE?
Answer:
INEFFECTIVE contains 11 letters: EEE, FF, II, C, T, N, V.
As all the letters are not different, we cannot use \( {}^{n}P_{r} \). The four-letter words will be among any one of the following categories:
1. 3 alike letters, 1 different letter; 2. 2 alike letters, 2 alike letters; 3. 2 alike letters, 2 different letters; 4. all different letters.
1. 3 alike, 1 different: 3 alike can be selected in one way, i.e. EEE. The different letter can be selected from F, I, T, N, V, C in \( {}^{6}C_{1} \) ways.
⇒ Number of groups = \( 1 \times {}^{6}C_{1} = 6 \); ⇒ Number of words = \( 6 \times \frac{4!}{3!\,1!} = 24 \)
2. 2 alike, 2 alike: Two sets of 2 alike letters can be selected from 3 sets (EE, II, FF) in \( {}^{3}C_{2} \) ways.
⇒ Number of words = \( {}^{3}C_{2} \times \frac{4!}{2!\,2!} = 18 \)
3. 2 alike, 2 different: ⇒ Number of groups = \( ({}^{3}C_{1}) \times ({}^{6}C_{2}) = 45 \)
⇒ Number of words = \( 45 \times \frac{4!}{2!} = 540 \)
4. All different: ⇒ Number of groups = \( {}^{7}C_{4} \) (out of E, F, I, T, N, V, C)
⇒ Number of words = \( {}^{7}C_{4} \times 4! = 840 \)
Hence, total number of four-letter words = 24 + 18 + 540 + 840 = 1422.

Example 25. In how many ways can 4 letters be selected from the letters of the word INEFFECTIVE?
Answer:
INEFFECTIVE contains 11 letters: EEE, FF, II, C, T, N, V. We make the following cases to select 4 letters.
Case 1: 3 alike and 1 different – 3 alike letters can be selected from the only set of 3 alike letters (EEE) in 1 way, and the different letter from the remaining 6 letters (F, I, C, T, N, V) in \( {}^{6}C_{1} \) ways.
⇒ The number of ways to select 3 alike letters and 1 different letter = \( 1 \times {}^{6}C_{1} = 6 \) …(i)
Case 2: 2 alike and 2 alike – we have to select 2 groups of 2 alike letters from (EE, FF, II) in \( {}^{3}C_{2} \) ways.
⇒ The number of ways to select '2 alike and 2 alike' letters = \( {}^{3}C_{2} = 3 \) …(ii)
Case 3: 2 alike and 2 different – 1 group of 2 alike letters can be selected from 3 sets of 2 alike letters (EE, FF, II) in \( {}^{3}C_{1} \) ways, and 2 different letters can be selected from the 6 remaining different letters (C, T, N, V and the remaining 2 letters of the sets of alike letters) in \( {}^{6}C_{2} \) ways.
⇒ The number of ways to select '2 alike and 2 different' letters = \( {}^{3}C_{1} \times {}^{6}C_{2} = 3 \times 15 = 45 \) …(iii)
Case 4: All different letters – these can be selected from the 7 different letters (I, E, F, N, C, T, V) in \( {}^{7}C_{4} \) ways.
⇒ The number of ways to select all different letters = \( {}^{7}C_{4} = 35 \) …(iv)
Combining (i), (ii), (iii) and (iv), the total number of ways to select 4 letters from the letters of the word 'INEFFECTIVE' = 6 + 3 + 45 + 35 = 89.

Example 26. In how many ways can a cricket team be selected from a group of 25 players containing 10 batsmen, 8 bowlers, 5 all-rounders and 2 wicketkeepers? Assume that the team of 11 players requires 5 batsmen, 3 all-rounders, 2 bowlers and 1 wicketkeeper.
Answer:
Divide the selection of the team into four operations.
I: Selection of batsmen can be done (5 from 10) in \( {}^{10}C_{5} \) ways.
II: Selection of bowlers can be done (2 from 8) in \( {}^{8}C_{2} \) ways.
III: Selection of all-rounders can be done (3 from 5) in \( {}^{5}C_{3} \) ways.
IV: Selection of the wicketkeeper can be done (1 from 2) in \( {}^{2}C_{1} \) ways.
⇒ The team can be selected in \( {}^{10}C_{5} \times {}^{8}C_{2} \times {}^{5}C_{3} \times {}^{2}C_{1} \) ways
\( = \frac{10! \times 8 \times 7 \times 10 \times 2}{5!\,5!\,2!} = 252 \times 28 \times 10 \times 2 = 141120 \)

Example 27. A mixed doubles tennis game is to be arranged from 5 married couples. In how many ways can the game be arranged if no husband and wife pair is included in the same game?
Answer:
To arrange the game we have to do the following operations.
(i) Select two men from 5 men in \( {}^{5}C_{2} \) ways.
(ii) Select two women from the 3 women excluding the wives of the men already selected. This can be done in \( {}^{3}C_{2} \) ways.
(iii) Arrange the 4 selected persons in two teams. If the selected men are \( M_1 \) and \( M_2 \) and the selected women are \( W_1 \) and \( W_2 \), this can be done in 2 ways:
\( M_1W_1 \) play against \( M_2W_2 \); \( M_2W_1 \) play against \( M_1W_2 \)
Hence, the number of ways to arrange the game = \( {}^{5}C_{2} \times {}^{3}C_{2} \times 2 \) = 10 × 3 × 2 = 60

Example 28. Find the sum of all five-digit numbers that can be formed using the digits 1, 2, 3, 4, 5 if repetition is not allowed.
Answer:
There are 5! = 120 five-digit numbers and there are 5 digits. Hence, by symmetry, each digit will appear in any place (unit's or ten's or …) \( \frac{5!}{5} = 24 \) times.
⇒ X = sum of the digits in any one place = \( \frac{5!}{5} \times (5 + 4 + 3 + 2 + 1) = \frac{5!}{5}(15) \)
⇒ The sum of all the numbers = X + 10X + 100X + 1000X + 10000X = X(1 + 10 + 100 + 1000 + 10000)
\( = \frac{5!}{5}(15)(11111) \) = 24 × 15 × 11111 = 3999960