Introduction

Let us start with thinking about how to assess the efficiency of a computer programme. For this we would need to estimate the number of times each procedure is called during the execution of the programme. How would we do this? The theory of combinatorics helps us in this matter, as you will see while studying this unit.

Combinatorics deals with counting the number of ways in which objects can be arranged according to some pattern (listing). Mostly, it deals with a finite number of objects and a finite number of ways of arranging them. Sometimes an infinite number of objects and infinite number of ways in which they can be arranged are also considered. However, in this unit and block, we shall restrict our discussion to a finite number of objects.

We start our discussion with two counting principles. These principles help us in counting the number of ways in which a task can be done when it consists of several subtasks, and there are many possible ways of doing the subtasks.

Then we look at arrangements of objects in which the order matters. Such arrangements are called permutations. Here we look at various linear and circular permutations, and how to count their number in a given situation.

Next, we consider arrangements of objects in which the order does not matter. Such arrangements are called combinations. We will consider situations that require us to count combinations. You will see that most of these situations require us to apply the multiplication principle also.

After that, we consider binomial and multinomial coefficients. We see how they are related to the objects studied in previous section.

Finally, we consider the applications of what we have presented in the rest of the unit, for finding the probability of the occurrence of an event. As you will see, this application is natural, since we use similar counting arguments for obtaining discrete probabilities. This discussion will be useful for you, for instance, in coding theory as well as in designing reliable computer systems.

We continue our study of combinatorics in the next unit. We also have a section of miscellaneous exercises at the end of the block of which several are based on this unit. Doing these exercises, and every exercise given in the unit, will help you achieve the following objectives of this unit.

Objectives

After going through this unit, you should be able to:

• explain the multiplication and addition principles, and apply them;
• differentiate between situations involving permutations and those involving combinations;
• perform calculations involving permutations and combinations;
• prove and use formulae involving binomial and multinomial coefficients;
• apply the concepts presented so far for calculating combinatorial probabilities.