The position of the pitcher can be filled in 5 ways, and with each of these there is a choice of 3 catchers. Hence the two positions together can be filled in 5 × 3 = 15 ways.

Fundamental Principle. If one act can be done in A ways and a second act in B ways, the total number of ways in which the two acts may be performed in succession is A.B.

The following theorem is a generalization of the fundamental principle.

Theorem. If one act can be done in A ways, a second in B ways, a third in C ways, and so on, they can all be done together in the order stated in A.B.C. ways.

EXERCISES

1. If two coins are tossed, in how many ways can they fall? 2. If two dice are thrown, in how many ways can they fall?

3. A committee of three is chosen from seven physicians, eight lawyers, and twelve business men, so that each group is represented. In how many ways can the committee be chosen?

4. If two dice and three coins are tossed, in how many ways can they fall?

132. Permutations. DEFINITION. Each arrangement which can be made of all or part of a number of things is called a permutation.

Thus the permutations of the letters a, b, c, taken three at a time are abc, acb, bac, bca, cab, cba, and their permutations taken two at a time are ab, ba, ac, ca, bc, cb.

The number of permutations of n different things taken r at a time is denoted by Pr.

Theorem. The number of permutations of n things taken r at a time is

nPrn(n - 1) (n-2)... (nr + 1).

There are r places to fill and n things from which to choose. For the first place there is a choice of n things. The second place can be filled with any one of the remaining n 1 things. The third can be filled in n 2 ways, and so on. For the rth place there is a choice of n (r-1) or nr + 1

things.

Corollary. The number of permutations of n things taken all at a time is

nPn = n(n − 1) (n − 2) 2 x 1 = n!

The symbol n! is read factional n, and represents the product of all the integers from 1 to n inclusive.

EXAMPLE. (a) In how many ways can the letters of the word triangle be arranged? (b) How many of the arrangements will begin with the letters tri in this order? (c) How many arrangements will have the letters tri together in any order? (d) How many arrangements consisting of three letters can be made from the word triangle?

=

(a) Here n = 8 and r 8, and hence the number of arrangements is 8! = 40,320.

=

(b) The first three places are filled and there remain five letters to be permutated in five places, hence the number of arrangements is 5P5

=

120.

(c) The letters tri can be permuted as a group with the remaining five letters, and then the three letters tri be permuted within their own group. Hence the number of arrangements is P3 × 6P6 3! 6! = 4320.

=

(d) Here n 8 and r = 3; hence the number of arrangements is §P3 =

=

8 x 7 x 6 = 336.

8

EXERCISES

1. In how many ways can five flags of different colors be arranged five in a line? Three in a line?

2. How many arrangements of all the letters of the word English will begin with a vowel, and end with a consonant? How many will have the

vowels together?

3. How many different numbers less than 1000 can be formed from the digits 1, 2, 3, 4, 5, 6?

4. In how many ways may first and second prizes be awarded, if there are 12 competitors in a race?

133. Combinations. DEFINITION. A group of things which is independent of the order of the elements is called a combination.

The combinations of a, b, c, taken two at a time are ab, ac, bc.

The selection ba is a different permutation from ab, but the same combination.

The six permutations of the letters abc taken three at a time, namely, abc, acb, bac, bca, cab, cba are different arrangements of one combination.

The number of combinations of n things taken r at a time is denoted by Cr.

Theorem 1. The number of combinations of n things taken r at a time is

Each combination of r things chosen from the n things can be arranged in r! ways.

Therefore all the combinations can be arranged in r!,C, ways. But this is the number of ways in which n things taken r at a time can be arranged, so that

Theorem 2. The number of combinations of n things taken r at a time is the same as the number of combinations of n things taken n r at a time.

Multiplying numerator and denominator of the formula for C, by (nr)! we have

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

n!
r!(nr)!'

By Theorem 1, we have

nCn-r =

r!(nr)!

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

=

(nr)!

EXAMPLE 1. A committee of 5 is to be chosen from 7 lawyers and 6 physicians. How many committees will contain (a) just 3 lawyers (b) at least 3 lawyers?

(a) The number of ways of selecting three lawyers is

Hence the number of committees which will contain exactly three lawyers is

(b) At least three lawyers are present in each committee of the types: 3 lawyers and 2 physicians, 4 lawyers and 1 physcian, and 5 lawyers. Hence the number of committees which contain at least three lawyers is

7C3 × 6C2 +7C4 × 6C1 +7 C5 = 756.

EXAMPLE 2. How many arrangements can be made consisting of two vowels and three consonants chosen from the letters of the word triangle? The vowels may be selected in C2 = 3 ways.

The consonants may be selected in C3 = 10 ways.

Hence the total number of selections consisting of two vowels and three consonants is 3C2 X 5C3 = 30.

Each of these selections can be arranged in 5! ways. Hence the required number of arrangements is 5! 3С2 × 5С5 = 3600.

EXERCISES

1. How many alloys can be made from thirty of the known metals chosen two at a time counting one alloy only for each pair of metals? Solve the problem if there are three metals in each alloy.

2. In how many ways can a basket ball team be selected from 9 candidates? If A plays center in every combination, in how many ways can the team be chosen?

3. How many arrangements can be made of 3 vowels and 4 consonants chosen from 5 vowels and 8 consonants?

4. How many straight lines are determined by (a) 5 points no 3 of which are in the same straight line? (b) n points, no 3 of which are in the same straight line?

5. In how many ways can a baseball nine be chosen from 13 candidates, provided A, B, C, D are the only battery candidates, and can play in no other position?

6. In how many ways can a committee of 5 be chosen from 7 democrats and 7 republicans, so that there will be (a) three democrats, (b) no more than three democrats, (c) at least three democrats on the committee?

134. The Binomial Expansion. In finding the product of the binomial factors (x + α1)(x + α2) (x + as), each partial product is obtained by choosing one and only one term from each factor and multiplying the three terms together. The sum of the partial products gives the desired product.

There is only one term containing x3, since the three x's can be chosen from the three factors in but one way.

The terms of the product containing x2 are obtained by choosing x from two of the factors and an a from the third factor, which gives the partial products x2a1, x2α2, x2α3. The number of such terms will be the number of ways we can choose an a from the three a's, or 3C1.

To obtain the term in x, we choose an x from one binomial and two a's from the two remaining in all possible ways, which gives the partial products rа1а2, Xа1αз, Xа2A3.

such products is therefore 3C2.

The number of

There is only one way of choosing the three a's.
Hence,

(x + a)3 = x3 + 3ax2 + 3a2x + a3.

And since, from the preceding, the coefficient of x2 is the number of ways we can choose an a from the three a's, the coefficient of x is the number of ways we can choose two a's out of three a's, and so on, we can write the expansion in the form

(x + a)3 = x3 + 3С1ax2 + 3C2α2x + 3Ñ3a3.

In a similar manner it can be shown that when n is a positive integer, we have