APPENDIX X.
ON COMBINATIONS.
There are some things connected with combinations which I place in an appendix, because I intend to demonstrate them more briefly than the matters in the text.
Suppose a number of boxes, say 4, in each of which there are counters, say 5, 7, 3, and 11 severally. In how many ways can one counter be taken out of each box, the order of going to the boxes not being regarded. Answer, in 5 × 7 × 3 × 11 ways. For out of the first box we may draw a counter in 5 different ways, and to each such drawing we may annex a drawing from the second in 7 different ways—giving 5 × 7 ways of making a drawing from the first two. To each of these we may annex a drawing from the third box in 3 ways—giving 5 × 7 × 3 drawings from the first three; and so on. The following statements may now be easily demonstrated, and similar ones made as to other cases.
If the order of going to the boxes make a difference, and if a, b, c, d be the numbers of counters in the several boxes, there are 4 × 2 × 3 × 1 × a × b × c × d distinct ways. If we want to draw, say 2 out of the first box, 3 out of the second, 1 out of the third, and 3 out of the fourth, and if the order of the boxes be not considered, the number of ways is
| a | a -1 | × | b - 1 | b - 2 | × c × d | d - 1 | d - 2 | ||
| 2 | 2 | 3 | 2 | 3 |
If the order of going to the boxes be considered, we must multiply the preceding by 4 × 3 × 2 × 1. If the order of the drawings out of the boxes makes a difference, but not the order of the boxes, then the number of ways is
a(a-1)b(b-1)(b-2)cd(d-1)(d-2)
The nth power of a, or aⁿ, represents the number of ways in which a counters differently marked can be distributed in n boxes, order of placing them in each box not being considered. Suppose we want to distribute 4 differently-marked counters among 7 boxes. The first counter may go into either box, which gives 7 ways; the second counter may go into either; and any of the first 7 allotments may be combined with any one of the second 7, giving 7 × 7 distinct ways; the third counter varies each of these in 7 different ways, giving 7 × 7 × 7 in all; and so on. But if the counters be undistinguishable, the problem is a very different thing.
Required the number of ways in which a number can be compounded of other numbers, different orders counting as different ways. Thus, 1 + 3 + 1 and 1 + 1 + 3 are to be considered as distinct ways of making 5. It will be obvious, on a little examination, that each number can be composed in exactly twice as many ways as the preceding number. Take 8 for instance. If every possible way of making 7 be written down, 8 may be made either by increasing the last component by a unit, or by annexing a unit at the end. Thus, 1 + 3 + 2 + 1 may yield 1 + 3 + 2 + 2, or 1 + 3 + 2 + 1 + 1: and all the ways of making 8 will thus be obtained; for any way of making 8, say a + b + c + d, must proceed from the following mode of making 7, a + b + c + (d - 1). Now, (d - 1) is either 0—that is, d is unity and is struck out—or (d - 1) remains, a number 1 less than d. Hence it follows that the number of ways of making n is 2ⁿ⁻¹. For there is obviously 1 way of making 1, 2 of making 2; then there must be, by our rule, 2² ways of making 3, 2³ ways of making 4; and so on.
| 1 |  | 1 + 1 + 1 + 1 | ||||
 | 1 + 1 + 1 | 1 + 1 + 2 | ||||
 | 1 + 1 | 1 + 2 + 1 | ||||
| 1 + 2 | 1 + 3 | |||||
| 2 + 1 | | 2 + 1 + 1 | |||
| 2 | 2 + 2 | |||||
| 3 | 3 + 1 | |||||
| 4 | ||||||