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 ifa,b,c,dbe the numbers of counters in the several boxes, there are 4 × 2 × 3 × 1 ×a×b×c×ddistinct 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 ofa, oraⁿ, represents the number of ways in whichacountersdifferently markedcan be distributed innboxes, 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 ofother 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, saya+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,dis unity and is struck out—or (d- 1) remains, a number 1 less thand. Hence it follows that the number of ways of makingnis2ⁿ⁻¹. 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 forminga+bas there are of formingaand then annexing to it a formation ofb; four times as many ways of forminga+b+cas there are of annexing to a formation ofaformations ofband ofc; and so on. Also, in summing numbers which make upa+b, there are ways in whichais 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. Ifabe the number of ways in whichncan be so made, andbthe number of ways in whichn+ 1 can be made, thena+bmust be the number of ways in whichn+ 2 can be made; for every way of making 12 out of odd numbers is either a way of making10 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 thenth number of this set is the number of ways (orders counting) in whichncan 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 whichmkcan be made of numbers divisible bym(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 thenth number in the first is the number of ways in whichncan be made up of numbers which, divided by 3, leave a remainder 1; and that thenth number in the second is the number of ways in whichncan 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 bymₙ the number of ways in whichmthings can be taken out ofnthings, so thatmₙ is the abbreviation for
Thenmₙ also represents the number of ways in whichm+ 1 numbers can be put together to maken+ 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 isnotincluded, 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 togethermnumbers to maken, 0 being included.
This last amounts to the solution of the following: In how many ways canncounters (undistinguishable from each other) be distributed intomboxes? And the following will now be easily proved: The number of ways of distributingcundistinguishablecounters intobboxes 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 whichm oddnumbers can be put together to maken, is the same as the number of ways in whichmeven numbers (0 included) can be put together to maken-m; and this is the number of ways in whichmnumbers (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 makenis the same as the number of combinations ofm-1 things out of ½(n-m) +m-1, or ½(n+m)-1. Unlessnandmbe 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 ofmₙ to stand for the number of ways in whichmthings may be taken out ofn. Suppose we have to take 5 out of 12: Let the 12 things be markeda, b, c, &c. and set apart one of them,a. Every collection of 5 out of the 12 either does or does not includea. 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 theother fourcan be chosen out of all buta. Consequently, 5₁₂ must be 5₁₁ + 4₁₁, and thus we prove in every case,
mₙ′ =mₙ₋₁ + (m- 1)ₙ₋₁
0ₙ andnₙ both are 1; for there is but one way of takingnone, and but one way of takingall. And againmₙ and (n-m)ₙ are the same things. And ifmbe greater thann,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 thenth row representsmₙ, the number of combinations ofmout ofn, 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 +xby actual algebraicalmultiplication, we see that the process makes the same oblique addition in the formation of the numerical multipliers of the powers ofx.
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 thebinomial theorem. If instead of 1 +xwe usex+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 sameadditions. If, before making the additions, we had always multiplied bya, 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 withp, 0, 0, &c. we should have gotp,p× 4a,p× 6a², &c. at the bottom of the several columns; and if we had written at the topx⁴,x³,x²,x, 1, we should have had all the materials for formingp(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 formingp(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 enteringq,r, andsunder their proper powers ofxin the first process, as follows
This process[65]is the one used inAppendix 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 writingx+ainstead ofxin a large class of algebraical expressions. For instance, what does 2x⁵ +x⁴ + 3x² + 7x+ 9 become whenx+ 5 is written instead ofx? The expression, made complete, is,
Answer, 2x⁵ + 51x⁴ + 520x³ + 2653x² + 6787x+ 6994.