# Difference Between Permutation and Combination

In combination we are concerned only with the number of things n each selection whereas in permutation we also consider the order of things which makes each arrangement different The symbol P_{r}, denotes the number of permutations of n different things taken r at a time, whereas ^{n}C_{r} denotes the number of combinations of n different things taken r at a time.

**Enquiry:** How can we find the number of ways of selection n things taken r at a time, when their order also matters?

This can be done by finding the number of permutations of n different things taken r at a time (n > r) or to find the value of ^{n}P_{r}.

This is same as finding the number of ways in which we can fill up r places when we have n different things at our disposal. The first place may be filled up in n-ways, because we may take any one of the n things. When it has been filled up in any one of these ways, the second place can then be filled up in (n - 1) ways, and since each way of filling up the first place can be associated with each way of filling up the second, the number of ways in which the first two places can be filled up is given by the product n(n - 1) ways, And when the first two places have been filled up in any way, the third place can be filled up in (n - 2) ways. And reasoning as before, the number of ways in which three places can be filled up is n(n - 1)(n - 2).

Proceeding thus, and noticing that a new factor is introduced with each new place filled up, and that at any stage the number of factors is the same as the number of places filled up, we shall have the number of ways in which r places can be filled up, we shall have the number of ways in which r places can be filled up equal to n(n - 1)(n - 2) ......... to r factor, and the rth factor is n - (r - 1), or n - r + 1. Therefore the number of permutations of n things taken r at a time is

^{n}P_{r} = n(n - 1)(n - 2)......(n - r + 1).

# Restricted Selection and Arrangement

(a) The number of ways in which r objects can be selected form n different objects if k particular objects are

(i) always included = ^{n-k}C_{r-k}.

(ii) never included = ^{n-k}C_{r}.

(b)The number of arrangement of n distinct objects taken r at a time so that k particular objects are

(i) always included = ^{n-k}C_{r-k}.r!,

(ii) never included = ^{n-k}C_{r}.r!.

A delegation of four students is to be selected form a total of 12 students. In how many ways can the delegation be selected if

(a) all the students are equally willing.

(b) two particular students have to be included in the delegation.

(c) two particular students do not wish to be together in the delegation.

(d) two particular students wish to be included together only,

(e) two particular students refuse to be together and two other particular student wish to be together only in the delegation.

(a) Formation of delegation means selection of 4 out of 12. Hence the number of ways = ^{12}C_{4} = 495.

(b) Two particular students are already selected. Hence we need to select 2 out of the remaining 10. Hence the number of ways = ^{10}C_{2} = 45.

(c) The number of ways in which both are selected = 45. Hence the number of ways in which the two are not included together = 495 - 45 = 450.

(d) There are two possible cases

(i) Either both are selected. In this case the number of ways in which this selection can be made = 45.

or

(ii) both are selected. In this case all the four students are selected from the rest of ten students.

This can be done in ^{10}C_{4} = 210 ways.

Hence the total number of ways of selection = 45 + 210 = 255.

(e) We assume that students A and B wish to be selected together and students C and D do not wish to be together. Now there are following 6 cases.

(i) (A, B, C) selected (D) not selected

(ii) (A, B, D) selected (C) not selected

(iii) (A, B) selected (C, D) not selected

(iv) (C) selected (A, B, D) not selected

(v) (D) selected (A, B, C) not selected

(vi) A, B, C, D not selected

For (i) the number of ways selection = ^{8}C_{1} = 8

For (ii) the number of ways selection = ^{8}C_{1} = 8

For (iii) the number of ways selection = ^{8}C_{2} = 28

For (iv) the number of ways selection = ^{8}C_{3} = 56

For (v) the number of ways selection = ^{8}C_{3} = 56

For (vi) the number of ways selection = ^{8}C_{4} = 70

Hence, total number of ways = 8 + 8 + 28 + 56 + 56 + 70 = 226.

Some results related to ^{n}C_{r}

(i) ^{n}C_{r} = ^{n}C_{n-r}

(ii) If ^{n}C_{r} = ^{n}C_{k}, then r = k or n-r = k

(iii) ^{n}C_{r} + ^{n}C_{r-1} = ^{n+1}C_{r}

(iv) ^{n}C_{r} = n/r ^{n-1}C_{r-1}

(v)

(vi) (a) If n is even ^{n}C_{r} is greatest for r = n/2

(b) If n is odd, is greatest for r = (n-1)/2,(n+1)/2

(a) How many diagonals are there in as n-sided polygon (n > 3?

(b) How many triangles can be formed by joining the vertices of an

n-sided polygon?

How many these triangles have

(i) exactly one side common with that of the polygon?

(ii) exactly two sides common with that of the polygon?

(iii) no side common with that of the polygon?

(a) Number of lines formed by joining the vertices of a polygon

= number of selection of 2 points each selected from the given n points

= ^{n}C_{2} = (n(n-1)!)/2.1 .

Out of ^{n}C_{2} lines, n are the sides of the polygon.

Hence the number of diagonals = ^{n}C_{2-n} = ((n(n-1))/2) - n = (n(n-3))/2 .

(b) Number of triangles formed by joining the vertices of the polygon = number of selection of 3 points from n points.

^{n}C_{3} = (n(n-1)(n-2))/3.2.1 .

Let the vertices of the polygon be marked as A_{1}, A_{2}, A_{3}, ......, A_{n}.

(i) Select two consecutive vertices A_{1}, A_{2} of the polygon. For the required triangles we can select the third vertex from the A_{4}, A_{5}, ..., A_{n-1}. This can be done in ^{n-4}C_{1} ways. Also two consecutive points (end points of a side of polygon) can beselected in n ways.

(ii) For the required triangle, we have to select three consecutive vertices of the polygon. i.e. (A_{1} A_{2} A_{3}), (A_{2} A_{3} A_{4}) (A_{3} A_{4}A_{5}) ... (A_{n} A_{1} A_{2}). This can be done in n ways.

(iii) Triangle having no side common + triangle having exactly one side common + triangle having exactly two sides common

(with those of the polygon) = Total number triangles formed

=> Triangle having no side common with those of the polygon.

= ^{n}C_{3} - n(n - 4) - n = ((n(n-1)(n-2))/6) -n(n - 4) - n.

= n/6 [n^{2} + 3n + 2 - 6n + 24 - 6] = [n^{2} + 9 + 20] = (n(n-4)(n-5))/6.

# All possible selections

**(i) Selection from distinct objects :**

The number of selections from n different objects, taking at least one = ^{n}C_{1} + ^{n}C_{2} +^{n}C_{3} + ... + ^{n}C_{n} = 2^{n} - 1.

In other words, for every object we have two choices, either select or reject in a particular group. Total number of choice (all possible selections) = 2.2.2. ...n times = 2^{n}. But this also includes the case when none is selected. And the number of such cases is 2^{n} - 1.

(ii) Selection from identical objects:

(a) The number of selections of r objects out of n identical objects is 1.

(b) Total number of selections of zero or more objects from n identical objects is n+1.

(c) The total number of selections of at least one out of a_{1} + a_{2} + a_{3} + ...... + an objects, where a_{1} are alike (of one kind), a_{2} are alike (of second kind) and so on ...... a_{n} are alike (of nth kind), is

[(a_{1} + 1)(a_{2} + 1)(a_{3} + 1).........(a_{n} + 1)] - 1.

In how many ways can a person having 3 coins of 25 paise, 4 coins of 50 paise and 2 coins of 1 rupee give none or some coins to a beggar?

The person has 3 coins of 25 paise, 4 coins of 50 paise and 2 coins of 1 rupee.

The number of ways in which he can give none or some coins to a beggar is (3 + 1)(4 + 1)(2 + 1) = 60 ways.

**(iv) (a) Total number of divisor's of a given natural number**

To find the number of factors of a given natural number greater than 1 we can write n as , where p_{1}, p_{2}, ......, p_{n} are distinct prime numbers and Î±_{1}, Î±_{2} ...... Î±_{n} are non-negative integers. Now any divisor of n will be of the form d = ; here number of factors will be equal to numbers of ways in which we can choose Î²_{1}s' which can be done in (Î±_{1} + 1)(Î±_{2} + 1)......(Î±_{n}+ 1) ways.

Sum of all the divisors of n is given by

**(b)The exponent of a prime number p _{1}**

**in n =**

**is given by**

How many positive factors are there of the number 360 and find the sum of all these factors.

Let n = 360 = 23.32.5

=> No. of factors of 360 = (3 + 1)(2 + 1)(1 + 1) = 24.

Sum of all the factors =((2^{4}-1)/1) . ((3^{2}-1)/2) . ((5^{2}-1)/4) = 15. 13. 6 = 1170.