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 indis- tinguishable.How many linear orderings are there in which no two defectives are consecutive? 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 nm+1 possible orderings in which there is at least one functional antenna between any two defective ones. ◆ 1 functional place for at most one defective FIGURE1.1:No consecutive defectives A useful combinatorial identity is ()=()+(",)1sr≤n (4.1) Equation(4.1)may be proved analytically or by the following combinatorial argu- ment:Consider a group of n objects,and fix attention on some particular one of these objectscall it object 1.Now,there aregroups of sizerthat contain object 1(since each such group is formed by selecting r-1 from the remaining n-1 objects).Also,there are groups of sizerthat do not contain object 1.As r there isa total ofgroupsfEquation(4.1)follows The values ar ofe referred toas binmial coece because of their prominence in the binomial theorem. The binomial theorem (x+y)"= () (4.2) We shall present wo proofs of the binomial the corem. The first is a proof by math ematical induction,and
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.
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+y)(x+y)"-1 =+("）- k-0 Letting i=k+1 in the first sum and i=k in the second sum,we find that c+r-2(二)y+(":)y =+[(:)+(“:)]+ =2+()w-+ ✉1 -()w 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)…xm+ym) Its e is in the sum each term being the roduct of n factors will for....n.For example, contain as s a factor eitheri or y (1+y1)2+y2)=x1x2+x1y2+y1x2+y12 Now,how many of the 2"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 thexi's and (n-k)of the yi's corresponds toa choice of a group of k from thenvaluesthere are such terms. Thus,letting xi=x,yi=y,i=1,...,n,we see that c+”-()y
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)3 Solution c+=(8)+()2+()y+(3)y =y2+3y2+3x2y+x3 ● EXAMPLE 4e How many subsets are there of a set consisting of n elements? 2()=1+y=2 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 corre- bset,namely,that subset consisting of all ele ethat we ave included the se consisting (that null set) as a su is 2 th 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 n,n. .n.where How many different divisions are possible?To answer this question,we note that there reposble choiees for er grou for ach choie of theo there arepble choies for the eond gropfor eac choice of the so on.It then follows from the generalized version of the basic counting principle that there are (n-m1)! =n-m)是n!n--2)!2 0！n！ n！ 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 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 items into the r groups in the following manner signing item Ito group /1,ntem 3.21,2 1= s to 1,2 6.8 group Bec permutat of th that the y poss of disti is the same as the ns of n it and n are alike. and n are alike.which was sho vn in Section 1.3 to equal 1l2!., Notation If m n+...+n=n,we define （,2n,by n! 气m,m,mr=m2…m Thus,( 1,2 represents the number of possible divisions of n distinct t groups of respective sizes m.n.... 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? 10t Solution.There are posible 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 10 ouion.There are 252 possible divisions. ◆ EXAMPLE 5c is of 5 each.How ygro und divide themselves nany differ are possible?
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 of the t consisting of 2 groups of 5 each.Hence,the desired answer is 10/5150=126 21 ◆ as anor or the fonowing theorem,which generalizes the binomial the The multinomial theorem (+2+…+x)”= (1,,n): n+…+nr=n The numbers( 1,2, are known as multinomial coefficients EXAMPLE 5d In the first round of a knockout tournament involvingn=2 plavers.the n plavers 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 that Ibe out nd 7h nd?(For instance,one com cats 8.) (b)How many outcor mes of the comletfoatonoore possible,here noucm ves tourr Oe way to determine the umber of the round is to first determine the number of poss ble pairings for t at round.To do so,note that the number of ways to divide the 8 players into a first pair,a second pair, n pair,and,the number of posible pair. ings when there is no ordering of the 4 pairs is 81 For each such pairing,there are to thewof that game,wn that there 8124 81 arepossible resuls of round 1.(Another way to see this is to note that there choices of and,for choice,here 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.)