THEOREM. The number of permutations of n objects taken r at a time is n (n - 1)... (n − r + 1). This is symbolized by Pr (I) This formula is easily remembered if one observes that the first factor is n, the total number of objects considered, and that the number of factors is r, the number of objects taken at a time. Thus P7,3 7.6.5. We prove this theorem by complete induction. = First, let r 1. There are evidently only n different arrangement of n objects, taking one object at a time, namely (assuming our objects to be the first n integers), 1, 2, 3, n. Let us take two objects at a time, i.e. let r = = 2. Since there are n objects, we have n ways of filling the first of the two places. When that is filled there are n - 1 objects left, and any one may be used to fill the second place. there are for r = 2 different permutations. Thus, by the Theorem, § 138, n (n − 1) We can fill the first m places in P n, m (1) different ways since there are that number of permutations of n things taken m at a time. This constitutes the first act (§ 138). The second act consists in filling the m+ 1st place, which may be done in nm ways by using any of the remaining nm objects. Thus the number of permutations of n things taken m + 1 at a time is which is the form that (I) assumes on replacing m by m +1. COROLLARY. The number of permutations of n things taken all Taking n = r in (I), we get (2). *n! is the symbol for 1·2·3 · 4 · · · (n − 1)n, and is read factorial n. (2) EXERCISES 1. How many permutations may be formed from 8 letters taken four at a time? Solution: n = = 8, r = : 4, n − r + 1 = 5, P8, 4= 8.7.6.5= 1680. 2. In how many different orders may 6 boys stand in a row? 3. How many different numbers less than 1000 can be formed from the digits 1, 2, 3, 4, 5? 4. How many arrangements of the letters of the alphabet can be made taking three at a time? 5. How many numbers between 100 and 10,000 can be formed from the digits 1, 2, 3, 4, 5, 6? 6. How many different permutations can be made of the letters in the word compute taking four at a time? 7. In a certain class there are 4 boys and 5 girls. In how many orders may they sit provided all the boys sit on one bench and all the girls on another? HINT. Use Corollary § 139, and then Theorem, § 138. 8. I have 6 books with red binding and 3 with brown. In how many ways may I arrange them on a shelf so that all the books of one color are together? 140. Combinations. Any group of things that is independent of the order of the constituents of the group is called a combination. The committee of men Jones, Smith, and Jackson is the same as the committee Jackson, Jones, and Smith. The sound made by striking simultaneously the keys EGC of a piano is the same as the sound made by striking CGE. In general a question involving the number of groups of objects that may be formed where the character of any group is unaltered by any change of order among its constituent parts is a question in combinations. Suppose for example that we ask how many committees of three men can be selected from six men. If the men are called A, B, C, D, E, F, there are, by § 139, 6.5.4 120 different arrangements or permutations of the six men in groups of three. But the permutations A, B, C; A, C, B; B, A, C, etc. (3! = 6 in all for the men A, B, and C), are all distinct, while evidently the six committees consisting of A, B, and C are identical. This is true for every distinct set of three men that we could select; that is, for the = six different permutations of any three men there is only one distinct committee. Hence the number of committees is one sixth the total number of permutations, or This leads to the general P6, 3. THEOREM. The number of combinations of n things taken rat a time is n (n − 1)... (n r + 1) This is symbolized by Cr r! The number of permutations of n things taken r at a time is In every group of r things which form a single combination there are (Cor., p. 145) r! permutations. Thus there are r! times as many permutations as combinations. That is, This formula is easily remembered if one observes that there is the same number of factors in the numerator as in the denominator. Thus Multiplying numerator and denominator of (II) by (n − r)!, This corollary saves computation in some cases. For instance, if we wish to compute C19, 17, it is more convenient to write C19, 17 C19, 2 = expression for C19, 17. 1918 171 than the EXERCISES 1. How many committees of 5 men can be selected from a body of 10 men three of whom can serve as chairman but can serve in no other capacity ? Solution: There are 7 men who may fill 4 places on the committee. There are 3 men to select from for the remaining place of chairman, and the selection may be made in 3 ways. Thus the committee can be made up in 3.35 105 ways. 2. How many distinct crews of 8 men may be selected from a squad of 14 men? 3. How many distinct triangles can be drawn having their vertices in 10 given points no three of which are in a straight line? 4. How many distinct sounds may be produced on 9 keys of a piano by striking 4 at a time? 5. In how many ways can a crew of 8 men and a hockey team of 5 men be made up from 20 men? 6. In how many ways may the product a b c d e f be broken up into factors each of which contains two letters? 7. If 8 points lie in a plane but no three in a straight line, how many straight lines can be drawn joining them in pairs? 8. How many straight lines can be drawn through n points taken in pairs no three of which are in the same straight line? 9. Seven boys are walking and approach a fork in the road. They agree that 4 shall turn to the right and the remainder turn to the left. In how many ways could they break up? Solution: The number of groups of 4 boys that can be formed from the party is C7, 4= 7.6.5.4 = 35. For each group of 4 boys there remains only a single group of 3 boys. Thus the total number of ways in which the party can divide up is precisely 35. 10. If there are 12 points in space but no four in the same plane, how many distinct planes can be determined by the points? HINT. Three points determine a plane. 11. Eight gentlemen meet at a party and each wishes to shake hands with all the rest. How many hand shakes are exchanged? 12. In how many ways can a baseball team of 9 men be selected from 14 men only two of whom can pitch but can play in no other position? 13. How many baseball teams can be selected from 15 men only four of whom can pitch or catch, provided these four can play in either of the two positions? 14. Two dormitories, one having 3 doors, the other having 5 doors, stand facing each other. A path runs from each door of one to every door of the other. How many paths are there? 15. Show that the number of ways in which p + q things may be divided (p + q)! into groups of p and q things respectively is p!q! 16. Out of 8 consonants and 3 vowels how many words can be formed each containing 3 consonants and 2 vowels? 17. A boat's crew consists of 8 men, three of whom can row only on one side and two only on the other. In how many ways can the crew be arranged ? 18. A pack of cards contains 52 distinct cards. In how many different Iways can it be divided into 4 hands of 13 cards each? 19. Five points lie in a plane, but no three in any other plane. How many tetrahedrons can be formed with these points taken with two points not in the plane? 141. Circular permutations. By circular permutations we mean the various arrangements of a group of things around a circle. THEOREM. The number of orders in which n things may be arranged in a circle is (n-1)!. A Suppose A is at the point at which we begin to arrange the digits 1, 2, 3, ..., n. Suppose we start our arrangement of digits at A with a given digit a. We have then virtually n-1 places to fill by the remaining n-1 digits. Thus we get (n−1)! (p. 145) permutations of the n digits keeping a fixed. But suppose we start our arrangement, that is, fill the place at A with any other digit, as b, and the remaining places in any order whatever. If we now go around the circle till we こ come to the digit a, the succession of digits from that point around the circle to a again must be one of the (n-1)! orders |