Permutations and Combination.
This is one of the most interesting chapters in JEE preparation.I will try to keep it simple since I intend to write this for beginners.
Basically, this chapter is about counting. Let’s start our discussion with principles of counting. Suppose you have a total of 15 chapters in physics, 28 in math, and 25 in chemistry for your JEE syllabus. If someone asks you that if you have to study one topic now, how many choices do you have? It’s simple right? You will just add the number of chapters and answer the question. It’s 68. This is what we call as the rule of sum. Let us put it in a mathematical way. Say you have task 1, which can be performed in m ways. You have another task. Task 2! It can be performed in n ways. Now the condition is that you need to perform one of the task. But both can’t be performed simultaneously. So, this can be done in m plus n ways.
Now let’s say you are fed up of all this mathematics and you decide to go on a vacation. You go to an agent. He tells you that there is no direct mode of transport to the place where you want to go. First you need to reach a nearby town by either a train or a flight. From there, you can either take a bus or a taxi or a rickshaw to reach your destination. So, how many choices do you have in total? These six choices, right. This is what we call as the rule of product. This says that if task one and two are steps of a procedure, then the procedure can be carried out in m into n ways.
I’ll show you the use of these principles in solving problems. Look at this example. We need to make a three digit even number. How many such numbers can we make? Here we have our number. Our task is to fill these three blanks. This first blank can be filled by any number from 1 to 9. So the task of filling the first blank can be done in 9 ways. Moving to second blank. Here we can even fill zero. So the task of filling the second blank can be done in 10 ways. Now comes the most important task. Filling the third blank! In order to make this number even, the last digit needs to be even. So this blank can be filled with either zero, two, four, six or eight. So, the third task can be done in 5 ways. Now we can apply our rule of product. The total number of three digit even numbers are 9 into 10 into 5, that is 450.
Let’s take another example. The task is to make four letter words with the letters L, A, T, E. The words don’t need to make sense. But remember, no letter must be repeated. So we again have four blanks. The first one can be filled with any letter. So the task of filling first blank can be done in four ways. Now, to fill the next blank, we have one less of a choice as we have used one letter to fill the first blank. So the task of filling this blank can be done in three ways. Similarly, filling this blank can be done in two ways and this can be done in only one way. So total number of four letter words that can be formed using these letters without repeating them is 4 into 3 into 2 into 1. That is 24. I think you are starting to get it.
Moving to our next example. Here, our friend Ram has a party. He invited 9 of his friends. If all of them have to shake hands with each other, how many total handshakes need to be done? Let’s say Ram starts shaking hands with each of his friends. So, he will shake hands with 9 friends. Now, if his first friend comes next to shake hands with the others in the party, he needs to shake hands with just 8 people. Who is the one with whom he doesn’t need to shake hands? It’s Ram. Ram has already shook hands with him. Similarly, next friend needs to shake hands with just 7 others. The last one will not need to shake hands with anyone as all would have already shook hands with him. So, total number of handshakes will be 9 plus 8 plus 7 plus so on upto 1. That is 45.
Let’s take one more example. Find the total number of 7 digit numbers in which no two consecutive digits are same. So, we have the 7 blanks. First can be filled in 9 ways. Any number other than zero. Suppose it is filled with 3. So, for the next blank, the options will be all numbers from zero to 9 other than 3. That is 9 options. Again, for the next blank also we will have 9 options, leaving the one which was filled in the second blank. So, every blank can be filled in 9 ways. So, total number of such 7 digit numbers is 9 to the power 7.
I assume you all have seen a chess board. Our next question is about that. We have to find the number of ways of selecting two small squares on a chess board such that they are not in the same row or same column. This is how a chess board looks like. It has 64 small squares on it. 32 black, and 32 white. So, we have to pick our first small square. We can pick anyone. So, the first square can be picked in 64 ways. Say we pick this one. Now, we cannot pick the second one from this row and this column. So, for picking the second one, we have 15 less choices. So, total number of ways is 64 into 64 minus 15.
I think that’s enough on the principles of counting. Now, we will discuss about factorial notation. This is going to be very useful in all the later concepts of this chapter. It is defined only for non-negative integers. Factorial of a non-negative integer n is denoted like this or this. It is defined as the product of first n natural numbers. So, if we say 4 factorial, it means 1 into 2 into 3 into 4. That is 24. Similarly, n factorial is written as n into n minus 1 into n minus 2 so on upto 1. What about 0 factorial? Zero factorial is defined as 1, same as 1 factorial.
Let’s start with a very interesting property of the factorial notation. We can find the exponent of a prime number in the prime factorization of a factorial. But before that, we need to discuss about the greatest integer function. It is denoted by square brackets. What does it do? By definition, GIF of x gives the greatest integer less than or equal to x. For example, GIF of 2 point 3 is 2. Gif of 7 is 7. GIF of minus 9.8 is minus 10.
So, I think we are ready to use it. Suppose we want to find the exponent of 3 in the prime factorization of 100 factorial. Watch the process carefully. The exponent is given by, GIF of 100 upon 3, plus GIF of 100 upon 3 square, plus GIF of 100 upon 3 cube, and so on until the terms start becoming zero. Like in this case, GIF of 100 upon 3 to the power 5 becomes zero. So, this sum gives us the exponent of 3 in the prime factorization of 100 factorial. This comes out to be 48.
This process can be used to solve very interesting questions. Like, suppose we want to find the number of zeroes at the end of 100 factorial. It means we need to find the exponent of 10 in 100 factorial. But 10 is not prime. But its factors 2 and 5 are. Let’s find the exponent of 2 and 5. They are 97 and 24 respectively. 2 power 97 into 5 power 24 equals 10 power 24 into 5 power 83. Thus the exponent of 10 here is 24. The answer is 24.
It’s time for you to try out some questions on your own now.