12 Chapter 1 Combinatorial Analysis Similarlyforeach resull of round1,there arepossible outcmes of round 21 and for each of the outcomes of the first two rounds,there arepossible outcomes oy by the eraid ba principle inthere are =8!possible outcomes of the tournament.Indeed,the same argument 4!21 sed to show that a knockout tournament of n=2players has n!possible the prece result,it is not difficult to con up with a mo tou nce b nd th nk the play for a result:Give the tournament winner rank 1.and g ive the final-round loser rank 2.For the two play- ers who lost in the next-to-last round.give rank 3 to the one who lost to the playe ranked 1 and give rank 4 to the one who lost to the player ranked 2.For the four players who lost in the second-to-last round,give rank 5 to the one who lost to player ranked 1,rank 6 to the one who lost to the player ranked 2,rank 7 to the one who lost to the player ranked 3,and rank 8 to the one who lost to the player ranked 4. Continuing on in this manner gives a rank to each player.(A more succinct descrip- tion is to give the winner of the tournament rank 1 and let the rank of a player who lost in a round having 2 matches be 2 plus the rank of the player who beat him,for k =0....,m -1.)In this manner,the result of the tournament can be represented by a permutation i1,i2,...,in,where ij is the player who was given rank j.Because different tournament results give rise to different permutations,and because there is a tournament result for each permutation,it follows that the ere are the same numb of possible tournament results as there are permutations of 1,....n. EXAMPLE 5e ++g2=(260)8+(a20）竭 +(0品2)486+(Lo) +(品)8+（品） =x号+号+号+2x12+213+2x2x *1.6 THE NUMBER OF INTEGER SOLUTIONS OF EQUATIONS There are possible outcomes when n distinguishable balls are to be distributed into r distinguishable urns.This result follows because each ball may be distributed into any ofr possible urns.Let us now,however,suppose that the n balls are indistinguish- able from each other.In this case,how many different outcomes are possible?As the balls are indistinguishable,it follows that the outcome of the experiment of distribut- ng the n balls into r urns can be described by a vector (x1.x2....,x).where xi denotes the number of balls that are distributed into the ith urn.Hence,the problem reduces to find hat the number of distinct nonnegative integer-valued vectors (i.x2.....x *Asterisks denote material that is optional
12 Chapter 1 Combinatorial Analysis Similarly, for each result of round 1, there are 4! 2! possible outcomes of round 2, and for each of the outcomes of the first two rounds, there are 2! 1! possible outcomes of round 3. Consequently, by the generalized basic principle of counting, there are 8! 4! 4! 2! 2! 1! = 8! possible outcomes of the tournament. Indeed, the same argument can be used to show that a knockout tournament of n = 2m players has n! possible outcomes. Knowing the preceding result, it is not difficult to come up with a more direct argument by showing that there is a one-to-one correspondence between the set of possible tournament results and the set of permutations of 1, ... , n. To obtain such a correspondence, rank the players as follows for any tournament result: Give the tournament winner rank 1, and give the final-round loser rank 2. For the two players who lost in the next-to-last round, give rank 3 to the one who lost to the player ranked 1 and give rank 4 to the one who lost to the player ranked 2. For the four players who lost in the second-to-last round, give rank 5 to the one who lost to player ranked 1, rank 6 to the one who lost to the player ranked 2, rank 7 to the one who lost to the player ranked 3, and rank 8 to the one who lost to the player ranked 4. Continuing on in this manner gives a rank to each player. (A more succinct description is to give the winner of the tournament rank 1 and let the rank of a player who lost in a round having 2k matches be 2k plus the rank of the player who beat him, for k = 0, ... , m − 1.) In this manner, the result of the tournament can be represented by a permutation i1, i2, ... , in, where ij is the player who was given rank j. Because different tournament results give rise to different permutations, and because there is a tournament result for each permutation, it follows that there are the same number of possible tournament results as there are permutations of 1, ... , n. . EXAMPLE 5e (x1 + x2 + x3) 2 = 2 2, 0, 0 x2 1x0 2x0 3 + 2 0, 2, 0 x0 1x2 2x0 3 + 2 0, 0, 2 x0 1x0 2x2 3 + 2 1, 1, 0 x1 1x1 2x0 3 + 2 1, 0, 1 x1 1x0 2x1 3 + 2 0, 1, 1 x0 1x1 2x1 3 = x2 1 + x2 2 + x2 3 + 2x1x2 + 2x1x3 + 2x2x3 . ∗1.6 THE NUMBER OF INTEGER SOLUTIONS OF EQUATIONS There are rn possible outcomes when n distinguishable balls are to be distributed into r distinguishable urns. This result follows because each ball may be distributed into any of r possible urns. Let us now, however, suppose that the n balls are indistinguishable from each other. In this case, how many different outcomes are possible? As the balls are indistinguishable, it follows that the outcome of the experiment of distributing the n balls into r urns can be described by a vector (x1, x2, ... , xr), where xi denotes the number of balls that are distributed into the ith urn. Hence, the problem reduces to finding the number of distinct nonnegative integer-valued vectors (x1, x2, ... , xr) such that x1 + x2 + ··· + xr = n ∗Asterisks denote material that is optional.
Section 1.6 The Number of Integer Solutions of Equations 13 To compute this number,let us start by considering the number of positive integer- olutions Toward that end imagin that we have n indisti uishable obie lined up and that we want to divide them into r nonempty groups.To do so.we can select r-1 of the n-1 spaces between adjacent objects as our dividing points.(See Figure 1.2.)For instance,if we have n=8 andr=3 and we choose the 2 divisors so as to obtain 000lo00l00 nobjects 0 Chooser-1 of the spaces FIGURE 1.2:Number of positive solutions then the resulting vector is33.=2.As there are possible selections,we have the following proposition. x2,...x)satisfying the equation x1+x3+…+x,=n>0,i=1,,r To obtain the number of nonnegative (as opposed to positive)solutions,note that the number of nonnegative solutions of x+x2+...+x=n is the same as the number of positive solutions of y+...+yr =n+r(seen by letting yi=xi+1,i =1,...,r).Hence,from Proposition 6.1,we obtain the following proposition. Proposition.2.There are distinct nonnegative integer-valued vee tors (x1,x2....,x)satisfying the equation +2+…+,=n (6.1) EXAMPLE 6a How many distinct nonnegative integer-valued solutions ofx+2=3 are possible? Solurion.There are (=4such solutions:(0.3).(1).(21).(3,0). EXAMPLE 6b An investor has 20 thousa nd dol ars to inve .Each nvestment must e in units of a thousand
Section 1.6 The Number of Integer Solutions of Equations 13 To compute this number, let us start by considering the number of positive integervalued solutions. Toward that end, imagine that we have n indistinguishable objects lined up and that we want to divide them into r nonempty groups. To do so, we can select r − 1 of the n − 1 spaces between adjacent objects as our dividing points. (See Figure 1.2.) For instance, if we have n = 8 and r = 3 and we choose the 2 divisors so as to obtain ooo|ooo|oo 0 ^ 0 ^ 0 ^ . . . ^ 0 ^ 0 n objects 0 Choose r 1 of the spaces ^. FIGURE 1.2: Number of positive solutions then the resulting vector is x1 = 3, x2 = 3, x3 = 2. As there are n − 1 r − 1 possible selections, we have the following proposition. Proposition 6.1. There are n − 1 r − 1 distinct positive integer-valued vectors (x1, x2, ... , xr) satisfying the equation x1 + x2 + ··· + xr = n xi > 0, i = 1, ... ,r To obtain the number of nonnegative (as opposed to positive) solutions, note that the number of nonnegative solutions of x1 + x2 + ··· + xr = n is the same as the number of positive solutions of y1 + ··· + yr = n + r (seen by letting yi = xi + 1, i = 1, ... ,r). Hence, from Proposition 6.1, we obtain the following proposition. Proposition 6.2. There are n + r − 1 r − 1 distinct nonnegative integer-valued vectors (x1, x2, ... , xr) satisfying the equation x1 + x2 + ··· + xr = n (6.1) EXAMPLE 6a How many distinct nonnegative integer-valued solutions of x1 + x2 = 3 are possible? Solution. There are 3 + 2 − 1 2 − 1 = 4 such solutions: (0, 3), (1, 2), (2, 1), (3, 0). . EXAMPLE 6b An investor has 20 thousand dollars to invest among 4 possible investments. Each investment must be in units of a thousand dollars. If the total 20 thousand is to be
14 Chapter 1 Combinatorial Analysis invested,how many different investment strategies are possible?What if not all the money need be invested? Solution.If we letxi,i=1.2.3,4,denote the number of thousands invested in stment i,then,when all is to be invested,..3.x are integers satisfying the cquation x1+2+x3+x4=20≥0 Hence,by Proposition,there are1771 possible investment strategies.If not all of the money need be invested,then if we let xs denote the amount kept in reserve,a strategy is a nonnegative integer-valued vector (x1,x2.x3,x4.xs)satisfying the equation x1+2+x3+x4+x5=20 Hence,by Proposition6.there are now10.626 possible strategies. ◆ EXAMPLE 60 How many terms are there in the multinomial expansion of (x+x2+...+x)"? Solution. 国++…+=∑(”m）…9 n where the sum is over all nonnegative integer-valued(m. ,nr)such thatm+…+ .Hence.by Proposition 6.2,there are )such terms ◆ EXAMPLE 6d Let us consider again example 4c.in which we have a set of n items.of which m are (indistinguishable and)defective and the remaining n-m are(also indistinguishable and)functional.Our objective is to determine the number of linear orderings in which no two defectives are next to each other.To determine this number,let us imagine that the defective items are lined up among themselves and the functional ones are now to be put in position.Let us denote x1 as the number of functional items to the left of the first defective,x2 as the number of functional items between the first two defectives,and so on.That is,schematically.we have x10x20…m0xm+1 nal item betw ir of defective number of vectors that satisfy the equation +…+m+1=n-m≥0，m+1≥0，>0，i=2,,m
14 Chapter 1 Combinatorial Analysis invested, how many different investment strategies are possible? What if not all the money need be invested? Solution. If we let xi, i = 1, 2, 3, 4, denote the number of thousands invested in investment i, then, when all is to be invested, x1, x2, x3, x4 are integers satisfying the equation x1 + x2 + x3 + x4 = 20 xi Ú 0 Hence, by Proposition 6.2, there are 23 3 = 1771 possible investment strategies. If not all of the money need be invested, then if we let x5 denote the amount kept in reserve, a strategy is a nonnegative integer-valued vector (x1, x2, x3, x4, x5) satisfying the equation x1 + x2 + x3 + x4 + x5 = 20 Hence, by Proposition 6.2, there are now 24 4 = 10,626 possible strategies. . EXAMPLE 6c How many terms are there in the multinomial expansion of (x1 + x2 + ··· + xr)n? Solution. (x1 + x2 + ··· + xr) n = n n1, ... , nr x n1 1 ··· xnr r where the sum is over all nonnegative integer-valued (n1, ... , nr) such that n1 + ··· + nr = n. Hence, by Proposition 6.2, there are n + r − 1 r − 1 such terms. . EXAMPLE 6d Let us consider again Example 4c, in which we have a set of n items, of which m are (indistinguishable and) defective and the remaining n − m are (also indistinguishable and) functional. Our objective is to determine the number of linear orderings in which no two defectives are next to each other. To determine this number, let us imagine that the defective items are lined up among themselves and the functional ones are now to be put in position. Let us denote x1 as the number of functional items to the left of the first defective, x2 as the number of functional items between the first two defectives, and so on. That is, schematically, we have x1 0 x2 0 ··· xm 0 xm+1 Now, there will be at least one functional item between any pair of defectives as long as xi > 0, i = 2, ... , m. Hence, the number of outcomes satisfying the condition is the number of vectors x1, ... , xm+1 that satisfy the equation x1 + ··· + xm+1 = n − m x1 Ú 0, xm+1 Ú 0, xi > 0, i = 2, ... , m
Summary 15 But,on lettin ri-2 this =we sce that that satisfy the cquation 1+2+…+ym+1=n-m+2 Hence.by Proposition.1,there outcomes.in agreement with the resuusohat wnpre inierested in the number of outcomes in which cach pair ctive items is s ated h at least 2 fr By the ame rea ing as that applied previou 1+·+xm+1=n-mx1≥0，xm+1≥0，≥2，i=2,,m Upon letting vi +1.:=x:-1.i=2 +1,we see that this is the same as the number of positive solutions of the equation y1+…+ym+1=n-2m+3 Hence.from Proposition 6.1,there are such outcomes. SUMMARY nent co of two phases is rrpossible outcomes of phase then there arempo there ossible utc s of the There are n!n(n -1)...3.2.1 possible linear orderings of n items.The quantity 0!is defined to equal 1. Let n! ()=m- when 0sisn,and let it equal 0 otherwise.This quantity represents the number of different subgroups of size i that can be chosen from a set of size n.It is often called a binomial coefficient because of its prominence in the binomial theorem,which states that +=2(）w 1=0 For nonnegative integers m.....nsumming to n, n! is the number of divisions of n items intordistinct nonoverlapping subgroups of sizes 11,12,,1r
Summary 15 But, on letting y1 = x1 + 1, yi = xi, i = 2, ... , m, ym+1 = xm+1 + 1, we see that this number is equal to the number of positive vectors (y1, ... , ym+1) that satisfy the equation y1 + y2 + ··· + ym+1 = n − m + 2 Hence, by Proposition 6.1, there are n − m + 1 m such outcomes, in agreement with the results of Example 4c. Suppose now that we are interested in the number of outcomes in which each pair of defective items is separated by at least 2 functional items. By the same reasoning as that applied previously, this would equal the number of vectors satisfying the equation x1 + ··· + xm+1 = n − m x1 Ú 0, xm+1 Ú 0, xi Ú 2, i = 2, ... , m Upon letting y1 = x1 + 1, yi = xi − 1, i = 2, ... , m, ym+1 = xm+1 + 1, we see that this is the same as the number of positive solutions of the equation y1 + ··· + ym+1 = n − 2m + 3 Hence, from Proposition 6.1, there are n − 2m + 2 m such outcomes. . SUMMARY The basic principle of counting states that if an experiment consisting of two phases is such that there are n possible outcomes of phase 1 and, for each of these n outcomes, there are m possible outcomes of phase 2, then there are nm possible outcomes of the experiment. There are n! = n(n − 1)··· 3 · 2 · 1 possible linear orderings of n items. The quantity 0! is defined to equal 1. Let n i = n! (n − i)! i! when 0 … i … n, and let it equal 0 otherwise. This quantity represents the number of different subgroups of size i that can be chosen from a set of size n. It is often called a binomial coefficient because of its prominence in the binomial theorem, which states that (x + y) n = n i=0 n i xi yn−i For nonnegative integers n1, ... , nr summing to n, n n1, n2, ... , nr = n! n1!n2! ··· nr! is the number of divisions of n items into r distinct nonoverlapping subgroups of sizes n1, n2, ... , nr.
16 Chapter 1 Combinatorial Analysis PROBLEMS 1.(a)How many different 7-place license plates are 10.In how many ways can 8 people be seated in a re for letters and are no restrictions on the seating (b)Repeat part(a)under the assumption that no arrangement? letter or number can be repeated in a single (b)persons A and B must sit next to each other? lcense plate (e)there are 4 men and 4 women and Ino 2 men 2.H6 (d) that the outcome is 3,4.3.1 if the first roll landed on 3,the second on 4,the third on 3.and the fourth (e)there are 4 married couples and each couple on I must sit together? 3 Twenty 11.In how many ways can 3 novels.2 mathematics ments are possible? books and I chemistry book be arranged on a 4.John,Jim,Jay,and Jack have formed a band con (a)the books can be a anged in a ny order? e D oys can play (b)the mathematics books must be together and he novels must be together? all 4 instruments,but Jay and Jack can each play (c)the nove must be ogether,but the other s can b ranged only piano and drums? ny or 2. nd so hip.best selected students from a class of 30.How many dif- 9.the second digit was either 0or 1.and the third any number of awards? s wer 13 a group of 20 peopl If everyon 6.wellknownyme starts as follows: take place? ves met a man with 7 wives. 14.How many 5-card poker hands are there? Each wife had 7 sacks 15.A dance class consists of 22 students of which 10 Each sack had 7 cats. are women and 12 are men.If 5 men and 5 women Each cat had 7 kittens. then pared off how many How many kittens did the traveler meet? 16 7.(a)In how many ways can3 boys and 3 girls sit in (b)row 6en hence,and 4 economics books.or n 2 a row if the bovs and the (a)both books are to be on the same subject? (b)the books are to be on different subjects? 1.6 (d)ow many ways if no two hild i low many di of the ve m 18 8.How many different letter arrangements can be dndependents.How manycommttr b】 eel ible (c)Mississippi? 19 roma group of 8 wome en and I6 men,a c mmitte (d)Arrange sible ne (a)2 of the men refuse to serve together? are po: (b)2 of the w vomen refuse to serve together? (c)1 man and 1 woman refuse to serve together?
16 Chapter 1 Combinatorial Analysis PROBLEMS 1. (a) How many different 7-place license plates are possible if the first 2 places are for letters and the other 5 for numbers? (b) Repeat part (a) under the assumption that no letter or number can be repeated in a single license plate. 2. How many outcome sequences are possible when a die is rolled four times, where we say, for instance, that the outcome is 3, 4, 3, 1 if the first roll landed on 3, the second on 4, the third on 3, and the fourth on 1? 3. Twenty workers are to be assigned to 20 different jobs, one to each job. How many different assignments are possible? 4. John, Jim, Jay, and Jack have formed a band consisting of 4 instruments. If each of the boys can play all 4 instruments, how many different arrangements are possible? What if John and Jim can play all 4 instruments, but Jay and Jack can each play only piano and drums? 5. For years, telephone area codes in the United States and Canada consisted of a sequence of three digits. The first digit was an integer between 2 and 9, the second digit was either 0 or 1, and the third digit was any integer from 1 to 9. How many area codes were possible? How many area codes starting with a 4 were possible? 6. A well-known nursery rhyme starts as follows: “As I was going to St. Ives I met a man with 7 wives. Each wife had 7 sacks. Each sack had 7 cats. Each cat had 7 kittens...” How many kittens did the traveler meet? 7. (a) In how many ways can 3 boys and 3 girls sit in a row? (b) In how many ways can 3 boys and 3 girls sit in a row if the boys and the girls are each to sit together? (c) In how many ways if only the boys must sit together? (d) In how many ways if no two people of the same sex are allowed to sit together? 8. How many different letter arrangements can be made from the letters (a) Fluke? (b) Propose? (c) Mississippi? (d) Arrange? 9. A child has 12 blocks, of which 6 are black, 4 are red, 1 is white, and 1 is blue. If the child puts the blocks in a line, how many arrangements are possible? 10. In how many ways can 8 people be seated in a row if (a) there are no restrictions on the seating arrangement? (b) persons A and B must sit next to each other? (c) there are 4 men and 4 women and no 2 men or 2 women can sit next to each other? (d) there are 5 men and they must sit next to each other? (e) there are 4 married couples and each couple must sit together? 11. In how many ways can 3 novels, 2 mathematics books, and 1 chemistry book be arranged on a bookshelf if (a) the books can be arranged in any order? (b) the mathematics books must be together and the novels must be together? (c) the novels must be together, but the other books can be arranged in any order? 12. Five separate awards (best scholarship, best leadership qualities, and so on) are to be presented to selected students from a class of 30. How many different outcomes are possible if (a) a student can receive any number of awards? (b) each student can receive at most 1 award? 13. Consider a group of 20 people. If everyone shakes hands with everyone else, how many handshakes take place? 14. How many 5-card poker hands are there? 15. A dance class consists of 22 students, of which 10 are women and 12 are men. If 5 men and 5 women are to be chosen and then paired off, how many results are possible? 16. A student has to sell 2 books from a collection of 6 math, 7 science, and 4 economics books. How many choices are possible if (a) both books are to be on the same subject? (b) the books are to be on different subjects? 17. Seven different gifts are to be distributed among 10 children. How many distinct results are possible if no child is to receive more than one gift? 18. A committee of 7, consisting of 2 Republicans, 2 Democrats, and 3 Independents, is to be chosen from a group of 5 Republicans, 6 Democrats, and 4 Independents. How many committees are possible? 19. From a group of 8 women and 6 men, a committee consisting of 3 men and 3 women is to be formed. How many different committees are possible if (a) 2 of the men refuse to serve together? (b) 2 of the women refuse to serve together? (c) 1 man and 1 woman refuse to serve together?