SECTION IX.ON PERMUTATIONS ANDCOMBINATIONS.
204. If a number of counters, distinguished by different letters, be placed on the table, and any number of them, say four, be taken away, the question is, to determine in how many different ways this can be done. Each way of doing it gives what is called acombinationof four, but which might with more propriety be called aselectionof four. Two combinations or selections are called different, which differ in any way whatever; thus,abcdandabceare different,dbeing in one andein the other, the remaining parts being the same. Let there be six counters,a,b,c,d,e, andf; the combinations of three which can be made out of them are twenty in number, as follow:
The combinations of four are fifteen in number, namely,
and so on.
205. Each of these combinations may be written in several different orders; thus,abcdmay be disposed in any of the following ways:
of which no two are entirely in the same order. Each of these is said to be a distinctpermutationofabcd. Considered as acombination, they are all the same, as each containsa,b,c, andd.
206. We now proceed to find how manypermutations, each containing one given number, can be made from the counters in another given number, six, for example. If we knew how to find all the permutations containing four counters, we might make those which contain five thus: Take any one which contains four, for example,abcfin whichdandeare omitted; writedandesuccessively at the end, which givesabcfd,abcfe, and repeat the same process with every other permutation of four; thus,dabcgivesdabceanddabcf. No permutation of five can escape us if we proceed in this manner, provided only we know those of four; for any given permutation of five, asdbfea, will arise in the course of the process fromdbfe, which, according to our rule, furnishesdbfea. Neither will any permutation be repeated twice, fordbfea, if the rule be followed, can only arise from the permutationdbfe. If we begin in this way to find the permutations of two out of the six,
abcdef
each of these gives five; thus,
agivesabacadaeaf
b...babcbdbebf
and the whole number is 6 × 5, or 30.
Again,
abgivesabcabdabeabf
ac...acbacdaceacf
and here are 30, or 6 × 5 permutations of 2, each of which gives 4 permutations of 3; the whole number of the last is therefore 6 × 5 × 4, or 120.
Again,
abcgivesabcdabceabcf
abd...abdcabdeabdf
and here are 120, or 6 × 5 × 4, permutations of three, each of which gives 3 permutations of four; the whole number of the last is therefore 6 × 5 × 4 × 3, or 360.
In the same way, the number of permutations of 5 is 6 × 5 × 4 × 3 × 2, and the number of permutations of six, or the number of different ways in which the whole six can be arranged, is 6 × 5 × 4 × 3 × 2 × 1. The last two results are the same, which must be; for since a permutation of five only omits one, it can only furnish one permutation of six. If instead of six we choose any other number,x, the number of permutations of two will bex(x-1), that of three will bex(x-1)(x-2), that of fourx(x-1)(x-2)(x-3), the rule being: Multiply the whole number of counters by the next less number, and the result by the next less, and so on, until as many numbers have been multiplied together as there are to be counters in each permutation: the product will be the whole number of permutations of the sort required. Thus, out of 12 counters, permutations of four may be made to the number of 12 × 11 × 10 × 9, or 11880.
EXERCISES.
207. In how many different ways can eight persons be arranged on eight seats?
Answer, 40320.
In how many ways can eight persons be seated at a round table, so that all shall not have the same neighbours in any two arrangements?[30]
Answer, 5040.
If the hundredth part of a farthing be given for every different arrangement which can be made of fifteen persons, to how much will the whole amount?
Answer, £13621608.
Out of seventeen consonants and five vowels, how many words can be made, having two consonants and one vowel in each?
Answer, 4080.
208. If two or more of the counters have the same letter upon them, the number of distinct permutations is less than that given by the last rule. Let there bea,a,a,b,c,d, and, for a moment, let us distinguish between the three as thus,a,a′,a″. Then,abca′a″d, anda″bcaa′dare reckoned as distinct permutations in the rule, whereas they would not have been so, had it not been for the accents. To compute the number of distinct permutations, let us make one withb,c, andd, leaving places for theas, thus, ( )bc( ) ( )d. If theas had been distinguished asa,a′,a″, we might have made 3 × 2 × 1 distinct permutations, by filling up the vacant places in the above, all which six are the same when theas are not distinguished. Hence, to deduce the number of permutations ofa,a,a,b,c,d, from that ofaa′a″bcd, we must divide the latter by 3 × 2 × 1, or 6, which gives
or 120. Similarly, the number of permutations ofaaaabbbccis
EXERCISE.
How many variations can be made of the order of the letters in the word antitrinitarian?
Answer, 126126000.
209. From the number of permutations we can easily deduce the number of combinations. But, in order to form these combinations independently, we will shew a method similar to that in (206). If we know the combinations of two which can be made out ofa,b,c,d,e, we can find the combinations of three, by writing successively at the end of each combination of two, the letters which come after the last contained in it. Thus,abgivesabc,abd,abe;adgivesadeonly. No combination of three can escape us if we proceed in this manner, provided only we know the combinations of two; for any given combination of three, asacd, will arise in the course of the process fromac, which, according to our rule, furnishesacd. Neither will any combination be repeated twice, foracd, if the rule be followed, can only arise fromac, since neitheradnorcdfurnishes it. If we begin in this way to find the combinations of the five,
Of the last,abcdgivesabcde, and the others none, which is evidently true, since only one selection of five can be made out of five things.
210. The rule for calculating the number of combinations is derived directly from that for the number of permutations. Take 7 counters; then, since the number of permutations of two is 7 × 6, and since two permutations,baandab, are in any combinationab, the number of combinations is half that of the permutations, or (7 × 6)/2. Since the number of permutations of three is 7 × 6 × 5, and as each combinationabchas 3 × 2 × 1 permutations, the number of combinations of three is
Also, since any combination of four,abcd, contains 4 × 3 × 2 × 1 permutations, the number of combinations of four is
and so on. The rule is: To find the number of combinations, each containingncounters, divide the corresponding number ofpermutations by the product of 1, 2, 3, &c. up ton. Ifxbe the whole number, the number of combinations of two is
that of three is
that of four is
211. The rule may in half the cases be simplified, as follows. Out of ten counters, for every distinct selection of seven which is taken, a distinct combination of 3 is left. Hence, the number of combinations of seven is as many as that of three. We may, therefore, find the combinations of three instead of those of seven; and we must moreover expect, and may even assert, that the two formulæ for finding these two numbers of combinations are the same in result, though different in form. And so it proves; for the number of combinations of seven out of ten is
in which the product 7 × 6 × 5 × 4 occurs in both terms, and therefore may be removed from both (108), leaving
which is the number of combinations of three out of ten. The same may be shewn in other cases.
EXERCISES.
How many combinations of four can be made out of twelve things?
Answer, 495.
How many combinations can be made of 13 out of 52; or how many different hands may a person hold at the game of whist?
Answer, 635013559600.