CHAPTER XXIII.

PERMUTATIONS AND COMBINATIONS.

DEFINITIONS.

1. The following examples will illustrate the character of an important class of problems.

Pr. 1. Write the numbers of two figures each which can be formed from the three figures, 4, 5, 6.

We have 45, 54, 46, 64, 56, 65.

Pr. 2. What committees of two persons each can be appointed from the three persons, A, B, C?

The committees may consist of A, B; A, C; or B, C.

These problems make clear the difference between groups of things, selected from a given number of things, in which the order is taken into account, as in Pr. 1, and in which the order is not taken into account, as in Pr. 2.

2. We are thus naturally led to the following definitions: A Permutation of any number of things is a group of some or all of them, arranged in a definite order.

A Combination of any number of things is a group of some or all of them, without reference to order.

3. It follows from these definitions that two permutations are different when some or all of the things in them are different, or when their order of arrangement is different; and that two combinations are different only when at least one thing in one is not contained in the other.

Thus, ab and ba are different permutations, but the same combination.

The permutations two at a time are formed from those one at a time, by annexing to each of the latter each remaining letter in turn; those three at a time from those two at a time in like manner; and so on. Evidently the permutations thus formed are all different.

Of four things, only four permutations one at a time can be formed. And since, in the permutations two at a time formed from those one at a time, each thing is followed by each remaining thing, none of those two at a time are omitted. For a similar reason, none of those three and four at a time are omitted. Therefore the above representation includes all permutations of the four letters, one, two, three, and four at a time.

5. The number of permutations of n things taken r at a time is denoted by the symbol „P.

Then from the enumeration of the preceding article, we have

P1 = 4, P2 = 12, P3 = 24, P1 = 24.

2

6. When the number of things is large, the preceding method of enumeration becomes laborious.

The following example illustrates a method of deriving a general formula for P

Each permutation one at a time gives as many permutations two at a time as there are things remaining to annex to it in turn, in this case three.

Each permutation two at a time gives as many permutations three at a time as there are things remaining to annex to it in turn, in this case two.

Therefore

P3=4P2 x 2 = 4 × 3 × 2.

2

In like manner‚ ‚P1=‚P ̧= 4 × 3 × 2 × 1.

In general, Prn (n-1) (n-2)... (n − r + 1),

=

(1)

From each permutation of n things one at a time we obtain, by annexing to it each of the n-1 remaining things in turn, n-1 permutations two at a time.

Therefore „P2 = nP1 (n − 1) = n (n − 1).

2 n

(2)

Again, from each permutation of n things two at a time we obtain, by annexing to it each of the n-2 remaining things in 2 permutations three at a time.

turn, n

Therefore P „P2 (n − 2) = n (n − 1) (n − 2).

In like manner,

=

„P1 = „P3(n − 3) = n (n − 1) (n − 2) (n − 3).

(3)

(4)

The method is evidently general. The number subtracted from n in the last factor in (1)–(4) is one less than the number of things taken at a time. Therefore,

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

7. Observe that the number of factors in the formula for „P, is equal to the number of things taken at a time.

E.g.,

8P5 = 8 × 7 × 6 × 5 × 4 = 6720.

8. If all the things are taken at a time, i.e., if r = n, we have

„P„ = n(n − 1)(n − 2).....(n − n + 1) = n(n − 1) (n − 2).....3 × 2 × 1.

E.g.,

5P5 = 5 x 4 x 3 x 2 x 1 = 120.

9. The continued product

is called Factorial-n, and is denoted by the symbol [n or n! Therefore the formula of the preceding article may be written nPn = \n.

E.g., P=7, or 7 !, = 7 × 6 × 5 × 4 × 3 × 2 × 1.

10. In many applications the things considered are not all different. We will now derive a formula for the number of permutations of n things, taken all at a time, when some of them are alike.

Let p of the n things be alike, and suppose the permutations n at a time to be formed. In any one of these permutations, let the p like things be replaced by p unlike things, different from all the rest. Then by changing the order of these p new things only, we can form p permutations from the one permutation. In like manner, p permutations can be formed from each of the given permutations. Therefore

T

T

Find the value of n, when

9.

P4=3P3

10. P20 P1 11. n+2P4=15 „P3. 12. n+1P4=30 n-1P2. 13. n+4P3=8n+3P2. 14. 2n+1P4=140 „P3

Find the value of k, when

15. 10Px+6=310P+5 16. 7Px+1=127P-1 17. 12P=2012P-2 18. How many numbers of 4 figures can be formed with 1, 2, 3, 4, 5, 6, 7?

19. How many numbers of 4 figures can be formed with 0, 1, 2, 3, 4, 5, 6, 7?

20. How many even numbers of 4 figures can be formed with 4, 5, 3, 2?

21. In how many ways can 6 pupils be seated in 10 seats? 22. How many numbers of 5 figures can be formed with 1, 2, 3, 4, 5, 6, 7, 8, 9, if the figure 7 be in the middle of each number?

23. How many permutations can be formed with the letters in the word Philippine?

24. How many permutations can be formed with the letters in the word Iloilo?

25. In how many ways can 7 men be seated at a round table?

26. In how many ways can a bracelet be made by stringing together 7 pearls of different shades?

COMBINATIONS.

n

11. The formula for the number of combinations of n things, r at a time, which is denoted by C,, is most readily obtained by deriving a relation between P, and C. The method will be illustrated by a particular example.

n