Chapter X: Section IX: On Permutations and Combinations

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 a _combination_ of four, but which might with more propriety be called a _selection_ of four. Two combinations or selections are called different, which differ in any way whatever; thus, _abcd_ and _abce_ are different, _d_ being in one and _e_ in the other, the remaining parts being the same. Let there be six counters, _a_, _b_, _c_, _d_, _e_, and _f_; the combinations of three which can be made out of them are twenty in number, as follow:

_abc_ _ace_ _bcd_ _bef_

_abd_ _acf_ _bce_ _cde_

_abe_ _ade_ _bcf_ _cdf_

_abf_ _adf_ _bde_ _cef_

_acd_ _aef_ _bdf_ _def_

The combinations of four are fifteen in number, namely,

_abcd_ _abde_ _acde_ _adef_ _bcef_

_abce_ _abdf_ _acdf_ _bcde_ _bdcf_

_abcf_ _abef_ _acef_ _bcdf_ _cdef_

and so on.

205. Each of these combinations may be written in several different orders; thus, _abcd_ may be disposed in any of the following ways:

_abcd_ _acbd_ _acdb_ _abdc_ _adbc_ _adcb_

_bacd_ _cabd_ _cadb_ _badc_ _dabc_ _dacb_

_bcad_ _cbad_ _cdab_ _bdac_ _dbac_ _dcab_

_bcda_ _cbda_ _cdba_ _bdca_ _dbca_ _dcba_

of which no two are entirely in the same order. Each of these is said to be a distinct _permutation_ of _abcd_. Considered as a _combination_, they are all the same, as each contains _a_, _b_, _c_, and _d_.

206. We now proceed to find how many _permutations_, 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, _abcf_ in which _d_ and _e_ are omitted; write _d_ and _e_ successively at the end, which gives _abcfd_, _abcfe_, and repeat the same process with every other permutation of four; thus, _dabc_ gives _dabce_ and _dabcf_. 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, as _dbfea_, will arise in the course of the process from _dbfe_, which, according to our rule, furnishes _dbfea_. Neither will any permutation be repeated twice, for _dbfea_, if the rule be followed, can only arise from the permutation _dbfe_. If we begin in this way to find the permutations of two out of the six,

_a_ _b_ _c_ _d_ _e_ _f_

each of these gives five; thus,

_a_ gives _ab_ _ac_ _ad_ _ae_ _af_
_b_ ... _ba_ _bc_ _bd_ _be_ _bf_

and the whole number is 6 × 5, or 30.

Again, _ab_ gives _abc_ _abd_ _abe_ _abf_
_ac_ ... _acb_ _acd_ _ace_ _acf_

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, _abc_ gives _abcd_ _abce_ _abcf_
_abd_ ... _abdc_ _abde_ _abdf_

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 be _x_(_x_-1), that of three will be _x_(_x_-1)(_x_-2), that of four _x_(_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.

[30] The difference between this problem and the last is left to the ingenuity of the pupil.

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 be _a_, _a_, _a_, _b_, _c_, _d_, and, for a moment, let us distinguish between the three as thus, _a_, _a′_, _a″_. Then, _abca′a″d_, and _a″bcaa′d_ are 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 with _b_, _c_, and _d_, leaving places for the _a_s, thus, ( ) _bc_ ( ) ( ) _d_. If the _a_s had been distinguished as _a_, _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 the _a_s are not distinguished. Hence, to deduce the number of permutations of _a_, _a_, _a_, _b_, _c_, _d_, from that of _aa′a″bcd_, we must divide the latter by 3 × 2 × 1, or 6, which gives

6 × 5 × 4 × 3 × 2 × 1
--------------------- or 120.
3 × 2 × 1

Similarly, the number of permutations of _aaaabbbcc_ is

9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1
---------------------------------
4 × 3 × 2 × 1 × 3 × 2 × 1 × 2 × 1.

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 of _a_, _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, _ab_ gives _abc_, _abd_, _abe_; _ad_ gives _ade_ only. 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, as _acd_, will arise in the course of the process from _ac_, which, according to our rule, furnishes _acd_. Neither will any combination be repeated twice, for _acd_, if the rule be followed, can only arise from _ac_, since neither _ad_ nor _cd_ furnishes it. If we begin in this way to find the combinations of the five,

_a_ _b_ _c_ _d_ _e_

_a_ gives _ab_ _ac_ _ad_ _ae_
_b_ ···· _bc_ _bd_ _be_
_c_ ···· _cd_ _ce_
_d_ ···· _de_

Of these, _ab_ gives _abc_ _abd_ _abe_
_ac_ ···· _acd_ _ace_
_ad_ ···· _ade_
_bc_ ···· _bcd_ _bce_
_bd_ ···· _bde_
_cd_ ···· _cde_
_ae_ _be_ _ce_ and _de_ give none.

Of these, _abc_ gives _abcd_ _abce_
_abd_ ···· _abde_
_acd_ ···· _acde_
_bcd_ ···· _bcde_
Those which contain _e_ give none, as before.

Of the last, _abcd_ gives _abcde_, 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, _ba_ and _ab_, are in any combination _ab_, 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 combination _abc_ has 3 × 2 × 1 permutations, the number of combinations of three is

7 × 6 × 5
----------.
1 × 2 × 3

Also, since any combination of four, _abcd_, contains 4 × 3 × 2 × 1 permutations, the number of combinations of four is

7 × 6 × 5 × 4
-------------,
1 × 2 × 3 × 4

and so on. The rule is: To find the number of combinations, each containing _n_ counters, divide the corresponding number of permutations by the product of 1, 2, 3, &c. up to _n_. If _x_ be the whole number, the number of combinations of two is

_x_(_x_ - 1)
-------------;
1 × 2

that of three is

_x_(_x_ - 1)(_x_ - 2)
---------------------;
1 × 2 × 3

that of four is

_x_(_x_ - 1)(_x_ - 2)(_x_ - 3)
------------------------------; and so on.
1 × 2 × 3 × 4

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

10 × 9 × 8 × 7 × 6 × 5 × 4
--------------------------,
1 × 2 × 3 × 4 × 5 × 6 × 7

in which the product 7 × 6 × 5 × 4 occurs in both terms, and therefore may be removed from both (108), leaving

10 × 9 × 8
----------,
1 × 2 × 3

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.

What number { 6 } { 8 } { 28
of combinations { 4 } out of { 11 } _Answer_, { 330
can be made of { 26 } { 28 } { 378
{ 6 } { 15 } { 5005

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.