Permutation and Combination
Factorial Notation : -
When we continuously multiply of n natural numbers or positive integers from 1 to n , then the product obtained is called n factorial or factorial n and it is represented by n! .
or n! = ( n - 1 ).( n - 2 )………..3.2.1
1.When n is given as a negative integer or a fraction, then the factorial value of the given number can not be determined. It is always zero.
i.e. ( -1 )! = 0
2. 0! = 1
3. n! = n( n - 1 )!
4. ( 2n )! = 2^{n} . n![ 1.3.5.7……….( 2n - 1 ) ]
Example 1. Evaluate .
( ⅰ ) | ||
13! |
( ⅱ ) | ||
( 6! x 3! ) |
( ⅲ ) | ||
9! |
Sol :- ( ⅰ ) | = | = 15 x 14 = 210 | ||
13! | 13! |
( ⅱ ) | = | = 4 x 3 x 7 = 84 | ||
( 6! x 3! ) | ( 6! x 3 x 2 ) |
( ⅲ ) | = | |||
9! | 9! |
= | = 10(132 + 1 ) = 133 x 10 = 1330 | |
9! |
( ⅰ ) 5.6.7.8.9.10 ( ⅱ ) 2.4.6.8.10.12
Sol :- ( ⅰ ) On multiplying and divided by 1.2.3.4 ,
= | = | |||
1.2.3.4 | 4! |
= ( 2.2.2.2.2.2 ).( 1.2.3.4.5.6) = 2^{6}.6!
Fundamental Principle of Counting :-
( 1 ) Multiplication Principle :-
If, when an event occurs in m different ways , after that the other event can occur in n different ways, then the total number of occurences of both events in the given sequence in m × n different ways is obtained.
Example 3. How many numbers of two digits can be formed out of the digits 1, 2, 3, in which no digit is repeated ?
Sol : - Total possible numbers to be formed of two digits from digits 1, 2, 3 = {12, 13, 21, 23, 31, 32}
Since no digit has been repeated in the numbers formed from the digits 1, 2, 3 in the above two digits.
Therefore, the total number of two digits from digits 1, 2, 3 will be 6.
( 2 ) Addition Principle :-
If when an event occurs in different ways of 'm' and other second event , which is independent of the first incident may occur in n different ways, then in the given sequence, both incidents occur in different ways.
Example 4 :- There are 100 students in a class with 60 boys and 40 girls .The class teacher selects either a boy or a girl for monitor post of the class .In how many ways , the class teacher can make this selection ?
Sol :- As there are 60 boys and 40 girls and monitor selected can be anyone from the given students .
Hence , required number of ways = 60 + 40 = 100
Permutation :-
Each individual arrangement which can be taken on the number of all the items or things given at a time, is called permutation. In other hand , when taking some or all of given number of things or objects are arranged in a certain sequence with a given order, then this arrangement is called permutation.
Assume r and n are positive integer, such that 1 ≤ r ≤ n . Then , the number of permutations of n different thing together with r objects , then r objects are choosen from the n objects . It is represented by ^{n}p_{r} Or P (n, r).
^{n} P _{r} = | |
( n - r )! |
Note: - Permutation of objects means "arrangement of things". The word arrangement is used if order of objects is taken as. Thus, if the order of different things changes, then their arrangement also changes.
For Example : - Number of permutations made together with 3 things out of 5 things
^{5} P _{3} = | ||
( 5 - 3 )! |
^{5} P _{3} = | ||
2! |
^{5} P _{3} = | = 60 | |
( 2 x 1 ) |
Some Important Results :-
^{n} P _{r} = | = n( n - 1 )( n - 2 )…………[ n - ( r + 1 )] ,0 ≤ r ≤ n | |
( n - r )! |
Evaluate :-
( ⅰ ) P( 5 , 4 ) ( ⅱ ) P( 9 , 5 ) and ( ⅲ ) P( 11 , 3 )
( ⅰ ) ^{5} P _{4} = | = | = 120 | ||
( 5 - 4 )! | 1! |
( ⅱ ) ^{9} P _{5} = | = | = 15120 | ||
( 9 - 5 )! | ( 4 x 3 x 2 x 1 ) |
( ⅲ ) ^{11} P _{3} = | = | = 990 | ||
( 11 - 3 )! | ( 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 ) |
2 . The number of permutations of n objects taken all at any given time, one of which p are alike and are similar to the second type of q and apart from them all are different. Then,
Permutation = n! / p!.q!
Example 5. There are 3 red, 1 white and 2 blue stones in one bag. They are drawn one by one and arranged in a row. Assuming that all 8 marble stones have been drawn, find out the number of their various arrangement.
Sol :- Here, n = 8, p_{1} = 3, P_{2} = 1 and p_{3} = 2
∴ Required number of different arrangement = | = | |||
p_{1}!.p_{2}!.p_{3}! | ( 3!.1!.2! ) |
= | = 56 x 60 = 3360 | |
( 3 x 2 x 1 x 1 x 2 x 1 ) |
Hence required total number of different arrangement is 3360 .
3. If n objects are selected from different r objects , which taken at that time, when each object is repeated allowed. Then,
Example 6:- Ram has 5 friends to invite on his marriage. In how many ways , can he send invitation cards to them , if he has 4 servants to carry the cards ?
Sol :- Invitation cards may be sent to each of the five friends by anyone of the four servants in 4 ways .
∴ Required ways = 4^{5} = 4 x 4 x 4 x 4 x 4 = 1024
Permutation under Restrictions : -
( a ) If n different things or objects are taken in such a way from various type of r things at a time , when a particular object is to be always included in each arrangement , then
( b ) Number of permutations of n different objects is taken from out of r object at a time , when s particular objects are to be always included in each arrangement.Then ,
( c )If n different things are taken from various type of r things at a time , when a particular thing is never taken in each arrangement. Which is given below : -
( e ) Number of permutations of n different things , taken all at a time , when m specific things never come together , then
5. Cyclic or circular Permutation :-
Example 7. In how many ways can seven men be seated at a round table ?
Sol :- Here , n = 7
Using the above given formula ,
∴ Required number of ways = ( 7 - 1 )! = 6! = 720
( b ) Such cyclic permutation in which there is no difference in clockwise and anticlockwise arrangements. That is, when the observation can be done from both sides, then the given number of cyclic arrangements ( permutations ) of different objects are below as :-
Number of cyclic permutations = | ||
2 |
Example 8 :- Find the number of ways in which 6 different beads can be arranged to form a necklace.
Sol :- Here , n = 6
Using the above given formula ,
∴ Required number of arrangement = | = | |||
2 | 2 |
= | = 60 | |
2 |
Combinations :-
When different groups or selections are to be made by taking some or all given things together, then the groups formed are called combination. Combination of things means - selection of things or objects. Clearly, the order of objects in the selection of objects has no significance. Thus, the selection of objects with the change of order of objects does not change.
Let n given different things or objects taken out of r things together to be made with a set of combinations and it is represented by c (n, r) or ^{n}c_{r}.
^{n} C _{r} = | (0 ≤ r ≤ n) | |
r!( n - r )! |
^{n} C _{r} = | ||
r! |
^{n} C _{r} = | ||
{ r( r - 1 )( r - 2 ) ……. 3.2.1 } |
For example :- The number of combinations of 4 items out of 6 items is given below:-
^{6} C _{4} = | = | = 15 | ||
{ 4!( 6 - 4 )! } | ( 4! x 2 x 1 ) |
Example 9. Find the value of the following -
( ⅰ ) ^{10} C _{4}
( ⅱ ) ^{11} C _{8}
( ⅲ ) ^{52} C _{49}
Sol :- ( ⅰ )^{10} C _{4} = | = | |||
4!( 10 - 4 )! | (4! . 6!) |
= | = 10 x 7 x 3 = 210 | |
( 4 x 3 x 2 x 1 x 6! ) |
( ⅱ )^{11} C _{8} = | = | |||
8!( 11 - 8 )! | (3! . 8!) |
= | = 11 x 5 x 3 = 165 | |
( 3 x 2 x 1 x 8! ) |
( ⅲ )^{52} C _{49} = | = | |||
49!( 52 - 49 )! | (3! . 49!) |
= | = 26 x 17 x 50 = 22100 | |
(3 x 2 x 1 x 49!) |
Some Important Properties :-
2. ^{n} C _{r - 1} + ^{n} C _{r} = ^{n + 1} C _{r}
Example 10 :- Evaluate ^{10} C _{4} + ^{10} C _{5}
Sol :- Here , n = 10 and r = 5
Using the above given property ,
∴ ^{10} C _{4} + ^{10} C _{5} = ^{10 + 1} C _{5} = ^{11} C _{5}
or y = n - x ⇒ x + y = n
Example 11 :- If ^{10} C _{2r} = ^{10} C _{r + 3} , Find the value of r .
Sol :- Here , n = 10
Using above given property , we have
∵ ^{10} C _{2r} = ^{10} C _{r + 3}
⇒ 2r = r + 3 ⇒ 2r - r = 3 ⇒ r = 3
Hence the value of r is 3 .
4. | = | ||
^{n} C _{r - 1} | r |
Example 12:- Evaluate | ||
^{10} C _{4} |
Using the above given property ,
∴ | = | ||
^{10} C _{4} | 5 |
= | ||
5 |
5. If n is an even number then the greatest value of ^{n} C _{r} is
6. If n is an odd number then the greatest value of ^{n} C _{r} is
7. ^{n} C _{r} = | ||
{ 1.2.3………r } |
8. Number of selections of zero or more things out of n different things
9. Number of combinations of n different things selecting at least one of them is
10. If r different things are taken from out of the given n things at a time , then the number of combinations
Example 13 :- In how many ways can 6 members forming a committee out of 11 be selected so that
( a ) three particular members must be included .
( b ) three particular members must not be included .
Sol :- ( a ) When three particular members are included then , we have to select 6 - 3 = 3 members out of 11 - 3 = 8.
∴ Required Number of ways = C ( 8 , 3 ) = | ||
3!.5! |
C ( 8 , 3 ) = | = 56 | |
(3 x 2 x 5!) |
( b ) When three particular members are not included then , we have to select 6 members out of 11 - 3 = 8.
∴ Required Number of ways = C ( 8 , 6 ) = | ||
6!.2! |
C ( 8 , 6 ) = | = 28 | |
(2 x 1 x 6!) |
And If r = n , then Number of selections of r consecutive things out of n things along a circle = 1
(d) If out of (p + q + r + t) things, p are alike of one kind, q are alike of second kind, r are alike of third kind and t are different, then the total number of selections is
(e) The number of ways of selecting some or all out of ( p + q + r ) items where p are alike of one kind, q are alike of second kind and rest are alike of third kind is
13.(a) Number of ways of dividing ( m + n ) different things in two groups containing m and n things, respectively ( m ≠ n ) .
^{m + n} C _{m} = | ||
m!.n! |
^{m + n + p} C _{m} = | ||
m!.n!.p! |
Some Important Useful Methods :-
1.When the number of triangles is formed by joining the angular points of a polygon of a given n sides as vertices are
6 |
Sol:-Here , n = 6
Using the above given formula,
Required number of triangle = | ||
6 |
= | = 20 | |
6 |
2. If n be the side of any given polygon and its diagonal is formed by joining the vertices of polygon , then
The number of diagonals = | ||
2 |
Sol :- Here , n = 8
Using the above given formula ,
Required number of diagonals = | ||
2 |
= | = 4 x 5 = 20 | |
2 |
3. If there are drawn ‘m’ horizontal lines and ‘n’ vertical lines in anything then the number of different rectangles formed are
Example 16 :- In a chess board there are 8 vertical and 8 horizontal lines. Find the number of rectangles formed in the chess board.
Sol :- Here , m = 8, n = 8
Required number of rectangles = ^{8}C_{2} × ^{8}C_{2}
Required number of rectangles = | × | |||
2!(8 - 2)! | 2!(8 - 2)! |
= | × | |||
(2 x 1 x 6!) | (2 x 1 x 6!) |
4. These are ‘n’ points in a plane out of which ‘m’ points are collinear. The number of triangles formed by the points as vertices are given by
Example 17 :- There are 12 points in a plane out of which 5 are collinear. Find the number of triangles formed by the points as vertices.
Sol :- Here , m = 5, n = 12
Using the above given formula ,
Required number of triangles =^{12}C_{3} - ^{5}C_{3}
Required number of triangles = | - | |||
3!(12 - 3)! | 3!(5 - 3)! |
= | - | |||
(3 x 2 x 1 x 9!) | (3! x 2 x 1) |
5. There are ‘n’ points in a plane out of which ‘m’ points are collinear. The number of straight lines formed by joining them are given by
Example 18 :- There are 12 points in a plane out of which 5 are collinear. Find the number of lines formed by joining them.
Sol :- Here , m = 5, n = 12
Using the above given formula ,
Required number of lines =^{12}C_{2} - ^{5}C_{2} + 1
Required number of lines = | - | + 1 | ||
2!(12 - 2)! | 2!(5 - 2)! |
= | - | + 1 | ||
(2 × 1 × 10!) | (2 × 1 × 3!) |
6. The number of quadrilaterals that can be formed by joining the vertices of a polygon of n sides are given by
where n > 3 | ||
24 |
Example 19 :- Find the number of quadrilaterals that can be formed with 10 points in a polygon of which no three points are collinear.
Sol :- Here , n = 10
Using the above given formula ,
Required number of quadrilaterals = | ||
24 |
= | = 210 | |
24 |
7. There are n points in a plane and no points are collinear, then the number of straight lines that can be drawn using these ‘n’ points are given by
2 |
Example 20 :- How many straight lines can be drawn with 14 points on a plane of which no points are collinear?
Sol :- Here , n = 14
Using the above given formula ,
Required number of straight lines = | ||
2 |
= | = 45 | |
2 |
8. In a party every person shakes hands with every other person. If there was a total of H handshakes in the party, then the number of persons ‘n’ who were present in the party can be calculated from the equation:
Total number of handshakes ( H )= ^{n} C _{2} = | ||
2 |
Example 21 :- In a party , every person shakes his hand with every other person only once .The total number of handshakes is 15 .How many number of presence persons in a meeting ?
Sol :- Let Number of presence persons in a meeting = n
Using the above given formula,
⇒ | = 15 | |
2 |
⇒ n( n - 1) = 6( 6 - 1 )
⇒ n = 6
∴ n = 6
Hence number of presence persons in a meeting are 6.