letters each, of which then letters are susceptible. But we shall obtain every time, n-1 results; thus, -1 re Now since there are n letters, each to be combined with n— served 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) (n-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), 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 x and x' represent any two consecutive numbers less than n, so that x+1=x'. (1) Let P represent the permutations of n letters taken x in a set, and P' the number of permutations of the letters taken x+1 or x' in a set. Now if we consider each of the P permutations apart from the other letters, there will be in every case n-x reserved letters. Thus we have n―x reserved letters to be annexed successively to each of the P permutations, in order to form the P' permutations with x+1 or x' letters in a set. This will give P(n—r) results; and we therefore have Now we will show that if, according to the law already enunciated, P= n(n-1) (n-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 Substituting this value of x in equation (4), gives (4) (5) Equations (3) and (5) are similar in form. Thus we have shown that if formula (4) 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 That is, n(n−1) (n—2)....1. (B) 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 ~ in a set; P' the number of permutations of r things, taken all together = 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 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-r things. That is, every possible combination containing r things, corresponds to a combination of n-r 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―r at a time. Let it be observed that the last factor in the numerator of Z' will be n—(n—r)+1 = r+1. Then 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. any Let Z represent the number of combinations for 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) `r(r−1)(r−2)....1 (1) And if in this equation we change r to r+1, the result must be the value of Z'; thus, Z = n(n−1)(n—2)....(n—r+1)(n—r) (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 Now Z' is greater or less than Z, according as less than unity. That is, when n-r >1, r+1 the number of combinations will be increased by giving to r its succeeding value; but when the number of combinations will be diminished by giving to r its succeeding value. Hence, that value of r which will give the greatest number of n -1 combinations, must not be less than n-1 or greater than +1, ; hence, it will have one of the three values, 1st. Suppose n even. Then the first and third values will be fractional, and therefore impossible for r; hence in this case 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 By (340), the number of combinations will be the same, if That is, when n is odd, the greatest number of combinations will be obtained by making n+1 the two values of r giving the same result. 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. |