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

CHAPTER XXVII

PERMUTATIONS AND COMBINATIONS

187. All the different orders in which it is possible to arrange a given number of things, by taking either some or all at a time, are called the permutations of the things.

Thus, the permutations of the figures 2 and 3, are 23, 32; the permutations of three figures, 2, 3, 4, taking two at a time, are 23, 24, 32, 42, 34, 43.

All the different selections that it is possible to make from a given number of things, taking either some or all at a time, without regard to the order in which they are arranged, are called the combinations of the things.

Thus, the combinations of three letters a, b, c, taken two at a time are ab, ac, bc, where the order of the letters is disregarded. Each of these combinations will furnish two permutations, as, ab, ba; ac, ca; bc, cb.

When all the things are taken, there can be only one combination, as abc of the three letters a, b, c.

Notation. The symbol for the number of permutations of n things taking r at a time, is Pr, of n different things taking n at a time, is Pn, of 6 different things taking 3 at a time, is Po.

Sometimes, instead of Pr, "P, or Pn‚r is used.

The symbol for the number of comb nations of n different things, taking r at a time, is C7; of n different things, taking n at a time, is Ch.

These are also sometimes written "Cr or Cnr and "C'n or C'nin

188. To find the number of permutations of n different things taken r at a time.

The permutations of a, b, c, taken two at a time, are

ab ba ca
ac bc cb

evidently formed by writing after each of the three letters each of the other letters. Therefore the total number of permutations is 3 X 2.

The number of permutations of n letters, taken 2 at a time, is found in the same way, by writing after each of the n letters, each of the remaining n 1 letters. Therefore the total number of permutations of n letters, taken 2 at a time, is n (n − 1).

[ocr errors]

If the n letters are taken 3 at a time, the permutations may be obtained by adding each of the remaining n - 2 letters to each permutation of the letters taken 2 at a time, or the total number of permutations of n letters, taken 3 at a time, is n(n - 1)(n 2). Hence, −

The number of permutations of n different things, taken r at a time, is equal to the continued product of he natural numbers from n down to n (r 1) inclusive, the number of factors being equal to r.

[ocr errors]

..P= n(n - 1)(n − 2)..... (n − r + 1) (1)

To get the factors from n down to 1, we must supply the factors (n r) (n − r

1)(n

r

[ocr errors]

2).....2.1.

If the right member of equation (1) is multiplied and divided by this product, which is nr (factorial n -r means the factors from 1 to n

[ocr errors][merged small]

r), we obtain,

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

Equation (1) is usually more convenient in the solution of numerical problems.

When all the n things are taken at a time, r =

equation (1) becomes,

n, and

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

1. In how many orders may 5 persons sit on a bench?

Substitute in the formula, P

5

=

5 X 4 X 3 X 2 X 1 = 120

2. Three persons enter a public telephone station in which there are 6 empty booths. In how many ways may they select booths?

This is evidently a problem to find the number of permutations that may be made of 6 things taken 3 at a time.

Hence P366 X5 X 4 120.

3. How many numbers of 4 figures each can be formed with the figures 1, 2, 3, 4?

4. How many permutations may be made of the letters in the word grapes?

5. Four persons board a boat on which there are 10 vacant seats. In how many ways may they choose seats? 6. In how many different ways may 10 books be arranged on a shelf?

7. If 8 dogs compete at a dog show, in how many ways may the blue and red ribbons be awarded?

189. To find the number of combinations of n different things taken r at a time.

If from the number of permutations of n things taken r at a time, we subtract the number of permutations made from combinations by changing the order of arrangement, we should have left the actual number of combinations of the n things, taken r at a time.

Thus, since two letters, as a and b, have two permutations, ab, ba, but only one combination, the number of combinations of n things, taken 2 at a time, will be only half the number of permutations of n things, taken 2 at a time.

Similarly, since three letters, taken three at a time, have 3 X 2 permutations, but only 1 combination, the number of combinations of n things, taken 3 at a time, is found by dividing the number of permutations of n things, taken 3 at a time, by 3 × 2.

In general then, since the number of permutations of n things taken n at a time is 2, but the number of combinations only 1,

The number of combinations of n different things, taken

r at a time, is equal to the number of permutations of n things, taken r at a time, divided by the number of permutations of r things taken r at a time.

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

Since for every combination of r things taken from n different things, there is left a combination of n − r things, The number of combinations of n different things, taken r at a time, is equal to the number of combinations when taken n r at a time.

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

1. In how many ways may a committee of three be selected from a club of 10 members?

As a committee is not changed by arranging the members of the committee in different orders, this is a problem in combinations.

[blocks in formation]

2. In how many ways may a committee of 8, consisting of 5 Republicans and 3 Democrats, be selected from 10 Republicans and 7 Democrats?

It is evident that 5 Republicans may be selected from 10 Republicans in C510 different ways.

Also 3 Democrats may be selected from 7 Democrats in C37 different

ways.

But as any selection of Republicans may be combined with any selection of Democrats to form this committee of 8, the total number of committees is found by multiplying C510 by C37.

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

3. From 7 consonants and 4 vowels, how many words may be formed, each word consisting of 4 consonants and 2 vowels, if any arrangement of the letters is considered a word?

The number of combinations of 4 consonants is C47 and the number of combinations of 2 vowels is C24.

Each combination of consonants may be combined with each combination of vowels, hence C47 × C24.

But each combination of 6 letters, 4 consonants and 2 vowels, has 6 permutations.

Hence, the total number of words is C47 X C24 × 6.

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

5. In how many ways may a man select a dinner party of 5 from 8 friends?

6. In how many ways may a football eleven be selected from 20 candidates?

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