IDOL Institute of Distance and Online Learning ENHANCE YOUR QUALIFICATION, ADVANCE YOUR CAREER.
2 Permutations and Combinations www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL
What we are learning today 3 ✘ Permutation www.cuidol.in 3 All right are reserved with CU-IDOL Unit-1(MAP-607)
4 1. FUNDAMENTAL COUNTING PRINCIPLE www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL
Fundamental Rule of Counting 5 ✘ A newly opened hotel offers food stuff in combos for 5 Rs.80. ✘ Variety Rice: lemon, tomato and curd ✘ Rotti: Chappathi and poori ✘ Juice: Lemon, apple and grape www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL
6 6 ✘ Find the total number of choices and draw a tree diagram. www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL
7 7 18 www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL
Can we use instead 8 ✘ Total number of choices = 3 × 2 × 3 = 18 8 www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL
9 9 ✘ One die is thrown ✘6 ✘ Two Dice are thrown ✘ 36 www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL
We should know this 10 ✘ FACTORIAL 10 www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL
How can it be easy 11 11 www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL
What is Permutation? 12 ✘ A permutation is an arrangement in a definite order of a 12 number of objects taken some or all at a time. ✘ With permutations, every little detail matters. It means the order in which elements are arranged is very important. www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL
There are two types of permutations: 13 1. Repetition is Allowed: For the number lock example 13 provided above, it could be “2-2-2”. 2. No Repetition Allowed: For example, the first three people in a race. You can’t be first and second at the same time. www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL
We will use this identity 14 ✘ n things taken r at a time 14 www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL
How we get this? 15 ✘ Let us assume r blank spaces in a row to be filled by n things. Take the 15 first space. This can be filled by any one of the n thing that are available and can be done in n ways. Having filled the first space by one of the [n] things, there are [(n − 1)] things left. Therefore, the second space can be filled with [(n − 1)] ways. Hence, the first and the second can be filled with [ n (n − 1)] ways. www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL
✘ When the first two places are filled, there will be [(n − 2)] things 16 left; and hence, the third place can be filled with [(n − 2)] ways. So, the first three spaces are filled in [ (n( n − 1)(n − 2)] ways. 16 Proceeding like this, then spaces are filled in ✘ ✘ [ n( n − 1)(n − 2) ... (n − r + 1)] ways ✘ ✘ nPr = n(n − 1) ... (n − r + 1) ✘ Multiply and divide the right-hand side by [1, 2, 3 … [n − r]], we have www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL
17 17 www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL
Remember this 18 ✘ 3 things taken n at a time 18 www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL
Example 19 ✘ Suppose you want to arrange your books on a 19 shelf. In how many ways can you do it? ✘ n = 7 and therefore, number of permutations is 7! = 7.6.5.4.3.2.1 = 5040. www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL
Example 3: How many 2 digit numbers can you make using 20 the digits 1, 2, 3 and 4 without repeating the digits? 20 This time we want to use 2 digits at the time to make 2 digit numbers. For the first digit we have 4 choices and for the second digit we have 3 choices (4 - 1 used already). Using the counting principle, the number of 2 digit numbers that we can make using 4 digits is given by 4 × 3 = 12 21 31 41 www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL
21 The above problem is that of arranging 2 digits out of 4 in a specific order. This is 21 also called permutating. The most important idea in permutations is that order is important. When you use the digits 3 and 4 to make a number, the number 34 and 43 are different hence the order of the digits 3 and 4 is important. In general permutating r (2 digit in the above example) items out of a set of n (4 digits in the above example) items is written as n P r and the formula is given by n P r = n! / (n - r)! ✘ 4 P 2 = 4! / (4 - 2)! = 24/2 = 12 = 4*3*2! /2! www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL
How many 3 letter words can we make 22 with the letters in the word LOVE? 22 ✘ Solution: There are 4 letters in the word love and making making 3 letter words is similar to arranging these 3 letters and order is important since LOV and VOL are different words because of the order of the same letters L, O and V. ✘ Hence it is a permutation problem. The number of words is given by 4 P 3 = 4! / (4 - 3)! = 24 = 4* 3*2! / www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL
Theorem: To compute the number of permutations 23 of n things taking all at a time, when the things are not all 23 different. ✘ Permutation of n Things Not All Different (Taken All Together) www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL
Find the number of permutations of the letters of 24 the word ‘Amalgamation’. 24 ✘ There are 12 letters and the repetition of characters are given as a − 4; m − 2; l − 1; t − 1; i − 1; o − 1; n − 1; g − 1. Hence, the required number of permutations. www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL
There are three copies each of 3 different books. In 25 how many ways can they be arranged on a self? 25 ✘ The total number of books = 3 × 3 = 9 ✘ Eng – 3 copies each ✘ Math – 3 ✘ History - 3 ; n = total no. of objects = 9 www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL
RESTRICTED PERMUTATION 26 26 www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL
Consider the set {A, B, C}, how many ways this can be 27 arranged by considering two elements at a time. 27 ✘ m = 3; k = 2; ✘ 3P2 = [3!]/[3 − 2]! = 6 ✘ {[A, B], [B, C], [C, A], [B, A], [C, B], [A, C]} www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL
28 28 ✘ Suppose if we fix A to be included in all cases, ✘ m − 1 = 2 and k − 1 = 1; Then ✘ 2P1 = 2 ✘ [{[B], [C]}; Since A is fixed] (___, A) www.cuidol.in {[A, B], [B, A], [A, C], [C, A]} All right are reserved with CU-IDOL Unit-1(MAP-607)
Consider the set {A, B, C}, how many ways this can be arranged by 29 considering two elements at a time by not considering A. Here, we are not considering A. 29 m − 1 = 2 and k = 2; Then, 2P2 = 2 [{b, c}, {c, b}] www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL
✘ How many words can be framed with the letters of the word 30 “RIGHT” when: 30 1. R and T taking in the end places. 2. G being always in the middle. 3. R and T taking in the end places. This implies that IGH (RT)Number of ways IGH can be arranged = 3! = 6 4. (R, T) can be arranged = 2! = 2 5. The total number of ways = 2 × 6 = 12 www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL
1. G being placed in the middle. Number of ways 31 RIHT can be arranged = 4! = 2 31 2. The total number of ways = 24 www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL
32 ✘ Example 3: In a library, there are 4 books on fairy tales, 5 books are novels and 3 books are on plays. In how many ways can you arrange these so that 32 books on the fairy tales are together in one place. The novels are together and plays are also together. The requirement is that these books should be in a specific order i.e., books on fairy tales, before novels, before plays. ✘ www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL
✘ Answer: There are 4 books on fairy tales and they have to be put 33 together. They can be arranged in 4! ways. Similarly, there are 5 novels. They can be arranged in 5! ways. 33 And there are 3 books on plays. They can be arranged in 3! ways. So, by the counting principle all of them together can be arranged in 4! × 5! × 3! ways = 17280 ways. www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL
✘ Type II 34 ✘ Example 4: In the above example what is the number of 34 permutations if the books are not to be kept in order? ✘ Answer: Whenever you are asked to keep a particular class of objects together, a convenient trick is to sort of glue them together in your head and treat them as one object. First, we consider the books on fairy tales, novels and plays as single objects. www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL
✘ These three objects i.e the one group of fairy tale books, the 35 one group of novels and the one group of plays can be arranged in 3! ways = 6 ways. 35 ✘ Let us fix one of these 6 arrangements. This may give us a specific order, say, novels → fairy tales → plays. ✘ Given this order, the books on the same subject can be arranged as follows. www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL
36 ✘ In other words, now we have to count the internal permutations. The 4 36 books on fairy tales can be arranged among themselves in 4! = 24 ways. The 5 novels can be arranged in 5! = 120 ways. The 3 plays can be arranged in 3! = 6 ways. ✘ For a given order, the books can be arranged in 24×120×6 = 17280 ways. Therefore, for all the 6 possible orders the books can be arranged in 6×17280 = 103680 ways. www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL
Circular Permutation 37 ✘ (4 − 1)! = 3! = 6. 37 www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL
38 38 In the above example, the position of the person depends on the clockwise or anticlockwise arrangement. The number of arrangement reduces to www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL
39 39 ✘ Problem: Find the number of ways in which four girls and three boys can arrange themselves in a row so that none of the boys is together? How is this arrangement different from that in a circular way? ✘ (By multiplication theorem) www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL
40 40 ✘ Solution: ✘ Case 1: Linear arrangement ✘ Let us first seat the four girls. The girls can seat in 4P4 = 4! = 24. ✘ _ G1 _ G2 _ G3 _ G4 _ ✘ For this type of arrangement, the boys can only sit on the five blanked ( _ ) position. Three boys can arrange themselves in 5 P 3 = 5! ⁄ 2! = 60. The required number of ways = 24 × 60 = 1440. www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL
Case 2: Circular arrangement 41 ✘ Since the condition is that none of the boys can sit together or 41 adjacent to each other. We can get the required number of ways if we subtract the ways in which the three boys can seat up together from the total number of arrangement. The total number of ways in which the four girls and three boys can sit around the table = (7 – 1)! = 6!. www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL
42 42 ✘ Let us assume that the three boys sit together. They are considered as one unit now. Here, we need to arrange only four girls and a unit of boy i.e., 4 + 1 = 5 persons. In the circular arrangement the required number of ways = (5 – 1)! = 4!. www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL
✘ These three boys can now rearrange themselves in 3! ways. By 43 the multiplication theorem, the number of the ways = 4! × 3!. 43 ✘ The number of ways in which the arrangement can take place if none of the boys is seated together is 6! – (4! × 3!) = 720 – 144 = 576. Here we see that in the circular arrangement the number of ways is less than those in the row or linear arrangement. www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL
44 THANK YOU www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL
Search
Read the Text Version
- 1 - 44
Pages: