Permutations and Combinations

Combination

Each of the groups or selections which can be made by taking some or all of a number of things without reference to the order of things in each group is called a combination.
For example, choosing two fruits out of a basket containing 4 oranges and 5 bananas - three combinations are possible - two oranges, two bananas or one orange and one banana.

Permutation

Each of the arrangements which can be made by taking some or all of a number of things is called permutation.
For example, the letters of word CAT can be arranged in six different ways
     CAT, CTA, ACT, ATC, TAC, TCA

Sometimes, students may be confused whether combination or permutation is being talked about. Certain key words/phrases can be helpful in deciding.
Combinations: Selection, choose, make group, distribute, committee, geometric problems.
Permutations: Arrangements, standing in a line, seated around a table, problems on digits or letters of a word.

Fundamental Theorem

1. Multiplication Principle (Principle of Association).

If a certain thing can be done in m ways, and if when it has been done, a second thing can be done in n ways, then the total number of ways in which two things can be done is mn.
For example, if there are eight top heroes and 4 top heroines, a film producer can choose from 8 x 4 = 32 pairs.

2. Addition Principle:

If there are two jobs which can be done in m and n ways respectively, then either of two jobs can be done in m + n ways.
For example, if the film producer has limited budget and he can afford either a top hero or a top heroine but not both, then he can choose in 8 +4 = 12 ways.

Illustrative Examples

Example

Three persons enter a railway carriage, where there are 5 vacant seats. In how many ways can they seat themselves?

Solution

First man can sit on any of 5 vacant seats. Then the second can sit on any of 4 vacant seats left. And the third can sit on any of 3 vacant seats left. Hence by fundamental principle of counting, the required number of ways is 5 x 4 x 3 = 60.

Example

How many numbers are there between 100 and 1000 such that

1. every digit is either 2 or 5
2. there is no restriction
3. the digit in the hundreds place is 5
4. atleast one of the digits is 5
5. exactly one of the digits is 5
6. no digit is repeated
7. atleast one digit is repeated
8. the digit in units place is 5?

Solution

The numbers between 100 and 1000 consist of 3 digits - 100 is included and 1000 is excluded.

1. Since every digit is 5 or 2, there are 2 ways of filling up of each of three digits (places). Thus the three digits can be filled in 2 x 2 x 2 = 8 ways. It is easy to see that the eight numbers satisfying giving condition are 222, 225, 252, 255, 522, 525, 552, 555.
2. The first digit has to be non-zero so there are 9 choices. Second and third digits can be any of ten digits 0 to 9. Hence required number of numbers is 9 x 10 x 10 = 900 (including 100 but excluding 1000).
3. Digit in hundreds place is fixed (5). The other two places can each be filled in 10 ways. Hence possible ways are 1 x 10 x 10 = 100. It is easy to see that numbers between 500 and 599 (both inclusive) fulfill given criteria.
4. First, let us find all numbers between 100 and 1000 which do not have digit 5 in any place. The number of such numbers is 8 x 9 x 9 = 648 (including 100). We have also seen in part (ii) that there are 900 numbers between 100 and 100 (including 100). Hence there are 900 -648 = 252 numbers between 100 and 1000 which have at least one digit as 5.
5. The numbers with exactly one digit as 5 are:
   (a) of type 5 x x = 1 x 9 x 9 = 81 (where x is non-five digit)
   (b) of type x 5 x= 8 x 1 x 9 = 72 (first digit is non-zero, non five)
   (c) of the x x 5 = 8 x 9 x 1 = 72
   Thus there are 81 +72 +72 = 225 numbers between 100 and 1000 which have exactly one digit as 5
6. First digit (i.e. hundreds digit) can be anything from 1 to 9; second digit can be then filled in 9 ways, and third digit in 8 ways. Thus number of numbers with no digit repeated is 9 x 9 x 8 = 648.
7. As there are 900 numbers between 100 and 1000 (including 100) and 648 of them have no digit repeated, there are 900 -648 = 252 numbers (including 100) which have at least one digit repeated.
8. The digit in hundreds place can be filled in 9 ways (1 to 9); the digit in tens place can be filled in 10 ways (0 to 9), and digit in units place can be filled in one way only as it is fixed (5). Hence required number of numbers is 9 x 10 = 90.

Exercise

1. There are 12 buses running between Delhi and Agra. In how many ways can a man plan his journey from Delhi to Agra and back? In how many ways can he go from Delhi to Agra and return by a different bus?
2. How many words (with or without meaning) of three English alphabets can be formed? How many of these have all distinct alphabets?
3. In how many ways can 2 prizes (in Science and Maths) be awarded to 15 students? In how many ways can the first and second prize in History be awarded to 15 students?
4. How many different numbers of 3 digits can be formed using only odd digits (i.e. 1, 3, 5, 7, 9)? Using only even digits (0, 2, 4, 6, 8)?
5. There are 4 doors in Lotus temple. In how many ways can a person enter the temple and leave by a different door?
6. There are 20 boys and 20 girls in a class. For staging the play Romeo and Juliet, how many lead pairs are possible? If a shy girl refuses to go on stage, how many pairs are possible?
7. Sandy has 5 shirts, 4 pants, 3 pairs of socks and 2 kinds of shoes. In how many different ways can he dress himself? (He does not know about colour combinations!)
8. Two cards are drawn, one at a time, and without replacement, from a deck of 52 cards. Determine the number of ways in which cards can be drawn. What will be the number of ways if the first card is replaced before the second is drawn?
9. How many orderings of the letters in the word SMILE are possible?
10. For a set of six true or false statements, no student in a class has written all correct answers and no two students in the class have written the same sequence of answers. What is the maximum number of students in the class, for this to be possible?

Answers