PERMUTATION AND COMBINATION
In this section we shall consider the technique for determining the number of possible outcomes of a particular experiment of the number of elements in a particular set.
FACTORIAL NOTATION
The product of the positive integer n can be written in the form n! (read “n factorial” )
n! = (n) (n–1) (n–2)………..3.2.1
It is also convenient to define 0! = 1
Example
7! = 7×6×5×4×3×2×1 = 5040
4! = 4×3×2×1 = 24
9! = 9×8×7! = 72×5040 = 362,880
Example
Example
Express in factorial Notation
(a) 9×8×7×6×5×4 (b) (n – 4) (n – 5) (n – 6) (c) (n + 6) (n + 5) (n + 4) (n + 3)
Example
Express in factor
(a) 19! – 17!
(b) 17! + 14!
(c) (n–1)! –(n–2)! – (n–3)!
(d) n! – (n – 3)!
Solution
(c) (n–1)! – (n–2)! –(n–3)! = (n–1)(n–2)(n–3)!– (n–2)(n–3)! – (n–3) !
= (n–3)! [(n–1) (n–2)– (n–2)–1]
= (n–3)! [n2 –3n+2–n+2–1]
= (n–3)! [n2–4n+3]
= (n–1)(n–3)(n–3)!
(d) n! – (n–3)!= n(n–1)(n–2)(n–3)! – (n–3) !
= (n–3)! [n(n–1)(n–2)–1]
= (n–3)! [n(n2–3n+2) –1]
=(n–3) ! (n3–3n2+2n –1)
PERMUTATION
The arrangement of objects taking into account the different order of arrangement is called Permutation. Consider a problem like finding the numbers of way of arranging WXYZ.
Working systematically WXYZ can be listed as
WXYZ XWYZ YWXZ ZWXY
WXZY XWZY YWZX ZWYX
WYXZ XYWZ YWZX ZWYX
WYZX XYZW YXZW ZXYW
WZXY XZWY YZWZ ZYWX
WZYX XZYW YZXW ZYXW
There are 24 arrangements
Consider arranging XYZ
XYZ YXZ ZXY
XZY YZX ZYX
There are six ways of arranging XYZ. You will notice that number of different arrangements of the letters WXYZ is equivalent to 4×3×2×1 = 24, while XYZ is equivalent to 3×2×1 = 6
In general, the permutation or arrangement of n unlike things taken all together is equal to the product to the product n (n–1)(n–2) ––––––––3×2×1. This is written as nPn = n!
Factorial n written n! is read n factorial
Example
6! = 6×5×4×3×2×1 = 720
5! = 5×4×3×2×1 = 120
4! = 4×3×2×1 = 24
3! = 3×2×1 = 6
Example
Suppose we are interested in the way 8 different books can be arranged to fill 3 vacant places on a bookshelf.
Solution
The first position can be taken by 8 books the second can be taken by 7 books, the third position can be taken be 6 books. So the number of ways, the first, second and third shelf can be filled is 8 × 7 × 6.
This arrangement is called permutation of 8 books taking 3 shelves at a time and is designated by
8P3 = 8×7×6
hence in general
is the permutation of n objects taking r at a time
Note
n! = n(n –1)(n – 2) – – – – × 3×2×1
= n(n – 1)!
If n = 1
Then 1! = 1×0!
We can define in factorial notation 0! = 1
Example
(i) 7P3 (ii) 10P2 (iii) 11P2
Solution
Example
Find the number of possible permutations of the letter of the word MATRIX
Solution
There are six different letter M,A,T,R,I and X in the word. Hence the number of permutation of the letters of the word is 6P6
6P6 = 6! = 6×5×4×3×2×1 = 720
Example
In how many ways can the 1st, 2nd, 3rd, 4th and 5th prizes be awarded in a class of 25 students.
Solution
The 1st prize can be award in 25 ways, the 2nd in 24 ways, the 3rd in 23 ways, the 4th in 22 ways and the 5th in 21 ways.
i.e.
Example
Solve for x
(a) 14. xp3 = x+2P4
(b) xP5 = 18. x–2P4
Solution
x2 + 3x + 2 = 14 (x – 2)
x2 + 3x + 2 = 14x – 28
x2 – 11x + 30 = 0
(x–6)(x–5) = 0
x = 6 or x = 5
x2 – x = 18 (x – 5)
x2 – x = 18x – 90
x2 – 19x + 90 = 0
(x – 9) (x – 10) = 0
x =9 or x =10
PERMUTATION INCLUDING IDENTICAL OBJECTS
The permutation or arrangement of n thing taken altogether when p are alike of a first kind, a q alike of a first kind, r alike of a first kind is
Example
Find the number of permutation of the word MATHEMATICS
Solution
There are 2M, 2A, 2T, 1H, 1C, I, IS, IE.
There are 11 letters, hence the total number of permutation of the letter of the word is
Example
Find the number of ways of arranging the letters of the word ABAKALIKI
Solution: Total number of letter in ABAKALIKI is 9
There are 3A, 1B, 2K, 1L, 2I.
Total arrangement =
Example:– In how many can two white and three red balls be arranged
Total numbers of balls = 5
We have 2 white and 3 red balls
Total arrangement =
CONDITIONAL PERMUTATION
When conditions are applied to the way things arranged, it then happen that permutation is said to be conditional.
Example
Find the number of ways; the letters of the word ABUJA can be permutated
(a) If the two As must always be apart
(b) If the two As must always be together
Solution
(a) Omitting out the two As, the letter BUJ can be arranged in 3! ways with each of these ways, the first A can be inserted in any one of 4 places
B U J
When this is done, the second A can be inserted in 3 ways, in which it will not come next to the first A but also the two As cannot be distinguished.
Therefore the number of arrangement is
(b) Taking the two As one object the letter of the word can be arranged in 3! Ways
*B * U * J *
As can occupy any of the asterisk positions in 4 ways. Hence the numbers of arrangement is 3! × 4 = 24 ways
Or
If the 2As must always be together, we take them as one the we have (AA) BUJ. The number of permutation of these letters is 4! = 24 ways
Example
1. Find the number of ways, the letters of the word ABAKALIKI can be arranged
(a) If the three As must always be together
(b) If the three As must always be apart
Solution
(a) Taking the three As one object, the letter of the B K L I K I can be arranged in
* B * K * L * I * K * I *
AAA can occupy any of the asterisk position in 7 ways. Hence the number of arrangements is
(b) Omitting out the three As, the letter BKLIKI can be arranged in
With each of these ways, the first A can be inserted in any one 7 places
B K L I L K I
The second A can be inserted in 6 ways and the third A can be inserted in 5 ways, in which they will not come next to each other, but also the three As cannot be distinguished.
Therefore the number of arrangement is
Example : How many number greater than 200 can be formed using the digit 1,2,3,4,5, if no digit
may be repeated.
Solution
The numbers formed using all 5 digits will be greater than 200.
The 5 – digits numbers can be arranged in 5P5 = 5! Ways
Also if we form a four digit number beginning with 5,4,3,2,1, i.e. the first digit can be 5 ways and remaining 3 – digit chosen from 4 can be arranged in 4p3
The arrangement for 4 – digits numbers = 5× 4P3 ways next we can form 3 – digits numbers greater than 200 using 5,4,3,2, to begin the number to be formed.
i.e. the first digit can be chosen 4 ways and the remaining 2 – digit chosen from 4 can be arranged 4P2
Total arrangement for the 3 – digit number = 4 × 4P2
Hence the total arrangement = 5! + 5 × 4P3 + 4 × 4P2 =288
Example
How many four and five digit numbers can be formed using the digit 2, 3, 4, 5 6 (no repetition)? How many will be greater than 300? How many will be even numbers.
Solution
(a) Numbers of 4 – digits = 5P4 = 5×4×3×2 = 120
Numbers of 5 – digits = 5P5 = 5! = 5×4×3×2×1 = 120
Number of 4 digits and 5 – digits number = 120 + 120 = 240
(b) Number of 3 – digit greater than 300 are those that begin with 3,4,5,6 = 4×4P2 = 48
Numbers that will be greater than 300 are number of 3 – digits, 4 – digits and 5 – digits
= 120 + 120+ 48 = 288
(c) If all the five digits are used and the number is to be even, the last (right hand) digits must be either 2,4,6 which gives 3 choices, when this is done, the remaining 4 digits from 4 can be arranged 4P4
Total arrangement for 5 – digit will be 3 × 4P4
If four digits is formed, and the number is even, the last (right hand) digits must be either 2,4,6 which also gives 3 choices, the remaining 3 – digits from 4P3
Total arrangement for 4 – digit will be 3 × 4P3
If three digits are formed and the number will be even. The last (right hand) digits must be either 2,4,6 which will give 3 choices, the remaining 2 digits from 4.
Total arrangement for 3 – digit = 3 × 4P2
Total number possible that would be even = 3× 4P4 + 3 × 4P3 +3 × 4P4 = 72 + 72 + 36
= 180
CYCLIC PERMUTATION
It is a permutation around a circular object, it must be noted, a circular object has no beginning and
no end, we fix one object (or person) and permute the remaining. The number of ways of doing this is
1 × (n – 1)! = (n – 1)!
Example
In how many ways can 6 students of a school be seated around a circular table
Solution
The problem is a cyclic permutation
The number of ways the 6 students can be seated = 1×(6–1)!
5! = 5×4×3×2×1 = 120
Example
In how ways can four men and two women be seated at a round table
(1) If a particular man and woman must sit together
(2) If the woman do not sit next to each other
Solution
1. If a particular man and woman must sit together. We fix the man and woman as one and this
can be done in two ways, and the remaining people can be arranged in 4! Ways
Hence the number of ways will be 2 × 4! = 48 ways
2. If two particular women must not sit together firstly, find the number of arrangement without
restriction. That will be 5! = 120 ways
Then the number of arrangement if the woman sit together, this can be alone in two ways and the remaining men can be arranged in 4! Ways. The number of arrangement will be 2×4! = 48 ways
Hence the number of ways possible if two particular woman must not sit together
= 120 – 48 ways
= 72 ways
Note:– The number of ways of arranging n – fixed objects around a circular ring which can be turned over is
PERMUTATION WITH REPETITION ALLOWED
If we are asked to find the number of permutation or arrangement of n things taken r at a time, when each n things can be repeated up to r times in any arrangement. Consider a situation where r boxes is to be filled with n objects, if any of the n objects can be used as many times as is like in any arrangement.
The first boxes can be filled in n ways and, when that is done, the second box can also be filled in n ways, since all the objects can be used again, hence the first two boxed can be filled in n × n = n2 ways
Similarly, there are n ways of filling the thirds box therefore the number of ways of filling the first three boxes is n × n × n = n3
Continuing in this way, it will be seen that r boxes can be r boxes can be filled in nr ways
Example
How many 3 – letter code can formed using the letters of alphabet if repetition is allowed.
Solution
There are 26 letters in the alphabet
A,B,C,……Z
Form our previous proof; there will be 263 = 17576
Example:– How many 4 – digit number can be formed from 2, 4, 6, 8, 10 if repetition is allowed.
Solution
54 = 625
COMBINATION
Combination or selection is a set of quantities chosen from a given set where attention is not paid on the order of the quantities within the set.
If we are given four letters a, b, c, d in how many ways can three letter be arranged from the four letters. The number of arrangement is 4P3 = 4×3×2 = 12
Consider, if we are not interested in the order of the letters, but only in number of selection of three letter would be 4C3
The number of selection or combinations of three letter chosen form four letter would be
Since order is irrelevant, abc, acd, bac, etc are the same selection. Each set of three can be arranged in 3! Way. But all these count combination or selection.
In general
nCr is the number of combination of n different objects taken r at a time without regard the order of arrangement .An alternative notation of
It can be shown that nCr = nCn–r
Note:– r! in took the second place in the denominator in equation (1),
while in nCn – r i.e. r! took the first place in the denominator .It is important that you take note of this point as we shall see its applications soon.
Replacing r by n in this result nCn = nC0 = 1
Example
Example
In how many ways can two males be selected from a class of sixteen?
Solution
Example
A committee consisting of 3 men and 5 women is to selected from 5 men and 10 women, find how ways this can be formed.
Solution
Number of ways of selecting 2 men from 5 men
Number of ways of selecting 5 women from 10 women is
Hence the number of ways of forming the committee = 252 × 10 = 2520 ways.
Example
A committee of 3 men and 3 women is to be chosen from 6 men and 4 women
i. How many different committees can be formed
ii. If one of the women refuses to serve on the same committee as a particular man, how many
committees are now possible
Solution
(i) The three men can be selected in 6C3 ways
The three women can be selected in 4C3
Therefore the number of possible committees = 6C3 × 4C3
= 80 ways
ii. Firstly, we find the number of committees which will include both these particular man and
woman we select therefore two more man from the 5 others (10 choices) and 2 more women from
the remaining 3. Hence the number of committee having both the particular man and woman is
5C2 × 3C1 = 30 ways
Therefore out of the 40 possible committees, then 12 will include both these people.
Hence 80 – 30 = 50 committees do not include both of them.
Example
The minister of the federal capital territory has accused some members of the senate of wanting to collect bribe before his approval to be a minister. The senate wants to look into the issue by constituting a committee of 6 members which is to be selected from 7 men and 4 women. How many ways can the committees selected so that.
A. At least one woman is always there in the committee
B. At least four men and one woman are always there in the committee.
Solution
A. In this case the committee possibilities are
1woman and 5 men
2 women and 4 men
3 woman and 3 men
4 women and 2 men
The first of these gives to
4C1 × 7C5 = 84 ways
The second gives rise to
4C3 × 7C4 = 210
The third gives rise to
4C3 × 7C3 = 140
The fourth gives rise to
4C4 × 7C2 = 21
Therefore total number of ways = 84 + 210 + 140 + 21 = 455 ways
(b) In this case the committee possibilities are
4 men and 2 women
5 men and 1 woman
The first will give rise 7C2 × 4C2 = 200
The second will give rise 7C5 × 4C1 = 84
Therefore total number of ways = 210+84 = 294
Example
A committee of seven is to be chosen from five Yorubas, four Ibos, seven Hausas. In how many way can this be done so that contains at least 2 Yorubas, and 3 Ibos
Solution
The following are the possible committee that can be formed
a. Yoruba Ibos Hausa
1. 2 3 2
2. 3 3 1
3. 4 3 0
4. 2 4 1
For (1) there will be 5C2 × 4C3 × 7C2 = 840 ways
(2) there will be 5C4 × 4C3 × 7C1 = 280 ways
(3) there will be 5C4 × 4C3 × 7C0 = 20 ways
(4) there will be 5C2 × 4C4 × 7C1 = 70 ways
Therefore the total number of ways of choosing the committee
= 840 + 280 + 20 + 70 = 1210
Example
Show that nCr + nCr–1 = n+1Cr
From l.h.s nCr + nCr–1 =
Comparing (1) and (2) we see that L.H.S = R.H.S
nCr + nCr–1 = n+1Cr
Click here to go back to the content page