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.