This is called the general solution of the equation, and by giving to p any positive integral value or zero, we obtain positive integral values of x and y; thus we have

p=0, 1, 2, 3,

x=6, 17, 28, 39,

y=5, 19, 33, 47,

the number of solutions being infinite.

Example 3. In how many ways can £5 be paid in half-crowns and florins? Let x be the number of half-crowns, y the number of florins; then

.9; and

Solutions are obtained by ascribing to p the values 1, 2, 3, therefore the number of ways is 9. If, however, the sum may be paid either in half-crowns or florins, p may also have the values 0 and 10. If p=0, then x=0, and the sum is paid entirely in florins; if p=10, then y=0, and the sum is paid entirely in half-crowns. Thus if zero values of x and y are admissible the number of ways is 11.

Example 4. The expenses of a party numbering 43 were £5. 14s. 6d.; if each man paid 5s., each woman 2s. 6d., and each child 1s., how many were there of each?

Let x, y, z denote the number of men, women, and children, respectively; then we have

Hence by substituting in (1), we obtain

z=5p-3.

Here p cannot be negative or zero, but may have positive integral values from 1 to 5. Thus

13x+11y=414.

4.

5. 23x+25y=915. 6. 41x+47y=2191. Find the general solution in positive integers, and the least values of x and y which satisfy the equations:

13. A farmer spends £752 in buying horses and cows; if each horse costs £37 and each cow £23, how many of each does he buy?

14. In how many ways can £5 be paid in shillings and sixpences, including zero solutions?

15. Divide 81 into two parts so that one may be a multiple of 8 and the other of 5.

16. What is the simplest way for a person who has only guineas to pay 10s. 6d. to another who has only half-crowns?

17. Find a number which being divided by 39 gives a remainder 16, and by 56 a remainder 27. How many such numbers are there?

18. What is the smallest number of florins that must be given to discharge a debt of £1. 6s. 6d., if the change is to be paid in half-crowns only?

19. Divide 136 into two parts one of which when divided by 5 leaves remainder 2, and the other divided by 8 leaves remainder 3.

20. I buy 40 animals consisting of rams at £4, pigs at £2, and oxen at £17: if I spend £301, how many of each do I buy?

21. In my pocket I have 27 coins, which are sovereigns, half-crowns or shillings, and the amount I have is £5. Os. 6d.; how many coins of each sort have I ?

H. H. A.

8

139.

CHAPTER XI.

PERMUTATIONS AND COMBINATIONS.

EACH of the arrangements which can be made by taking some or all of a number of things is called a permutation.

Each of the groups or selections which can be made by taking some or all of a number of things is called a combination.

Thus the permutations which can be made by taking the letters a, b, c, d two at a time are twelve in number, namely, ab, ac, ad, bc, bd, cd,

ba, ca, da, cb, db, dc;

each of these presenting a different arrangement of two letters. The combinations which can be made by taking the letters a, b, c, d two at a time are six in number: namely,

ab, ac, ad, bc, bd, cd;

each of these presenting a different selection of two letters.

From this it appears that in forming combinations we are only concerned with the number of things each selection contains; whereas in forming permutations we have also to consider the order of the things which make up each arrangement; for instance, if from four letters a, b, c, d we make a selection of three, such as abc, this single combination admits of being arranged in the following ways:

abc, acb, bca, bac, cab, cba,

and so gives rise to six different permutations.

140. Before discussing the general propositions of this chapter there is an important principle which we proceed to explain and illustrate by a few numerical examples.

If one operation can be performed in m ways, and (when it has been performed in any one of these ways) a second operation can then be performed in n ways; the number of ways of performing the two operations will be m x n.

If the first operation be performed in any one way, we can associate with this any of the n ways of performing the second operation: and thus we shall have n ways of performing the two operations without considering more than one way of performing the first; and so, corresponding to each of the m ways of performing the first operation, we shall have n ways of performing the two; hence altogether the number of ways in which the two operations can be performed is represented by the product

mxn.

Example 1. There are 10 steamers plying between Liverpool and Dublin; in how many ways can a man go from Liverpool to Dublin and return by a different steamer?

There are ten ways of making the first passage; and with each of these there is a choice of nine ways of returning (since the man is not to come back by the same steamer); hence the number of ways of making the two journeys is 10 × 9, or 90.

This principle may easily be extended to the case in which there are more than two operations each of which can be performed in a given number of ways.

Example 2. Three travellers arrive at a town where there are four hotels; in how many ways can they take up their quarters, each at a different hotel?

The first traveller has choice of four hotels, and when he has made his selection in any one way, the second traveller has a choice of three; therefore the first two can make their choice in 4 x 3 ways; and with any one such choice the third traveller can select his hotel in 2 ways; hence the required number of ways is 4 × 3 × 2, or 24.

141. To find the number of permutations of n dissimilar things taken r at a time.

This is the same thing as finding the number of ways in which we can fill up r places when we have n different things at our disposal.

The first place may be filled up in n ways, for any one of the things may be taken; when it has been filled up in any one o

these ways, the second place can then be filled up in n - 1 ways; and since each way of filling up the first place can be associated with each way of filling up the second, the number of ways in which the first two places can be filled up is given by the product n (n-1). And when the first two places have been filled up in any way, the third place can be filled up in n - 2 ways. reasoning as before, the number of ways in which three places can be filled up is n (n − 1) (n − 2).

And

Proceeding thus, and noticing that a new factor is introduced with each new place filled up, and that at any stage the number of factors is the same as the number of places filled up, we shall have the number of ways in which r places can be filled up equal to

n (n-1) (n-2)......to r factors;

and the rth factor is

n-(r-1), or n−r+1.

Therefore the number of permutations of n things taken r at a time is

COR. a time is

or

n (n-1) (n-2)......(n − r + 1).

The number of permutations of n things taken all at

It is usual to denote this product by the symbol [n, which is read "factorial n." Also n! is sometimes used for n.

142. We shall in future denote the number of permutations of n things taken r at a time by the symbol "P,, so that

In working numerical examples it is useful to notice that the suffix in the symbol "P, always denotes the number of factors in the formula we are using.

143. The number of permutations of n things taken at a time may also be found in the following manner.

Let "P, represent the number of permutations of n things taken rat a time.