In the last article, we have tried to solve some combinatorics problems from our own intiuition. It’s all how you use multiplication and addition. We saw why n! gives us the number of ways to arrange n distinct objects.

We also developed a notion of filling vacant spaces. This idea of filling vacant spaces along with multiplication rule is really powerful and this is exactly where ^n P_r comes from. ^n P_r gives us the number of ways to arrange r objects from n objects. Today we are going to look at a bunch of different problems with the idea of filling vacant spaces.

Q1. How many 4 digit numbers can be formed using the digits 0, 1, 2, 3, 4 (without repetition)?

Let’s take 4 vacant spaces. We can’t put 0 in the first place, since it’ll make a 4 digit number. So, there are 4 options for the first digit. Once we have used 1 digit, we’ve 4 digits left. So in the second place, we have 4 options. Now we’ve 3 digits left, so for the third place we have 3 options and so on.

   4      4      3      2   

So, the number of ways are 4 \times 4 \times 3 \times 2 = 96. The same calculation can also be done with ^n p_r. The first cell has 4 options and once you filled that you have 4 digits and you need 3 more digits to make it a 4 digit number. The number ways you can form of 3 digits using 4 digits are ^4P_{3}. So, the total ways are = 4 \times ^4P_{3} = 96.

There is another approach for this. If there were no 0, the answer would be ^5P_4. But in this case, ^5P_4 is wrong, because there are some wrong cases starting with 0. If we can calculate the number of wrong cases then we can substract that from ^5P_4 to get our answer. Try yourself to find the number of wrong cases.

Q2. How many 4 digit numbers can be formed using the digits 1, 2, 3, 4, 5 (repetition allowed)?

Let’s take 4 vacant spaces. Notice that repetition is allowed, so we’ll always have 5 options. So, all the 4 digits will have 5 options each. We are not reducing options, since repetition is allowed. For example 5555 will be a valid 4 digit number and we have to count it, according to the problem.

   5      5      5      5   

So, the number of ways are 5 \times 5 \times 5 \times 5 = 5^4.

Q3. How many 4 digit numbers can be formed using the digits 0, 1, 2, 3, 4 (repetition allowed)?

First take 4 vacane spaces. Notice, if we place 0 at the first cell it is not going to be a 5 digit number. So in the first place, we can put 4 digits. For all the other cells, there’ll be 5 options.

   4      5      5      5   

So, the number of ways are 4 \times 5 \times 5 \times 5 = 4 \times 5^3

Q4. How many 4 digit numbers divisible by 4 can be formed using the digits 0, 1, 2, 3, 4 (without repetition)?

We know that if when the sum of the last two digits of a number is divisible by 4, that whole number is divisible by 4. So Let’s pick the last 2 digits and write it down in the cells.

Let’s pick the last 2 digits 0, 4 (marked as red). We already used 2 digits and have 3 digits left. So in the first and the second cell have 3 and 2 options respectively. Total ways are 3 \times 2.

   3      2      0      4   

Simillarly pick the last 2 digits 1, 2 (marked as gray). We already used 2 digits and have 3 digits left. Notice for the first place we have 2 options, since we can’t put a 0 there. Once we pick that, we’ll have 2 options for the second place. Total ways are 2 \times 2.

   2      2      1      2   

Simillarly the other 4 ways of putting last 2 digits divisible by 4 are,

   3      2      2      0   
   2      2      2      4   
   2      2      3      2   
   3      2      4      0   

The total number of ways = (3 \times 2) + (2 \times 2)+ (3 \times 2) + (2 \times 2) + (2 \times 2) + (3 \times 2) = (6 \times 3) + (3 \times 4) = 18 + 12 = 30.

Q5. How many 4 digit numbers can be formed using the digits 0, 1, 2, 3, 4 (without repetition) such that even places are occupied by even numbers and odd places are occupied by odd numbers.

Let’s take 4 vacant spaces. The first cell is odd and we have 2 odd digits. So we have 2 options. Simillarly, for the second cell we have 3 options and so one. You get the idea. The number of ways are = 2 \times 3 \times 1 \times 2 = 12.

   2      3      1      2   

Q6. In a train 3 seats are vacant. In how many ways can 5 passengers sit?

From now we are going to use the ^n p_r formula, wherever we can. We know ^n p_r tells us the number of ways we can arrange r objects out of n distinct objects. So, the answer is simply.
^5 p_3 = \frac{5!}{(5 – 3)!} = 60

Q7. How many 4 letter words be created using the letters of the word MONKEY (words can be meaningless)?

^5 p_4 = \frac{5!}{(5 – 4)!} = 120

Q8. How many different words can be formed using all the letters of the word STICK?

^5 p_5 = \frac{5!}{(5 – 5)!} = 120

Q9. How many numbers of 5 digits can be formed from the numbers 2, 0, 5, 3, 7 (without repetition)?

There are 5! ways of arranging all 5 digits. But the numbers where the digit starts with 0 is not a 5 digit number. How many numbers are there which are not 5 digits? Suppose 0 is fixed at the first positon. We have 4 other digits. How many ways we can arrange those 4 digits? 4! right? Those 4! ways are the wrong arrangements of digits which start with 0. So the number of ways are

5! – 4! = (120 – 24) = 96

What if the items are not distinct?

Suppose we have digits 1, 3 and 3. How many 3 digit numbers can we form? We can form 3 numbers 133, 331, 313. But when we have 3 distint digits, there are 3! = 6 ways.

Let’s take the number 133. Now when we swap same digits, it doesn’t change the number. For example, if we swap the first 3 with the last 3, it remains the same. There are 2! ways of arranging 33. To eliminate those from our result, we do the opposite of multiplication. That is to divide 3! by 2!. So, the numbers of ways are \frac{3!}{2!}.

Q10. How many words can be created by rearranging the letters of the word DHAKA?

\frac {5!}{2!} = \frac{120}{2} = 60

Q11. How many words can be created by rearranging the letters of the word CHITTAGONG?

\frac {10!}{2! \times 2!} = \frac{3628800}{4} = 907200

Q12. You are in point A and you want to go to point B in shortest possible path, then how many shortest paths are possible?

                           B  
                              
                              
   A                           

To reach the point B we have to move 5 units to the right, and 3 units to the top. Any permutation of 5 units to the right and 3 units upward will give us the shortest path. Since we are not going down or left, this is the shortest path. So, we can represent it as a string, “RRRRRUUU”. The number of ways to arrange the letters is the number of ways to reach B from A. So, the answer is \frac{8!}{5! \times 3!}.

Do you like Naimul Haque's articles? Follow on social!
Comments to: Combinatorics – Filling vacant spaces

    Your email address will not be published. Required fields are marked *