Permutation

kumar — Wed, 31 Aug 2011 07:54:58 GMT

Introduction:

Permutation: The ways of arranging or selecting smaller or equal number of persons or objects from a group of persons or objects with regard to the order of arrangement or selection, are called permutations.

In simple words, it means arrangement of things where the order of things is considered.

Let us consider an Example,

We have to form a number consisting of three digits using the digits 1, 2, 3. The total number of

Possible arrangement will be =6 (Factorial 3 ie.3x2x1):

Alternative 1: (1, 2, 3)

Alternative 2: (2, 3, 1)

Alternative 3: (3, 1, 2)

Alternative 4: (1, 3, 2)

Alternative 5: (2, 1, 3)

Alternative 6: (3, 2, 1)

Each one of these possibilities is called permutation of three digits taken all at a time.

Permutations can also be calculated by using the following formula:

ⁿP_r = n (n-1) (n-2)……. (n-r+1)

or ⁿP_r = n! / (n-r)!

Where n = total no. of things

r =things to be chosen

Again, if we have to form a number consisting of two digits using the digits 1, 2, 3. The total number of Possible arrangement following the above formula will be =6

Alternative 1: (1, 2)

Alternative 2: (2, 3)

Alternative 3: (3, 1)

Alternative 4: (1, 3)

Alternative 5: (2, 1)

Alternative 6: (3, 2)

Each one of these possibilities is called permutation of two digits taken at a time.

Fundamental Principles of counting:

(a) Multiplication Rule: If a certain thing can be done in ‘m’ different ways and when it has been done, a second thing can be done in ‘n’ different ways then total number of ways of doing both things simultaneously be = m x n.

(And) = Multiply

E.g. If one can go to school by 5 different buses and then come back by 4 different buses then total number of ways of going to and coming back from school = 5x4 = 20 ways.

(b) Addition Rule: If there are two different jobs which can be done in ‘m’ ways and in ‘n’ ways respectively then either of two jobs can be done in (m + n) ways.

(Or) = Add

E.g. If one wants to go school either by 5 buses or to by auto where there are 4 autos, then total number of ways of going = 5+4 = 20 ways.

Practical Approach:

A) Permutation of things when they all are different: To find the total number of permutation of n different things taken n or r at a time will be:

ⁿP_r = n! / (n-r)!

Ex.1. In how many ways the word "Square” can be arranged taking all at a time.

Ans: Since there is 6 different letters, the number of permutations of choosing all at a time equals

⁶P₆=6x5x4x3x2x1 =720 ways

Ex.2. In how many ways the word "Square” can be arranged taking 3 at a time.

Ans: Since there is 6 different letters, the number of permutations of choosing 3 at a time equals

⁶P₃=6x5x4 =120 ways

B) Permutation of things when they all are not different: To find the total number of permutation of n different things taken all at a time will be:

ⁿP_r = n! / (p)! (q)! (r)!

Ex.1. In how many ways the word "Jalpaiguri” can be arranged taking all at a time.

Ans: Since there is 10 letters where A and I is repeated 2 times, the number of permutations of choosing all at a time equals = 10! / (2)! 2)! = 9, 07,200 ways.

C) Permutation of things which may be repeated: To find the total number of permutation of n different things in which any item can be repeated without restriction, the total number of possible arrangement will be ⁿP_r = n³

The above point will be clear by the following example.

Ex.1. In a quiz competition there are 6 students. In how many ways 1^st, 2^nd and 3^rd prizes can be awarded to 6 students.

Again if there are three prizes, one in quiz, one in sport and one in drawing. In how many ways these prizes can be distributed.

Ans: 1^st case: Since prizes are based on position,

1^st prize can be awarded in 6 ways

2^nd prize can be awarded in 5 ways

3^rd prize can be awarded in 4 ways.

Total no of permutations will be = 120 ways (ⁿP_r)

2^nd case: Since prizes are based on competition, all the prizes can be awarded to same student i.e.

1^st prize can be awarded in 6 ways to 6 students.

2^nd prize can be awarded in 6 ways to 6 students.

3^rd prize can be awarded in 6 ways to 6 students.

Total no of permutations will be: n³= 6³=216 ways

D) Permutation in a ring or in a circle: To find the total number of permutation of n different things in which any item can be repeated without restriction, the total number of possible arrangement will be = (n-1)!

There are three different cases. Consider the following example:

Ex.1. In how many ways can 6 persons be arranged at a round table so that 2 particular persons may sit together?

Ans: Arrangement with respect to table: Taking 2 persons as one person, we are to arrange 5 (=1+4) persons in 5! ways. Again 2 persons may sit amongst themselves in 2! Ways.

Therefore, the reqd. no. of arrangement = 5! X 2! = 240 ways

Arrangement with respect to each other: at first 2 particular persons can be arranged themselves in 2! Ways. Keeping them fixed and taking as one person, all the 5 persons (including remaining 4 persons) can be arranged in (5-1)=4! Ways.

Therefore, the reqd. no. of arrangement = 4! X 2! = 48 ways

Again, Suppose that we have to arrange 6 persons in such a way that no person has the same neighbours in both clockwise and anticlock wise direction, in such a case the required no. of permutations will be = ½*(6-1)! = 60 ways.

E) Restricted Permutation:

a) To find the total number of permutation of n different things taken r at a time in which p particular things never occur is: ^n-pP _r.

Ex.1. In how many ways 10 things can be arranged taking 3 at a time in which 2 particular things never occur?

Ans: n= 10, r=3 and p=2,

Therefore, number of ways = ^n-pP _r=^10-2P₃=⁸P₃=336 ways

b) To find the total number of permutation of n different things taken r at a time in which p particular things occupy stated place is: ^{n –
p}P _{r - p}.

Ex.1. Find the number of different numbers of 3 digits can be formed with the digits 1, 2,3,4,5 in which the unit place is always occupied by 5.

Ans: n= 5, r=3 and p=1,

Therefore, number of ways = ^{n –
p}P_{r - p} =^5-1P_3-1=⁴P₂=12 ways

c) To find the total number of permutation of n different things taken r at a time in which p particular things always present is: ^{(n – p)}P_{(r
– p)} x ^rP_p.

Ex.1. In how many ways 10 things can be arranged taking 3 at a time in which 2 particular things always occur?

Ans: n=10, r=3 and p=2,

Therefore, number of ways = ^n-pP _{r –p} x ^rP_p=^10-2P _{3 –2} x ³P₂

=⁸P ₁ x ³P₂=8 x 3 =24

d) To find the total number of permutation of n different things taken r at a time in which p particular things always occur together in an assigned order is: (r-p+1) x ^{(n – p)}P_{(r – p)} .

Ex.1. Find the number of different numbers of 3 digits can be formed with the digits 1, 2,3,4,5 in which (12) is always together and also in the order given.

Ans: n= 5, r=3 and p=2,

Therefore, number of ways = ⁽r-p+1) x ^{(n – p)} P_{(r – p)} = (3-2+1) x ^{(5 – 2)} P_{(3 – 2)}

= (4) x ⁽³⁾ P₍₁₎

= 4 x 3 = 12 ways

Note: if 12 are not in the order, then the number of ways will be

=12 x 2! = 24 ways

Here 2 are for arrangement of 1and 2 in two ways.

e) To find the total number of permutation of n different things taken all at a time in which p particular things will occur in assigned order is: ⁿP_r= n ! / P!

Ex.1. If the word NOT be arranged with three letters in such a way that O should be placed before T, then what will be the total number of permutations.

=3! / 2! = 3 ways.

(Permutations are NOT, OTN, ONT.)

Dynamictutorials

Permutation