Section 1.3 Permutations 3 eo the bai priniple that there are 3 X 4 X 5 X 2 120 possible subcommittees EXAMPLE 2c Solution.By the generalized version of the basic principle,the answer is 26.26 26·10·10.1010=175,760.000. EXAMPLE 2d onedpotse e functiater Solurion.Let the points be 1.2. Simce ut be theror for ac 1.2.it follows that there are 2 possible functions. EXAMPLE 2e In this case,there would be 26.25.24.10.9.8.7=78.624,000 possible license plates. 1.3 PERMUTATIONS cab,and since the first object in the permutation can be any of the 3.the secondo ct in the permutations. fortoth n(n-1)n-2).3.21=l different permutations of thenobjects. EXAMPLE3a How many different batting orders are possible for a baseball team consisting of 9 players? Solurion.There are9!=362.880 possible batting orders
Section 1.3 Permutations 3 Solution. We may regard the choice of a subcommittee as the combined outcome of the four separate experiments of choosing a single representative from each of the classes. It then follows from the generalized version of the basic principle that there are 3 * 4 * 5 * 2 = 120 possible subcommittees. . EXAMPLE 2c How many different 7-place license plates are possible if the first 3 places are to be occupied by letters and the final 4 by numbers? Solution. By the generalized version of the basic principle, the answer is 26 · 26 · 26 · 10 · 10 · 10 · 10 = 175,760,000. . EXAMPLE 2d How many functions defined on n points are possible if each functional value is either 0 or 1? Solution. Let the points be 1, 2, . , n. Since f(i) must be either 0 or 1 for each i = 1, 2, . , n, it follows that there are 2n possible functions. . EXAMPLE 2e In Example 2c, how many license plates would be possible if repetition among letters or numbers were prohibited? Solution. In this case, there would be 26 · 25 · 24 · 10 · 9 · 8 · 7 = 78,624,000 possible license plates. . 1.3 PERMUTATIONS How many different ordered arrangements of the letters a, b, and c are possible? By direct enumeration we see that there are 6, namely, abc, acb, bac, bca, cab, and cba. Each arrangement is known as a permutation. Thus, there are 6 possible permutations of a set of 3 objects. This result could also have been obtained from the basic principle, since the first object in the permutation can be any of the 3, the second object in the permutation can then be chosen from any of the remaining 2, and the third object in the permutation is then the remaining 1. Thus, there are 3 · 2 · 1 = 6 possible permutations. Suppose now that we have n objects. Reasoning similar to that we have just used for the 3 letters then shows that there are n(n − 1)(n − 2)··· 3 · 2 · 1 = n! different permutations of the n objects. EXAMPLE 3a How many different batting orders are possible for a baseball team consisting of 9 players? Solution. There are 9! = 362,880 possible batting orders.
4 Chapter 1 Combinatorial Analysis EXAMPLE 3b students obtain the same score. ccording to (a)How many different rankings are possible? ()re re he thehe Solution.(a)Because each ranking corre ble e are 6!possibler of th th there are(6!)()=(720)24)=17.280 possible rankings in this case. ■ EXAMPLE 3c Ms.Jones has 10 books that she is going to put on her bookshelf.Of these,4 are mathematics books.are chemistry bo KS, 2 are istory books.and is a anguage possible? books are book.Similarly,for each possible ordering of the subjects,there!possibl We shall now determine the number of permutations of a set of n objects when cer aianoftccbiciaiCndolgiheblcammcachohcrTosethisnaionstaigr EXAMPLE 3d How many different letter arrangements can be formed from the letters PEPPER? when the 's and the However,cor of th s themselves and the E's among themselve s.then the resultant arrangement would still be of the form PPEPER.That is,all 3!2!permutations rthere re c pbe leer arang
4 Chapter 1 Combinatorial Analysis EXAMPLE 3b A class in probability theory consists of 6 men and 4 women. An examination is given, and the students are ranked according to their performance. Assume that no two students obtain the same score. (a) How many different rankings are possible? (b) If the men are ranked just among themselves and the women just among themselves, how many different rankings are possible? Solution. (a) Because each ranking corresponds to a particular ordered arrangement of the 10 people, the answer to this part is 10! = 3,628,800. (b) Since there are 6! possible rankings of the men among themselves and 4! possible rankings of the women among themselves, it follows from the basic principle that there are (6!)(4!) = (720)(24) = 17,280 possible rankings in this case. . EXAMPLE 3c Ms. Jones has 10 books that she is going to put on her bookshelf. Of these, 4 are mathematics books, 3 are chemistry books, 2 are history books, and 1 is a language book. Ms. Jones wants to arrange her books so that all the books dealing with the same subject are together on the shelf. How many different arrangements are possible? Solution. There are 4! 3! 2! 1! arrangements such that the mathematics books are first in line, then the chemistry books, then the history books, and then the language book. Similarly, for each possible ordering of the subjects, there are 4! 3! 2! 1! possible arrangements. Hence, as there are 4! possible orderings of the subjects, the desired answer is 4! 4! 3! 2! 1! = 6912. . We shall now determine the number of permutations of a set of n objects when certain of the objects are indistinguishable from each other. To set this situation straight in our minds, consider the following example. EXAMPLE 3d How many different letter arrangements can be formed from the letters PEPPER? Solution. We first note that there are 6! permutations of the letters P1E1P2P3E2R when the 3P’s and the 2E’s are distinguished from each other. However, consider any one of these permutations—for instance, P1P2E1P3E2R. If we now permute the P’s among themselves and the E’s among themselves, then the resultant arrangement would still be of the form PPEPER. That is, all 3! 2! permutations P1P2E1P3E2R P1P2E2P3E1R P1P3E1P2E2R P1P3E2P2E1R P2P1E1P3E2R P2P1E2P3E1R P2P3E1P1E2R P2P3E2P1E1R P3P1E1P2E2R P3P1E2P2E1R P3P2E1P1E2R P3P2E2P1E1R are of the form PPEPER. Hence, there are 6!/(3! 2!) = 60 possible letter arrangements of the letters PEPPER.
Section 1.4 Combinations 5 In general,the same reasoning as that used in Example 3d shows that there are n ！2!·n different permutations of n objects,of which m are alike,n are alike.are alike EXAMPLE3e the United the nationalities of the players in the order in which they placed,how many outcomes are possible? Solution.There are 10！ 413121T=12,600 possible outcomes EXAMPLE 3f identical? Solution.There are 91 432=1260 different signals. ◆ 1.4 COMBINATIONS un interested n determining the number of difterent groups of r object o vled he malten bere are hu there are thus 5 43 and C- -will be counted 6 times (that is.all of the permutations ABC ACB,BAC In general,as n(n- oftem couldbe solectedrep (n-1)·(n-r+1) n! =m-r17可
Section 1.4 Combinations 5 In general, the same reasoning as that used in Example 3d shows that there are n! n1! n2! ··· nr! different permutations of n objects, of which n1 are alike, n2 are alike, . , nr are alike. EXAMPLE 3e A chess tournament has 10 competitors, of which 4 are Russian, 3 are from the United States, 2 are from Great Britain, and 1 is from Brazil. If the tournament result lists just the nationalities of the players in the order in which they placed, how many outcomes are possible? Solution. There are 10! 4! 3! 2! 1! = 12,600 possible outcomes. . EXAMPLE 3f How many different signals, each consisting of 9 flags hung in a line, can be made from a set of 4 white flags, 3 red flags, and 2 blue flags if all flags of the same color are identical? Solution. There are 9! 4! 3! 2! = 1260 different signals. . 1.4 COMBINATIONS We are often interested in determining the number of different groups of r objects that could be formed from a total of n objects. For instance, how many different groups of 3 could be selected from the 5 items A, B, C, D, and E? To answer this question, reason as follows: Since there are 5 ways to select the initial item, 4 ways to then select the next item, and 3 ways to select the final item, there are thus 5 · 4 · 3 ways of selecting the group of 3 when the order in which the items are selected is relevant. However, since every group of 3—say, the group consisting of items A, B, and C—will be counted 6 times (that is, all of the permutations ABC, ACB, BAC, BCA, CAB, and CBA will be counted when the order of selection is relevant), it follows that the total number of groups that can be formed is 5 · 4 · 3 3 · 2 · 1 = 10 In general, as n(n − 1)···(n − r + 1) represents the number of different ways that a group of r items could be selected from n items when the order of selection is relevant, and as each group of r items will be counted r! times in this count, it follows that the number of different groups of r items that could be formed from a set of n items is n(n − 1)···(n − r + 1) r! = n! (n − r)! r!
6 Chapter 1 Combinatorial Analysis Notation and terminology We dfine(）forr=nby (0）=nn and say thatrepresents the umber of possible cmbinations ofnobject taken r at a time. Thusrepresents the number of diferent groups of siethat could be selected fromaset ofnobjects when the order of selection isnot considered relevant. EXAMPLE 4a Solatton.There.1 3·21 =1140 possible committees ■ EXAMPLE 4b Solurlen.As there are possible groups of 2 women.and possible gro of3mcn.it follrom the basie principle that thereare(白)）(3）= (很）}气30 p2 womcn and3am wsuppose that 2 of the men refuse to serve together.Because a total of （(2)（）=5 out of the(3）=35 possible groups of3 men contain both of the feuding men,it follows that there are 35-5=30 groups that do not contain both of the feuding men.Because there are still=10 ways to choose the 2 women,there are 30.10=300 possible committees in this case
6 Chapter 1 Combinatorial Analysis Notation and terminology We define n r , for r . n, by n r = n! (n − r)! r! and say that n r represents the number of possible combinations of n objects taken r at a time.† Thus, n r represents the number of different groups of size r that could be selected from a set of n objects when the order of selection is not considered relevant. EXAMPLE 4a A committee of 3 is to be formed from a group of 20 people. How many different committees are possible? Solution. There are 20 3 = 20 · 19 · 18 3 · 2 · 1 = 1140 possible committees. . EXAMPLE 4b From a group of 5 women and 7 men, how many different committees consisting of 2 women and 3 men can be formed? What if 2 of the men are feuding and refuse to serve on the committee together? Solution. As there are 5 2 possible groups of 2 women, and 7 3 possible groups of 3 men, it follows from the basic principle that there are 5 2 7 3 = 5 · 4 2 · 1 7 · 6 · 5 3 · 2 · 1 = 350 possible committees consisting of 2 women and 3 men. Now suppose that 2 of the men refuse to serve together. Because a total of 2 2 5 1 = 5 out of the 7 3 = 35 possible groups of 3 men contain both of the feuding men, it follows that there are 35 − 5 = 30 groups that do not contain both of the feuding men. Because there are still 5 2 = 10 ways to choose the 2 women, there are 30 · 10 = 300 possible committees in this case. . †By convention, 0! is defined to be 1. Thus, n 0 = n n = 1. We also take n i to be equal to 0 when either i < 0 or i > n.
Section 1.4 Combinations 7 EXAMPLE 4c tinguishable.How many linear orderings are there in which no two defectives are consecutive? antennas.Hence,there are least one functional antenna between any two defective ones. AIA1A1.A141A 1 functional place for at most one defective FIGURE1.1:No consecutive defectives A useful combinatorial identity is ()=(?1）+(",)1≤r≤m (4.1) binatorial objectscallit objec 1.Now,there are groups of siethat contain object 1 (since each such group is formed by selectingr-1 from the remaining n1 objects).Also,there are groups of size r that do not contain object 1.As there is a total of groups of si Equation (4.1)follows. The values are often referred to as binomial coefficients because of their prominence in the binomial theorem. The binomial theorem +-2() (4.2)
Section 1.4 Combinations 7 EXAMPLE 4c Consider a set of n antennas of which m are defective and n − m are functional and assume that all of the defectives and all of the functionals are considered indistinguishable. How many linear orderings are there in which no two defectives are consecutive? Solution. Imagine that the n − m functional antennas are lined up among themselves. Now, if no two defectives are to be consecutive, then the spaces between the functional antennas must each contain at most one defective antenna. That is, in the n − m + 1 possible positions—represented in Figure 1.1 by carets—between the n − m functional antennas, we must select m of these in which to put the defective antennas. Hence, there are n − m + 1 m possible orderings in which there is at least one functional antenna between any two defective ones. . ^ 1 ^ 1 ^ 1 . . . ^ 1 ^ 1 ^ 1 functional ^ place for at most one defective FIGURE 1.1: No consecutive defectives A useful combinatorial identity is n r = n − 1 r − 1 + n − 1 r 1 . r . n (4.1) Equation (4.1) may be proved analytically or by the following combinatorial argument: Consider a group of n objects, and fix attention on some particular one of these objects—call it object 1. Now, there are n − 1 r − 1 groups of size r that contain object 1 (since each such group is formed by selecting r − 1 from the remaining n − 1 objects). Also, there are n − 1 r groups of size r that do not contain object 1. As there is a total of n r groups of size r, Equation (4.1) follows. The values n r are often referred to as binomial coefficients because of their prominence in the binomial theorem. The binomial theorem (x + y) n = n k=0 n k xkyn−k (4.2) We shall present two proofs of the binomial theorem. The first is a proof by mathematical induction, and the second is a proof based on combinatorial considerations.