EXAMPLE 2. How many numbers can be formed with the digits 3, 2, 5, 6, 5, 2, 3, 4, so that the odd digits always occupy the odd places? The odd digits 3, 5, 5, 3, can be arranged in their four places in The even digits 2, 6, 2, 4, can be arranged in their four places in Each of the ways in (1) can be associated with each of the ways in (2). Hence, the required number of ways is 621. The number of arrangements of n things r at a time, if each thing may be repeated once, twice, rangement, is n". up to r times in any ar places can be filled up, Here the number of ways in which when there are n different things at one's disposal, and when each of then things is used as often as one pleases in any arrangement, is to be considered. The first place may be filled in n ways, and when it has been filled in any one way, the second place may also be filled in n ways, since one is not barred from using the same thing again. Hence, the first two places may be filled n×n, or n2 different ways. The third place can also be filled in n ways, and hence, the first three places can be filled in n2 × n, or n3 different ways. Since at any stage of this process the exponent of n is the same as the number of the last place filled, the number of different ways in which the places can be filled will be n". EXAMPLE.-In how many ways can the following prizes be given away to a class of 21 pupils: the first and the second Mathematical, the first and the second Classical, the first Science, and the first Spanish, if no pupil may receive a first and a second prize in the same subject? The first Mathematical prize may be given in 21 ways, and for each way the first Mathematical prize can be given, the second Mathematical prize can be given in 20 ways; hence, the first and the second Mathematical can be given in 420 ways. Similarly, the first and the second Classical can be given in 420 ways, since they may be obtained by a boy who has already received a prize. Mathematical and the Classical prizes can be given in Thus the 420 × 420 = 176400 ways; but the first Science may be given in 21 ways, and the first Spanish may be given in 21 ways. Hence, all the prizes may be given in ways. 420 × 420 × 21 × 21 = 77792400 622. How many selections can be made of n things by taking some or all of them? Each thing may be taken or left; i. e., it can be dealt with in two ways. But either way one thing is dealt with may be associated with either way each of the other things is dealt with. Therefore, the number of selections is After rejecting the case in which all the things are left and none taken, the total number of ways is In how many ways EXAMPLE.--There are 10 books on a table. can 1 or more of them be taken from the table? One must take some or all of the books; and, therefore, the number of ways is 210 1 = 1023. This result can be verified as follows: the books may be taken singly, in twos, in threes, etc.; therefore, the number of possible selections =10+ 10+ 10+...+ 10 C10 3 = 10 +45 +120 +210+252 +210+ 120 + 45 + 10+1, = 1023. PROBLEMS 1. Find the number of permutations that can be made out of the letters of the words, (1) rector, (2) oculist, (3) algorithm. 2. How many arrangements can be made out of the letters of each of the words in problem 1, taking (1) two letters at a time, (2) three letters at a time, (3) six letters at a time? 3. How many combinations can be made out of the letters of the word diplomat, taking (1) five letters at a time, (2) seven letters at a time, (3) eight letters at a time? 4. Find the number of permutations that can be made out of the letters of the words (1) phenomenon, (2) Oskaloosa, (3) concatenation. 5. Of the permutations that can be made out of the letters of the word quadrilateral, in how many will the immediately follow the d? 6. In the following equations find n: (1) 2n C'3: nC2 = 44: 3. (2) 584n+6: 544n. = 30800:1. n+3 (3) „C's = „C 7. Find the number of combinations three at a time of the letters a, b, c, d, when the letters may be repeated three times. 8. Find the number of ways n books can be arranged on a shelf so that two particular books shall not be together. 10. In how many ways may a product of m factors be formed 11. A man has four different coats, seven different vests, and five different pairs of trousers. In how many different suits may he appear? 12. How many different arrangements can be made out of the letters in the product ab c1? 13. From three cocoanuts, four apples, and two oranges, how many selections of fruit can be made, if at least one of each kind is taken? 14. If a guard of men is formed out of a company of m men, and guard duty is equally distributed, show that no two particular men will be together on guard r (r — 1) times out of m (m—1). 15. A man puts his hand in a bag containing n different things. If he may draw 0, 1, 2, or any number up to n, how many drawings can he make? 16. Find the sum of all numbers greater than 10,000 formed by using the digits 1, 3, 5, 7, 9. 17. In how many ways can 7 persons form a ring? In how many ways can 7 Englishmen and 7 Americans sit down at a round table so that no two Americans shall be together? 18. How many different sums of money can be made with the following coins: a cent, a dime, a quarter, a half-dollar, and a dollar? 19. In how many ways can five things be distributed among two persons? 20. In a lottery 5,000 tickets are issued. In how many ways may 450 tickets each win a prize? 21. How many numbers of six digits may be formed out of the numbers 0, 1, 2, 3, 4, 5, 6? 22. In how many ways may twelve balls be distributed among three boxes, so that three balls are in the first box, four balls in the second, and five balls are in the third? 23. A polygon is formed by joining points in a plane. Find the number of straight lines, not sides of the polygon, which can be drawn joining any two angular points. Solution. n 2 C number of lines which can be drawn between n points. Of these n are sides of the polygon; hence the number of diagonals is C.-n, or "(-3). n 2 n 2 24. How many lines of limited length may be formed by the intersection of n lines? 25. In how many points can n lines intersect if p of them are parallel? 26. If straight lines pass through a point A, m through B, and n through C, and no one of the straight lines contains more than one of the points, A, B, C, and no three meet in any point except A, B, or C, find how many triangles are formed by the lines. 27. Of n straight lines, p pass through one point and q through another; in how many points may all the lines intersect? 28. There are p points in a plane, no three of which are in the same straight line, with the exception of q of them, which are all in the same straight line; find the number (1) of straight lines, (2) of triangles which result from joining them (q <p). 29. How many different n-sided polygons may be formed by n straight lines in a plane? 30. The streets of a city are arranged like the lines of a chess board. There are m streets running north and south, and n east and west. Find the number of ways in which a man can travel from the northwest corner to the southeast corner, going the shortest possible distance. 31. In how many ways may 2n persons be seated at two round tables, n persons being seated at each? 32. Show that n planes through the center of a sphere, no three of which pass through the same diameter, will divide the surface of a sphere into no n + 2 parts. 33. Find the number of parts in a sphere when it is divided by a + b + c . . . planes through the center, a of the planes passing through one given diameter, b through a second, e through a third, and so on; and no plane passing through more than one of these given diameters. 1 34. Show that n straight lines, no two of which are parallel and no three of which meet in a point, divide a plane into 1⁄2 n (n + 1) + 1 parts. 35. Show that n planes, no four of which meet in a point, divide space into (n3+5n+6) different regions. 36. Find the number of combinations of 3n things, n at a time, when n of the things and no more, are alike. 37. Find the number of ways mn things can be distributed among m persons so that each person shall have n of them. cards 38. There are p suits of cards, each suit consisting of 9 numbered from 1 to q; find the number of sets of q cards numbered from 1 to q which can be made from all the suits. |