8 Chapter 1 Combinatorial Analysis Proof of the Binomial Theorem by Induction:Whenn=1,Equation(4.2)reduces to x+y=(0)y+()y°=y+x Assume Equation(4.2)for n-1.Now. x+y”=x+x+y-1 =+2(”) (0)+(' Lettingi=k+1in the first sum andi=k in the second sum,we find that +r-(任)+("：) i-0 r+[(:=)+(小w+y =+2()+y -()w eeeoequiyolomsyBquioa).Byntniaeacomm Combinatorial Proof of the Binomial Theorem:Consider the product G1+y1)x2+y2.cn+y) Its expansion consists of the sum of 2"terms,each term being the product ofn factors. (1+y1)2+y2)=x12+x1y2+y12+y12 ach toa choice of a group of k from then valuesthere are such terms. Thus,lettingxi=xyi=y,i=1,.n we see that a+”()
8 Chapter 1 Combinatorial Analysis Proof of the Binomial Theorem by Induction: When n = 1, Equation (4.2) reduces to x + y = 1 0 x0y1 + 1 1 x1y0 = y + x Assume Equation (4.2) for n − 1. Now, (x + y) n = (x + y)(x + y) n−1 = (x + y) n−1 k=0 n − 1 k xkyn−1−k = n−1 k=0 n − 1 k xk+1yn−1−k + n−1 k=0 n − 1 k xkyn−k Letting i = k + 1 in the first sum and i = k in the second sum, we find that (x + y) n = n i=1 n − 1 i − 1 xi yn−i + n−1 i=0 n − 1 i xi yn−i = xn + n−1 i=1 n − 1 i − 1 + n − 1 i xi yn−i + yn = xn + n−i i=1 n i xi yn−i + yn = n i=0 n i xi yn−i where the next-to-last equality follows by Equation (4.1). By induction, the theorem is now proved. Combinatorial Proof of the Binomial Theorem: Consider the product (x1 + y1)(x2 + y2)···(xn + yn) Its expansion consists of the sum of 2n terms, each term being the product of n factors. Furthermore, each of the 2n terms in the sum will contain as a factor either xi or yi for each i = 1, 2, . , n. For example, (x1 + y1)(x2 + y2) = x1x2 + x1y2 + y1x2 + y1y2 Now, how many of the 2n terms in the sum will have k of the xi’s and (n − k) of the yi’s as factors? As each term consisting of k of the xi’s and (n − k) of the yi’s corresponds to a choice of a group of k from the n values x1, x2, . , xn, there are n k such terms. Thus, letting xi = x, yi = y, i = 1, . , n, we see that (x + y) n = n k=0 n k xkyn−k
Section 1.5 Multinomial Coefficients 9 EXAMPLE 4d Expand (x +y) Solution c+驴=()3+()y+()2,+(3)y =y3+3y2+3x2y+x3 EXAMPLE 4e How many subsets are there of a set consisting of n elements? .Since there aresubsets of si k,the desired answer is 2()-a+r-: Note that we have included the set consisting of 0 elements(that is,the null set) the Hencc,the ro 1.5 MULTINOMIAL COEFFICIENTS In this How many different divisions are possible?To answer this question,we note that there are possible choices for the first group:for each choice of the first group. there arepossible choices for the second group:for eac choice of the first two groupsthere are possible choices for the third group:and 3 henolromthe neralizd v of the basic counting princip (）(“mm）-(0-m-。-） 一a一ma—- n! (n-n1)1 0!, =n1ln2.nr possible divisions
Section 1.5 Multinomial Coefficients 9 EXAMPLE 4d Expand (x + y)3. Solution. (x + y) 3 = 3 0 x0y3 + 3 1 x1y2 + 3 2 x2y + 3 3 x3y0 = y3 + 3xy2 + 3x2y + x3 . EXAMPLE 4e How many subsets are there of a set consisting of n elements? Solution. Since there are n k subsets of size k, the desired answer is n k=0 n k = (1 + 1) n = 2n This result could also have been obtained by assigning either the number 0 or the number 1 to each element in the set. To each assignment of numbers, there corresponds, in a one-to-one fashion, a subset, namely, that subset consisting of all elements that were assigned the value 1. As there are 2n possible assignments, the result follows. Note that we have included the set consisting of 0 elements (that is, the null set) as a subset of the original set. Hence, the number of subsets that contain at least one element is 2n − 1. . 1.5 MULTINOMIAL COEFFICIENTS In this section, we consider the following problem: A set of n distinct items is to be divided into r distinct groups of respective sizes n1, n2, . , nr, where r i=1 ni = n. How many different divisions are possible? To answer this question, we note that there are n n1 possible choices for the first group; for each choice of the first group, there are n − n1 n2 possible choices for the second group; for each choice of the first two groups, there are n − n1 − n2 n3 possible choices for the third group; and so on. It then follows from the generalized version of the basic counting principle that there are n n1 n − n1 n2 ··· n − n1 − n2 − ··· − nr−1 nr = n! (n − n1)! n1! (n − n1)! (n − n1 − n2)! n2! ··· (n − n1 − n2 − ··· − nr−1)! 0! nr! = n! n1! n2! ··· nr! possible divisions.
10 Chapter 1 Combinatorial Analysis Another this r 1.2. adivision of the n tem into the r groups in the following manner a10n1,2, to group i.item2 t the permutation 1.1.232.1.2.1 corresponds to as ening items 1.2.6.8 to the first group,items3,5 7to the second group,and item 4to the third group.Because every 一dgee一nd mare oc nis the same as the number of permutations of n items of 1.3 to equal Notation IEm+m+.+h=we define气m,购)by (1,”)=m2. Thus, 1,2 represents the number of possible divisions of n distinct ct groups of respective sizes m. EXAMPLE 5a A police department in a small city consists of 10 officers.If the department policy is 101 Thereare 52 possible divisions EXAMPLE 5b to an A tcan 10 o There are252 posible divisions ◆ EXAMPLE SC
10 Chapter 1 Combinatorial Analysis Another way to see this result is to consider the n values 1, 1, . , 1, 2, . , 2, . , r, . ,r, where i appears ni times, for i = 1, . ,r. Every permutation of these values corresponds to a division of the n items into the r groups in the following manner: Let the permutation i1, i2, . , in correspond to assigning item 1 to group i1, item 2 to group i2, and so on. For instance, if n = 8 and if n1 = 4, n2 = 3, and n3 = 1, then the permutation 1, 1, 2, 3, 2, 1, 2, 1 corresponds to assigning items 1, 2, 6, 8 to the first group, items 3, 5, 7 to the second group, and item 4 to the third group. Because every permutation yields a division of the items and every possible division results from some permutation, it follows that the number of divisions of n items into r distinct groups of sizes n1, n2, . , nr is the same as the number of permutations of n items of which n1 are alike, and n2 are alike, ., and nr are alike, which was shown in Section 1.3 to equal n! n1!n2! ··· nr! . Notation If n1 + n2 + ··· + nr = n, we define n n1, n2, . , nr by n n1, n2, . , nr = n! n1! n2! ··· nr! Thus, n n1, n2, . , nr represents the number of possible divisions of n distinct objects into r distinct groups of respective sizes n1, n2, . , nr. EXAMPLE 5a A police department in a small city consists of 10 officers. If the department policy is to have 5 of the officers patrolling the streets, 2 of the officers working full time at the station, and 3 of the officers on reserve at the station, how many different divisions of the 10 officers into the 3 groups are possible? Solution. There are 10! 5! 2! 3! = 2520 possible divisions. . EXAMPLE 5b Ten children are to be divided into an A team and a B team of 5 each. The A team will play in one league and the B team in another. How many different divisions are possible? Solution. There are 10! 5! 5! = 252 possible divisions. . EXAMPLE 5c In order to play a game of basketball, 10 children at a playground divide themselves into two teams of 5 each. How many different divisions are possible?
Section 1.5 Multinomial Coefficients 11 Solurion.Note that this example is different from Example 5b because now the order of the two teams is irrelevant.That is,there is no A and B team,but just a division consisting of 2 groups of 5 each.Hence,the desired answer is 101/515到=126 21 ◆ nthnerave theimalt The multinomial theorem +2+.+= 0m1.m）: m .十=n That is,the sum is over all nonnegative integer-valued vectors(m,.n)such The mumbers)are known as mulmnomcocn EXAMPLE 5d of the gamesrimiatedhil thwnergoonround.where the oninge playerphe (b)How of the Solurion.One way to determine the number of possible outcomes for the initial the numo athird pair,and ao pair is2.) Thus,the number of possible pair- ings when there is no ordering of the 4 pairs is For each such pairing,there are pl choices from each pair as to the winner of that game.showing that the there are possibl choices of thewinners and,for each suc choie,there are 4ways to pair thewer th the 4 lses showing that there are possible results for the first round.)
Section 1.5 Multinomial Coefficients 11 Solution. Note that this example is different from Example 5b because now the order of the two teams is irrelevant. That is, there is no A and B team, but just a division consisting of 2 groups of 5 each. Hence, the desired answer is 10!/(5! 5!) 2! = 126 . The proof of the following theorem, which generalizes the binomial theorem, is left as an exercise. The multinomial theorem (x1 + x2 + ··· + xr) n = (n1, . , nr) : n1 + ··· + nr = n n n1, n2, . , nr x n1 1 x n2 2 ··· xnr r That is, the sum is over all nonnegative integer-valued vectors (n1, n2, . , nr) such that n1 + n2 + ··· + nr = n. The numbers n n1, n2, . , nr are known as multinomial coefficients. EXAMPLE 5d In the first round of a knockout tournament involving n = 2m players, the n players are divided into n/2 pairs, with each of these pairs then playing a game. The losers of the games are eliminated while the winners go on to the next round, where the process is repeated until only a single player remains. Suppose we have a knockout tournament of 8 players. (a) How many possible outcomes are there for the initial round? (For instance, one outcome is that 1 beats 2, 3 beats 4, 5 beats 6, and 7 beats 8. ) (b) How many outcomes of the tournament are possible, where an outcome gives complete information for all rounds? Solution. One way to determine the number of possible outcomes for the initial round is to first determine the number of possible pairings for that round. To do so, note that the number of ways to divide the 8 players into a first pair, a second pair, a third pair, and a fourth pair is 8 2, 2, 2, 2 = 8! 24 . Thus, the number of possible pairings when there is no ordering of the 4 pairs is 8! 24 4!. For each such pairing, there are 2 possible choices from each pair as to the winner of that game, showing that there are 8!24 24 4! = 8! 4! possible results of round 1. (Another way to see this is to note that there are 8 4 possible choices of the 4 winners and, for each such choice, there are 4! ways to pair the 4 winners with the 4 losers, showing that there are 4! 8 4 = 8! 4! possible results for the first round.)
12 Chapter 1 Combinatorial Analysis Similaly.for eac resul of round 1,thereare possible of round2. and for each of the outcomes of the first two rounds,there are possible outcomes ofround 3.Consequently,by the generalized basic principle of counting.there are used to show that a knockout tournament of n=2mplayers has n!possible lt it is not difficult to with a r in such the ina-round the t Give ers who lost in the next-to-last round,give rank o the one who lost to the player ranked 1 and give rank 4 to the one who lost to the player ranked 3,and rank 8 to the one who lost to the player ranked 4 Continuing onn this manner gives a rank to each player.(A mor 0.1.n this manner.the result of the tournament can be represented a permutation if n,whe re ti is the player wh o was given rank Be o formutio i olththerrameume of possible tournament results as there are permutations of 1,.n. EXAMPLE 5e 国++a2-（2a.0)8端+(0.20)粥 +（062)s+（1,0)树 +（1品1）x+（0.1) =x+号+x号+212+213+223 ◆ 1.6 THE NUMBER OF INTEGER SOLUTIONS OF EQUATIONS nuishaboall mayei Ther ible oute es when n distinguishable balls e to be distributed into any of r possiblc urns.my different outcomes are possble? t of distrib ing the n balls intor urns can be described by a vector(1.2. e ri denotes ctors (,2. x+2+,.·十xr=n 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.