Permutations and Combinations
Quantitative Aptitude & Business Statistics
The Fundamental Principle of Multiplication If there are n1 ways of doing one operation, n2 ways of doing a second operation, n3 ways of doing a third operation , and so forth,
Quantitative Aptitude & Business Statistics:Permutations and Combinations
then the sequence of k operations can be performed in n1 n2 n3.. nk ways. N= n1 n2 n3.. nk
Quantitative Aptitude & Business Statistics:Permutations and Combinations
A used car wholesaler has agents who classify cars by size (full, medium, and compact) and age (0 - 2 years, 2- 4 years, 4 - 6 years, and over 6 years). Determine the number of possible automobile classifications.
Example 1
Quantitative Aptitude & Business Statistics:Permutations and Combinations
Solution 0-2
Full(F)
2-4 4-6 >6 0-2 2-4 4-6 >6 0-2 2-4 4-6 >6
Medium (M) Compact
(C) The tree diagram enumerates all possible classifications, the total number of which is 3x4= 12. Quantitative Aptitude & Business 5
Statistics:Permutations and Combinations
Example 2
Mr. X has 2 pairs of trousers, 3 shirts and 2 ties. He chooses a pair of trousers, a shirt and a tie to wear everyday. Find the maximum number of days he does not need to repeat his clothing.
Quantitative Aptitude & Business Statistics:Permutations and Combinations
Solution
The maximum number of days he does not need to repeat his clothing is 232 = 12
Quantitative Aptitude & Business Statistics:Permutations and Combinations 7
1.2 Factorials
The product of the first n consecutive integers is denoted by n! and is read as factorial n. That is n! = 1234. (n-1) n For example, 4!=1x2x3x4=24, 7!=1234567=5040. Note 0! defined to be 1.
Quantitative Aptitude & Business Statistics:Permutations and Combinations 8
The product of any number of consecutive integers can be expressed as a quotient of two factorials, for example, 6789 = 9!/5! = 9! / (9 4)! 1112131415= 15! / 10!
=15! / (15 5)! In particular, n(n 1)(n 2)...(n r + 1)
Quantitative Aptitude & Business Statistics:Permutations and Combinations 9
1.3 Permutations
(A)
Permutations
A permutation is an arrangement of objects. abc and bca are two different permutations.
Quantitative Aptitude & Business Statistics:Permutations and Combinations
10
1. Permutations with repetition
The number of permutations of r objects, taken from n unlike objects, can be found by considering the number of ways of filling r blank spaces in order with the n given objects. If repetition is allowed, each blank space can be filled by the objects in n different ways.
Quantitative Aptitude & Business Statistics:Permutations and Combinations 11
1 n
2 n
3 n
4 n
r n
Therefore, the number of permutations of r objects, taken from n unlike objects, each of which may be repeated any number of times
= n n n .... n(r factors) = nr
Quantitative Aptitude & Business Statistics:Permutations and Combinations 12
2. Permutations without repetition
If repetition is not allowed, the number of ways of filling each blank space is one less than the preceding one.
1 n 2 n-1 3 n-2 4 n-3 r n-r+1
13
Quantitative Aptitude & Business Statistics:Permutations and Combinations
Therefore, the number of permutations of r objects, taken from n unlike objects, each of which can only be used once in each permutation
=n(n 1)(n2) .... (nr + 1)
Various notations are used to represent the number of permutations of a set of n elements taken r at a time;
Quantitative Aptitude & Business Statistics:Permutations and Combinations
14
some of them are
P , Pr , P (n, r )
n r n
Since
n! ( n r )! n( n 1)(n 2)....(n r + 1)(n r )...3 2 1 = ( n r )...3 2 1 = n( n 1)(n 2)....(n r + 1)
Prn , n Pr , P (n, r )
=P
We have
n r
n! P = (n r )!
n r
Quantitative Aptitude & Business Statistics:Permutations and Combinations 15
Example 3
How many 4-digit numbers can be made from the figures 1, 2, 3, 4, 5, 6, 7 when (a) repetitions are allowed; (b) repetition is not allowed?
Quantitative Aptitude & Business Statistics:Permutations and Combinations
16
Solution (a) Number of 4-digit numbers = 74 = 2401. (b) Number of 4 digit numbers =7 6 5 4 = 840.
Quantitative Aptitude & Business Statistics:Permutations and Combinations
17
Example 4 In how many ways can 10 men be arranged (a) in a row, (b) in a circle?
Solution
(a)
Number of ways is = 3628800
10 10
Quantitative Aptitude & Business Statistics:Permutations and Combinations
18
Suppose we arrange the 4 letters A, B, C and D in a circular arrangement as shown. D Note that the arrangements ABCD, BCDA, CDAB and DABC are not distinguishable.
Quantitative Aptitude & Business Statistics:Permutations and Combinations
19
For each circular arrangement there are 4 distinguishable arrangements on a line. If there are P circular arrangements, these yield 4P arrangements on a line, which we know is 4!.
Hence
4! P = = (4 1)!= 3! 4
Quantitative Aptitude & Business Statistics:Permutations and Combinations 20
Solution (b)
The number of distinct circular arrangements of n objects is (n 1)! Hence 10 men can be arranged in a circle in 9! = 362 880 ways.
Quantitative Aptitude & Business Statistics:Permutations and Combinations
21
When arranging elements in order , certain restrictions may apply. In such cases the restriction should be dealt with first..
(B) Conditional Permutations
Quantitative Aptitude & Business Statistics:Permutations and Combinations
22
Example 5 How many even numerals between 200 and 400 can be formed by using 1, 2, 3, 4, 5 as digits (a) if any digit may be repeated; (b) if no digit may be repeated?
Quantitative Aptitude & Business Statistics:Permutations and Combinations
23
Solution (a) Number of ways of choosing the hundreds digit = 2. Number of ways of choosing the tens digit = 5. Number of ways of choosing the unit digit = 2. Number of even numerals between 200 and 400 is 2 5 2 = 20.
Quantitative Aptitude & Business Statistics:Permutations and Combinations 24
Solution (b)
If the hundreds digit is 2, then the number of ways of choosing an even unit digit = 1, and the number of ways of choosing a tens digit = 3.
the number of numerals formed 113 = 3.
Quantitative Aptitude & Business Statistics:Permutations and Combinations
25
If the hundreds digit is 3, then the number of ways of choosing an even. unit digit = 2, and the number of ways of choosing a tens digit = 3.
number of numerals formed = 123 = 6. the number of even numerals between 200 and 400 = 3 + 6 = 9
Quantitative Aptitude & Business Statistics:Permutations and Combinations 26
Example 6 In how many ways can 7 different books be arranged on a shelf (a) if two particular books are together;
Quantitative Aptitude & Business Statistics:Permutations and Combinations
27
Solution (a)
If two particular books are together, they can be considered as one book for arranging. The number of arrangement of 6 books = 6! = 720. The two particular books can be arranged in 2 ways among themselves. The number of arrangement of 7 books with two particular books
Quantitative Aptitude & Business Statistics:Permutations and Combinations 28
(b) if two particular books are separated?
Solution (b)
Total number of arrangement of 7 books = 7! = 5040. the number of arrangement of 7 books with 2 particular books separated = 5040 1440 = 3600.
Quantitative Aptitude & Business Statistics:Permutations and Combinations
29
(C) Permutation with Indistinguishable Elements
In some sets of elements there may be certain members that are indistinguishable from each other. The example below illustrates how to find the number of permutations in this kind of situation.
Quantitative Aptitude & Business Statistics:Permutations and Combinations 30
Example 7 In how many ways can the letters of the word ISOS CELES be arranged to form a new word ?
Solution If each of the 9 letters of ISOSCELES were different, there would be P= 9! different possible words.
Quantitative Aptitude & Business Statistics:Permutations and Combinations 31
However, the 3 Ss are indistinguishable from each other and can be permuted in 3! different ways. As a result, each of the 9! arrangements of the letters of ISOSCELES that would otherwise spell a new word will be repeated 3! times.
Quantitative Aptitude & Business Statistics:Permutations and Combinations
32
To avoid counting repetitions resulting from the 3 Ss, we must divide 9! by 3!. Similarly, we must divide by 2! to avoid counting repetitions resulting from the 2 indistinguishable Es. Hence the total number of words that can be formed is
9! 3! 2! = 30240
Quantitative Aptitude & Business Statistics:Permutations and Combinations 33
If a set of n elements has k1 indistinguishable elements of one kind, k2 of another kind, and so on for r kinds of elements, then the number of permutations of the set of n elements is
Quantitative Aptitude & Business Statistics:Permutations and Combinations
n! k1!k 2 ! k r !
34
1.4 Combinations
When a selection of objects is made with no regard being paid to order, it is referred to as a combination. Thus, ABC, ACB, BAG, BCA, CAB, CBA are different permutation, but they are the same combination of letters.
Quantitative Aptitude & Business Statistics:Permutations and Combinations
35
Suppose we wish to appoint a committee of 3 from a class of 30 students. We know that P330 is the number of different ordered sets of 3 students each that may be selected from among 30 students. However, the ordering of the students on the committee has no significance,
Quantitative Aptitude & Business Statistics:Permutations and Combinations 36
so our problem is to determine the number of three-element unordered subsets that can be constructed from a set of 30 elements. Any three-element set may be ordered in 3! different ways, so P330 is 3! times too large. Hence, if we divide P330 by 3!,the result will be the number of unordered subsets of 30 elements taken 3 at a time.
Quantitative Aptitude & Business Statistics:Permutations and Combinations
37
This number of unordered subsets is also called the number of combinations of 30 elements taken 3 at a time, denoted by C330 and
1 30 C = P3 3! 30! = = 4060 27!3!
30 3
Quantitative Aptitude & Business Statistics:Permutations and Combinations
38
In general, each unordered relement subset of a given nelement set (r n) is called a combination. The number of combinations of n elements taken r at a time is denoted by Cnr or nCr or C(n, r) .
Quantitative Aptitude & Business Statistics:Permutations and Combinations
39
A general equation relating combinations to permutations is 1 n n! n C r = Pr = r! (n r )!r!
Quantitative Aptitude & Business Statistics:Permutations and Combinations
40
Note: (1) Cnn = Cn0 = 1 (2) Cn1 = n (3) Cnn = Cnn-r
Quantitative Aptitude & Business Statistics:Permutations and Combinations
41
Example8
If 167 C 90+167 C x =168 C x then x is Solution: nCr-1+nCr=n+1 Cr Given 167 C90+167c x =168C x We may write 167C91-1 + 167 C91=167+1 C61 =168 C91 X=91
Quantitative Aptitude & Business Statistics:Permutations and Combinations 42
Example9
If 20 C 3r= 20C 2r+5 ,find r Using nCr=nC n-r in the right side of the given equation ,we find , 20 C 3r =20 C 20-(2r+5) 3r=15-2r r=3
Quantitative Aptitude & Business Statistics:Permutations and Combinations
43
Example 10
If 100 C 98 =999 C 97 +x C 901 find x. Solution 100C 98 =999C 98 +999C97 = 999C901+999C97 X=999
Quantitative Aptitude & Business Statistics:Permutations and Combinations
44
Example11
If 13 C 6 + 2 13 C5 +13 C 4 =15 C x ,the value of x is Solution : 15C x= 13C 6 + 13 C 5 + 13 C 4 = =(13c 6+13 C 5 ) + (13 C 5 + 13 C 4) = 14 C 6 +14 C 5 =15C6 X=6 or x+6 =15 X=6 or 8
Quantitative Aptitude & Business Statistics:Permutations and Combinations
45
Example12
If n C r-1=36 ,n Cr =84 and n C find r Solution
r+1
=126 then
n-r+1 =7/3 * r nCr +1
nCr 84 7 = = nCr 1 36 3
3/2 (r+1)+1 =7/3 * r r=3
nCr
126 3 = = 84 2
Quantitative Aptitude & Business Statistics:Permutations and Combinations
46
Example 13
How many different 5-card
hands can be dealt from a deck of 52 playing cards?
Quantitative Aptitude & Business Statistics:Permutations and Combinations
47
Solution
Since we are not concerned with the order in which each card is dealt, our problem concerns the number of combinations of 52 elements taken 5 at a time. The number of different hands is C525 2118760.
Quantitative Aptitude & Business Statistics:Permutations and Combinations
48
Example 14
6 points are given and no three of them are collinear.
(a) How many triangles can be formed by using 3 of the given points as vertices?
Quantitative Aptitude & Business Statistics:Permutations and Combinations
49
Solution: Solution (a) Number of triangles = number of ways of selecting 3 points out of 6 = C63 = 20.
Quantitative Aptitude & Business Statistics:Permutations and Combinations
50
b) How many pairs of triangles can be formed by using the 6 points as vertices ?
Quantitative Aptitude & Business Statistics:Permutations and Combinations
51
Let the points be A, B, C, D, E, F. If A, B, C are selected to form a triangles, then D, E, F must form the other triangle. Similarly, if D, E, F are selected to form a triangle, then A, B, C must form the other triangle.
Quantitative Aptitude & Business Statistics:Permutations and Combinations
52
Therefore, the selections A, B, C and D, E, F give the same pair of triangles and the same applies to the other selections. Thus the number of ways of forming a pair of triangles = C63 2 = 10
Quantitative Aptitude & Business Statistics:Permutations and Combinations
53
Example 15
From among 25 boys who play basketball, in how many different ways can a team of 5 players be selected if one of the players is to be designated as captain?
Quantitative Aptitude & Business Statistics:Permutations and Combinations
54
Solution
A captain may be chosen from any of the 25 players. The remaining 4 players can be chosen in C254 different ways. By the fundamental counting principle, the total number of different teams that can be formed is 25 C244265650.
Quantitative Aptitude & Business Statistics:Permutations and Combinations
55
(B) Conditional Combinations
If a selection is to be restricted in some way, this restriction must be dealt with first. The following examples illustrate such conditional combination problems.
Quantitative Aptitude & Business Statistics:Permutations and Combinations 56
A committee of 3 men and 4 women is to be selected from 6 men and 9 women. If there is a married couple among the 15 persons, in how many ways can the committee be selected so that it contains the married
Quantitative Aptitude & Business Statistics:Permutations and Combinations
57
Solution If the committee contains the married couple, then only 2 men and 3 women are to be selected from the remaining 5 men and 8 women. The number of ways of selecting 2 men out of 5 = C52 = 10.
Quantitative Aptitude & Business Statistics:Permutations and Combinations
58
The number of ways of selecting 3 women out of 8 =C83 = 56. the number of ways of selecting the committee = lO 56 = 560.
Quantitative Aptitude & Business Statistics:Permutations and Combinations
59
Example 17
Find the number of ways a team
of 4 can be chosen from 15 boys and 10 girls if (a) it must contain 2 boys and 2 girls,
Quantitative Aptitude & Business Statistics:Permutations and Combinations
60
Solution (a) Boys can be chosen in C152 = 105 ways Girls can be chosen in C102 = 45 ways. Total number of ways is 105 45 = 4725.
Quantitative Aptitude & Business Statistics:Permutations and Combinations
61
(b)
it must contain at least 1 boy and 1 girl.
Solution : If the team must contain at least 1 boy and 1 girl it can be formed in the following ways: (I) 1 boy and 3 girls, with C151 C103 = 1800 ways, (ii) 2 boys and 2 girls, with 4725 ways, (iii) 3 boys and 1 girl, with C153 C101 = 4550 ways. the total number of teams is
Quantitative Aptitude & Business Statistics:Permutations and Combinations 62
Example 18
Mr. .X has 12 friends and
wishes to invite 6 of them to a party. Find the number of ways he may do this if (a) there is no restriction on choice,
Quantitative Aptitude & Business Statistics:Permutations and Combinations 63
Solution (a) An unrestricted choice of 6 out of 12 gives C126 924.
Quantitative Aptitude & Business Statistics:Permutations and Combinations
64
(b)
two of the friends is a couple and will not attend separately,
Quantitative Aptitude & Business Statistics:Permutations and Combinations
65
B Solution If the couple attend, the remaining 4 may then be chosen from the other 10 in C104 ways. If the couple does not attend, then He simply chooses 6 from the other 10 in C106 ways. total number of ways is C104 + C106 = 420.
Quantitative Aptitude & Business Statistics:Permutations and Combinations 66
Find the number of ways in which 30 students can be divided into three groups, each of 10 students, if the order of the groups and the arrangement of the students in a group are immaterial.
Example 19
Quantitative Aptitude & Business Statistics:Permutations and Combinations
67
Let the groups be denoted by A, B and C. Since the arrangement of the students in a group is immaterial, group A can be selected from the 30 students in C3010 ways .
Solution
Quantitative Aptitude & Business Statistics:Permutations and Combinations
68
Group B can be selected from the remaining 20 students in C2010 ways. There is only 1 way of forming group C from the remaining 10 students.
Quantitative Aptitude & Business Statistics:Permutations and Combinations
69
Since the order of the groups is immaterial, we have to divide the product C3010 C2010 C1010 by 3!, hence the total number of ways of forming the three groups is
1 30 20 10 C3 C10 C10 3!
Quantitative Aptitude & Business Statistics:Permutations and Combinations 70
Example20
If n Pr = 604800 10 C r =120 ,find the value of r We Know that nC r .r P r = nPr . We will use this equality to find r 10Pr =10Cr .r| r |=604800/120=5040=7 | r=7
Quantitative Aptitude & Business Statistics:Permutations and Combinations 71
Example 21
Find the value of n and r n Pr = n P r+1 and n C r = n C r-1 Solution : Given n Pr = n P r+1 n r=1 (i) n C r = n C r-1 n-r = r-1 (ii) Solving i and ii r=2 and n=3
Quantitative Aptitude & Business Statistics:Permutations and Combinations
72
Multiple choice Questions
Quantitative Aptitude & Business Statistics:Permutations and Combinations
73
1. Eleven students are participating in a race. In how many ways the first 5 prizes can be won? A) 44550 B) 55440 C) 120 D) 90
Quantitative Aptitude & Business Statistics:Permutations and Combinations 74
1. Eleven students are participating in a race. In how many ways the first 5 prizes can be won? A) 44550 B) 55440 C) 120 D) 90
Quantitative Aptitude & Business Statistics:Permutations and Combinations 75
2. There are 10 trains plying between Calcutta and Delhi. The number of ways in which a person can go from Calcutta to Delhi and return A) 99. B) 90 C) 80 D) None of these
Quantitative Aptitude & Business Statistics:Permutations and Combinations
76
2. There are 10 trains plying between Calcutta and Delhi. The number of ways in which a person can go from Calcutta to Delhi and return A) 99. B) 90 C) 80 D) None of these
Quantitative Aptitude & Business Statistics:Permutations and Combinations
77
3. 4P4 is equal to A) 1 B) 24 C) 0 D) None of these
Quantitative Aptitude & Business Statistics:Permutations and Combinations
78
3. 4P4 is equal to A) 1 B) 24 C) 0 D) None of these
Quantitative Aptitude & Business Statistics:Permutations and Combinations
79
4.In how many ways can 8 persons be seated at a round table? A) 5040 B) 4050 C) 450 D) 540
Quantitative Aptitude & Business Statistics:Permutations and Combinations 80
4.In how many ways can 8 persons be seated at a round table? A) 5040 B) 4050 C) 450 D) 540
Quantitative Aptitude & Business Statistics:Permutations and Combinations 81
5. If
P13 : P12 =3 : then 4
n+1
value of n is A) B) C) D) 15 14 13 12
Quantitative Aptitude & Business Statistics:Permutations and Combinations
82
5. If
P13 : P12 =3 : then 4
n+1
value of n is A) B) C) D) 15 14 13 12
Quantitative Aptitude & Business Statistics:Permutations and Combinations
83
6.Find r if 5Pr = 60 A) 4 B) 3 C) 6 D) 7
Quantitative Aptitude & Business Statistics:Permutations and Combinations
84
6.Find r if 5Pr = 60 A) 4 B) 3 C) 6 D) 7
Quantitative Aptitude & Business Statistics:Permutations and Combinations
85
7. In how many different ways can seven persons stand in a line for a group photograph? A) 5040 B) 720 C) 120 D) 27
Quantitative Aptitude & Business Statistics:Permutations and Combinations 86
7. In how many different ways can seven persons stand in a line for a group photograph? A) 5040 B) 720 C) 120 D) 27
Quantitative Aptitude & Business Statistics:Permutations and Combinations 87
8. If 18 Cn = 18 Cn+ 2 of n is ______ A) 0 B) 2 C) 8 D) None of above
then the value
Quantitative Aptitude & Business Statistics:Permutations and Combinations
88
8. If 18 Cn = 18 Cn+ 2 of n is ______ A) 0 B) 2 C) 8 D) None of above
then the value
Quantitative Aptitude & Business Statistics:Permutations and Combinations
89
9. The ways of selecting 4 letters from the word EXAMINATION is A) 136. B) 130 C) 125 D) None of these
Quantitative Aptitude & Business Statistics:Permutations and Combinations
90
9. The ways of selecting 4 letters from the word EXAMINATION is A) 136. B) 130 C) 125 D) None of these
Quantitative Aptitude & Business Statistics:Permutations and Combinations
91
10 If 5Pr = 120, then the value of r is A) 4,5 B) 2 C) 4 D) None of these
Quantitative Aptitude & Business Statistics:Permutations and Combinations
92
10 If 5Pr = 120, then the value of r is A) 4,5 B) 2 C) 4 D) None of these
Quantitative Aptitude & Business Statistics:Permutations and Combinations
93
THE END
Permutations and Combinations
