Permutations

A permutation is an arrangement of some elements in which order matters. In other words a Permutation is an ordered Combination of elements.

Examples

· From a set S ={x, y, z} by taking two at a time, all permutations are −

xy,yx,xz,zx,yz,zyxy,yx,xz,zx,yz,zy.

· We have to form a permutation of three digit numbers from a set of numbers S={1,2,3}S={1,2,3}. Different three digit numbers will be formed when we arrange the digits. The permutation will be = 123, 132, 213, 231, 312, 321

Number of Permutations

The number of permutations of ‘n’ different things taken ‘r’ at a time is denoted by nPrnPr

nPr=n!(n−r)!nPr=n!(n−r)!

where n!=1.2.3.…(n−1).nn!=1.2.3.…(n−1).n

Proof − Let there be ‘n’ different elements.

There are n number of ways to fill up the first place. After filling the first place (n-1) number of elements is left. Hence, there are (n-1) ways to fill up the second place. After filling the first and second place, (n-2) number of elements is left. Hence, there are (n-2) ways to fill up the third place. We can now generalize the number of ways to fill up r-th place as [n – (r–1)] = n–r+1

So, the total no. of ways to fill up from first place up to r-th-place −

nPr=n(n−1)(n−2).....(n−r+1)nPr=n(n−1)(n−2).....(n−r+1)

=[n(n−1)(n−2)...(n−r+1)][(n−r)(n−r−1)…3.2.1]/[(n−r)(n−r−1)…3.2.1]=[n(n−1)(n−2)...(n−r+1)][(n−r)(n−r−1)…3.2.1]/[(n−r)(n−r−1)…3.2.1]

Hence,

nPr=n!/(n−r)!nPr=n!/(n−r)!

Some important formulas of permutation

· If there are n elements of which a1a1 are alike of some kind, a2a2 are alike of another kind; a3a3 are alike of third kind and so on and arar are of rthrth kind, where (a1+a2+...ar)=n(a1+a2+...ar)=n.

Then, number of permutations of these n objects is = n!/[(a1!(a2!)…(ar!)]n!/[(a1!(a2!)…(ar!)].

· Number of permutations of n distinct elements taking n elements at a time = nPn=n!nPn=n!

· The number of permutations of n dissimilar elements taking r elements at a time, when x particular things always occupy definite places = n−xpr−xn−xpr−x

· The number of permutations of n dissimilar elements when r specified things always come together is − r!(n−r+1)!r!(n−r+1)!

· The number of permutations of n dissimilar elements when r specified things never come together is − n!–[r!(n−r+1)!]n!–[r!(n−r+1)!]

· The number of circular permutations of n different elements taken x elements at time = npx/xnpx/x

· The number of circular permutations of n different things = npn/nnpn/n

Some Problems

Problem 1 − From a bunch of 6 different cards, how many ways we can permute it?

Solution − As we are taking 6 cards at a time from a deck of 6 cards, the permutation will be 6P6=6!=7206P6=6!=720

Problem 2 − In how many ways can the letters of the word 'READER' be arranged?

Solution − There are 6 letters word (2 E, 1 A, 1D and 2R.) in the word 'READER'.

The permutation will be =6!/[(2!)(1!)(1!)(2!)]=180.=6!/[(2!)(1!)(1!)(2!)]=180.

Problem 3 − In how ways can the letters of the word 'ORANGE' be arranged so that the consonants occupy only the even positions?

Solution − There are 3 vowels and 3 consonants in the word 'ORANGE'. Number of ways of arranging the consonants among themselves =3P3=3!=6=3P3=3!=6. The remaining 3 vacant places will be filled up by 3 vowels in 3P3=3!=63P3=3!=6 ways. Hence, the total number of permutation is 6×6=366×6=36

Combinations

A combination is selection of some given elements in which order does not matter.

The number of all combinations of n things, taken r at a time is −

nCr=n!r!(n−r)!nCr=n!r!(n−r)!

Problem 1

Find the number of subsets of the set {1,2,3,4,5,6}{1,2,3,4,5,6} having 3 elements.

Solution

The cardinality of the set is 6 and we have to choose 3 elements from the set. Here, the ordering does not matter. Hence, the number of subsets will be 6C3=206C3=20.

Problem 2

There are 6 men and 5 women in a room. In how many ways we can choose 3 men and 2 women from the room?

Solution

The number of ways to choose 3 men from 6 men is 6C36C3 and the number of ways to choose 2 women from 5 women is 5C25C2

Hence, the total number of ways is − 6C3×5C2=20×10=2006C3×5C2=20×10=200

Problem 3

How many ways can you choose 3 distinct groups of 3 students from total 9 students?

Solution

Let us number the groups as 1, 2 and 3

For choosing 3 students for 1^st group, the number of ways − 9C39C3

The number of ways for choosing 3 students for 2^nd group after choosing 1st group − 6C36C3

The number of ways for choosing 3 students for 3^rd group after choosing 1^st and 2^nd group − 3C33C3

Hence, the total number of ways =9C3×6C3×3C3=84×20×1=1680=9C3×6C3×3C3=84×20×1=1680