Permutation and combination topics and examples- 1.pptx

Permutations and combinations are mathematical concepts for counting arrangements and selections, respectively. Permutations are arrangements where order matters, such as a lock's combination, calculated with the formula \(nPr=n!\) \(/(n-r)!\). Combinations are selections where order does not matter, like choosing a committee, calculated with the formula \(nCr=n!\) \(/(r!*(n-r)!)\). 

1. Permutation and combination-1 Counting MN rule of counting MNP rule of counting Problems- 1. Based on counting 2. Based on MN rule of counting 3. Based on MNP rule of counting

2. Counting It is a process of determining the number of elements of a finite set of objects. In many cases direct counting becomes quite tough and in such cases we need special cases of counting to make it easier The special cases of counting are- 1. MN rule of counting 2. MNP rule of counting 3. Permutation 4. Combination MNP rule of counting and permutation are basically same thing

3. Example 1- There is a knockout chess tournament (the player who loses the game will be eliminated from the tournament) with participation of 32 players. Each game must result in a winner. How many games will be played to decide the winner of the tournament? Example 2- There is a knockout chess tournament (the player who loses the game will be eliminated from the tournament) with participation of 50 players. Each game must result in a winner. How many games will be played to decide the winner of the tournament? Example 3- In climbing a round pole of 80 m height, a monkey climbs 5 m in a min and slips 2 m in the alternate min. How much time would the monkey take to get to the top of the pole? Example 4- There are 8 different locks, with exactly 1 key for each lock. All the keys have been mixed up. What is the maximum number of trials required in order to determine which key belongs to which lock?

4. Solutions Solution 1- We may think of 5 rounds of 16 games, 8 games (pre-quarter final), 4 games (quarter final), 2 games (semi-final) and 1 game (final) and so total 31 games. After these 5 rounds (i.e. 31 games), 31 players will be eliminated. So, we need 31 games. But it’s better to use another approach which will be discussed in solution 2 Solution 2- The approach used to solve example 1 cannot be used in this example because after 1st round of 25 games there will be 25 players and 25 is an odd number and so we cannot move further with this approach. So, in this we need to use another approach that whoever will lose any game will leave the tournament. Total 31 players should leave to decide 1 champion. So, we need total 31 games (The answer for such problems is n-1, where n is the number of participants) Solution 3- In 2 min, monkey will cover total 3 m. After 50 min, the monkey will cover 75 m. In 51st min, monkey will reach the top of pole i.e. 80 m. So, 51 min is our required answer Solution4 - Solution will be provided later. Answer is 28. You need to discuss how it is 28

5. MN rule of counting Count the number of cross on left side and on right side

6. MN rule of counting There are 20 crosses on both sides of paper in the last slide. But, we can see that counting is easy in the right side. Why? It is so, because the crosses are arranged in rows and columns on the right side. And so we can count the total number of crosses = 4 × 5 = 20 Where 4 = number of rows and 5 = number of columns So, if we can arrange objects in m rows and n columns. The number of objects can be counted easily as m × n. This rule or arranging objects in rows and columns so that we can count them easily is called MN rule of counting

7. Example on MN rule of counting Example - There are 5 boys and 7 girls in a class. In how many ways we can choose CRs for class (1 Boys CR and 1 girls CR)

8. Example on MN rule of counting Example - There are 5 boys and 7 girls in a class. In how many ways we can choose CRs for class (1 Boys CR and 1 girls CR) Solution - Let the 5 boys be a, b, c, d and e and 7 girls be 1, 2, 3, 4, 5, 6 and 7. Now we can choose a as boys CR and 1 as girls CR. In this way we can choose anyone from a to e to be the boys CR and any one among the 7 girls for girls CR. So, the possible number of ways are – a1, a2, …….e7 This way we will count total 35 pairs via physical counting We can simple use MN rule as 5 × 7 = 35 (we can see that MN rule is less time consuming as compared to physical counting)

9. MNP rule is extension of MN rule but it has a special case which can be understood as- Let there are n people and there are r positions (n ≥ r). No person can take more than 1 position and we cannot fill a position by more than 1 person. So, total number of ways in which we can fill r positions can be obtained as- For 1st position we have n choices For 2nd position we have n-1 choices (as the person who was chosen for 1st position cannot take any other position now) Similarly, for 3rd position we have n-2 choices and so on So, we can see for each new position the number of choices gets reduced by 1 Total number of choices = n (n-1) (n-2)… (n+1-r) For example if there were 10 people and 4 positions Number of choices = 10 × 9 × 8 × 7 = 5040 This rule of filling r positions by total available n objects such that each object can take a unique position and each position can be filled by only 1 object is MNP rule of counting MNP rule of counting and Permutation are same thing. We can say that Permutation is MNP rule of counting. So, any problem which can be solved by MNP rule can also be solved by formula of Permutation. We will see how we can solve problems by using MNP rule and Permutation (to get same solution after discussion on Permutation) The problems based on numbers (choosing digits for all the places of the number) partially (not exactly) use MNP rule of counting

10. Problems based on digits (partially based on MNP rule) Example 1- How many total 3-digit numbers are there? Example 2- How many total 3-digit odd numbers are there? Example 3- How many total 3-digit numbers are there such that repetition of digits is not allowed?

11. Problems based on digits (partially based on MNP rule) Example 1- How many total 3-digit numbers are there? Solution 1- This is not exactly MNP rule problem because if repetition of digits is allowed than we are not using the concept that for each new position there will be 1 less choice There are 9 choices for 1st place (0 is not allowed) There are 10 choices for 2nd place (0 is allowed) There are 10 choices for 3rd place (0 is allowed) Total number of choices = 9 × 10 × 10 = 900 Example 2- How many total 3-digit odd numbers are there? Solution 2 – This is again not using MNP rule There are 9 choices for 1st place (0 is not allowed) There are 10 choices for 2nd place (0 is allowed) There are 5 choices for 3rd place (1, 3, 5, 7, 9) Total number of choices = 9 × 10 × 5 = 450 Example 3- How many total 3-digit numbers are there such that repetition of digits is not allowed? Solution 3- This is partially based on MNP rule There are 9 choices for 1st place (0 is not allowed) There are 9 choices for 2nd place (0 is allowed, but the digit which will be used in 1st digit cannot be used for 2nd digit There are 8 choices for 3rd place Total number of choices = 9 × 9× 8 = 648 (It uses MNP rule partially as the digit used once cannot be used again. But for 1st place 0 cannot be used. So, choices for 1st and 2nd place remain same i.e. 9)

12. Example 4- How many 4 digit numbers can be formed with 0, 3, 7, 8 and 9? Solution: Example 5- How many 4 digit numbers can be formed with 0, 3, 7, 8 and 9 so that repetition of digits is not allowed? Solution: Example 6- How many 4 digit numbers more than 8000 can be formed with 0, 3, 7, 8 and 9 so that repetition of digits is not allowed? Solution:

13. Example 7- How many total 3-digit numbers are there if repetition of digits is not allowed and the number is divisible by 5? Solution- Digits cannot be repeated and number is divisible by 5. Any number is divisible by 5 if the last digit is 0 or 5

14. Example 4- How many 4 digit numbers can be formed with 0, 3, 7, 8 and 9? Solution: Example 5- How many 4 digit numbers can be formed with 0, 3, 7, 8 and 9 so that repetition of digits is not allowed? Solution: Example 6- How many 4 digit numbers more than 8000 can be formed with 0, 3, 7, 8 and 9 so that repetition of digits is not allowed? Solution:

15. Example 7- How many total 3-digit numbers are there if repetition of digits is not allowed and the number is divisible by 5? Solution- Digits cannot be repeated and number is divisible by 5. Any number is divisible by 5 if the last digit is 0 or 5 Case 1- Last digit is 0 So, 0 is fixed on 3rd place. So, there is 1 choice for 3rd place (i.e. 0) and 9 choices ( 1 to 9) are left for 2 remaining places (1st and 2nd) There are 9 choices for 1st place There are 8 choices for 2nd place (0 is already used in 3rd place) There is 1 choice for 3rd place (i.e. 0) Total number of choices = 9 × 8 × 1 = 72 Case 2- Last digit is 5 So, 5 is fixed on 3rd place. So, there is 1 choice for 3rd place (i.e. 5) and 9 choices (0 to 4 and 5 to 9) are left for 2 remaining places (1st and 2nd) There are 8 choices for 1st place ( 0 and 5 are not available) There are 8 choices for 2nd place (5 cannot be used and the digit chosen for 1st place cannot be used, but 0 can be used so there are total 8 choices) There is 1 choice for 3rd place (i.e. 5) Total number of choices = 8 × 8 × 1 = 64 So, total number of such numbers are = 72 + 64 = 136