Page images
PDF
EPUB

Example. In how many ways can 5 prizes be given away to 4 boys, when each boy is eligible for all the prizes?

Any one of the prizes can be given in 4 ways; and then any one of the remaining prizes can also be given in 4 ways, since it may be obtained by the boy who has already received a prize. Thus two prizes can be given away in 42 ways, three prizes in 43 ways, and so on. Hence the 5 prizes can be given away in 45, or 1024 ways.

153. To find the total number of ways in which it is possible to make a selection by taking some or all of n things.

Each thing may be dealt with in two ways, for it may either be taken or left; and since either way of dealing with any one thing may be associated with either way of dealing with each one of the others, the number of ways of dealing with the n things is

2 × 2 × 2 × 2......to n factors.

But this includes the case in which all the things are left, therefore, rejecting this case, the total number of ways is 2′′ −1. This is often spoken of as "the total number of combinations" of n things.

Example. A man has 6 friends; in how many ways may he invite one or more of them to dinner?

He has to select some or all of his 6 friends; and therefore the number of ways is 26-1, or 63.

This result can be verified in the following manner.

The guests may be invited singly, in twos, threes,......; therefore the number of selections =6C1+°C 2+6C3+°С 4+°С5+ °C 6

154.

=6+15+20+15+6+1=63.

To find for what value of r the number of combinations of n things r at a time is greatest.

[merged small][merged small][merged small][merged small][merged small][merged small][merged small][merged small][merged small][merged small][merged small][merged small][merged small][merged small][merged small][merged small][merged small][ocr errors][ocr errors][merged small]

which shews that it decreases as r increases. Hence as r receives

n−r+1

may be written

n+1

[ocr errors]

the values 1, 2, 3...... in succession, "C, is continually increased

[merged small][merged small][ocr errors][merged small][merged small][merged small][merged small][merged small][ocr errors][merged small][merged small][merged small][merged small][merged small][merged small][merged small]

We have to choose the greatest value of r consistent with this inequality.

(1) Let n be even, and equal to 2m; then

[blocks in formation]

and for all values of r up to m inclusive this is greater than r.

n
2'

Hence by putting r = m = we find that the greatest number of combinations is "C..

n

2

(2) Let n be odd, and equal to 2m + 1; then

[blocks in formation]

and for all values of r up to m inclusive this is greater than r; but when r = m + 1 the multiplying factor becomes equal to 1, and "C+"C; that is, "C.

=

[ocr errors]

and therefore the number of combinations is greatest when the

[blocks in formation]

155. The formula for the number of combinations of n things r at a time may be found without assuming the formula for the number of permutations.

Let "C, denote the number of combinations of n things taken r at a time; and let the n things be denoted by the letters a, b, c, d,....

711

Take away a; then with the remaining letters we can form -1C combinations of n-1 letters taken r - 1 at a time. With each of these write a; thus we see that of the combinations of n things r at a time, the number of those which contain a is "C; similarly the number of those which contain b is "-C -1; and so for each of the n letters.

n-1

Therefore n "'C_ is equal to the number of combinations r at a time which contain a, together with those that contain b, those that contain c, and so on.

But by forming the combinations in this manner, each particular one will be repeated r times. For instance, if r3, the combination abc will be found among those containing a, among those containing b, and among those containing c.

Hence

[merged small][ocr errors][ocr errors][merged small][ocr errors][ocr errors][merged small][merged small][merged small][merged small][merged small][ocr errors][merged small][ocr errors][ocr errors][merged small][merged small][merged small][merged small][merged small][merged small][merged small][merged small][merged small][merged small][merged small][merged small][merged small][merged small][ocr errors][merged small][subsumed][merged small][merged small][subsumed][merged small][merged small]

Multiply together the vertical columns and cancel like factors from each side; thus

156.

[ocr errors][merged small][merged small]

To find the total number of ways in which it is possible to make a selection by taking some or all out of p+q+r+ things, whereof p are alike of one kind, q alike of a second kind, r alike of a third kind; and so on.

The p things may be disposed take 0, 1, 2, 3, p of them. disposed of in q+1 ways; the

so on.

H. H. A.

......

of in Ρ + 1 ways; for we may Similarly the q things may be r things in r+1 ways; and

9

Hence the number of ways in which all the things may be disposed of is (p + 1) (g + 1) (r + 1) ......

But this includes the case in which none of the things are taken; therefore, rejecting this case, the total number of ways is

[blocks in formation]

157.

A general formula expressing the number of permutations, or combinations, of n things taken r at a time, when the things are not all different, may be somewhat complicated; but a particular case may be solved in the following manner.

Example. Find the number of ways in which (1) a selection, (2) an arrangement, of four letters can be made from the letters of the word proportion.

There are 10 letters of six different sorts, namely o, o, o; p,p; r, r; t; i; n. In finding groups of four these may be classified as follows:

(1) Three alike, one different.

(2) Two alike, two others alike.

(3) Two alike, the other two different.
(4) All four different.

(1) The selection can be made in 5 ways; for each of the five letters, p, r, t, i, n, can be taken with the single group of the three like letters o.

(2) The selection can be made in 3C, ways; for we have to choose two out of the three pairs o, o; P, p; r, r. This gives 3 selections.

(3) This selection can be made in 3 x 10 ways; for we select one of the 3 pairs, and then two from the remaining 5 letters. This gives 30 selections. (4) This selection can be made in 6C ways, as we have to take 4 different letters to choose from the six o, p, r, t, i, n. This gives 15 selections.

4

Thus the total number of selections is 5 +3+30+15; that is, 53.

In finding the different arrangements of 4 letters we have to permute in all possible ways each of the foregoing groups.

[blocks in formation]

(4) gives rise to 15 × 14, or 360 arrangements.

Thus the total number of arrangements is 20+18+360+360; that is, 758,

EXAMPLES. XI. b.

1. Find the number of arrangements that can be made out of the letters of the words

[blocks in formation]

2. In how many ways can 17 billiard balls be arranged, if 7 of them are black, 6 red, and 4 white?

3. A room is to be decorated with fourteen flags; if 2 of them are blue, 3 red, 2 white, 3 green, 2 yellow, and 2 purple, in how many ways can they be hung?

4. How many numbers greater than a million can be formed with the digits 2, 3, 0, 3, 4, 2, 3?

5. Find the number of arrangements which can be made out of the letters of the word algebra, without altering the relative positions of vowels and consonants.

6. On three different days a man has to drive to a railway station, and he can choose from 5 conveyances; in how many ways can he make the three journeys ?

7. I have counters of n different colours, red, white, blue,......; in how many ways can I make an arrangement consisting of r counters, supposing that there are at least r of each different colour?

8. In a steamer there are stalls for 12 animals, and there are cows, horses, and calves (not less than 12 of each) ready to be shipped; in how many ways can the shipload be made?

9. In how many ways can n things be given to p persons, when there is no restriction as to the number of things each may receive? 10. In how many ways can five things be divided between two persons?

11. How many different arrangements can be made out of the letters in the expression a3b24 when written at full length?

12. A letter lock consists of three rings each marked with fifteen different letters; find in how many ways it is possible to make an unsuccessful attempt to open the lock.

13. Find the number of triangles which can be formed by joining three angular points of a quindecagon.

14. A library has a copies of one book, b copies of each of two books, c copies of each of three books, and single copies of d books. In how many ways can these books be distributed, if all are out at once?

15. How many numbers less than 10000 can be made with the eight digits 1, 2, 3, 0, 4, 5, 6, 7 ?

16. In how many ways can the following prizes be given away to a class of 20 boys: first and second Classical, first and second Mathematical, first Science, and first French?

« PreviousContinue »