Example 1. From 7 Englishmen and 4 Americans a committee of 6 is to be formed: in how many ways can this be done, (1) when the committee contains exactly 2 Americans, (2) at least 2 Americans? (1) The number of ways in which the Americans can be chosen is 4C2; and the number of ways in which the Englishmen can be chosen is 7C4. Each of the first groups can be associated with each of the second; hence the required number of ways =1C2 × 7C1 (2) We shall exhaust all the suitable combinations by forming all the groups containing 2 Americans and 4 Englishmen; then 3 Americans and 3 Englishmen; and lastly 4 Americans and 2 English men. The sum of the three results will give the answer. Hence the required number of ways=4C2 x 7С4+*Сg × 7C3 +1C4×7C2 3 =210+140+21=371. In this example we have only to make use of the suitable formulæ for combinations, for we are not concerned with the possible arrangements of the members of the committee among themselves. Example 2. Out of 7 consonants and 4 vowels, how many words can be made each containing 3 consonants and 2 vowels? The number of ways of choosing the three consonants is 7C, and the number of ways of choosing the 2 vowels is 4C2; and since each of the first groups can be associated with each of the second, the number of combined groups, each containing 3 consonants and 2 vowels, is 7C, x4C2• Further, each of these groups contains 5 letters, which may be arranged among themselves in 15 ways. Hence EXAMPLES XXXVII. a. 1. Find the value of 5P4, "P, 8C5, 25C23 2. How many different arrangements can be made by taking (1) five (2) all of the letters of the word soldier? 3. If "C: n-1C1=8 : 5, find n. 4. How many different selections of four coins can be made from a bag containing a dollar, a half-dollar, a quarter, a florin, a shilling, a franc, a dime, a sixpence and a penny? 5. How many numbers between 3000 and 4000 can be made with the digits 9, 3, 4, 6? 6. In how many ways can the letters of the word volume be arranged if the vowels can only occupy the even places? 7. If the number of permutations of n things four at a time is fourteen times the number of permutations of n-2 things three at a time, find n. 8. From 5 teachers and 10 boys how many committees can be selected containing 3 teachers and 6 boys? 9. If 20C=20Cr-10, find "C12, 18 C,. 10. Out of the twenty-six letters of the alphabet in how many ways can a word be made consisting of five different letters two of which must be a and e? 11. How many words can be formed by taking 3 consonants and 2 vowels from an alphabet containing 21 consonants and 5 vowels? 12. A stage will accommodate 5 passengers on each side: in how many ways can 10 persons take their seats when two of them remain always upon one side and a third upon the other? 372. Hitherto, in the formulæ we have proved, the things have been regarded as unlike. Before considering cases in which some one or more sets of things may be like, it is necessary to point out exactly in what sense the words like and unlike are used. When we speak of things being dissimilar, different, unlike, we imply that the things are visibly unlike, so as to be easily distinguishable from each other. On the other hand we shall always use the term like things to denote such as are alike to the eye and cannot be distinguished from each other. For instance, in Ex. 2, Art. 371, the consonants and the vowels may be said each to consist of a group of things united by a common characteristic, and thus in a certain sense to be of the same kind; but they cannot be regarded as like things, because there is an individuality existing among the things of each group which makes them easily distinguishable from each other. Hence, in the final stage of the example we considered each group to consist of five dissimilar things and therefore capable of 5 arrangements among themselves. [Art. 367, Cor.] Р 373. To find the number of ways in which n things may be arranged among themselves, taking them all at a time, when of the things are exactly alike of one kind, q of them exactly alike of another kind, r of them exactly alike of a third kind, and the rest all different. Let there be n letters; suppose of them to be a, q of them to be b, r of them to be c, and the rest to be unlike. Let x be the required number of permutations; then if in any one of these permutations the p letters a were replaced by p unlike letters different from any of the rest, from this single permutation, without altering the position of any of the remaining letters, we could form p new permutations. Hence if this change were made in each of the x permutations, we should obtain xx jp permutations. Similarly, if the q letters b were replaced by q unlike letters, the number of permutations would be x × × 2. In like manner, by replacing the r letters c by r unlike letters, we should finally obtain xx px qxr permutations. But the things are now all different, and therefore admit of n permutations among themselves. Hence which is the required number of permutations. Any case in which the things are not all different may be treated similarly. Example 1. How many different permutations can be made out of the letters of the word assassination taken all together? We have here 13 letters of which 4 are s, 3 are a, 2 are i, and 2 Hence the number of permutations are n. 13 43 22 =13.11.10.9.8.7.3.5 =1001 × 10800=10810800. Example 2. How many numbers can be formed with the digits 1, 2, 3, 4, 3, 2, 1, so that the odd digits always occupy the odd places? The odd digits 1, 3, 3, 1 can be arranged in their four places in The even digits 2, 4, 2 can be arranged in their three places in Each of the ways in (1) can be associated with each of the ways in (2). Hence the required number= 374. To find the number of permutations of n things r at a time, when each thing may be repeated once, twice,......up to r times in any arrangement. Here we have to consider the number of ways in which r places can be filled up when we have n different things at our disposal, each of the n things being used as often as we please in any arrangement. The first place may be filled up in n ways, and, when it has been filled up in any one way, the second place may also be filled up in n ways, since we are not precluded from using the same thing again. Therefore the number of ways in which the first two places can be filled up is n x n or n2. The third place can also be filled up in n ways, and therefore the first three places in n3 ways. Proceeding in this manner, and noticing that at any stage the index of n is always the same as the number of places filled up, we shall have the number of ways in which the r places can be filled up equal to n”. 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 Hence the 5 prizes can be given away in 45, or 1024 ways. on. 375. To find for what value of r the number of combinations of n things r at a time is greatest. n-r+1 g The multiplying factor n+1 may be written which shows that it decreases as r increases. Hence as r receives the values 1, 2, 3, ......in succession, "C, is continually increased, We have to choose the greatest value of r consistent with this inequality. (1) Let n be even, and equal to 2m; then 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 (2) Let n be odd, and equal to 2m+1; then n+1 2m+2 ==m+1; 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 "Cm+1="Cm; that is, "C2+1="Cn−1; and therefore the number of combinations is greatest when the things are taken n+1 n-1 or 9 2 at a time; the result being the same in the two cases. 2 |