2 Chapter 1 Combinatorial Analysis The basic principle of counting Suppose that two experiments are to be performed.Then if experiment 1 can result in any one of m possible outcomes and if,for each outcome of experiment 1,there are n possible outcomes of experiment 2,then together there are mn possible out- comes of the two experiments. Proof of the Basic Principle:The basic principle may be proven by enumerating all the possible outcomes of the two experiments;that is. (11).(1.2. ,(1,)） (21),(2,2),,(2,n) (m,1),0m,2),,0m,n) where we say that the outcome is(i,))if experiment 1 results in its ith possible out then results in its jth possible outcome.Hence,the set of e outcomes consists of m rows,each containing nelements.This proves the EXAMPLE 2a A small community consists of 10 women.each of whom has 3 children.If one woman and one of her children are to be chosen as mother and child of the year,how many different choices are possible? Solution.By regarding the choice of the as the out e of the first experi ch When there are more than two experiments to b performed,the basic principle can be generalizec The generalized basic principle of counting Ifrexperiments that are to be performed are such that the first one may result in any of m possible outcomes;and if,for each of these n possible outcomes,there are n2 possible outcomes of the second experiment;and if,for each of the possible outcomes of the first two experiments,there are n3 possible outcomes of the third experiment;and if...,then there is a total of n.n2...n possible outcomes of the r experiments. EXAMPLE 2b A college planning committee consists of 3 freshmen,4 sophomores,5 juniors,and 2 seniors.A subcommittee of 4,consisting of 1 person from each class,is to be chosen. How many different subcommittees are possible?
2 Chapter 1 Combinatorial Analysis The basic principle of counting Suppose that two experiments are to be performed. Then if experiment 1 can result in any one of m possible outcomes and if, for each outcome of experiment 1, there are n possible outcomes of experiment 2, then together there are mn possible outcomes of the two experiments. Proof of the Basic Principle: The basic principle may be proven by enumerating all the possible outcomes of the two experiments; that is, (1, 1), (1, 2), ... , (1, n) (2, 1), (2, 2), ... , (2, n) # # # (m, 1), (m, 2), ... , (m, n) where we say that the outcome is (i, j) if experiment 1 results in its ith possible outcome and experiment 2 then results in its jth possible outcome. Hence, the set of possible outcomes consists of m rows, each containing n elements. This proves the result. EXAMPLE 2a A small community consists of 10 women, each of whom has 3 children. If one woman and one of her children are to be chosen as mother and child of the year, how many different choices are possible? Solution. By regarding the choice of the woman as the outcome of the first experiment and the subsequent choice of one of her children as the outcome of the second experiment, we see from the basic principle that there are 10 * 3 = 30 possible choices. . When there are more than two experiments to be performed, the basic principle can be generalized. The generalized basic principle of counting If r experiments that are to be performed are such that the first one may result in any of n1 possible outcomes; and if, for each of these n1 possible outcomes, there are n2 possible outcomes of the second experiment; and if, for each of the possible outcomes of the first two experiments, there are n3 possible outcomes of the third experiment; and if ..., then there is a total of n1 · n2 ··· nr possible outcomes of the r experiments. EXAMPLE 2b A college planning committee consists of 3 freshmen, 4 sophomores, 5 juniors, and 2 seniors. A subcommittee of 4, consisting of 1 person from each class, is to be chosen. How many different subcommittees are possible?
Section 1.3 Permutations 3 Solution.We may regard the choice of a subcommittee as the combined outcome of the four eriments of choosin esentative fr m each of the are3×4×5×2=120 possible subcommittees. EXAMPLE 2e 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 onn points are possible if cach functional value is cither Solution. Let be1,2 .n.Since ef(i)must be either 0 or 1 for each i EXAMPLE 2 many license plates would be possible if repetition among letters prohibited? Solut this ,there would be26·25·24·10·9·8·7=78,624,000 poss ense 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 of3 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(0n-1)0n-2)…3.2·1=nl 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. ◆
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 tion is given, and according to their performance.Assume that no two (a)How many different rankings are possible? (b)If the men are ranked just among themselves and the women just among them- selves.how many different rankings are possible? (a)Because each ranking corespondstoaparticular ordered arrangem of the 10 pe cople,the a swer to this part is 1 re are 6!pos kings of the men among t emselves and 4!po basic principle th there are (6!) =(72024 e w 41 this case EXAMPLE 3c mathemate boor hemy re mstory hook duge 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 arrangemen e,as there are 4!possible orderings of the subjects,the desired We shall now determine the number of permu tations of a set of n objects when cer tain of the nour minds.consider the folls owing example EXAMPLE3d How many different letter arrangements can be formed from the letters PEPPER? Solution.We first note that there when the 3Ps and the 2Es are disti any one of these permutations .However.o rmutations of the letters ino -for instance,PP2EP3E2R.If we now permute the wold r he tom故eS，分men PIP2E1P3ER PiP2EP3E1R PIP3EP2ER PP3E2P2ER P2P EP3E2R P2PE2P3ER P2P3EP E2R P2P3E2P ER P3PEP2E2R P3P2E1P1E2R P3P2E2P1E1R are of the form PPEPER.Hence,there are 6!/(3!2!)=60 possible letter arrange. ments of the letters PePPER
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! nl2!…nl different permutations of n objects,of which n are alike,n2 are alike,....n are alike. EXAMPLE 3e of which 4are Russian,3 are from the United om If the tou ament result lists jus the nati Solution.There are 101 403121T=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 41312=1260 different signals. 1.4 COMBINATIONS We are often interested in determining the number of different groups ofobjects that could be Io fnobjects.For instance.how many differen groups of 3 could the tems A.B D anc wer thi on as I initia ways to nem,an ys to ect there are thus e group of 3 em. e order nd c unted 6 times (that is all of the ABO ACR RAC 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 32.7=10 as n(n 1)represents the num er of different ways that a e se when the o er c n is re and r items in this s that n(n-1)…(m-r+1) n! (n -r)!r!
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 define(r）forr≤nby (C）=an n! and say that(） represents the number of possible combinations of n object taken r at a time. Thus.represents the number of different groups of could be selected from a set ofn 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? Salaien.There are1140 posible commites ■ EXAMPLE 4b ees co e men are serve on the e comm Solution.As there are possible groups of 2 women.and possible groups of 3 men,it follows from the basie principle that there are =350 possible committees consisting of 2 women and 3 men. suppose that 2 of the men refuse to serve together.Because a total of =5 out of the=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?=10 ways to choose the 2 women,there are 30.10=300 possible committees in this case. By convention..dedtobe.ms(8）=(日）=L.We alko take(t）tobeequ to0when eitheri <0ori>n
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.