APPENDIX X. ON COMBINATIONS.

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ₙ

If we now write down the table of symbols in which the (m + 1)th

number of the nth row represents mₙ, the number of combinations of m out of n, we see it proved above that the law of formation of this table is as follows: Each number is to be the sum of the number above it and the number preceding the number above it. Now, the first row must be 1, 1, 0, 0, 0, &c. and the first column must be 1, 1, 1, 1, &c. so that we have a table of the following kind, which may be carried as far as we please: