with an b, ad,...., bd,....) C, d, letters each, of which the n letters are susceptible. But we shall obtain every time, n-1 results ; thus, ab, (n-1 results); ac, ba, be, ca, cb, cd,...., da, db, dc, etc. eto. etc. Now since there are n letters, each to be combined with n-1 reserved letters, there will be in all n(n-1) results. That is, The number of permutations of n letters taken two at a time, is n(n-1). Second :-If we consider each of the permutations of the n letters with two in a set, apart from the other letters, there will be in every case n—2 reserved letters. Hence, to permute the n letters with three in a set, we shall have n— -2 reserved letters, to be annexed successively to each of the n(n-1) permutations with two in a set, thus forming n(n-1)(n-2) new results. That is, The number of permutations of n letters taken three at a time, is n(n-1) (1–2). If the permutations of the n letters taken r-1 at a time were formed, there would be with respect to each, n-(1-1), or n—r+1, reserved letters. And we might conjecture from the two preceding cases, that the number of permutations of n letters taken r at a time, is n(n-1)(n-—2)....(n-r+1). (4) or, the product of the natural numbers from n down to n-r+1, inclusive. This may be demonstrated in a general manner, as follows : Let w and x' represent any two consecutive numbers less than ng *+1= '. (1) Let P represent the permutations of n letters taken w in a set, and P' the number of permutations of the letters taken æ+1 or a' in a set. Now if we consider each of the P permutations apart from the other letters, there will be in every case n— reserved letters. Thus we have n-reserved letters to be annexed successively to each of the P permutations, in order to form the P' permutations 80 that with x+1 or a' letters in a set. This will give P(n—r) results ; and we therefore have P(n-= P. (2) Now we will show that if, according to the law already enunciated, P=n(n-1) (1–2)....(n-x+1), (3) then the value of P' will be expressed by a similar formula. For, multiply both members of equation (3) by n—x, and equate the result with the second member of (2); we have P=n(n-1) (n-2) ...(n-x). But from equation (1), we have X = x'-1. Substituting this value of x in equation (4), gives P = n(n-1) (n—2)....(n^'+1). (5) Equations (3) and (5) are similar in form. Thus we have shown that if formula (A) holds when the letters are taken x at a time, it will hold when the letters are taken x+1 at a time. But it has been proved to hold when the letters are taken three at a time; hence it holds when they are taken four at a time; hence also it holds when they are taken five at a time, and so on. Thus it is true universally. NOTE.---In the practical application of formula (A), it will be well to remember that the number of factors is equal to the number of letters taken in a set. 338. To find the number of permutations of n things taken all at a time, put r = n in formula (A); the result will be (n-1) (–2)...... (B) That is, The number of permutations of n things taken all together in a set, is equal to the continued product of the natural numbers from n down to 1, inclusive. 339. To find the number of combinations of n things taken r ut a time. Let Z =the number of combinations of n things, taken r in a set; P= the number of permutations of n things, taken r in a set ; 2=Pro 2= (C) Now it is evident that all of the P permutations can be obtained, by subjecting the r things in each of the Z combinations to all the permutations of which they are susceptible. But a single combination of r things produces P' permutations, taking all the things in a set; hence the Z combinations will give ZXP' permutations, and we shall therefore have ZXP=P; P Whence, But by (337), P=n(n-1)(n—2)....(nếr+1); and by (338), P'=r(r-1)(r^2).... 1. Hence, we have n(n-1)(n-2)....( nr+1) r(r-1)(r-2)....1 That is, The number of combinations of n letters taken r at a time, is equal to the continued product of the natural numbers from n down to n-r+1 inclusive, divided by the continued product of the natural numbers from r down to 1 inclusive. 340. It is evident that for every combination of r things which we take out of n things, there will be left a combination of n— things. That is, every possible combination containing r things, corresponds to a combination of n— things which remain. Hence, The number of combinations of n things taken r at a time, is equal to the number of combinations of n things taken n-r at a time. This proposition may be demonstrated algebraically as follows: Let Z represent the number of combinations of n things taken r at a time, and Z the number of combinations of n things taken n— at a time. Let it be observed that the last factor in the numerator of Zwill be n-(n-r)+1=r+1. Then n(n—1)(n—2)....(n=+1), r(r-1) (r-2)....1 (n--r)(n--7-1)....1 By division we obtain 1. n(n-1)(n-2)....1 Whence, Z= Z'. 341. To find for what value of r, the number of combinations of n things taken r at a time is the greatest. Consider r as a varying quantity, being at first unity, and changing to 2, 3, 4, .... successively. Let Z represent the number of combinations for any value of r, and Z' the number of combinations for the succeeding value of r. We have n(n-1)(n-2)....(n-r+2)(n-r+1) (1) And if in this equation we change r to r+1, the result must be the value of Z'; thus, n(n-1)(1–2)....(nếr+1)(n—) (2) Divide (2) by (1), observing that in the second member of (2), the factor which immediately precedes (n-r+1) is (n-r+2); we have is greater or Now Z' is greater or less than Z, according as r+1 less than unity. That is, when nr >1, r+1 the number of combinations will be increased by giving to r its succeeding value ; but when r+1 <1, the number of combinations will be diminished by giving to r its succeeding value. n 1 71<1, then r> 무 And if 2 Hence, that value of r which will give the greatest number of 21 combinations, must not be less than or greater than 2 +1, 2 n+1 ; hence, it will have one of the three values, 2 -1 n+1 2 2' 2 1st. Suppose n even. Then the first and third values will be fractional, and therefore impossible for r; hence in this case or n n 2' 2d. Suppose n odd. Then the second value will be fractional, and consequently impossible for r; hence, in this case r must have at least one of the other values. We will show that it may have either of them. For, suppose r = 무 n 2 By (340), the number of combinations will be the same, if -1 n+1 2 That is, when n is odd, the greatest number of combinations will be obtained by making -1 n+1 2 the two values of r giving the same result. or EXAMPLES OF PERMUTATIONS AND COMBINATIONS. 1. How many different permutations may be formed of 10 letters taken four at a time? Ans. 5040. 2. How many different permutations may be made of 6 things taken all together in a set ? Ans. 720. |