Formula - Permutation,Combination & Probability


INTRODUCTION

Factorial : The important mathematical term “Factorial” has extensively used in this chapter.

The product of first n consecutive natural numbers is defined as factorial of n. It is denoted by n! or \(\lfloor n\).Therefore,

n! = 1 × 2 × 3 ×....× (n - 1) × n

For example, 5! = 5 × 4 × 3 × 2 × 1 = 120

\(\frac{n!}{r!} \neq \left( \frac{n}{r}\right )! \)

0! = 1

The factorials of fractions and negative integers are not defined.

Example 1

1. Prove that n! + 1 is not divisible by any natural number between 2 and ‘n’.

Sol. Since n! = 1 . 2 .3 .4 …..(n – 1) .n

Therefore n! is divisible by any number from 2 to ‘n’.

Consequently n! + 1, when divided by any number between 2 and ‘n’ leaves 1 as remainder.

Hence, n! + 1 is not divisible by any number between 2 and’n’.

FUNDAMENTAL PRINCIPLES OF COUNTING

1. Principle of Addition : If an event can occur in 'm' ways and another event can occur in 'n' ways independent of the first event, then either of the two events can occur in (m + n)ways.

2. Principle of Multiplication : If an operation can be performed in 'm' ways and after it has been performed in anyone of these ways, a second operation can be performed in 'n' ways, then the two operations in succession can be performed in (m × n) ways.

Example 2

2. In a class there are 10 boys and 8 girls. The class teacher wants to select a student for monitor of the class.In how many ways the class teacher can make this selection ?

Sol. The teacher can select a student for monitor in two exclusive ways

(i) Select a boy among 10 boys, which can be done in 10 ways OR

(ii) Select a girl among 8 girls, which can be done in 8 ways.

Hence, by the fundamental principle of addition, either a boy or a girl can be selected in 10 + 8 = 18 ways.

Example 3

3. In a class there are 10 boys and 8 girls. The teacher wants to select a boy and a girl to represent the class in a function.In how many ways can the teacher make this selection?

Sol. The teacher has to perform two jobs :

(i) To select a boy among 10 boys, which can be done in 10 ways.

(ii) To select a girl, among 8 girls, which can be done in 8 ways.

Hence, the required number of ways = 10 × 8 = 80.

Example 4

4. There are 6 multiple choice questions in an examination. How many sequences of answers are possible, if the first three questions have 4 choices each and the next three have 5 choices each?

Sol. Each of the first three questions can be answered in 4 ways and each of the next three questions can be answered in 5 different ways.

Hence, the required number of different sequences of answers = 4 × 4 × 4 × 5 × 5 × 5 = 8000.

Example 5

5. Five persons entered a lift cabin on the ground floor of an 8-floor house. Suppose that each of them can leave the cabin independently at any floor beginning with the first. What is the total number of ways in which each of the five persons can leave the cabin at any of the 7 floors?

Sol. Any one of the 5 persons can leave the cabin in 7 ways independent of other.

Hence the required number of ways = 7 × 7 × 7 × 7 × 7 = 75.

Method of Sampling : Sampling process can be divided into following forms :

1. The order is IMPORTANT and the repetition is ALLOWED,each sample is then a SEQUENCE.

2. The order is IMPORTANT and the repetition is NOT ALLOWED, each sample is then a PERMUTATION.

3. The order is NOT IMPORTANT and repetition is ALLOWED, each sample is then a MULTISET.

4. The order is NOT IMPORTANT and repetition is NOT ALLOWED, each sample is then a COMBINATION.

PERMUTATION

Each of the arrangements, which can be made by taking, some or all of a number of things is called a PERMUTATION.

For Example : Formation of numbers, word formation, sitting arrangement in a row.

The number of permutations of 'n' things taken 'r' at a time is denoted by nPr. It is define as, nPr = \(\frac{n!}{\left ( n - r \right )!}\)

nPn = n!

Circular permutations:

(i) Arrangements round a circular table :

Consider five persons A, B, C, D and E to be seated on the circumference of a circular table in order (which has no head). Now, shifting A, B, C, D and E one position in anticlockwise direction we will get arrangements as follows:

11

we see that arrangements in all figures are same.

∴ The number of circular permutations of n different things taken all at a time is nPnn = (n - 1)!if clockwise and anticlockwise orders are taken as different.

(ii) Arrangements of beads or flowers (all different) around a circular necklace or garland:

Consider five beads A, B, C, D and E in a necklace or five flowers A, B, C and D, E in a garland etc. If the necklace or garland on the left is turned over we obtain the arrangement on the right, i.e., anticlockwise and clockwise order of arrangements are not different.

Thus the number of circular permutations of ‘n’ different things taken.

1

all at a time is ½(n – 1)!, if clockwise and anticlockwise orders are taken to be some.

Example 6

6. Prove that nPr = n – 1Pr + r.n – 1Pr – 1

Sol.

n – 1Pr + rn – 1Pr – 1 = \(\frac{\left ( n ? 1 \right )!}{\left ( n ? 1 ? r \right )!} + r\frac{\left ( n ? 1 \right )!}{\left ( n ? 1 ? r + 1\right )!}\)

= \(\left ( n ? 1 \right )!\left \{ \frac{1}{\left ( n ? 1 ? r\right )!} + \frac{r}{\left ( n ? r \right )!} \right \}\)

= \(\left ( n ? 1 \right )!\left \{\frac{n ? r + r}{\left ( n ? r \right )!} \right \} = \frac{n!}{\left ( n ? r \right )!}\) = nPr

Example 7

7. Prove that nPr = (n – r + 1)nPr – 1

Sol. We have

(n – r + 1)nPr – 1 = (n – r + 1)\(\frac{n!}{\left ( n ? r + 1\right )!}\)

= (n – r + 1)\(\frac{n!}{\left ( n ? r + 1\right )\left ( n ? r \right )!}\)

= \(\frac{n!}{\left ( n ? r \right )!}\) = nPr

Example 8

8. The number of four digit numbers with distinct digits is :

(a) 9 × 9C3

(b) 9 × 9P3

(c) 10C3

(d) 10P3

Sol.(b) The thousandth place can be filled up in 9 ways with any one of the digits 1, 2, 3, …., 9. After that the other three places can be filled up in 9C3 ways, with any one of the remaining 9 digits including zero. Hence, the number of four digit numbers with distinct digits = 9 × 9P3.

Example 9

9. The number of ways in which 10 persons can sit round a circular table so that none of them has the same neighbours in any two arrangements.

Sol. 10 persons can sit round a circular table in 9! ways. But here clockwise and anticlockwise orders will give the same neighbours. Hence the required number of ways = ½ 9!

Example 10

10. In how many different ways can five boys and five girls form a circle such that the boys and girls are alternate?

2

Sol. After fixing up one boy on the table the remaining can be arranged in 4! ways.

There will be 5 places, one place each between two boys which can be filled by 5 girls in 5! ways.

Hence by the principle of multiplication, the required number of ways = 4! × 5! = 2880.

Example 11

11. In how many ways can 5 boys and 5 girls be seated at a round table no two girls may be together ?

Sol. Leaving one seat vacant between two boys may be seated in 4! ways. Then at remaining 5 seats, 5 girls any sit in 5!ways. Hence the required number = 4! × 5!

Conditional Permutations

1. Number of permutations of n things taking r at a time, in which a particular thing always occurs = r.n - 1Pr - 1.

Distinguishable Permutations

Suppose a set of n objects has n1 of one kind of object, n2 of a second kind, n3 of a third kind, and so on, with n = n1 + n2 + n3 + . . . + nk, Then the number of distinguishable permutations of the n objects is \(\frac{n!}{n_{1}!n_{2}!n_{3}!...n_{k}!}\)

Example 12

12. In how many distinguishable ways can the letters in BANANA be written?

Sol. This word has six letters, of which three are A’s, two are N’s,and one is a B. Thus, the number of distinguishable ways the letters can be written is

\(\frac{6!}{3!2!1!} = \frac{6 \times 5 \times 4 \times 3!}{3!2!} = 60\)
Example 13

13. How many 4 digits number (repetition is not allowed) can be made by using digits 1 – 7 if 4 will always be there in the number?

Sol. Total digits (n) = 7

Total ways of making the number if 4 is always there

= r × n – 1Pr – 1 = 4 × 6P3 = 480.

2. Number of permutations of n things taking r at a time, in which a particular thing never occurs = n - 1Pr.

Example 14

14. How many different 3 letter words can be made by 5 vowels, if vowel ‘A’ will never be included?

Sol. Total letters (n) = 5

So total number of ways = n – 1Pr = 5 – 1P3 = 4P3 = 24

3. Number of permutations of n different things taking all at a time, in which m specified things always come together = m!(n – m + 1)!

4. Number of permutations of n different things taking all at a time, in which m specified things never come together = n! – m!(n – m + 1)!

Example 15

15. In how many ways can we arrange the five vowels, a, e, i, o & u if :

(i) two of the vowels e and i are always together.
(ii) two of the vowels e and i are never together.

Sol. (i) Using the formula m!(n – m + 1)!

Here n = 5, m = 2(e & i)

=> Required no. of ways = 2!(5 –2 + 1)! = 2 × 4! = 48

Alternative :

As the two vowels e & i are always together we can consider them as one, which can be arranged among themselves in 2! ways.

Further the 4 vowels (after considering e & i as one) can be arranged in 4! ways.

Total no. of ways = 2! × 4! = 48

(ii) No. of ways when e & i are never together = total no. of ways of arranging the 5 vowels – no. of ways when e & i are together = 5! – 48 = 72

Or use n! – m!(n – m+ 1)! = 5! – 48 = 72

5.The number of permutations of ‘n’ things taken all at a time,when ‘p’ are a like of one kind, ‘q’ are a like of second, ‘r’ a like of third, and so on = \(\frac{n!}{p!q!r!}.\)

Example 16

16. How many different words can be formed with the letters of the world MISSISSIPPI.

Sol.In the word MISSISSIPPI, there are 4 I’s, 4 S’s and 2 P’s.Thus required number of words = \(\frac{\left ( 11 \right )!}{4!2!4!} = 34650\)

6.The number of permutations of ‘n’ different things, taking ‘r’at a time, when each thing can be repeated ‘r’ times = nr

Example 17

17. In how many ways can 5 prizes be given away to 4 boys,when each boy is eligible for all the prizes?

Sol. Any one of the prizes can be given in 4 ways; then any one of the remaining 4 prizes can be given again in 4 ways, since it may even be obtained by the boy who has already received a prize.

Hence 5 prizes can be given 4 × 4 × 4 × 4 × 4 = 45 ways.

Example 18

18. How many numbers of 3 digits can be formed with the digits 1, 2, 3, 4, 5 when digits may be repeated?

Sol. The unit place can be filled in 5 ways and since the repetitions of digits are allowed, therefore, tenth place can be filled in 5 ways.

Furthermore, the hundredth place can be filled in 5 ways also.

Therefore, required number of three digit numbers is 5 × 5 × 5 = 125.

Example 19

19. In how many ways 8 persons can be arranged in a circle?

Sol. The eight persons can be arranged in a circle in (8 – 1)! = 7! = 5040.

Example 20

20. Find the number of ways in which 18 different beads can be arranged to form a necklace.

Sol. 18 different beads can be arranged among themselves in a circular order in (18 – 1)! = 17! ways. Now in the case of necklace there is no distinct between clockwise and anticlockwise arrangements. So, the required number of arrangements = ½(17!) = 17!2

COMBINATION

Each of the different selections that can be made with a given number of objects taken some or all of them at a time is called a COMBINATION.

The number of combinations of 'n' dissimilar things taken 'r' at a time is denoted by nCr or C(n, r).It is defined as,

nCr = \(\frac{n!}{r!\left ( n - r \right )!}\)

Example 21

21. If nPr = nPr + 1 and nCr = nCr – 1 then the values of n and r are

(a) 4, 3
(b) 3, 2
(c) 4, 2
(d) None of these

Sol.(b) We have, nPr = nPr + 1

=> \(\frac{n!}{\left ( n ? r \right )!} = \frac{n!}{\left(n ? r ? 1\right)!} \Rightarrow \frac{1}{\left ( n ? r \right )} = 1\)

or n – r = 1 …(1)

Also, nCr = nCr – 1 => r + r – 1 = n => 2r – n = 1 ….(2)

Solving (1) and (2), we get r = 2 and n = 3

Example 22

22. Prove that

nCr – 2 + 3.nCr – 1 + 3.nCr + nCr + 1 = n + 2Cr + 2

sol.

nCr – 2 + 3.nCr – 1 + 3.nCr + nCr + 1

= nCr – 2 + nCr – 1 + 2(nCr – 1 + nCr) + (nCr + nCr + 1)

= n + 1Cr – 1 + 2.n + 1Cr + n + 1Cr + 1

= (n + 1Cr – 1 + n + 1Cr) + (n + 1Cr + n + 1Cr + 1)

= n + 2Cr + n + 2Cr + 1 = n + 3Cr + 1

Example 23

23. If nPr = 720 nCr, then r is equal to

(a) 3
(b) 7
(c) 6
(d) 4

Sol.(c) nPr = 720nCr

or \(\frac{n!}{\left ( n ? r \right )!} = \frac{720(n!)}{\left(n ? r\right)!r!}\)

=> r! = 720 = 1 × 2 × 3 × 4 × 5 × 6!

or r = 6

Example 24

24. In how many ways a hockey team of eleven can be elected from 16 players?

Sol. Total number of ways = 16C11 = \(\frac{16!}{11! \times 5!}\) = 4368.

= \(\frac{16 \times 15 \times 14 \times 13 \times 12}{5 \times 4 \times 3 \times 2 \times 1} = 4368.\)

REMEMBER
nC0 = 1, nCn = 1; nPr = r!nCr

nCr = nCn – r

nCr – 1 + nCr = n + 1Cr

nCx = nCy => x + y = n

nCr = nCr + 1 = n + 1Cr

nCr = nr.n – 1Pr – 1

nCr = 1r(n – r + 1)nr – 1

nC1 = nCn – 1 = n

Conditional Combinations

1. Number of combinations of n distinct things taking r(≤n) at a time, when k (0 ≤ k ≤ r) particular objects always occur
= n - kCr - k.

2. Number of combinations of n distinct objects taking r(≤n) at a time, when k (0 ≤ k ≤ r) particular objects never occur
= n - kCr.

3. Number of selections of r things from n things when p particular things are not together in any selection
= nCr - n - pCr - p

4. Number of selection of r consecutive things out of n things in a row = n – r + 1

5. Number of selection of r consecutive things out of n things along a circle

3

6. The number of Combinations of 'n' different things taking some or all at a time

= nC1 + nC2 + nC3 + ..... + nCn = 2n - 1

Example 25

25. In a class of 25 students, find the total number of ways to select two representative,

(i) if a particular person will never be selected.

(ii) if a particular person is always there.

Sol.(i) Total students (n) = 25

A particular students will not be selected (p) = 1,

So total number of ways = 25 – 1C2 = 24C2 = 276

(ii) Using n – pCr – p no. of ways = 25 – 1C2 – 1 = 24C1 = 24.

NOTE : If a person is always there then we have to select only 1 from the remaining 25 – 1 = 24
Example 26

26. There are 10 lamps in a hall. Each of them can be switched on independently. The number of ways in which the hall can be illuminated is

(a) 102
(b) 1023
(c) 210
(d) 10 !

Sol. Since each bulb has two choices, either switched on or off,therefore required number = 210 – 1 = 1023.

7. The number of ways of dividing 'm + n' things into two groups containing 'm' and 'n' things respectively

= m + nCm nCn = \(\frac{\left ( m + n \right )!}{m!n!}\)

8. The number of ways of dividing ‘m + n + p’ things into three groups containing ‘m’, ‘n’ and ‘p’ things respectively

= m + n + pCm.n + pCp = \(\frac{\left ( m + n + p\right )!}{m!n!p!}\)

(i) If m = n = p ie. '3m' things are divided into three equal groups then the number of combinations is

\(\frac{\left ( 3m \right )!}{m!m!m!3!} = \frac{\left ( 3m \right )!}{(m!)^{3}3!}\)

(ii) Buf if '3m' things are to be divided among three persons,then the number of divisions is \(\frac{\left ( 3m \right )!}{(m!)^{3}}\)

9.If mn distinct objects are to be divided into m groups. Then,the number of combination is \(\frac{\left ( mn \right )!}{m!(n!)^{m}}\) when the order of groups is not important and \(\frac{\left ( mn \right )!}{(n!)^{m}}\) whenthe order of groups is important

Example 27

27. The number of ways in which 52 cards can be divided into 4 sets, three of them having 17 cards each and the fourth one having just one card

(a) \(\frac{52!}{\left ( 17! \right )^{3}}\)

(b) \(\frac{52!}{\left ( 17! \right )^{3}3!}\)

(c) \(\frac{51!}{\left ( 17! \right )^{3}}\)

(d) \(\frac{51!}{\left ( 17! \right )^{3}3!}\)

Sol. Here we have to divide 52 cards into 4 sets, three of them having 17 cards each and the fourth one having just one card. First we divide 52 cards into two groups of 1 card and 51 cards. this can be done in \(\frac{52!}{1!51!}\) ways.

Now every group of 51 cards can be divided into 3 groups of 17 each in \(\frac{51!}{\left ( 17! \right )^{3}3!}\).

Hence the required number of ways

= \(\frac{52!}{1!51!}.\frac{51!}{\left ( 17! \right )^{3}3!} = \frac{52!}{\left ( 17! \right )^{3}3!}\)

NUMBER OF RECTANGLES AND SQUARES

(a) Number of rectangles of any size in a square of size n × n is \(\sum_{r = 1}^{n} r^{3}\) and number of squares of any size is \(\sum_{r = 1}^{n} r^{2}\).

(b) Number of rectangles of any size in a rectangle size n × p (n < p) is np4 (n + 1) (p + 1) and number of squares of any size is \(\sum_{r = 1}^{n}\) (n + 1 - r)(p + 1 - r)

Example 28

28. The number of squares that can be formed on a chessboard is

(a) 64
(b) 160
(c) 224
(d) 204

Sol.(d) A chessboard is made up of 9 equispaced horizontal and vertical line. To make a 1 × 1 square, we must choose two consecutive horizontal and vertical lines from among these. This can be done in 8 × 8 = 82 ways. A 2 × 2 square needs three consecutive horizontal and vertical lines, and we can do this in 7 × 7 = 72 ways.

Continuing in this manner, the total number of square is

82 + 72 + 62 + …. + 22 + 12 = \(\frac{8\left ( 8 + 1 \right )\left [ \left ( 2 \times 8 \right ) + 1 \right ]}{6} = 204.\)