Permutations and Combinations, Objectives, Fundamental Principle of Counting, Permutations

Glide to success with Doorsteptutor material for ISS : fully solved questions with step-by-step explanation- practice your way to success.

Download PDF of This Page (Size: 132K)

  • One day, I wanted to travel from Bangalore to Allahabad by train. There is no direct train from Bangalore to Allahabad, but there are trains from Bangalore to Itarsi and from Itarsi to Allahabad. From the railway timetable I found that there are two trains from Bangalore to Itarsi and three trains from Itarsi to Allahabad. Now, in how many ways can I travel from Bangalore to Allahabad?

  • There are counting problems which come under the branch of Mathematics called combinatory.

  • In this lesson we shall consider simple counting methods and use them in solving such simple counting problems.

Objectives

After studying this lesson, you will be able to:

  • Find out the number of ways in which a given number of objects can be arranged

  • State the Fundamental Principle of Counting

  • Define and evaluate it for different values of

  • State that permutation is an arrangement and write the meaning of

  • State that and apply this to solve problems

  • Show that

  • State that a combination is a selection and write the meaning of

  • Distinguish between permutations and combinations

  • Derive and apply the result to solve problems

  • Derive the relation

  • Verify that and give its interpretation

  • Derive and apply the result to solve problems.

Fundamental Principle of Counting

  • Let us now solve the problem mentioned in the introduction. We will write to denote trains from Bangalore to Itarsi and for the trains from Itarsi to Allahabad. Suppose I take to travel from Bangalore to Itarsi. Then from Itarsi I can take or or .

  • So the possibilities are and where denotes travel from Bangalore to Itarsi by and travel from Itarsi to Allahabad by . Similarly, if I take to travel from Bangalore to Itarsi, then the possibilities are and . Thus, in all there are possible ways of travelling from Bangalore to Allahabad.

  • Here we had a small number of trains and thus could list all possibilities. Had there been trains from Bangalore to Itarsi and trains from Itarsi to Allahabad, the task would have been very tedious. Here the Fundamental Principle of Counting or simply the Counting Principle comes in use:

  • If any event can occur in ways and after it happens in any one of these ways, a second event can occur in ways, then both the events together can occur in ways.

Example:

How many multiples of are there from to ?

Solution:

As you know, multiples of are integers having or in the digit to the extreme right

(i.e. the unit’s place).

The first digit from the right can be chosen in ways.

The second digit can be any one of

i.e. There are choices for the second digit.

Thus, there are multiples of from to.

Permutations

  • Suppose you want to arrange your books on a shelf. If you have only one book, there is only one way of arranging it. Suppose you have two books, one of History and one of Geography.

  • You can arrange the Geography and History books in two ways. Geography book first and the History book next, GH or History book first and Geography book next; HG. In other words, there are two arrangements of the two books.

  • Now, suppose you want to add a Mathematics book also to the shelf. After arranging History and Geography books in one of the two ways, say GH, you can put Mathematics book in one of the following ways: MGH, GMH or GHM. Similarly, corresponding to HG, you have three other ways of arranging the books. So, by the Counting Principle, you can arrange Mathematics, Geography and History books in ways ways.

  • By permutation we mean an arrangement of objects in a particular order. In the above example, we were discussing the number of permutations of one book or two books.

  • In general, if you want to find the number of permutations of n objects , how can you do it? Let us see if we can find an answer to this.

  • Similar to what we saw in the case of books, there is one permutation of object, permutations of two objects and permutations of 3 objects. It may be that, there are permutations of objects. In fact, it is so, as you will see when we prove the following result.

Theorem 1:

The total number of permutations of n objects is .

Proof:

We have to find the number of possible arrangements of different objects.

The first place in an arrangement can be filled in n different ways. Once it has been done, the second place can be filled by any of the remaining objects and so this can be done in ways. Similarly, once the first two places have been filled, the third can be filled in ways and so on. The last place in the arrangement can be filled only in one way, because in this case we are left with only one object.

Using the counting principle, the total number of arrangements of n different objects is

The product occurs so often in Mathematics that it deserves a name and notation. It is usually denoted by (or by read as factorial).

Here is an example to help you familiarise yourself with this notation.

Example:

Evaluate (a) (b)

Solution:

(a)

(b) ,

Therefore,

Notice that satisfies the relation,

This is because,

Of course, the above relation is valid only for because has not been defined so far. Let us see if we can define to be consistent with the relation. In fact, if we define then the relation holds for also.

Developed by: