**Permutation and Combination**

**Permutation**: Permutation means arrangement of things. The word arrangement is used, if the order of things

__is considered__.

**Combination**: Combination means selection of things. The word selection is used, when the order of things has

__no importance__.

**Example:**Suppose we have to form a number of consisting of three digits using the digits 1,2,3,4, To form this number the digits have to be arranged. Different numbers will get formed depending upon the order in which we arrange the digits. This is an example of Permutation.

Now suppose that we have to make a team of 11 players out of 20 players, This is an example of combination, because the order of players in the team will not result in a change in the team. No matter in which order we list out the players the team will remain the same! For a different team to be formed at least one player will have to be changed.

Now let us look at two fundamental principles of counting:

**Addition rule**: If an experiment can be performed in ‘*n*‘ ways, & another experiment can be performed in m ways then either of the two experiments can be performed in (m+n) ways. This rule can be extended to any finite number of experiments.

**Example:** Suppose there are 3 doors in a room, 2 on one side and 1 on other side. A man want to go out from the room. Obviously he has 3 options for it. He can come out by door A or door B or door C.

**Multiplication Rule**: If a work can be done in m ways, another work can be done in ‘

*n*‘ ways, then both of the operations can be performed in m×n ways. It can be extended to any finite number of operations.

**Example:**Suppose a man wants to cross-out a room, which has 2 doors on one side and 1 door on other site. He has 2×1=2 ways for it.

Factorial

*n*: The product of first ‘

*n*‘ natural numbers is denoted by n!.

n!=

*n*(

*n*-1)(

*n*-2)∙…∙3∙2∙1

Ex. 5!=5×4×3×2×1=120

Note 0!=1

**Permutation**

Number of permutations of ‘*n*‘ different things taken ‘*r*‘ at a time is given by

Proof: Say we have ‘

*n*‘ different things.

Clearly the first place can be filled up in ‘

*n*‘ ways. Number of things left after filling-up the first place =

*n*-1.

So the second-place can be filled-up in (

*n*-1) ways. Now number of things left after filling-up the first and second places =

*n*-2

Now the third place can be filled-up in (

*n*-2) ways.

Thus number of ways of filling-up first-place =

*n*

Number of ways of filling-up second-place =

*n*-1

Number of ways of filling-up third-place =

*n*-2

Number of ways of filling-up

*r*-th place =

*n*-(

*r*-1)=

*n*–

*r*+1

By multiplication – rule of counting, total number of ways of filling up, first, second, … ,

*r*-th place together:

*n*(

*n*-1)(

*n*-2)·…·(

*n*–

*r*+1)

Hence:

Number of permutations of ‘

*n*‘ different things taken all at a time is given by

^{n}P

_{n}=

*n*!

Proof:

Now we have ‘

*n*‘ objects, and

*n*-places.

Number of ways of filling-up first-place =

*n*

Number of ways of filling-up second-place =

*n*-1

Number of ways of filling-up third-place =

*n*-2

Number of ways of filling-up

*r*-th place, i.e. last place =1

Number of ways of filling-up first, second, …,

*n*-th place

*n*(

*n*-1)(

*n*-2)·…·3·2·1

^{n}P

_{n}=

*n*!

**Concept**: We have

Putting

*r*=

*n*, we have

^{n}P

_{n}=

*n*!/0!

But

^{n}P

_{n}=

*n*!

Clearly it is possible, only when 0!=1. Hence it is proof that 0!=1.

Note: Factorial of negative-number is not defined. The expression (–1)! has no meaning.

**Examples:**

Q1. How many different signals can be made by 5 flags from 8 flags of different colours?

Ans.: Number of ways taking 5 flags out of 8 flags =^{8}P_{5}.

Q2. How many words can be made by using the letters of the word “SIMPLETON” taken all at a time?

Ans.: There are 9 different letters of the word “SIMPLETON”

Number of permutations taking all the letters at a time =

^{9}P

_{9}=9!=362880.

Number of permutations of *n*-thing, taken all at a time, in which *p* are of one type, *q* of them are of second-type, ‘*r*‘ of them are of third-type, and rest are all different is given by

**Example:**In how many ways can the letters of the word “Pre-University” be arranged?

Ans.: There are 2e, 2i, 2r, each other letter is only one of the word.

Number of permutations of

*n*-things, taken ‘

*r*‘ at a time when each thing can be repeated

*r*-times is given by =

*n*

^{r}.

Proof.

Number of ways of filling-up first-place =

*n*

Since repetition is allowed, so

Number of ways of filling-up second-place =

*n*

Number of ways of filling-up third-place

Number of ways of filling-up

*r*-th place =

*n*

Hence total number of ways in which first, second,…,

*r*-th, places can be filled-up

=

*n*×n×n×… ‘

*r*‘ factors.

=

*n*

^{r}

**Example:**A child has 3 pocket and 4 coins. In how many ways can he put the coins in his pocket.

Ans.: First coin can be put in 3 ways, similarly second, third and forth coins also can be put in 3 ways.

So total number of ways =3×3×3×3=3

^{4=81}.

Circular Permutations

There are two cases of circular-permutations:

(a) If clockwise and anti clock-wise orders are different, then total number of circular-permutations is given by (*n*-1)!

(b) If clock-wise and anti-clock-wise orders are taken as not different, then total number of circular-permutations is given by ((*n*-1!))⁄2!

Note: Number of circular-permutations of ‘

*n*‘ different things taken ‘

*r*‘ at a time:

(a) If clock-wise and anti-clockwise orders are taken as different, then total number of circular-permutations =

^{n}P

_{r}⁄r

(b) If clock-wise and anti-clockwise orders are taken as not different, then total number of circular – permutation =

^{n}P

_{r}⁄2r

**Example:** How many necklace of 12 beads each can be made from 18 beads of different colours?

Ans.: Here clock-wise and anti-clockwise arrangements are same.

Hence total number of circular–permutations:

Restricted – Permutations

**Example:**How many words can be formed with the letters of the word ‘OMEGA’ when:

(i) ‘O’ and ‘A’ occupying end places.

(ii) ‘E’ being always in the middle

(iii) Vowels occupying odd-places

(iv) Vowels being never together.

Ans.:

(i) When ‘O’ and ‘A’ occupying end-places

⇒ M.E.G. (OA)

Here (OA) are fixed, hence M, E, G can be arranged in 3! ways

But (O,A) can be arranged themselves is 2! ways.

⇒ Total number of words =3!×2!=12 ways.

(ii) When ‘E’ is fixed in the middle

⇒ O.M.(E).G.A.

Hence four-letter O.M.G.A. can be arranged in 4! i.e 24 ways.

(iii) Three vowels (O,E,A,) can be arranged in the odd-places (1st, 3rd and 5th) =3! ways.

And two consonants (M,G,) can be arranged in the even-place (2nd, 4th)=2 ! ways

⇒ Total number of ways =3!×2!=12 ways.

(iv) Total number of words =5!=120!

If all the vowels come together, then we have: (O.E.A).M.G

These can be arranged in 3! ways.

But (O,E.A.) can be arranged themselves in 3! ways.

⇒ Number of ways, when vowels come-together =3!×3!

=36 ways

⇒ Number of ways, when vowels being never-together

=120-36=84 ways.

**Combination**

Number of Combination of ‘*n*‘ different things, taken ‘*r*‘ at a time is given by

Restricted – Combinations

**Example:**In how many ways can a cricket-eleven be chosen out of 15 players? if

(i) A particular player is always chosen,

(ii) A particular is never chosen.

Ans:

(i) A particular player is always chosen, it means that 10 players are selected out of the remaining 14 players. Required number of ways

(ii) A particular players is never chosen, it means that 11 players are selected out of 14 players.

⇒ Required number of ways

Number of ways of selecting one or more things from ‘

*n*‘ different things is given by 2

^{n-1}. Proof: Total number of subsets of a set by excluding empty subset equals 2

^{n-1}.

**Example:**John has 8 friends. In how many ways can he invite one or more of them to dinner?

Ans.: John can select one or more than one of his 8 friends.

⇒ Required number of ways =28–1=255.