73

CHAPTER X.

PERMUTATIONS AND COMBINATIONS.

80. Permutations denote the different orders in which any quantities may be arranged; Combinations denote the different collections that may be formed out of them, without regard to the order in which they are placed. Thus ab and ba form different permutations, but only one combination.

81. If there be n things, a, b, c, d, &c., then, by taking them one by one, the number of permutations formed will be n. By placing a before each of the other (n-1) things, there will be (n-1) permutations with a standing first; also in like manner (n-1) with b standing first; and so on for the whole n quantities. Hence there are

n(n-1) permutations taken two together.

Suppose a to be removed, there are (n-1) things remaining, and of these there are

(n − 1) (n — 2) permutations taken two together. By prefixing a to each of these, there will be

(n-1) (n-2) permutations of three with a standing first; and similarly (n-1) (n-2) with b standing first; and so on for each of the n quantities. There are therefore

n(n-1) (n-2) permutations taken three together.

Pr

Collecting these results, and taking P1, P2, P3,... P to denote the numbers of permutations of n things taken 1, 2, 3,...r, together respectively, we get

P = n(n − 1) (n − 2) (n − 3) (n — 4);

5

and hence we may infer, that generally

Pr = n(n − 1) (n − 2) (n − 3) . . (n − r + 1).

82. Assuming that this law holds true when (r-1) things are taken together, then

true that the number of permutations of the remaining (n − 1) things taken (-1) together, is

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

...

found by putting (n-1) for n in the preceding equation.

Now, by prefixing a to each of these last permutations, their number would remain the same, but there would be r taken together instead of r — 1.

In like manner it may be shown that the same number of permutations may be formed of these n things taken r together, in which b stands first, and so on for each of the others. If therefore

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

it follows that

Pr = n(n − 1) (n − 2) (n − 3) . . . (n−r + 1).

—

=

But it has 3; therefore

That is, if the assumed law be true for any one value of r, it must be true for the next higher value. been proved to hold true when r= 2, and r = it is true when r : 4, and if true for 4, then also for 5; and so on for any number.

If rn, the last factor in the above formula becomes 1, therefore denoting the number of permutations of n things taken altogether by Pn, we have

or

Pn = n(n − 1) (n − 2) . . 3. 2. 1,

=1.2.3.4

n.

EXERCISES.

(1.) Find the number of permutations of 8 things taken 2 together, 3 together, 4 together, and all together.

Ans. 56, 336, 1680, and 40320. (2.) In how many different ways may a party of 12 be

arranged at table?

Ans. 479001600.

(3.) The number of permutations of n things, taken 4 to- · gether 8 times the number taken 3 together; find n.

Ans. 11.

(4.) In how many ways may a class of 9 boys be arranged? Ans. 362880. (5.) In the permutations formed out of the eight letters a, b, c, d, e, f, g, h, taken altogether, how many begin with ab? how many with abc? and how many with abcd?

Ans. 720, 120, and 24. (6.) The number of permutations of 18 things taken r together 12 times the number taken r—1 together; find r. Ans. 7.

(7.) In how many ways can 8 persons be seated at a round table, so that all shall not have the same neighbours twice? Ans. 2520.

(8.) Find the number of changes which can be rung with a peal of 7 bells, and what difference will be made in the number by the absence of one ringer? Ans. 5040, & 4320.

83. Again, let C1, C2, C3 .. Cr, denote the number of combinations of n things taken 1 by 1, 2 by 2, 3 by 3 . . . r by r together;

then it is evident that C1 =n.

And since each combination of 2 things, as ab, admits of 2 permutations, ab, and ba, it follows that

Similarly, since each combination of 3 things admits of 3.2.1 permutations,

And, generally, since each combination of r things admits of 1.2.3... r permutations,

84. On examining this last formula, it will be observed that the number of factors is the same in the numerator and denominator of the second member, and in both is always =r, the number of things taken together.

n

85. Also, since of n things if r be taken, there will be

r remaining; for every combination of r things, there will always be another of n-r things remaining: hence

(1.) Find the number of combinations of 12 things taken 2 together, 3 together, and 6 together.

Ans. 190.

Ans. 66, 220, and 924. (2.) Find the number of combinations of 20 things taken 18 together. (3.) Find the number of combinations of 50 things taken 4 together, 10 together, 40 together, and 46 together. Ans. 230300, and 10272278170. (4.) How many different hands may a person hold at the game of whist? Ans. 635013559600. (5.) How many combinations may be formed of the letters in the word "Equations" taken 5 together? and in how many of them will the first letter E occur?

Ans. 126, and 70. (6.) From a company of 30 soldiers, 5 are selected every day to act as sentinels; on how many days may a different selection be made? and on how many of these will any particular man be on duty? Ans. 142506 days, and 23751.

(7.) An innkeeper engaged to provide a dinner every day for 6 persons, to be selected out of a party of 12, so long as the same 6 should not meet twice; what would be the amount of his bill at half-a-crown each per day?

Ans. £693. (8.) How many different sums may be formed with a sovereign, a half-sovereign, a crown, a half-crown, a shilling, a sixpence, and a penny?

Ans. 127.

(9.) Find how many triangles may be formed by joining the angular points of a polygon of n sides.

(10.) Expand 2" in the form (1+1)", and thence prove that the total number of combinations of n things taken 1, 2, 3 ... n together 2" — 1.

=

(11.) The total number of combinations of 2 n things 33 times the total number of combinations of n things; find n. Ans. n5.

(12.) Out of a committee of 12, how many sub-committees may be formed, each consisting of not more than 8?

Ans. 3796.

(13.) Let P denote the number of permutations of n things taken all together, when some of them recur, and prove that if a recurr times; b, s times; c, t times, &c.

(14.) Find the number of permutations that can be formed from the letters of each of the following words taken all together:-Algebra, Permutations, Combinations, Susannah, Philippopolis, and Mississippi. Ans. 2520; 239500800;

119750400; 5040; 10810800; and 34650.

CHAPTER XI.

INDETERMINATE COEFFICIENTS.

86. The general principle of the method of Indeterminate Coefficients consists in assuming certain letters to express the unknown coefficients in an expression for some required quantity, the general form of which expression is known; then, according to the nature of the investigation, two expressions of the same form are found, which are rendered identical by making the coefficients of the corresponding terms equal; and by means of the series of equations thus obtained the values of the assumed coefficients are determined.