If in any one of the actual permutations we suppose that the a's are all changed into p letters different from each other and from all the rest; then, by changing only the arrangement of these p new letters, we should, instead of a single permutation, have p different permutations.

Hence, if the a's were all changed into p letters different from each other and from all the rest, the b's, c's, &c. being unaltered, there would be Px p permutations.

Similarly, if in any one of these new permutations we suppose that the b's are all changed into q letters different from each other and from all the rest, we should obtain q permutations by changing the order of these q new letters. Hence the whole number of permutations would now be P x px q.

By proceeding in this way we see that if all the letters were changed so that no two were alike, the total number of permutations would be P x px q× r...

But the number of permutations all together of n different things is n. Hence Px p × │q × │r... = n;

Ex. 6. Find the number of permutations of all the letters of each of the words acacia, hannah, success and mississippi.

Ans. 60, 90, 420, 34650.

Ex. 7. In how many ways may a party of 8 take their places at a round table; and in how many ways can 8 different beads be strung on a necklace? Ans. 17, 7.

Ex. 8. In how many ways may a party of 4 ladies and 4 gentlemen be arranged at a round table, the ladies and gentlemen being placed alternately?

Ans. 144.

Ex. 9. The number of permutations of n things all together in which r specified things are to be in an assigned order is

r

Ex. 10. The number of ways in which n books can be arranged on a shelf so that two particular books shall not be together is (n − 2) |n − 1. Ex. 11. Prove, by general reasoning, that „Pr=n-1Pr+r. n-1Pr−1·

COMBINATIONS.

239. Definition. The different ways in which a selection of r things can be made from n things, without regard to the order of selection or arrangement, are called the combinations of the n things r at a time.

Thus the different combinations of the letters a, b, c, d three at a time are abc, abd, acd and bcd.

The number of combinations of n different things r at a time is denoted by the symbol „Cr

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

Let the different things be represented by the letters a, b, c...

Now in the combinations of the n letters r together the number in which a particular letter occurs is equal to the number of combinations of the remaining n − 1 letters r — 1 at a time. Hence in the whole number of combinations together every letter occurs C times, and therefore the total number of letters is n x since there are r letters in each combination, number of the letters must be r× „Cr.

Hence r× „C, = n × n-1Cr-1•

Similarly we have in succession

Also

n-1 r-1

n-1

Cr-1; but, the total

Hence, by multiplying corresponding members of the above equations and cancelling the common factors, we have

C

[r × 0,= n (n − 1) (n − 2)............ (n − r + 1),

n

By multiplying the numerator and denominator of the fraction on the right by n

- r, we have

n (n − 1) (n − 2)... (n − r + 1) × | n − r

=

nr

rn r

n

↑ n r

=

.(ii).

By comparing the above result with that obtained in Art. 238, it will be seen that „P, Cr. The relation P=Cxr can however be at once obtained from the consideration that every combination of r different things would give rise to r permutations, if the order of the letters were altered in every possible way.

n n

Note. In order that the formula (ii) may be true when r=n, we must suppose that 0=1, since „C1 = 1. We should also obtain the result |0=1 by putting n = 1 in the relation n = n│n = n n − 1.

241. Theorem. The number of combinations of n different things r together is equal to the number of the combinations n-r together.

The proposition follows at once from the fact that whenever r things are taken out of n things, n-r must be left; and therefore the number of different ways of taking r things must be just the same as the number of different ways of leaving or taking n-r things.

The result can also be obtained from the formula (ii) of the last Article.

It should be remarked that the first method of proof holds good when the n things are not all different, to which case the formulae of Art. 240 are not applicable.

Ex. 6.

Find n and r having given that P=272 and C=136.

Ans. n=17, r=2.

Ex. 7. Find n and r having given nCr-1:nCr: nCr+1 :: 2 : 3 : 4.

Ans. n=34, r=14.

Ex. 8. How many words each containing 3 consonants and 2 vowels can be formed from 6 consonants and 4 vowels?

6

The consonants can be chosen in C-20 ways; the vowels can be chosen in 4C2=6 ways; hence 20 x 6 different sets of letters can be chosen, and each of these sets can be arranged in P=120 ways. Hence the required number is 20 × 6 × 120.

X

Ex. 9. How many different sums can be formed with a sovereign, a half-sovereign, a crown, a half-crown, a shilling and a sixpence?

Number required =6C1+6C2+6C3+6C4+6C5+6C6=63.

Ex. 10. Shew that, in the combinations of 2n different things n together, the number of combinations in which a particular thing occurs is equal to the number in which it does not occur.

Ex. 11. Shew that, in the combinations of 4n different things n together, the number of combinations in which a particular thing occurs is equal to one-third of the number in which it does not

occur.

Ex. 12. Out of a party of 4 ladies and 3 gentlemen one game at lawntennis is to be arranged, each side consisting of one lady and one gentleman. In how many ways can this be done?

Ans. 36.

Ex. 13. The figures 1, 2, 3, 4, 5 are written down in every possible order: how many of the numbers so formed will be greater than 23000?

Ans. 90.

Ex. 14. At an election there are four candidates and three members to be elected, and an elector may vote for any number of candidates not greater than the number to be elected. In how many ways may an elector vote?

Ans. 14.

If the total number of combinations of (n + 1) things r together be divided into two groups according as they do or do not contain a certain particular letter, it is clear that the number of the combinations which do not contain the letter is the number of combinations r together of the remaining n things, and the number of the combinations which do contain the letter is the number of ways in which 1 of the remaining n things can be taken.

r

The above result can also be proved as follows:

n

=

n+1

243. Greatest value of C. To find the greatest value of „C, for a given value of n.

From the formulae of Art. 240, we have

Hence „C,„„„, according as n−r+1 =r; that is,

r-1

according as r 1 (n + 1).