Permutation & Combination Tricks & Tips
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 [a,b,c,d][a,b,c,d], the letter arrangement abcabc will form a permutation that is different from the arrangement of same three letters, bcabca. This second arrangement is another unique 3 letter permutation of the 4 letters [a,b,c,d][a,b,c,d].
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,
3P3=3×2=factorial(3) =3!3P3=3×2=factorial(3) =3!
=3×2×1=6=3×2×1=6
All possible 3 letter permutations or distinct arrangements of 3 letters a, b, c are,
abc, acb, bca, bac, cab, cbaabc, acb, bca, bac, cab, cba
If there were 4 distinct letters [a,b,c,d][a,b,c,d] instead of three, the total number of different ways to arrange the letters or permutations will be,
4P4=4!=244P4=4!=24
Case 2: Let us now consider another case of all possible permutations of 3 letters out of 4 letters [a,b,c,d][a,b,c,d]. 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,
4P3=4×3×2=24=4!(4−3)!4P3=4×3×2=24=4!(4−3)!
Similarly, number of permutation of 3 objects out of 5 different objects is,
5P3=5×4×3=60=5!(5−3)!5P3=5×4×3=60=5!(5−3)!
In general, number of permutations of nn distinct objects out of mm distinct objects is,
mPn=m×(m−1)×(m−2)...×(m−n+1)mPn=m×(m−1)×(m−2)…×(m−n+1)
=m!(m−n)!=m!(m−n)!
The expression m×(m−1)×(m−2)...×(m−n+1)m×(m−1)×(m−2)…×(m−n+1) is multiplied and divided by (m−n)!(m−n)! to get m!m! in the numerator and (m−n)!(m−n)! 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×(m−1)×(m−2)...×(m−n+1)m×(m−1)×(m−2)…×(m−n+1) arrangements or permutations are formed following a systematic method.
Take note: Number of permutations of mm out of mm distinct objects is same as (m−1)(m−1) out of mmdistinct objects.
mPm=m!(m−m)!=m!0!mPm=m!(m−m)!=m!0!
=m!1!=m![m−(m−1)]!=mPm−1=m!1!=m![m−(m−1)]!=mPm−1
That means 4 out of 4 object permutations, that is 4!=244!=24 is same as 3 out of 4 permutations, which is also 24.
By definition, 0!=10!=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,
5P3=5!(5−3)!5P3=5!(5−3)!
=5!2!=5×4×3=60=5!2!=5×4×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×5P2=4×5!(5−2)!4×5P2=4×5!(5−2)!
=4×5!3!=4×5×4=80=4×5!3!=4×5×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×3=93×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 mm out of mm permutation in which pp 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 xx. In each of these permutations, there are pp objects in various positions of the arrangements. Let us take one of these xx arrangements. In this arrangement, if we make these pp objects all distinct now, we will have p!p! ways to rearrange these now different pp objects among the particular positions of the specific arrangement of xxchosen.
Thus if we make the pp objects distinct, for each of the xx arrangements we will have p!p! new arrangements and we will reach the mm out of mm distinct object permutations. This means,
mPm=m!=x×p!or, x=m!p!mPm=m!=x×p!or, x=m!p!
Ultimately it is a simple relationship – for pp alike objects in mm objects, the mm out of mm permutation is m!m! divided by p!p!.
If there are qq more alike objects in mm in addition to pp alike objects, we just need to divide our previous permutation by q!q!. Thus, for pp, qq and rr alike objects in mm objects the number of mm out of mm permutations is,
m!p!q!r!m!p!q!r!
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,
6!2!=6×5×4×3×2×12×1=3606!2!=6×5×4×3×2×12×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×2×2×2×2×2=26=642×2×2×2×2×2=26=64
Combination
Basic concepts
Combination is selection of rr objects from a set of nn distinct objects. In this case, there is no importance attached to the order of selection. Each unique set of rr objects selected form one combination.
As in each such combination the rr objects selected can be ordered among themselves in r!r!unique ways, if we order all the combinations in this way we would get the permutation of rr out of nn distinct objects. Thus, number of combinations multiplied with r!r! gives us number of permutations.
So,
Number of combinations,
nCr=Number of Permutationsr!nCr=Number of Permutationsr!
=n!r!(n−r)!=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,
5C3=5!3!(5−3)!=5!3!2!=105C3=5!3!(5−3)!=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(4−1)=3 members out of (8−1)=7(8−1)=7 members. The required number of ways then,
7C3=7!3!(7−3)!=7!3!4!=357C3=7!3!(7−3)!=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(8−2)=6 and the required number of combinations is,
6C4=6!4!(6−4)!=6!4!2!=156C4=6!4!(6−4)!=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?
- 1600
- 900
- 4800
- 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?
- 9
- 12
- 15
- 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,
- 65666
- 66660
- 66550
- 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?
- 388
- 276
- 150
- 212
Problem 5. In how many ways can the letters of the word METRIC be arranged so that the two vowels are never together?
- 480
- 960
- 560
- 280
Problem 6. How many straight lines can be drawn from 15 non-collinear points?
- 110
- 105
- 115
- 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?
- 2800
- 2880
- 2400
- 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?
- 15
- 20
- 16
- 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,
- 45
- 91
- 90
- 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?
- 3150
- 3350
- 3250
- 4500
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.
Permutation
1. ^{n}P_{r} = n! / (n-r)!
Combination
- ^{n}C_{r} = n!/ r! × (n-r)!
- ^{n}C_{0} = 1
- ^{n}C_{n} = 1
- ^{n}C_{r} = ^{n}Cn – r
- ^{n}C_{a} = ^{n}C_{b} => a = b => a+b = n
- ^{n}C_{0} + ^{n}C_{1}+ ^{n}C_{2}+ ^{n}C_{3}+ ……………+ ^{n}C_{n }=_{ 2}^{n}
Permutation vs Combination
- order
- arrange or choose
- number of permutation > number of combination
In Arrangements we have,
Questions :
Factorial Notation
Counting Rules
Multiplication
= 6
If a work A can be done in m ways and another work B can be done in n ways and C is the final work which is done only when both A and B are done, then the no. of ways of doing the final work ?
Sol :
C = m × n
C = 3 × 2 = 6
Addition rule
Problems and Solutions
the no. of digits = 5
Sol:
Ques 3. Find the number of different words that can be formed from the word ‘SUCCESS’.
Sol : No. of Permutation = n! / p! × q!, where p = of one type , q = ( of another type ).
Ques 4. How many different 5 – digit numbers can be formed by using the digits of the number 713628459 ?
Sol :
Total of such numbers = 5 × 5 v 3 = 75
req no. = 30+75 = 105
Ques 8. A round table conference is to be held between delegates of 15 companies. In how many ways can they be seated if delegates from two MNCs may wish to sit together ?
Sol :
Since delegates from two multinational companies will sit together, so considering these two delegates as one unit, there will be 13 + 1 = 14 delegates who can be arranged in a circular table in 14! ways.
The two delegates from the MNCs can be arranged among themselves in 2! ways.
Using the product rule, the required no. of ways = 14!×2!
Ques 9. A person has 12 friends out of which 7 are relatives. In how many ways can he invite 6 friends such that at least 4 of them are relatives ?
Sol:
Question 10. How many numbers of five digits can be formed with the digits 0, 1, 2, 4, 6 and 8 ?
Sol:
Required no. of numbers = 5 × ^{5}P_{4}= 5 × 5! = 5×120 = 600
Permutations: The hairy details
Let’s start with permutations, or all possible ways of doing something. We’re using the fancy-pants term “permutation”, so we’re going to care about every last detail, including the order of each item. Let’s say we have 8 people:
1: Alice
2: Bob
3: Charlie
4: David
5: Eve
6: Frank
7: George
8: Horatio
How many ways can we award a 1st, 2nd and 3rd place prize among eight contestants? (Gold / Silver / Bronze)
We’re going to use permutations since the order we hand out these medals matters. Here’s how it breaks down:
- Gold medal: 8 choices: A B C D E F G H (Clever how I made the names match up with letters, eh?). Let’s say A wins the Gold.
- Silver medal: 7 choices: B C D E F G H. Let’s say B wins the silver.
- Bronze medal: 6 choices: C D E F G H. Let’s say… C wins the bronze.
We picked certain people to win, but the details don’t matter: we had 8 choices at first, then 7, then 6. The total number of options was 8 · 7 · 6 = 336.
Let’s look at the details. We had to order 3 people out of 8. To do this, we started with all options (8) then took them away one at a time (7, then 6) until we ran out of medals.
We know the factorial is:
Unfortunately, that does too much! We only want 8 · 7 · 6. How can we “stop” the factorial at 5?
This is where permutations get cool: notice how we want to get rid of 5 · 4 · 3 · 2 · 1. What’s another name for this? 5 factorial!
So, if we do 8!/5! we get:
And why did we use the number 5? Because it was left over after we picked 3 medals from 8. So, a better way to write this would be:
where 8!/(8-3)! is just a fancy way of saying “Use the first 3 numbers of 8!”. If we have n items total and want to pick k in a certain order, we get:
And this is the fancy permutation formula: You have n items and want to find the number of ways k items can be ordered:
Combinations, Ho!
Combinations are easy going. Order doesn’t matter. You can mix it up and it looks the same. Let’s say I’m a cheapskate and can’t afford separate Gold, Silver and Bronze medals. In fact, I can only afford empty tin cans.
How many ways can I give 3 tin cans to 8 people?
Well, in this case, the order we pick people doesn’t matter. If I give a can to Alice, Bob and then Charlie, it’s the same as giving to Charlie, Alice and then Bob. Either way, they’re equally disappointed.
This raises an interesting point — we’ve got some redundancies here. Alice Bob Charlie = Charlie Bob Alice. For a moment, let’s just figure out how many ways we can rearrange 3 people.
Well, we have 3 choices for the first person, 2 for the second, and only 1 for the last. So we have 3 · 2 · 1 ways to re-arrange 3 people.
Wait a minute… this is looking a bit like a permutation! You tricked me!
Indeed I did. If you have N people and you want to know how many arrangements there are for all of them, it’s just N factorial or N!
So, if we have 3 tin cans to give away, there are 3! or 6 variations for every choice we pick. If we want to figure out how many combinations we have, we just create all the permutations and divide by all the redundancies. In our case, we get 336 permutations (from above), and we divide by the 6 redundancies for each permutation and get 336/6 = 56.
The general formula is
which means “Find all the ways to pick k people from n, and divide by the k! variants”. Writing this out, we get our combination formula, or the number of ways to combine k items from a set of n:
A few examples
Here’s a few examples of combinations (order doesn’t matter) from permutations (order matters).
- Combination: Picking a team of 3 people from a group of 10. C(10,3) = 10!/(7! · 3!) = 10 · 9 · 8 / (3 · 2 · 1) = 120.Permutation: Picking a President, VP and Waterboy from a group of 10. P(10,3) = 10!/7! = 10 · 9 · 8 = 720.
- Combination: Choosing 3 desserts from a menu of 10. C(10,3) = 120.Permutation: Listing your 3 favorite desserts, in order, from a menu of 10. P(10,3) = 720.
Problem Sets On Permutation & Combinations
- How many 3 digit number can be formed with the digits 5, 6, 2, 3, 7 and 9 which are divisible by 5 and none of its digit is repeated?
a) 12
b) 16
c) 20
d) 24
e) None of these - In how many different ways can the letter of the word ELEPHANT be arranged so that vowels always occur together?
a) 2060
b) 2160
c) 2260
d) 2360
e) None of these - There are 4 bananas, 7 apples and 6 mangoes in a fruit basket. In how many ways can a person make a selection of fruits from the basket.
a) 269
b) 280
c) 279
d) 256
e) None of these - There are 15 points in a plane out of which 6 are collinear. Find the number of lines that can be formed from 15 points.
a) 105
b) 90
c) 91
d) 95
e) None of these - In how many ways 4 Indians, 5 Africans and 7 Japanese be seated in a row so that all person of same nationality sits together
a) 4! 5! 7! 3!
b) 4! 5! 7! 5!
c) 4! 6! 7! 3!
d) can’t be determined
e) None of these - In how many ways 5 Americans and 5 Indians be seated along a circular table, so that they are seated in alternative positions
a) 5! 5!
b) 6! 4!
c) 4! 5!
d) 4! 4!
e) None of these - 4 matches are to be played in a chess tournament. In how many ways can result be decided?
a) 27
b) 9
c) 81
d) 243
e) None of these
Q(8 –9) There are 6 players in a cricket which is to be sent to Australian tour. The total number of members is 12.
- If 2 particular member is always included
a) 210
b) 270
c) 310
d) 420
e) None of these - If 3 particular player is always excluded
a) 76
b) 82
c) 84
d) 88
e) None of these - In a group of 6 boys and 5 girls, 5 students have to be selected. In how many ways it can be done so that at least 2 boys are included
a) 1524
b) 1526
c) 1540
d) 1560
e) None of these
- How many words of 4 letters with or without meaning be made from the letters of the word ‘NUMBER’, when repetition of letters is not allowed?
A) 480
B) 360
C) 240
D) 360
E) 24 - In how many ways the letters of the word ‘ALLIGATION’ be arranged taking all the letters?
A) 120280
B) 453600
C) 360340
D) 3628800
E) None of these - In how many ways all the letters of the word ‘MINIMUM’ be arranged such that all vowels are together?
A) 60
B) 30
C) 90
D) 70
E) 120 - In how many ways a group of 4 men and 3 women be made out of a total of 8 men and 5 women?
A) 720
B) 140
C) 120
D) 360
E) 210 - How many 3 digit numbers are divisible by 4?
A) 256
B) 225
C) 198
D) 252
E) 120 - How many 3 digits numbers have exactly one digit 2 in the number?
A) 225
B) 240
C) 120
D) 160
E) 185 - There are 8 men and 7 women. In how many ways a group of 5 people can be made such that the particular woman is always to be included?
A) 860
B) 1262
C) 1001
D) 1768
E) 984 - There are 6 men and 7 women. In how many ways a committee of 4 members can be made such that a particular man is always to be excluded?
A) 280
B) 420
C) 220
D) 495
E) 460 - How many 4 digit words can be made from the digits 7, 8, 5, 0, and 4 without repetition?
A) 70
B) 96
C) 84
D) 48
E) 102 - In how many ways 8 students can be given 3 prizes such that no student receives more than 1 prize?
A) 348
B) 284
C) 224
D) 336
E) None of these
- In how many ways can 3 prizes be given away to 12 students when each student is eligible for all the prizes ?
A.1234
B.1728
C.5314
D.1331
E.None of these - Total no of ways in which 30 sweets can be distributed among 6 persons ?
A.35 C _{5}
B.36 C _{5}
C.36 C _{6}
D.35!/5!
E.None of these - A bag contains 4 red balls and 5 black balls. In how many ways can i make a selection so as to take atleast 1 red ball and 1 black ball ?
A.564
B.345
C.465
D.240
E.None of these - In how many ways can 7 beads be strung into necklace ?
A.2520
B.5040
C.720
D.360
E.None of these - Find the no of 3 digit numbers such that atleast one of the digit is 6 (with repetitions) ?
A.252
B.345
C.648
D.560
E.None of these - In how many ways can 7 girls and 4 boys stand in a row so that no 2 boys are together ?
A.8467200
B.9062700
C.7407000
D.8407200
E.None of these - In how many ways the letters of the word PERMUTATION be arranged ?
A.10!/2!
B.10!
C.11!
D.11!/2!
E.None of these - How many numbers can be formed with the digits 1, 7, 2, 5 without repetition ?
A.89
B.56
C.64
D.72
E.None of these - There are 3 boxes and 6 balls. In how many ways these balls can be distributed if all the balls and all the boxes are different?
A.243
B.512
C.729
D.416
E.None of these - In how many ways can 4 books be selected out of 10 books on different subjects ?
A.210
B.320
C.716
D.5040
E.None of these