In the two series, 1 1 1 2 3 4 6 9 13 19 28, &c.
0 1 0 1 1 1 2 2 3 4 5, &c.,
the first has each new term after the third equal to the sum of the last and last but two; the second has each new term after the third equal to the sum of the last but one and last but two. Shew that the nth number in the first is the number of ways in which n can be made up of numbers which, divided by 3, leave a remainder 1; and that the nth number in the second is the number of ways in which n can be made up of numbers which, divided by 3, leave a remainder 2.
It is very easy to shew in how many ways a number can be made up of a given number of numbers, if different orders count as different ways. Suppose, for instance, we would know in how many ways 12 can be thus made of 7 numbers. If we write down 12 units, there are 11 intervals between unit and unit. There is no way of making 12 out of 7 numbers which does not answer to distributing 6 partition-marks in the intervals, 1 in each of 6, and collecting all the units which are not separated by partition-marks. Thus, 1 + 1 + 3 + 2 + 1 + 2 + 2, which is one way of making 12 out of 7 numbers, answers to
| 1 | 1 | 111 | 11 | 1 | 11 | 11 |
in which the partition-marks come in the 1st, 2d, 5th, 7th, 8th, and 10th of the 11 intervals. Consequently, to ask in how many ways 12 can be made of 7 numbers, is to ask in how many ways 6 partition-marks can be placed in 11 intervals; or, how many combinations or selections can be made of 6 out of 11. The answer is,
| 11 × 10 × 9 × 8 × 7 × 6 | , or 462. |
|---|---|
| 1 × 2 × 3 × 4 × 5 × 6 |
Let us denote by mₙ the number of ways in which m things can be taken out of n things, so that mₙ is the abbreviation for
| n × | n - 1 | × | n - 2 | ... as far as | n - m + 1 |
|---|---|---|---|---|---|
| 2 | 3 | m |
Then mₙ also represents the number of ways in which m + 1 numbers can be put together to make n + 1. What we proved above is, that 6₁₁ is the number of ways in which we can put together 7 numbers to make 12. There will now be no difficulty in proving the following:
2ⁿ = 1 + 1ₙ + 2ₙ + 3ₙ ... + nₙ
In the preceding question, 0 did not enter into the list of numbers used. Thus, 3 + 1 + 0 + 0 was not considered as one of the ways of putting together four numbers to make 5. But let us now ask, what is the number of ways of putting together 7 numbers to make 12, allowing 0 to be in the list of numbers. There can be no more (nor fewer) ways of doing this than of putting 7 numbers together, among which 0 is not included, to make 19. Take every way of making 12 (0 included), and put on 1 to each number, and we get a way of making 19 (0 not included). Take any way of making 19 (0 not included), and strike off 1 from each number, and we have one of the ways of making 12 (0 included). Accordingly, 6₁₈ is the number of ways of putting together 7 numbers (0 being allowed) to make 12. And (m- 1)ₙ₊ₘ₋₁ is the number of ways of putting together m numbers to make n, 0 being included.