## 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! .

n! = 1.2.3.4.5………..( n - 1 ).( n - 1 )
or n! = ( n - 1 ).( n - 2 )………..3.2.1

Ex - 4! = 4 x 3 x 2 x 1 = 24

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 )! = 2n . n![ 1.3.5.7……….( 2n - 1 ) ]

Example 1. Evaluate .

 ( ⅰ ) 15! 13!

 ( ⅱ ) 9! ( 6! x 3! )

 ( ⅲ ) ( 12! + 10! ) 9!

 Sol :- ( ⅰ ) 15! = ( 15 x 14 x 13! ) = 15 x 14 = 210 13! 13!

 ( ⅱ ) 9! = ( 9 x 8 x 7 x 6! ) = 4 x 3 x 7 = 84 ( 6! x 3! ) ( 6! x 3 x 2 )

 ( ⅲ ) ( 12! + 10! ) = ( 12 x 11 x 10 x 9! + 10 x 9! ) 9! 9!

 = 9!(12 x 11 x 10 + 10) = 10(132 + 1 ) = 133 x 10 = 1330 9!

Example 2. Convert into factorials .
( ) 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.5.6.7.8.9.10 = 10! 1.2.3.4 4!

( ) 2.4.6.8.10.12 = ( 2 x 1).( 2 x 2 ).( 2 x 3 ).( 2 x 4 ).( 2 x 5 ).( 2 x 6 )
= ( 2.2.2.2.2.2 ).( 1.2.3.4.5.6) = 26.6!

#### ( 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.

The total number of ways is m + n .

Note: - The above two principles can be extended for any finite number of any event. That is, It can use both theories for more than two events.

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 npr Or P (n, r).

 n P r = n! ( 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! ( 5 - 3 )!

 5 P 3 = 5! 2!

 5 P 3 = ( 5 x 4 x 3 x 2 x 1 ) = 60 ( 2 x 1 )

#### Some Important Results :-

 n P r = n! = 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 = 5! = ( 5 x 4 x 3 x 2 x 1 ) = 120 ( 5 - 4 )! 1!

 ( ⅱ ) 9 P 5 = 9! = ( 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 ) = 15120 ( 9 - 5 )! ( 4 x 3 x 2 x 1 )

 ( ⅲ ) 11 P 3 = 11! = ( 11 x 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 ) = 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, p1 = 3, P2 = 1 and p3 = 2

 ∴ Required number of different arrangement = n! = 8! p1!.p2!.p3! ( 3!.1!.2! )

 = ( 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 ) = 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,

The total number of ways of permutations = nr

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 = 45 = 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

The number of permutations = r⋅ (n - 1) P (r - 1)

( 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 ,

The number of permutations = s!⋅(r - ( s - 1 )) n - s P r - s

( 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 : -

n - 1 P r

( d ) If n different things or objects are taken in such a way all at a time , when m specified things always come together ,Then

The number of permutations = m! × (n - m + 1)!

( e ) Number of permutations of n different things , taken all at a time , when m specific things never come together , then

The number of permutations = n ! - m! × (n - m + 1) !.

#### 5. Cyclic or circular Permutation :-

( a ) Number of cyclic or circular arrangements of n different things = ( n - 1 ) !

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 = ( n - 1 )! 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 = ( 6 - 1 )! = 5! 2 2

 = ( 5 x 4 x 3 x 2 x 1 ) = 60 2

Hence the number of ways is 60 .

#### 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 ncr.

 n C r = n! (0 ≤ r ≤ n) r!( n - r )!

 n C r = n P r r!

 n C r = { n( n - 1 )( n - 2 )……( n - r + 1 ) } { r( r - 1 )( r - 2 ) ……. 3.2.1 }

If r > n then , n C r = 0
For example :- The number of combinations of 4 items out of 6 items is given below:-

 6 C 4 = 6! = ( 6 x 5 x 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 = 10! = 10! 4!( 10 - 4 )! (4! . 6!)

 = ( 10 x 9 x 8 x 7 x 6! ) = 10 x 7 x 3 = 210 ( 4 x 3 x 2 x 1 x 6! )

 ( ⅱ )11 C 8 = 11! = 11! 8!( 11 - 8 )! (3! . 8!)

 = ( 11 x 10 x 9 x 8! ) = 11 x 5 x 3 = 165 ( 3 x 2 x 1 x 8! )

 ( ⅲ )52 C 49 = 52! = 52! 49!( 52 - 49 )! (3! . 49!)

 = (52 x 51 x 50 x 49!) = 26 x 17 x 50 = 22100 (3 x 2 x 1 x 49!)

#### Some Important Properties :-

1.n C r = n C n - r
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

3. If n C x = n C y , then either x = y
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 = ( n - r + 1 ) n C r - 1 r

 Example 12:- Evaluate 10 C 5 10 C 4

Sol :- Here , n = 10 and r = 5
Using the above given property ,

 ∴ 10 C 5 = ( 10 - 5 + 1 ) 10 C 4 5

 = 4 5

5. If n is an even number then the greatest value of n C r is

n C n/2

6. If n is an odd number then the greatest value of n C r is

n C (n + 1)/2 or n C (n - 1)/2

 7. n C r = { n( n - 1 )( n - 2 )……( n - r + 1 ) } { 1.2.3………r }

8. Number of selections of zero or more things out of n different things

n C 0 + n C 1 + n C 2 + ……….+ n C n = 2n

9. Number of combinations of n different things selecting at least one of them is

n C 1 + n C 2 + n C 3 + ……….+ n C n = 2n - 1

10. If r different things are taken from out of the given n things at a time , then the number of combinations

( a ) When p particular things are always included = n - p C r - p

( b ) When p particular things are never included = n - p C r

( c ) When p particular things are not together in any selection = n C r - n - p C r - p

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 ) = 8! 3!.5!

 C ( 8 , 3 ) = (8 x 7 x 6 x 5!) = 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 ) = 8! 6!.2!

 C ( 8 , 6 ) = (8 x 7 x 6!) = 28 (2 x 1 x 6!)

11.( a ) Number of selections of r consecutive things out of n things in a row = n - r + 1.

(b) If r < n , then Number of selections of r consecutive things out of n things along a circle = n

And If r = n , then Number of selections of r consecutive things out of n things along a circle = 1

12.(a) Number of selections of r things (r ≤ n) out of n identical things is 1.

(b) Number of selections of zero or more things out of n identical things = n + 1.

(c) Number of selections of one or more things out of n identical things = n

(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

[ (p + 1) (q + 1) (r + 1) 2t - 1 ].

(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

[ { (p + 1) (q + 1) (r + 1) } - 1 ].

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!

(b) Number of ways of dividing ( m + n + p ) different things in three groups containing m, n and p things, respectively ( m ≠ n ≠ p ) .

 m + n + p C m = ( m + n + p )! 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

 n( n - 1 )( n - 2 ) 6

Example 14 . Find the number of triangles formed by joining the vertices of an hexagon .
Sol:-Here , n = 6
Using the above given formula,

 Required number of triangle = 6( 6 - 1 )( 6 - 2 ) 6

 = (6 x 5 x 4) = 20 6

Hence number of triangle = 20

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 = n( n - 3 ) 2

Example 15 :- How many diagonals are there in a octagon ?
Sol :- Here , n = 8
Using the above given formula ,

 Required number of diagonals = 8( 8 - 3 ) 2

 = (8 x 5) = 4 x 5 = 20 2

Hence number of diagonals is 20 .

3. If there are drawn ‘m’ horizontal lines and ‘n’ vertical lines in anything then the number of different rectangles formed are

( m C 2 × n C 2 )

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 = 8C2 × 8C2

 Required number of rectangles = 8! × 8! 2!(8 - 2)! 2!(8 - 2)!

 = (8 x 7 x 6!) × (8 x 7 x 6!) (2 x 1 x 6!) (2 x 1 x 6!)

Hence Required number of rectangles = 28 x 28 = 784

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

n C 3 - m C 3

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 =12C3 - 5C3

 Required number of triangles = 12! - 5! 3!(12 - 3)! 3!(5 - 3)!

 = (12 x 11 x 10 x 9!) - (5 x 4 x 3!) (3 x 2 x 1 x 9!) (3! x 2 x 1)

Hence Required number of triangles = 220 - 10 = 210

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

n C 2 - m C 2 + 1

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 =12C2 - 5C2 + 1

 Required number of lines = 12! - 5! + 1 2!(12 - 2)! 2!(5 - 2)!

 = (12 × 11 × 10!) - (12 × 11 × 10!) + 1 (2 × 1 × 10!) (2 × 1 × 3!)

Hence required number of lines = 66 - 10 + 1 = 57

6. The number of quadrilaterals that can be formed by joining the vertices of a polygon of n sides are given by

 n( n - 1 )( n - 2 )( n - 3 ) 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 = 10( 10 - 1 )( 10 - 2 )( 10 - 3 ) 24

 = ( 10 x 9 x 8 x 7 ) = 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

 n( n - 1 ) 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 = 10( 10 - 1 ) 2

 = ( 10 x 9 ) = 45 2

Hence required number of straight lines are 45 .

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 = n( n - 1 ) 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,

 ⇒ n( n - 1) = 15 2

⇒ n( n - 1) = 30
⇒ n( n - 1) = 6( 6 - 1 )
⇒ n = 6
∴ n = 6
Hence number of presence persons in a meeting are 6.