Elements of arithmetic

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

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.

This table exhibits the ways of making 1, 2, 3, and 4. Hence it follows (which I leave the reader to investigate) that there are twice as many ways of forming a + b as there are of forming a and then annexing to it a formation of b; four times as many ways of forming a + b + c as there are of annexing to a formation of a formations of b and of c; and so on. Also, in summing numbers which make up a + b, there are ways in which a is a rest, and ways in which it is not, and as many of one as of the other.

Required the number of ways in which a number can be compounded of odd numbers, different orders counting as different ways. If a be the number of ways in which n can be so made, and b the number of ways in which n + 1 can be made, then a + b must be the number of ways in which n + 2 can be made; for every way of making 12 out of odd numbers is either a way of making 10 with the last number increased by 2, or a way of making 11 with a 1 annexed. Thus, 1 + 5 + 3 + 3 gives 12, formed from 1 + 5 + 3 + 1 giving 10. But 1 + 9 + 1 + 1 is formed from 1 + 9 + 1 giving 11. Consequently, the number of ways of forming 12 is the sum of the number of ways of forming 10 and of forming 11. Now, 1 can only be formed in 1 way, and 2 can only be formed in 1 way; hence 3 can only be formed in 1 + 1 or 2 ways, 4 in only 1 + 2 or 3 ways. If we take the series 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, &c. in which each number is the sum of the two preceding, then the nth number of this set is the number of ways (orders counting) in which n can be formed of odd numbers. Thus, 10 can be formed in 55 ways, 11 in 89 ways, &c.

Shew that the number of ways in which mk can be made of numbers divisible by m (orders counting) is 2ᵏ⁻¹.

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

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,

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

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ₙ

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:

Thus, in the row 9, under the column headed 4, we see 126, which is 9 × 8 × 7 × 6 ÷ (1 × 2 × 3 × 4), the number of ways in which 4 can be chosen out of 9, which we represent by 4-{9}.

If we add the several rows, we have 1 + 1 or 2, 1 + 2 + 1 or 2², next 1 + 3 + 3 + 1 or 2³, &c. which verify a theorem already announced; and the law of formation shews us that the several columns are formed thus:

so that the sum in each row must be double of the sum in the preceding. But we can carry the consequences of this mode of formation further. If we make the powers of 1 + x by actual algebraical multiplication, we see that the process makes the same oblique addition in the formation of the numerical multipliers of the powers of x.

• 1 + x
• 1 + x
• 1 + x
• x + x²
• 1 + 2x + x²
•  
• 1 + 2x +   x²
• 1 +   x
• 1 + 2x +   x²
• x + 2x² + x³
• 1 + 3x + 3x² + x³

Here are the second and third powers of 1 + x: the fourth, we can tell beforehand from the table, must be 1 + 4x + 6x² + 4x³ + x⁴; and so on. Hence we have

(1 + x)ⁿ = 0ₙ + 1ₙx + 2ₙx² + 3ₙx³ + ... + nₙxⁿ

which is usually written with the symbols 0ₙ, 1ₙ, &c. at length, thus,

This is the simplest case of what in algebra is called the binomial theorem. If instead of 1 + x we use x + a, we get

(x + a)ⁿ = xⁿ + 1ₙaxⁿ⁻¹ + 2ₙa²xⁿ⁻² + 3ₙa³xⁿ⁻³ + ... + nₙaⁿ

We can make the same table in another form. If we take a row of ciphers beginning with unity, and setting down the first, add the next, and then the next, and so on, and then repeat the process with one step less, and then again with one step less, we have the following:

In the oblique columns we see 1 1, 1 2 1, 1 3 3 1, &c. the same as in the original table, and formed by the same additions. If, before making the additions, we had always multiplied by a, we should have got the several components of the powers of 1 + a, thus,

where the oblique columns 1 + a, 1 + 2a + a², 1 + 3a + 3a² + a³, &c., give the several powers of 1 + a. If instead of beginning with 1, 0, 0, &c. we had begun with p, 0, 0, &c. we should have got p, p × 4a, p × 6a², &c. at the bottom of the several columns; and if we had written at the top x⁴, x³, x², x, 1, we should have had all the materials for forming p(x + a)⁴ by multiplying the terms at the top and bottom of each column together, and adding the results.

Suppose we follow this mode of forming p(x + a)³ + q(x + a)² + r(x + a) + s.

px³ + 3pax² + 3pa²x + pa³ + qx² + 2qax + qa² + rx + ra + s

= px³ + (3pa + q)x² + (3pa² + 2qa + r)x + pa³ + qa² + ra + s

Now, observe that all this might be done in one process, by entering q, r, and s under their proper powers of x in the first process, as follows

This process[65] is the one used in Appendix XI., with the slight alteration of varying the sign of the last letter, and making subtractions instead of additions in the last column. As it stands, it is the most convenient mode of writing x + a instead of x in a large class of algebraical expressions. For instance, what does 2x⁵ + x⁴ + 3x² + 7x + 9 become when x + 5 is written instead of x? The expression, made complete, is,

Answer, 2x⁵ + 51x⁴ + 520x³ + 2653x² + 6787x + 6994.