Problems 17 20.A person has 8 friends,of whom 5 will be invited in different beds in the same room,how many to a party. assignments are possible? (a)How many choices are there if 2 of the friends 24.Expand (3x2 +y)5. (b)Ho ing and will attend together? ble? 21.Consider the grid of points shown here.Suppose nd(r,42r+3r14 that,starting at the point la A.you can go on 27.f12p ded into 3cc tees of respective sizes,4,and 5,how many divisions are reached.How many different paths from A toB 28.possible? 8 new teachers are to be divide from A.you must take eps to the nign steps upwa 29.Ten weight lifters are competing in a team weight lifting contest.Of the lifters,3 are from the United States,4 are from ussia,2 are from China,and individual identities.how many different outcomes are possible from the point of view of scores?How n thr nd ?in the h thre 30.Delegates from 10 countries,including Russia. France,England,and the United States,are to be seated in a row.How erent sea a e pos other and the Russian and U.S.delegates are not 22 In Problem 21 how n are to be divided am from A to B that g the following lattice? eceive at least I black hoard? *32.An elevator starts at the basement with 8 peo ple (not includi the elevator operator)and dis by the I rea he e perceived the the elpe people con 33 tselams m and the must be integral in units of 1 thousand dollars and there are minimal investments that need to be made if one is to in es.Th th dollars.How many different investment strategies are available if 23.A psychology laboratory conducting dream (a)an investment must be made in each opportu- researc contain rooms with 2 beds in eac (b) estments must be made in at least 3 of the 4opportunities?
Problems 17 20. A person has 8 friends, of whom 5 will be invited to a party. (a) How many choices are there if 2 of the friends are feuding and will not attend together? (b) How many choices if 2 of the friends will only attend together? 21. Consider the grid of points shown here. Suppose that, starting at the point labeled A, you can go one step up or one step to the right at each move. This procedure is continued until the point labeled B is reached. How many different paths from A to B are possible? Hint: Note that to reach B from A, you must take 4 steps to the right and 3 steps upward. B A 22. In Problem 21, how many different paths are there from A to B that go through the point circled in the following lattice? B A 23. A psychology laboratory conducting dream research contains 3 rooms, with 2 beds in each room. If 3 sets of identical twins are to be assigned to these 6 beds so that each set of twins sleeps in different beds in the same room, how many assignments are possible? 24. Expand (3x2 + y)5. 25. The game of bridge is played by 4 players, each of whom is dealt 13 cards. How many bridge deals are possible? 26. Expand (x1 + 2x2 + 3x3)4. 27. If 12 people are to be divided into 3 committees of respective sizes 3, 4, and 5, how many divisions are possible? 28. If 8 new teachers are to be divided among 4 schools, how many divisions are possible? What if each school must receive 2 teachers? 29. Ten weight lifters are competing in a team weightlifting contest. Of the lifters, 3 are from the United States, 4 are from Russia, 2 are from China, and 1 is from Canada. If the scoring takes account of the countries that the lifters represent, but not their individual identities, how many different outcomes are possible from the point of view of scores? How many different outcomes correspond to results in which the United States has 1 competitor in the top three and 2 in the bottom three? 30. Delegates from 10 countries, including Russia, France, England, and the United States, are to be seated in a row. How many different seating arrangements are possible if the French and English delegates are to be seated next to each other and the Russian and U.S. delegates are not to be next to each other? ∗31. If 8 identical blackboards are to be divided among 4 schools, how many divisions are possible? How many if each school must receive at least 1 blackboard? ∗32. An elevator starts at the basement with 8 people (not including the elevator operator) and discharges them all by the time it reaches the top floor, number 6. In how many ways could the operator have perceived the people leaving the elevator if all people look alike to him? What if the 8 people consisted of 5 men and 3 women and the operator could tell a man from a woman? ∗33. We have 20 thousand dollars that must be invested among 4 possible opportunities. Each investment must be integral in units of 1 thousand dollars, and there are minimal investments that need to be made if one is to invest in these opportunities. The minimal investments are 2, 2, 3, and 4 thousand dollars. How many different investment strategies are available if (a) an investment must be made in each opportunity? (b) investments must be made in at least 3 of the 4 opportunities?
18 Chapter 1 Combinatorial Analysis THEORETICAL EXERCISES 1.Prove the generalized version of the basic counting the choice of the chair.argue that there are eriments are to be per (nk+1)possible choices. (c)By focusing first on the choice of the chair the first experiment results in outcome i,then the and then on the choice of the other committe members.argue that there are nki of the 3.In ho cted fr )(()n ( cif the order of selection is consid ered relevant? 4.There are different linear arrangements ofn (）=m-+(”)=( mhite Give balls of which re black and 5.Determine the number of vectors(x1.....).such (e)Use the factorial definition oftoverify that eachxi is either 0 or 1 and the identity in part (d). ()-(-)n=k Give a combinatorial argument (no computations 7.Give an analytic proof of Equation(4.1) is identity. 8.Prove that How m numbered member? （"+m)=(8)()+(1)(,”) 12.Consider the following combinatorial identity: +…+()(0) 24()-2 (a)Present a combinatorial argument for this Hcaym entity by considering a set of n people and 9.Use Theoretical Exercise 8 to prove that e o ways.me a chairperson for the committee. ()-() Hint: Chommcodseknds6tpe (i)How many possible selections are there (）How many possibles be designated as chairperson (a)By focusing first on the choice of the commit (b) e following identity for n= tee and then on the choice of the chair.argue that there arek possible choices (b)By focusing first on the choice of the nonchair committee members and then on 2()=w+
18 Chapter 1 Combinatorial Analysis THEORETICAL EXERCISES 1. Prove the generalized version of the basic counting principle. 2. Two experiments are to be performed. The first can result in any one of m possible outcomes. If the first experiment results in outcome i, then the second experiment can result in any of ni possible outcomes, i = 1, 2, ... , m. What is the number of possible outcomes of the two experiments? 3. In how many ways can r objects be selected from a set of n objects if the order of selection is considered relevant? 4. There are n r different linear arrangements of n balls of which r are black and n − r are white. Give a combinatorial explanation of this fact. 5. Determine the number of vectors (x1, ... , xn), such that each xi is either 0 or 1 and n i=1 xi Ú k 6. How many vectors x1, ... , xk are there for which each xi is a positive integer such that 1 … xi … n and x1 < x2 < ··· < xk? 7. Give an analytic proof of Equation (4.1). 8. Prove that n + m r = n 0 m r + n 1 m r − 1 +··· + n r m 0 Hint: Consider a group of n men and m women. How many groups of size r are possible? 9. Use Theoretical Exercise 8 to prove that 2n n = n k=0 n k 2 10. From a group of n people, suppose that we want to choose a committee of k, k … n, one of whom is to be designated as chairperson. (a) By focusing first on the choice of the committee and then on the choice of the chair, argue that there are n k k possible choices. (b) By focusing first on the choice of the nonchair committee members and then on the choice of the chair, argue that there are n k − 1 (n − k + 1) possible choices. (c) By focusing first on the choice of the chair and then on the choice of the other committee members, argue that there are n n − 1 k − 1 possible choices. (d) Conclude from parts (a), (b), and (c) that k n k = (n − k + 1) n k − 1 = n n − 1 k − 1 (e) Use the factorial definition of m r to verify the identity in part (d). 11. The following identity is known as Fermat’s combinatorial identity: n k = n i=k i − 1 k − 1 n Ú k Give a combinatorial argument (no computations are needed) to establish this identity. Hint: Consider the set of numbers 1 through n. How many subsets of size k have i as their highestnumbered member? 12. Consider the following combinatorial identity: n k=1 k n k = n · 2n−1 (a) Present a combinatorial argument for this identity by considering a set of n people and determining, in two ways, the number of possible selections of a committee of any size and a chairperson for the committee. Hint: (i) How many possible selections are there of a committee of size k and its chairperson? (ii) How many possible selections are there of a chairperson and the other committee members? (b) Verify the following identity for n = 1, 2, 3, 4, 5: n k=1 n k k2 = 2n−2n(n + 1)
Theoretical Exercises 19 For a combinatorial proof of the p consider a set of n people and argue that both whipostive integer satisying 15.Let H(n)be the number of vectors the chairperson). retary (possibly Hint: H(n)=n (i)How many different selections result in the committee containing exactly k peo- H=∑H-10k>1 ple? are there Hint:How many vectors are there in which (Hoar x= the chairperson and the secretary being (b)Use the preceding recursion to compute different? H3(5) Hint:First compute H2(n)for n =1,2,3,4.5. (e)Now argue that 16.Consider a tournament of n contestants in which 2()=a+ the outcome is an ordering of these contestants. with ties allowed.Thath eoutcome partitior ine of the plavers that tied for first p the nex 13.Show that,for n>0. group being those that tied for the next-best posi tion.and soon.Let M)denote -1y(）)=0 ferent poso =0 first,or they ould tie for first. 14:Use the binomial theoncitiee ofsizeistbe (a)List all the possible outcomes whenn=3. chom a se .a com 出cao0e (b)With N(0)defined to equal 1,argue,without any computations,that of poss Nm=∑(？）Na-D first by supposing that the committee is chosen first and then the subcommittee is (b)Use part (a)to prove the following combina- hemula of partqalnt torial identity: 2(G)0)-()-sn (c)Use part(a)and Theoretical Exercise 13 to (d)Use the recursion to find N(3)and N(4). show that 17.Pres ent a combinatorial explanation of why 2(G)()-0icn (”)-(m”,)
Theoretical Exercises 19 For a combinatorial proof of the preceding, consider a set of n people and argue that both sides of the identity represent the number of different selections of a committee, its chairperson, and its secretary (possibly the same as the chairperson). Hint: (i) How many different selections result in the committee containing exactly k people? (ii) How many different selections are there in which the chairperson and the secretary are the same? (ANSWER: n2n−1.) (iii) How many different selections result in the chairperson and the secretary being different? (c) Now argue that n k=1 n k k3 = 2n−3n2(n + 3) 13. Show that, for n > 0, n i=0 (−1) i n i = 0 Hint: Use the binomial theorem. 14. From a set of n people, a committee of size j is to be chosen, and from this committee, a subcommittee of size i, i … j, is also to be chosen. (a) Derive a combinatorial identity by computing, in two ways, the number of possible choices of the committee and subcommittee— first by supposing that the committee is chosen first and then the subcommittee is chosen, and second by supposing that the subcommittee is chosen first and then the remaining members of the committee are chosen. (b) Use part (a) to prove the following combinatorial identity: n j=i n j j i = n i 2n−i i … n (c) Use part (a) and Theoretical Exercise 13 to show that n j=i n j j i (−1) n−j = 0 i < n 15. Let Hk(n) be the number of vectors x1, ... , xk for which each xi is a positive integer satisfying 1 … xi … n and x1 … x2 … ··· … xk. (a) Without any computations, argue that H1(n) = n Hk(n) = n j=1 Hk−1(j) k > 1 Hint: How many vectors are there in which xk = j? (b) Use the preceding recursion to compute H3(5). Hint: First compute H2(n) for n = 1, 2, 3, 4, 5. 16. Consider a tournament of n contestants in which the outcome is an ordering of these contestants, with ties allowed. That is, the outcome partitions the players into groups, with the first group consisting of the players that tied for first place, the next group being those that tied for the next-best position, and so on. Let N(n) denote the number of different possible outcomes. For instance, N(2) = 3, since, in a tournament with 2 contestants, player 1 could be uniquely first, player 2 could be uniquely first, or they could tie for first. (a) List all the possible outcomes when n = 3. (b) With N(0) defined to equal 1, argue, without any computations, that N(n) = n i=1 n i N(n − i) Hint: How many outcomes are there in which i players tie for last place? (c) Show that the formula of part (b) is equivalent to the following: N(n) = n−1 i=0 n i N(i) (d) Use the recursion to find N(3) and N(4). 17. Present a combinatorial explanation of why n r = n r, n − r .
20 Chapter 1 Combinatorial Analysis 18.Argue that 2L.Argue that there are eactly()(n”,十k） n-1 solutionsof n-1 x1+x2+··+xr=n +(mm”-1m）+… n-1 +（, for which exactly k of thex;are equal to 0. ,,-1 Hint:Use an argument similar to the one used to establish Equation(4.1). +23.Does/pos e the .ove the mutinomial theo tical balls be dis least m;balls,for each i=1.. .r?Assume that n≥=1m. SELF-TEST PROBLEMS AND EXERCISES 1.How nts are there 7.Give a combinatorial explanation of the identity (a)A and B are next to each other? (b)A is before B? (）)=() (e)Aand B are next to each other and Cand D 8.Consider n-digit numbers where each digit is one are also next to each other? of the 10 integers. .9.How many such num- ch people and 3 British e digits a a1 (b)0 appears as a digit a total of i times.i= ing arrangements are possible when p ple of the 0.. ame nationality must sit next to each other? 9.Consider three classes,each consisting of n stu- 3.A president,treasurer,and secretary,all different. dents.Fr is group of 3n students,a group of 3 e chosen f oma clu ting of 10 peo ssible if many cers ar (b)How many choices are there in which all3 stu- (a)there are no restrictions? ents are in the same class? (b)A and B will not serve together? (c)How many choices are there Can will se ve together or not at all? rent classass and erve only if he is president? (d)How many choices are there in which all3 stu- 4.A student is to answer 7 out of 10 questions in ts are in different classes? an examir ation.How many choices has she?How (a)through (d). if she must answer at least 3 of the first 5 (e)Using the re 10. med f 5. divide ear more than twice?(For instance.41434 is not allowed.) the others 2 each? 6.How many di ofrent 7-p lace hcens plates group of 6 pec t allowed to contain e ent dcouple bers is allowed and that there is no restriction on (b)How many choices are there if the group must where the letters or numbers can be placed. also consist of 3 men and 3 women?
20 Chapter 1 Combinatorial Analysis 18. Argue that n n1, n2, ... , nr = n − 1 n1 − 1, n2, ... , nr + n − 1 n1, n2 − 1, ... , nr + ··· + n − 1 n1, n2, ... , nr − 1 Hint: Use an argument similar to the one used to establish Equation (4.1). 19. Prove the multinomial theorem. ∗20. In how many ways can n identical balls be distributed into r urns so that the ith urn contains at least mi balls, for each i = 1, ... ,r? Assume that n Ú r i=1 mi. ∗21. Argue that there are exactly r k n − 1 n − r + k solutions of x1 + x2 + ··· + xr = n for which exactly k of the xi are equal to 0. ∗22. Consider a function f(x1, ... , xn) of n variables. How many different partial derivatives of order r does f possess? ∗23. Determine the number of vectors (x1, ... , xn) such that each xi is a nonnegative integer and n i=1 xi … k SELF-TEST PROBLEMS AND EXERCISES 1. How many different linear arrangements are there of the letters A, B, C, D, E, F for which (a) A and B are next to each other? (b) A is before B? (c) A is before B and B is before C? (d) A is before B and C is before D? (e) A and B are next to each other and C and D are also next to each other? (f) E is not last in line? 2. If 4 Americans, 3 French people, and 3 British people are to be seated in a row, how many seating arrangements are possible when people of the same nationality must sit next to each other? 3. A president, treasurer, and secretary, all different, are to be chosen from a club consisting of 10 people. How many different choices of officers are possible if (a) there are no restrictions? (b) A and B will not serve together? (c) C and D will serve together or not at all? (d) E must be an officer? (e) F will serve only if he is president? 4. A student is to answer 7 out of 10 questions in an examination. How many choices has she? How many if she must answer at least 3 of the first 5 questions? 5. In how many ways can a man divide 7 gifts among his 3 children if the eldest is to receive 3 gifts and the others 2 each? 6. How many different 7-place license plates are possible when 3 of the entries are letters and 4 are digits? Assume that repetition of letters and numbers is allowed and that there is no restriction on where the letters or numbers can be placed. 7. Give a combinatorial explanation of the identity n r = n n − r 8. Consider n-digit numbers where each digit is one of the 10 integers 0, 1, ... , 9. How many such numbers are there for which (a) no two consecutive digits are equal? (b) 0 appears as a digit a total of i times, i = 0, ... , n? 9. Consider three classes, each consisting of n students. From this group of 3n students, a group of 3 students is to be chosen. (a) How many choices are possible? (b) How many choices are there in which all 3 students are in the same class? (c) How many choices are there in which 2 of the 3 students are in the same class and the other student is in a different class? (d) How many choices are there in which all 3 students are in different classes? (e) Using the results of parts (a) through (d), write a combinatorial identity. 10. How many 5-digit numbers can be formed from the integers 1, 2, ... , 9 if no digit can appear more than twice? (For instance, 41434 is not allowed.) 11. From 10 married couples, we want to select a group of 6 people that is not allowed to contain a married couple. (a) How many choices are there? (b) How many choices are there if the group must also consist of 3 men and 3 women?
Self-Test Problems and Exercises 21 e eme th Assuming that all scores are distinct(no ties),how omen ad many posted results are possible? 16.How many subsets of size 4 of the set S= men,how many di fferent committees are contain at leat one of the clemenis 13.An art collection on auction consisted of4 Dalis.5 17.Give an analytic verification of van Goghs,and 6 Picassos.At the auction were 5 art collectors.If reporter noted only the numb (份=（付+-+(《2）1sk≤n been recorded if all of the works were sold? *14.Determine the number of vectors()such Now.give a combinatorial argument for this that each xi is a positive integer and identity. ∑≤k sisting ofa single parent and 2 childre n 5 fan ilies consisting of 2 parents and a single child,7 studen fparents and 3 ren,and ren. The posted results of the examination will list the 19.If there are no restrictions on where the digits and stance, tters an digits are poss to Brown receiving the higher sre
Self-Test Problems and Exercises 21 12. A committee of 6 people is to be chosen from a group consisting of 7 men and 8 women. If the committee must consist of at least 3 women and at least 2 men, how many different committees are possible? ∗13. An art collection on auction consisted of 4 Dalis, 5 van Goghs, and 6 Picassos. At the auction were 5 art collectors. If a reporter noted only the number of Dalis, van Goghs, and Picassos acquired by each collector, how many different results could have been recorded if all of the works were sold? ∗14. Determine the number of vectors (x1, ... , xn) such that each xi is a positive integer and n i=1 xi … k where k Ú n. 15. A total of n students are enrolled in a review course for the actuarial examination in probability. The posted results of the examination will list the names of those who passed, in decreasing order of their scores. For instance, the posted result will be “Brown, Cho” if Brown and Cho are the only ones to pass, with Brown receiving the higher score. Assuming that all scores are distinct (no ties), how many posted results are possible? 16. How many subsets of size 4 of the set S = {1, 2, ... , 20} contain at least one of the elements 1, 2, 3, 4, 5? 17. Give an analytic verification of n 2 = k 2 + k(n − k) + n − k 2 , 1 … k … n Now, give a combinatorial argument for this identity. 18. In a certain community, there are 3 families consisting of a single parent and 1 child, 3 families consisting of a single parent and 2 children, 5 families consisting of 2 parents and a single child, 7 families consisting of 2 parents and 2 children, and 6 families consisting of 2 parents and 3 children. If a parent and child from the same family are to be chosen, how many possible choices are there? 19. If there are no restrictions on where the digits and letters are placed, how many 8-place license plates consisting of 5 letters and 3 digits are possible if no repetitions of letters or digits are allowed. What if the 3 digits must be consecutive?