Counting Principles CHAPTER Qh. 14.1.1 DEFINITION Permutations Permutations represents a counting process where the order must be taken into account. For example, the number of permutations of the letters A, B,C and D, if only two are taken at a time, can be enumerated as AB, AC, AD, BA, BC, BD, CA, CB, CD, DA, DB, BC That is, AC is a different permutation from CA (different order). Instead of permutation the term arrangement is often used. This definitions lead to a number of Counting Principles which we now look at. 14.1.2 MULTIPLICATION PRINCIPLE Rule 1: For example, if a dic is rolled twice, there are a total of 6? = 36 possible outcomes. Rule 2: For example, if a person has three different coloured pairs of pants, four different shirts, five different ties and three different coloured pairs of socks, the total number of different ways that this person can dress is equal to 3x 4x 5x3 = 180 ways Rule 3: Because of the common usage of this expression, we use the factorial notation. That is, we write which is read as m factorial, Notice also that 0! is defined as 1, ie.,0!=1 For example, in how many ways can 4 boys and 3 girls be seated on a park bench? In this case any one of the seven children can be seated at one end, meaning that the adjacent position can be a7 be BEd,MATHEMATICS - Higher Level (Core) filled by any one of the remaining six children, similarly, the next adjacent seat can be occupied by any one of the remaining 5 children, and so on ‘Therefore, in total there are 7x 6 x 5x4x3x2x 1 = 7! = 5040 possible arrangements. Using the TI-83, we have: Enter 7: Select MATH and PRB: Select option 4: ! and press ENTER: i soda We start by visualising this situation: ‘Consider the case where John uses Road 1 first. c he possibilities are: B Road | then a, Road | then b, A Road | then c, Road I then d. pT) “That is, there are 4 possible routes ‘Then, for each possible road from A to B there are another 4 leading from B to C Allin all, there are 44444 = 3x4 = 12 different ways John can get from A to C via B In travelling from P to Q there are: x3 x 1 paths (along P to A to B to Q) x 3x 2x 1 paths (along P to C to D to Eto Q) 2.=1 «2 paths (along P to F to Q) In total there are 3 +6 + = 11 paths 478Counting Principles CHAPTER Qh. We think of this problem as follows: The golfer has 3 possible drivers to use and so the first task can be carried out in 3 ways. The golfer has 4 possible tees to use and so the second task can be carried out in 4 ways. The golfer has 5 golf balls to use and so the third task can be carried out in 5 ways. [Using the multiplication principle, there are a total of 3 x 4 x 5 = 60 ways to take the first hit, 14.1.3 PERMUTATIONS Based on the definition given in §14.1.1 we have the following rule: Rule 4: For example, the total number of arrangements of 8 books on a bookshel! if only 5 are used is 8! 8! =a 6720. given by “P, ‘When using the TI-83, we can either use the same approach as in the previous example or use the nPr function: ‘Type the first number, 8, then select MATH and PRB, then select option 2:nPr, enter the second number, 5, and then press ENTER: Ne fPirandB in’ 479MATHEMATICS - Higher Level (Core) We have 5 boys to be arranged in a row with certain constraints (2) The constraint is that we can only use 3 boys at a time. In other words, we want the number of arrangements (permutations) of 5 objects taken 3 at a time. From rule 4: n=5,r=3, St _ 120 (5-3)! 2 (>) This time we want the number of arrangements of 5 boys taking all S at atime. From rule 4: n=5,r=5, Therefore, number of arrangements 120 ‘Therefore, number of arrangements = = 120 Box method Problems like Example 14.4 can be solved using a method known as “the box method”. In that particular example, part (a) can be considered as filling three boxes (with only one object per box) using 5 objects: Box 1 Box 2 Box 3 ‘The first box can be filled in 5 different ways (as there are 5 possibilities available). Therefore we ‘place 5° in box 1: Box 1 Box 2 Box 3 5 Now, as we have used up one of the objects (occupying box 1), we have 4 objects left that can be used to fill the second box. So, we ‘place 4” in box 2: Box 1 Box 2 Box 3 5 4 At this stage we are left with three objects (as two of them have been used). Meaning that there are 3 possible ways in which the third box can be filled. So, we ‘place 3° in box 3: Box 1 Box 2 Box 3 5 4 3 This is equivalent to saying, that we can carry out the first task in 5 different ways, the second task in 4 different ways and the third task in 3 different ways. Therefore, using the multiplication principle we have that the total number of arrangements is 5 x 4x3 = 60 Sxdx3x2x1 2x1 Sx4x3 60 i.e., the last step in the evaluation process is the same as the step used in the ‘box method’, Comparing this to the expression *P, = =a 480Counting Principles CHAPTER Qh. We have a situation where there are five positions to be filled: [Letter] [Letter] [Number] [Number] [Number] ‘That is, the first position must be occupied by one of 26 letters, similarly, the second position must be occupied by one of 26 letters. The first number must be made up of one of nine different digits (as zero must be excluded), whilst the other two positions have 10 ligits that can be used. Therefore, using Rule 2, we have: ‘Total number of arrangements = 26 x 26 x 9 x 10 x 10 = 608400 a) Continuing in this manner we have: Consider the five boxes Box1 Box? Box3_ Box4_—_BoxS Only the digits 4 and 5 can occupy the first box (so as to obtain a number greater than. 40 000). So there are 2 ways to fill box 1: Box _Box2_ _Box3_ Bord Box 2 Box 2 can now be filled using any of the remaining 5 digits. So, there are 5 ways of filling box 2: Box Box? Box3_ Box4__Box$ 2 3 We now have 4 digits left to be used. So, there are 4 ways of filling box 3: Box _Box2_ Box3_ Box Box 2 5 4 Box1 Box? Box3_ Box4 Box 2 5 4 3 2 ‘Then, using the multiplication principle we have 2x 5x 4x3 x2 = 240 arrangements. Otherwise, we could have relied on rule 4 and obtained 2 x°P, = 2x 120 = 240 b) As in part (a), only the digits 4 and 5 can occupy the first box. Ti repetition is allowed, then boxes 2 to 5 can each be filled using any of the 6 digits: Boxl Box? _Box3_ Box4__BoxS 2 6 6 6 6 Using the multiplication principle there are 2x 6 x 6 x 6x6 = 2592 arrangements. 481MATHEMATICS - Higher Level (Core) However, one of these arrangements will also include the number 40 000. Therefore, the number of 5 digit numbers greater than 40 000 (when repetition is allowed) is given by 2592 - 1 = 2591 Tie Piet Foe "Py = = TA = 0 n(n—1)(n—2)(n—3)! 3! ° n—3n? + 2n-60 = 0 Using the TI-83 to solve this polynomial, we have: ien=5. The word ‘HIPPOPOTAMUS’ is made up of 12 letters, unfortunately, they are not all different! Meaning that although we can swap the three P’s with each other, the word will remain the same. Now, the total number of times we can re-arrange the Ps (and not alter the word) is 3! = 6 times (as there are three Ps). Therefore, if we ‘blindly’ use Rule 2, we will have increased the number of arrangements 6 fold. Therefore, we will need to divide the total number of ways of arranging 12 objects by 6. 12! That is, However, we also have 2 Os, and so, the same argument holds. So that in fact, we now 79833600. 12! have a total of 7-5, = 39916800 arrangements ‘This example is a special case of permutations with repetitions: Rule 5: 482Counting Principles CHAPTER J}. 10. nn. 12. A,B and C are three towns. There are 5 roads linking towns A and B and 3 roads linking towns B and C. How many different paths are there from town A to town C via town B? In how many ways can 5 letters be mailed if there are (a) 2 mail boxes available? (b) 4 mail boxes available? ‘There are 4 leters to be placed in 4 letter boxes. In how many ways can these letters be mailed if (@) only one letter per box is allowed? (b) there are no restrictions on the number of letters per box? Consider the cubic polynomial p(x) = ax3 + bx?-Sx +c (a) If the coefficients, a, b and c come from the set { -3, possible cubics if no repetitions are allowed. (b) Find the number of cubies if the coefficients now come from { —3 (again without repetitions), 1, 1,3}, find the number of —1,0, 1,3} The diagram alongside shows the possible routes linking towns A, B,C and D. A person leaves town A for town C. How many different routes can be taken if the person is always heading towards town C In how many different ways can Susan get dressed if she has 3 skirts, 5 blouses, 6 pairs of socks and 3 pairs of shoes to chose from” In how many different ways can 5 different books be arranged on a shelf? In how many ways can 8 different boxes be arranged taking 3 at a time? How many different signals can be formed using 3 flags from 5 different flags. Three Italian, two Chemistry and four Physics books are to be arranged on a shelf. In how many ways can this be done (@)___ if there are no restrictions? (b) _ ifthe Chemistry books must remain together? (©) ___ ifthe books must stay together by subject? Find n if "P, = 380 5 boys and 5 girls, which include a brother-sister, pair are to be arranged in a straight ine. Find the number of possible arrangements if (@) there are no restrictions. (b) the tallest must be at one end and the shortest at the other end. (©) the brother and sister must be i.—together_ ii. separated 483MATHEMATICS — Higher Level (Core) 13. In how many ways can the letters of the word Mississippi be arranged? 14. _Inhow many ways can three yellow balls, three red balls and four orange balls be arranged in a row if the balls are identical in everyway other than their colour? 45. Inset of 8 letters, m of them are the same and the rest different. If there are 1680 possible arrangements of these 8 letters, how many of them are the same? Combinations On the otherhand, combinations represent a counting process where the order has no importance. For example, the number of combinations of the letters A, B,C and D, if only two are taken at a time, can be enumerated as: AB, AC, AD, BC.BD, CD, That is, the combination of the letters A and B, whether written as AB or BA, is considered as being the same. Instead of combination the term selection is often used. Rule 6: For example, in how many ways can 5 books be selected from 8 different books? In this instance, wwe are talking about selections and therefore, we are looking at combinations. Therefore we have, the selection of 8 books taking 5 at a time is equal to 8) _ st (3) ~ (8=5)r 3151 Using the TI-83 we can make use of the nCr function: ‘Type the first number, 8, then select MATH and PRB, then select option 3:nCr, enter the second number, 5, and then press ENTER: naTH NUM CPx lade] [B ncr 5 Lirand einer incr randint¢ randtorn< andeine 484Counting Principles CHAPTER Qh. First we look at the number of ways we can select the women members (using Rule 6): We have to select 3 from a possible 5, therefore, this can be done in °C, = 10 ways. Similarly, the men can be selected in “C, = 6 ways. Using Rule 2, we have that the total number of possible committees = °C, x “C, = 60 Case 1: Case 2: Husband included 6 men left If the husband is included, the wife must be removed (so that she cannot be included). We then have to select 2 more men from the remaining 6 men and 2 women from the Wife included J busband removed 6 men left 4 women tet 3 Pal Le 1 committee remaining 4 women, This is done in °C, x *C, = 90 ways If the wife is included, the husband must be removed. We then have to select 3 men from the remaining 6 men and 1 woman from the remaining 4 women. This is done is °C, x *C, = 80 ways ‘Therefore there are a total of °C, x “C, + °C, x *C, = 90 + 80 = 170 possible committees, 1. Inhow many ways can 5 basketball players be selected from 12 players? 2. A tennis club has 20 members. @) &) Tn how many ways can a committee of 3 be selected. In how many ways can this be done if the captain must be on the committee? 485,MATHEM. ICS — Higher Level (Core) 3. Inhow many ways can 3 red balls, 4 blue balls and 5 white balls be selected from 5 red balls, 5 blue balls and 7 white balls? In how many ways can 8 objects be divided into 2 groups of 4 objects? A cricket training squad consists of 4 bowlers, 8 batsmen, 2 wicket keepers and 4 fielders. From this squad a team of 11 players is to be selected. In how many ways can this be done if the team must consist of 3 bowlers, 5 batsmen, | wicket keeper and 2 fielders? - Aclass consists of 12 boys of whom 5 are prefects. How any committees of 8 can be formed if the committee is to have (a) 3 prefects? (b) at least 3 prefeects? 7. Inhow many ways can 3 boys and 2 girls be arranged in a row if a selection is made from 6 boys and 5 girls? 8. (5) 36 show that n3—3n? + 2n—336 = 0. Hence find n. 9. — Inhow many ways can a jury of 12 be selected from 9 men and 6 women so that there are at least 6 men and no more than 4 women on the jury. 40. show that ("5 1) ("5 1) = (1)? Hence find nit ("5 1) -("5") = 16 aT Em - MISCELLANEOUS QUESTIONS Five different coloured flags can be run up a mast. (@) How many different signals can be produced if all five flags are used? (b) How many different signals can be produced if any number of flags is used? 2. Inhow many different ways can 7 books be arranged in a row? 3. Inhow many different ways can three boys and four girls be seated in a row? In how many ways can this be done if (@) no two girls are sitting next to each other, (b) the ends are occupied by girls? 4. In how many different ways can 7 books be arranged in a row if (@) 3 specifed books must be together, (b) two specified books must occupy the ends 5. A school council consists of 12 members, 6 of whom are parents, 2 are students, the Principal and the remainder are teachers. The school captain and vice-captain must be on the council. If there are 10 parents and 8 teachers nominated for positions on the school council, how many different committees can there be? 48610. 1. 12. 13. 14. 15. 16. 7. 18. 19. Counting Principles CHAPTER J}. A committee of 5 men and $ women is to be selected from 9 men and 8 women. How many possible committees can be formed? Amongst the 17 people, there is a married couple. If the couple cannot serve together, how ‘many committees could there be? A sports team consists of 5 bowlers (or pitchers), 9 batsmen and 2 keepers (or back-stops) How many different teams of 11 players can be chosen from the above squad if the team consists of (@) 4 bowlers (pitchers), 6 batsmen and 1 keeper (back-stop)? (b) 6 batsmen (pitchers) and at least 1 keeper (back-stop)? ‘Twenty people are to greet each other by shaking hands. How many hand shakes are there? How many arrangements of the letters of the word “MARRIAGE” ate possible? How many arrangements of the letters of the word “COMMISSION” are possible? A committee of 4 is to be selected from 7 men and 6 women. In how many ways can this, be done if (@) there are no restrictions? (b) there must be an equal number of men and women on the committee? (©) there must be at least one member of each sex on the committee? Prove that (a) (+00) = C2) ) "IP = "Parx"P_, A circle has n points on its circumference. How many chords joining pairs of points can be drawn? A circle has n points on its circumference, What is the maximum number of points of intersection of chords inside the circle? (@) Show that 2" 3 (3) (6) Inhow many way can 8 boys be divided into two unequal sets? Whilst at the library, Patrick decides to select $ books from a group of 10. In how many different ways can Patrick make the selection? A fish tank contains 5 gold coloured tropical fish and 8 black coloured tropical fish. (@)__ Inhow many ways can five fish be selected? (b) — Ifatotal of have been selected from the tank, how many of these contain two gold fish? In how many ways can 4 people be accommodated if there are 4 rooms available? Acar can hold 3 people in the front seat and 4 in the back seat. In how many ways can 7 people be seated in the car if John and Samantha must sit in the back seat and there is only ‘one driver? 487MATHEM. ICS — Higher Level (Core) In how many ways can six men and two boys be arranged in a row if: (a) the two boys are together? (b) the two boys are not together? (©) there are at least three men separating the boys? In how many ways can the letters of the word “TOGETHER” be arranged? In how many of these arrangements are all the vowels together? In how many ways can 4 women and 3 men be arranged in a row, if there are 8 women and 5 men to select from? In how many ways can 4 women and 3 men be arranged in a circle? In how many ways can this be done if the tallest woman and shortest man must be next to each other? In how many ways can 5 maths books, 4 physics books and 3 biology books be arranged on a shelf if subjects are kept together? How many even numbers of 4 digits can be formed using (a) no figure is repeated? (b) repetition is allowed? 6,7,8if 5 men and 5 women are to be seated around a circular table. In how many ways can this be done if the men & women alternate? A class of 20 students contains 5 student representatives. A committee of 8 is to be formed. How many different committees can be formed if there are (@) only 3 student representatives? (b) at least 3 student representatives? How many possible juries of 12 can be selected from 12 women & 8 men so that there are at Jeast 5 men and not more than 7 women? In how many ways can 6 people be seated around a table if 2 friends are always (@) together? (b) separated? 488