Εικόνες σελίδας
PDF
Ηλεκτρ. έκδοση

with an

b,

ad,...., bd,....)

C,

[ocr errors]

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(nr) 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 ;
P= the number of permutations of r things, taken all together

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),
Z:

r(r-1) (r-2)....1
n(n-1)(1–2)....(r+1)

(n--r)(n--7-1)....1

[ocr errors]

By division we obtain
Z n(n-1)(1–2)....1

1.
2= )-

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)
Z
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,

n(n-1)(1–2)....(nếr+1)(n—)
(r+1rr-1)....1

(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

[ocr errors]
[merged small][ocr errors][merged small][merged small][ocr errors]

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.

[ocr errors][merged small][merged small][merged small][merged small][merged small]

n 1

71<1, then r>

[ocr errors]
[ocr errors]

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

[ocr errors]

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

[ocr errors]

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.

« ΠροηγούμενηΣυνέχεια »