# Permutation Computation

Permutation means arrangement of things. The word arrangement indicates that the order of things is considered.

In mathematics, Permutation refers to the act of arranging all the members of a set into some sequence or order, or if the set is already ordered, rearranging (reordering) its elements

For example, the anagram of a word having all different letters, is permutation of letters. In the original word, the letters are already ordered.

For the set {1,2,3}, there are six possible permutation, namely: (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), and (3,2,1)

Permutation is the number of  ways of arranging or selecting smaller or equal number of persons or objects from a group of persons or collection of objects considering the order of arrangement or selection.

Factorial

The factorial function n (written as |n or  n! ), represents the product of the series of  integers from 1 to n both inclusive.

Thus, n! = n(n − 1)  (n − 2)  ………..3.2.1

Characteristics of Factorial

i) 0!=1, ii) n! is defined only for positive integers, iii) n!=n ´ (n-1)!

Ex. 1: 3! = 3 X 2 X 1 = 6 ; Ex. 2:  4! = 4 X 3 X 2 X 1 = 24; Ex 3: 6! = 6 X 5 X 4 X 3 X 2 X 1= 720.

Ex 4.Compute (32!) / (28!) = {(32x31x30x29)} x28!] / 28! = (32x31x30x29) = 863040.

# Permutation Formula

Permutation Formula

The number of possible arrangements are is denoted by npr, where P stands for permutation, n is the given number of things and ‘r’ is the number of things taken at a time.

For example 5p2 denotes number of permutation or arrangement of 5 objects taken 2 at a time. $\displaystyle ^{n}{{P}_{r}}=\left[ {\frac{{\left( {n!} \right)}}{{(n-r)!}}} \right]$

Circular Permutation

When the objects are arranged in a closed curve (no starting or no end), such arrangement or permutation is known as circular permutation.

For example, for 4 items a,b,c,d, the arrangement abcd, dabc, cdab, bcda are same in circular combination, where there is no start or end positions. So, these 4 linear permutations are equivalent to 1 in circular permutation. Hence, there are nPn /n ways or (n-1)! ways in circular permutation. This is like fix up one position and then arrange the rest (n-1) in (n-1)! ways.

Ex: A Board meeting is attended by 6 directors sitting in chairs in a circle. In how many ways can they arrange themselves ?

Fix up one position and arrange the remaining five about him. Possible number of arrangements  5! = 5 x 4 x 3 x 2. = 120 ways

Permutation with Restrictions

Rule 1 : Number of Permutation of n distinct objects taken r at a time, when a particular object is not taken is  n-1Pr

Since the particular object is always excluded, we have n-1 distinct tings to choose from. So, the permutations are n-1Pr

Rule 2: Number of Permutation of n distinct objects taken r at a time, when a particular object is  always taken is r(n-1Pr-1).

If the particular object is first placed, from remaining n-1 objects, r-1 objects can be selected in n-1Pr-1 ways. Similarly, placing the particular object in 2nd, 3rd … upto rth place, we have n-1Pr-1 Permutations. So, the total permutations are  r( n-1Pr-1)

# Permutation – Problems

Permutation – Problems and Solution

Ex 1: Two executives enter in a meeting room where there are seven chairs in a line, find in how many ways can they take their seats.

Number of ways = nPr  . Here  n=7, r=2, So, the number of permutation $\displaystyle {{=}^{7}}{{P}_{2}}=\text{ }\frac{{\left( {7!} \right)}}{{\left( {5!} \right)}}=\frac{{\left( {7\times 6} \right)\times 5!}}{{5!}}=7\times 6=42.$

Ex.2 : In how many ways can the letters of the word DAUGHTER be arranged so that the vowels may never be separated ?

As vowels must be together (never separated), consider the 3 vowels (AUE) as one letter. Considering the 3 vowels as one letter, we have only 6 letters D,G,H,T,R (AUE) to arrange. Here the number of arrangements keeping the vowels together = 6P6 = 6! = (6x5x4x3x2) = 720

Again the vowels (while keeping them together), ay be arranged in 3P3 ways, i.e in 3! ways, i.e in (3×2) ways, i.e in 6 ways

So, combining both the permutations, the word can be arranged in 720 x 6 = 4320 ways

Ex. 3: How many different words can be made out of the letters of the word MATHEMATICS? In how many of these will the vowels always come together?

Step 1 : Number of different words: There are 11 letters in the word  MATHEMATICS.  In non-vowels (consonants), M, A, T are repeating twice. So, the possible permutations are $\displaystyle \left[ {\frac{{\left( {11!} \right)}}{{\left( {2!\times 2!\times 2!} \right)}}} \right]=\frac{{\left( {11!} \right)}}{8}$

= 39916800/8= 49,89,600

Step 2 : Number of different words with vowels together : The number of permutations in which vowels would come together $\displaystyle =\text{ }\left[ {8!\div \left( {2!\text{ }2!} \right)} \right]\times \left( {\frac{{4!}}{2}} \right)$ $\displaystyle =\left[ {\frac{{\left( {8\times 7!} \right)}}{{\left( {2\times 2\times 2} \right)}}} \right]\times \left[ {\frac{{\left( {4!} \right)}}{{2x}}} \right]$

= (7!)x (4!) = 5040 x 24=1,20,960 (There are 11 letters, 8 distinct and 3 repeating twice. There are 4 vowels, with repeating 2 A’s)

# Permutation – Problems

Permutation – Problems and Solution

Ex 1: Six boys and five girls are to be seated for a photograph in a row such that no two girls sit together and no two boys sit together. Find the number of ways in which this can be done.

Step 1 : We have 11 persons in a row and we want the 6 boys and 5 girls to be seated such that no two girls and no two boys are together. If we number the positions from left to right, the arrangement will be possible if and only if boys occupy the odd places and girls occupy the even places in the row.

Step 2 : The six odd places from 1 to 11 may filled in by 6 boys in 6P6 ways.

Five even places from 2 to 10 may be filled in by 5 girls in 5P5 ways.

Step 3 : Hence, the total number of required arrangements = 6P6 X 5P5 =

6! X 5! = 720 X 120 = 86400.

# Permutation – Problems

Permutation – Problems and Solution

Ex 1:In how many ways can the letter of the word ‘balloon’ be arranged, so that two l’s do not come together ?

There are 7 letters in the word balloon, of which the letter l  and o are repeated 2 times each

So the no. of arrangements without restriction $\displaystyle \frac{{\left( {7!} \right)}}{{\left( {2!\times 2!} \right)}}=1260$

Considering 2 l’s as one letter, we have only 6 letters, arrangement  may be done in (6!) / (2!) = 360 ways

So, the reqd. arrangement, in which 2 l’s do not come together = 1260 – 360 = 900.

# Combination

Combination Formula

Combination is the number of ways in which smaller or equal number of things are arranged or selected from a collection of things, where the order of selection or arrangement is not Important

The expression of Combination is denoted by nCr where C is the number of combination, n is number of objects, r is the number of things taken at a time nC= [(n!) / {r! x (n-r)!}]

Ex 12C4  = [12! / {(12-4) ! x 4!}] = [(12!) / {(8!) X (4!)}] = [{(12x11x10x9x8!)} / {(8!) x (4!)}]

= (12x11x10x9) / (4x3x2) = 495

Characteristics of Combination

(i) nCn =1, (ii) nC0 = 1, (iii) nCr =nCnr , (iv) nC1 = n (v) n+1Cr=ncr+nCr-1

# Combination – Problems

Combination – Problems and Solution

Ex 1: A committee of 7 members is to be chosen from 7 company secretaries (CS), 4 lawyers (L)  and 6 Engineers (E). In how many ways can this be done if in the committee to have at least one member from each group and at least 3 company secretaries?

Possible Methods of Combination

Method 1 : 3 CS, 2L, 2 E= 7C3 x4C2 x5C $\displaystyle =\left[ {\frac{{(7\times 6\times 5)}}{{(3\times 2)}}} \right]\times \left( {\frac{{\left( {4\times 3} \right)}}{2}} \right)\text{ }\times ~\left[ {\frac{{\left( {5\times 4} \right)}}{2}} \right]=2100$

Method 2 : 4 CS, 2L, 1 E= 7C4 x4C2 x5C $\displaystyle =\left[ {\frac{{(7\times 6\times 5)}}{{(3\times 2)}}} \right]\times \left( {\frac{{\left( {4\times 3} \right)}}{2}} \right)\text{ }\times ~\left( 5 \right)=1050$

Method 3 : 4 CS, 1L, 2 E= 7C4 x4C1 x5C $\displaystyle =\left[ {\frac{{(7\times 6\times 5)}}{{(3\times 2)}}} \right]\times \left( 4 \right)\times ~\left[ {\frac{{\left( {5\times 4} \right)}}{2}} \right]=1400$

Method 4 : 5 CS, 1L, 1 E= 7C5 x4C1 x5C $\displaystyle =\frac{{\left( {7\times 6\times 5\times 4} \right)}}{2}=420$

Method 5 : 3 CS, 3L, 1 E= 7C3 x4C3 x5C $\displaystyle =\left[ {\frac{{(7\times 6\times 5)}}{{(3\times 2)}}} \right]\times \left( {\frac{{\left( {4\times 3\times 2} \right)}}{{3\times 2}}} \right)\text{ }\times ~5=700$

Method 6 : 3 CS, 1L, 3 E= 7C3 x4C1 x5C $\displaystyle =\left[ {\frac{{(7\times 6\times 5)}}{{(3\times 2)}}} \right]\times \left( 4 \right)\times ~\left[ {\frac{{\left( {5\times 4} \right)}}{2}} \right]=1400$

Therefore, total number of ways = 2,100 + 1,050 + 1,400 + 420 + 700 + 1,400 = 7070 ways.

# Combination – Problems

Combination – Problems and Solution

Ex 1: How many different cricket teams of 7 players may be formed from 8 batsmen and 5 bowlers members ?

Combination of  7 players from 8 Batsmen and 5 Bowlers

Team 1 : Batsmen (7) Bowlers (0) =  8C7 X 5C0 = 8×1 = 8

Team 2 : Batsmen (6) Bowlers (1) =  8C6 X 5C1 = 28×5= 140

Team 3 : Batsmen (5) Bowlers (2) =  8C5 X 5C2 = 560

Team 4 : Batsmen (4) Bowlers (3) =  8C4 X 5C3 = 700

Team 5 : Batsmen (3) Bowlers (4) =  8C3 X 5C4 = 280

Team 6 : Batsmen (2) Bowlers (5) =  8C2 X 5C5 = 28

Different cricket teams can be formed in

( 8 + 140 + 560 + 700 + 280 + 28 ) = 1716 ways

# Combination – Problems

Combination – Problems and Solution

Ex 1: From 7 teachers (T) and 4 office staff (S), a group of 5 is to be formed. In how many ways can this be done to include at least one office staff ?

1 office staff can be selected out of 4 office staff  in 4C1 ways and 4 teachers can be selected from 7 teachers in 7C4 ways. Now each way of selecting office staff can be associated with each way of selecting teachers. So 1 office staff and 4 teachers can be selected in 4C1 X 7C4 ways.

Combination of a group of 5 of 5 Teachers / Staff

Group 1 : S1 + T4= 4C1 X 7C4 ways = 4×35 = 140

Group 2 : S2 + T3= 4C2 X 7C3 ways = 6x 35 = 210

Group 3 : S3 + T2= 4C3 X 7C2 ways = 4×21 = 84

Group 4 : S4 + T1= 4C4 X 7C1 ways = 1×7 = 7

So, the groups can be formed in 140 + 210 + 84 + 7 = 441 ways

# Combination – Problems

Combination – Problems and Solution

Ex.1 If nP4 : nP5=1:4 Compute the value of n.

nP4 : nP5 =1 : 4.

Step 1 : So [{n(n – 1 )(n -2) (n-3 )} / {n(n – 1 )(n – 2) (n – 3 )(n – 4)}] = 1/4 $\displaystyle \mathbf{Step}\text{ }\mathbf{2}:Or,\text{ }\frac{1}{{\left( {n-4} \right)}}=\frac{1}{4}.$
Or , n-4 =4, or n= 4+4 = 8

Ex 2: If  nC 10 = nC15 Compute the value of 28Cn.

Step 1nC 10  =  nC14,  or nC 10  =  nCn-14

So, 10=n-14, n=24

Step 2 : 28Cn =28C24 = 28C28 24   =28C4 $\displaystyle =\frac{{(28\times 27\times 26\times 25)}}{{(1\times 2\times 3\times 4)}}=20475$

Ex 3: A firm wishes to simultaneously promote two of its 6 department heads to assistant managers. In how many ways these promotions can take place?

The promotion of candidates do not matter in which order they are done.
So, it can be done in $\displaystyle ^{6}{{C}_{2}}=\frac{{\left( {6\times \times 5} \right)}}{2}=\text{1}5\text{ }ways$

Ex. 4 : A Company needs 2 engineers from 9 men applying for the post. In how many ways can these selections take place?

The selection of candidates do not matter in which order they are taken. Hence, the company can select in any of 9C2 ways $\displaystyle =~\frac{{\left( {9\times 8} \right)}}{{\left( {2\times 1} \right)}}=36\text{ }ways.~$

To see PDF