CHAPTER 1 - Permutations and Combinations - Fundamental Principle of Counting

This chapter is one of the most interesting chapters that we’ll study at this level. The beauty and challenge of this branch of mathematics lies in the in numerous tricks and mathematical artifices that abound in this subject. Clarity of thought, more than any thing else, is what is required to understand the subject properly. Also, you’d do best if you refrain from memorising any formulae or particular cases here; concentrate on building a logical approach, solving everything from first principle.

The main objective of this chapter is to count. Given a set  of things or objects or persons ( or whatever), we need to arrange a subset  of  (according to some constraints) or select a subset  of  (again, according to certain criteria). In fact, we are actually interested in counting the number of such arrangements or selections. Read the following questions:

“From a team of  cricket players, how can we select a playing team of players?

“There are  people whom we need to seat in  rows of  seats each. How many ways exist of doing so?

“From a deck of  playing cards, in how many ways can we select two red cards and three black cards?”

“How many rectangles exist on a standard  chessboard?”

“How many factors does  have? In general, how many factors does a natural number  have?”

These are some of the many types of questions which we’ll learn to solve in this chapter.

We’ll build a systematic approach to deal with such counting issues. To really appreciate the beauty of the solving techniques that we’ll develop, you are urged to try out each and every question that we solve here, on your own first, and only then look at the solution. Only this approach will help you solve counting questions elegantly.

The fundamental principle of counting is so fundamental that you already must have used it practically a lot many times without realising it. In other words, this principle is already programmed into our minds. A logical, step-by-step application of this principle gives rise to the entire subject of permutations and combinations.

Suppose you have  boys and  girls. From this group of , you want to select a couple ( a boy and a girl). How many ways exist of forming this couple?

Let us label the boys as  and  and the girls as  and .

There are  ways to choose a boy. Once you’ve chosen a boy, say , there are now  ways to choose a girl. In other words, the boy  can form the couple  or . Similarly, for every other boy, there exist  girls with whom that boy can be paired. Thus, the total number of ways in which a pair can be formed is:

The most crucial aspect in this calculation is that you must realise that the task of selecting a boy is independent of the task of selecting a girl. This means that which boy you select has no effect what so ever on which girl you select; the selection of a boy and that of a girl are independent of each other.

Another subtle point must be made here. There are  ways to select a boy. These  ways are mutually exclusive. This means that a selection of any particular boy, once made, rules out the selection of the other  boys. Similarly, there are  mutually exclusive ways to select a girl.

Let us consider another example now. We need to travel from New Delhi, India to Fiji Islands (in the South Pacific Ocean). We must change flights, first at Singapore and then at Sydney, Australia. There are  different flights available from New Delhi to Singapore,  from Singapore to Sydney and  from Sydney to Fiji.

How may ways exist of making a flight plan from New Delhi to Fiji?

Assume that we are in Singapore. From Singapore, we have  available flights to Sydney ( mutually exclusive ways). For each of these  flights, we have further ways (flights) from Sydney to Fiji. Thus, we have a total of ways of travelling from Singapore to Fiji.

Now, how many ways do we have to reach Singapore from New Delhi in the first place?  flights. For each of these  flights, we have  further ways of reaching Fiji From Singapore (as we just calculated in the preceding paragraph). Thus, the total number of ways  of travelling from New Delhi to Fiji is . In other words,

Intuitively easy, isn’t it?

Let us now generalise the results of these two examples into our fundamental principle of counting.

Consider the set of tasks  which are all independent of each other. This means that task  has “no relation ” to task  if  the choice of how to accomplish task  has thus “no effect” on the choice of how to accomplish  talk for , (you’ll realise the meaning of “no relation” and “no effect” more specifically later). Task  can be accomplished in  mutually exclusive ways.

The fundamental principle of counting says that the set of tasks  can be accomplished in  ways.

Here are more examples that illustrate this simple yet extremely powerful principle. A proper understanding of this principle is absolutely essential for the subject of counting to be fully comprehensible.

• Think of a standard six-faced die, with the markings  and . Suppose that you have two such dice. When these two dice are thrown call the number that shows up on the first die  and the one on the second die. How many pairs  are possible?
  There are  mutually exclusive ways in which a number can show up on the first die. Similarly,  such ways exist for the second die. The fundamental principle of counting says that the total number of possible pairs is 
• Suppose that we have a (unlimited) supply of the letters  available with us. How many  letter chains can we form using these letters?
  Imagine  blank spaces for the -letter chain that we are supposed to form (numbered  to ):

• We now have  tasks at hand; each task correspond to filling a space in Fig.. Realise that these  tasks are independent of each other. For example, what you fill in place  has no effect on what you fill in place  since you’ ve been assured an unlimited supply of letters. Each task can be accomplished in 6 possible ways. For example, you can fill place  in possible ways : with . Thus, by the fundamental principle of counting, the total number of ways to form the -letter chain would be .
• Now consider the scenario when you don’t have an unlimited supply of letters available. Suppose that you have only one of each of the  letters available. How many -letter chains can be formed now?
  You must realise that this limited-supply-of-letters situation is very different from the previous one.
  In this situation, once you fill a particular place with a particular letter, you are left with one letter less to choose from, from the remaining places.
  Let us start with filling the places from left to right. To fill place – , w e have  letters to choose from, but once we’ve filled place – , we now have only  letters to choose from, to fill place – . Continuing in this way, place – , place –  and place –  can then be filled in  and  ways respectively.
  
  The fundamental principle of counting tells us that the total number of chains in this case will be . You might think that in this case filling up place –  and place –  are not independent tasks. In other words, how we fill place- has a certain relation to how we fill place – . For example, if we fill place- with , we cannot fill any other place with  and thus, how we fill place –  has a definite effect on how we are able to fill the other places. This is definitely true. But when we talk about the independence of two events, it is in a different sense:

Let event  be filling place- and event  be filling place- after event  has been accomplished, i.e. after place- has been filled. There are  ways of accomplishing  and  ways of accomplishing . Which  letters contribute to event  (i.e which of the  remaining letters can we choose for place -) definitely depends on how event  was accomplished, but the event  is itself the choice of one of the  symbols contributing to event . The number of ways in which this choice can be made is still independent of how event  was accomplished. Whatever selection was made for event , the number of ways in which  can be accomplished still remains . This is the sense that should be attached to the phrase “independent events”.

These three examples should have given you a pretty good idea about three concepts : mutually exclusive events, independent events and the fundamental principle of counting. Ponder over these examples for a bit longer and think up examples of you own till your feel very comfortable with these new concepts.