| 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.
This last amounts to the solution of the following: In how many ways can n counters (undistinguishable from each other) be distributed into m boxes? And the following will now be easily proved: The number of ways of distributing c undistinguishable counters into b boxes is (b - 1)b + c - 1, if any box or boxes may be left empty. But if there must be 1 at least in each box, the number of ways is (b - 1)c - 1; if there must be 2 at least in each box, it is (b - 1)c- b-1; if there must be 3 at least in each box, it is (b - 1)c - 2b - 1; and so on.
The number of ways in which m odd numbers can be put together to make n, is the same as the number of ways in which m even numbers (0 included) can be put together to make n-m; and this is the number of ways in which m numbers (odd or even, 0 included) can be put together to make ½(n-m). Accordingly, the number of ways in which m odd numbers can be put together to make n is the same as the number of combinations of m-1 things out of ½(n-m) + m-1, or ½(n + m)-1. Unless n and m be both even or both odd, the problem is evidently impossible.
There are curious and useful relations existing between numbers of combinations, some of which may readily be exhibited, under the simple expression of mₙ to stand for the number of ways in which m things may be taken out of n. Suppose we have to take 5 out of 12: Let the 12 things be marked a, b, c, &c. and set apart one of them, a. Every collection of 5 out of the 12 either does or does not include a. The number of the latter sort must be 5₁₁; the number of the former sort must be 4₁₁, since it is the number of ways in which the other four can be chosen out of all but a. Consequently, 5₁₂ must be 5₁₁ + 4₁₁, and thus we prove in every case,
mₙ′ = mₙ₋₁ + (m - 1)ₙ₋₁
0ₙ and nₙ both are 1; for there is but one way of taking none, and but one way of taking all. And again mₙ and (n-m)ₙ are the same things. And if m be greater than n, mₙ is 0; for there are no ways of doing it. We make one of our preceding results more symmetrical if we write it thus,
2ⁿ = 0ₙ + 1ₙ + 2ₙ + ... + nₙ