18 Chapter 1 Combinatorial Analysis THEORETICAL EXERCISES e generalized version of the basic counting the choice of the chair,argue that there are ents are to be perfo (1)possible choices. 3.In how many ways canr objects be selected from (d)parts ()()and()that the order of 4.There are different linear arrangements ofr ()=a-+k”)=二 balls of whic (e)Use the factorial definition ofto verify that eachis either 0or 1 and n.such y 豆 ()-2(=)n≥k 6.Hov (no computations ,.navicpoeofofEquaion（4I 8.Prove that （"+m)=(8)(）+(1)(,) n.&oaitheotcingonbinaioialiteniyg +.+()(0) 24()- (a)Present a combinatorial a ment for this mpeople and 9.Use Theoretical Exercise 8 to prove that dbeeecnoaeoaniHeotayeamd ero for the cm (0)-() (i)How many possible selections are there comite ofdhper (ii)How many possible sel as are ther and the other co tee and then on t that there arek possible choices. 2()e-a+n
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 different s (a)Without any computations,argue that the chairperson). etary (pos Hint: H(n)=n ple? M-空0k>1 (偷aehc e (ANSWER:2) Hin:How many vectors are there in which different? (e)Now argue that which 2()=na+动 the rderin g of these contestants vers 13.Show that,for n>0, on.nds Let denote them of dif 2-r()=0 (a)List all the possible outcomes whenn=3. oWoNgdtioedoqa1.arge,wiou Nm=工（日）Nm-D i=l chosen. (()et 2()0-()ms N-∑(？）Na (d)Use the recursion to find N(3)and N(4) 2(9)0)-0i<n 17.Present a combinatorial explanation of why ()=(”,）
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 exactly()(n”,+k】 solutionsof +(mm”11)+ +2+.+=n n-1 +(m-1) for which exactly k of the x are equal to 0 similar to the one used to e the number of vector such ntical balls be dis tributed in 名 SELF-TEST PROBLEMS AND EXERCISES 7.Give a combinatorial explanation of the identity ()to each other? ()=（n”,) ext toeach other? and 3 British how ()umc. are to be chosen f rom a club How many choices are there in whichall stu C and D will ser e together or not at all? 4.A student is to nswer 7 ou of 10 questions (e) (a)through (d). nt 7-place license plates ar en 3 of the ent 1.p sare let rs anc mar ried couple (b)How many choices are there if the group must 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 1m of 6 people is to be me Assuming that all scores are distinct(no ties).how group consisting of nsiet o n and 16. 3.459 17.Give an analytic verification of (份）-（囹+km-+(（2)1sk≤n ivcombinatorial armet fors .In a certain community.there are families 公4从 child The posted 19.If there the osted b
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?
CHAPTER 2 Axioms of Probability 2.1 INTRODUCTION SOME SIMPLE PROPOSITIONS SAMPLE SPACES HAVING EQUALLY LIKELY OUTCOMES TY AS A MEASIN 2.1 INTRODUCTION 2.2 SAMPLE SPACE AND EVENTS Consider an experiment whose outcome is not p edictable with certainty.however although the outcome of the experiment will not be known in advance,let us suppose 1.the determination of the sex of S={g,b创 where the outcome g means that the child is a girl and b that it is a boy S=(all 7!permutations of (1.2,3,4,5,6,7)) e themone then the mm The outc thethn the ml S=((H,H),(H.T).(T,H),(T,T)) 保Re照。 cond coins are tails 22
CHAPTER 2 Axioms of Probability 2.1 INTRODUCTION 2.2 SAMPLE SPACE AND EVENTS 2.3 AXIOMS OF PROBABILITY 2.4 SOME SIMPLE PROPOSITIONS 2.5 SAMPLE SPACES HAVING EQUALLY LIKELY OUTCOMES 2.6 PROBABILITY AS A CONTINUOUS SET FUNCTION 2.7 PROBABILITY AS A MEASURE OF BELIEF 2.1 INTRODUCTION In this chapter, we introduce the concept of the probability of an event and then show how probabilities can be computed in certain situations. As a preliminary, however, we need the concept of the sample space and the events of an experiment. 2.2 SAMPLE SPACE AND EVENTS Consider an experiment whose outcome is not predictable with certainty. However, although the outcome of the experiment will not be known in advance, let us suppose that the set of all possible outcomes is known. This set of all possible outcomes of an experiment is known as the sample space of the experiment and is denoted by S. Following are some examples: 1. If the outcome of an experiment consists in the determination of the sex of a newborn child, then S = {g, b} where the outcome g means that the child is a girl and b that it is a boy. 2. If the outcome of an experiment is the order of finish in a race among the 7 horses having post positions 1, 2, 3, 4, 5, 6, and 7, then S = {all 7! permutations of (1, 2, 3, 4, 5, 6, 7)} The outcome (2, 3, 1, 6, 5, 4, 7) means, for instance, that the number 2 horse comes in first, then the number 3 horse, then the number 1 horse, and so on. 3. If the experiment consists of flipping two coins, then the sample space consists of the following four points: S = {(H, H),(H, T),(T, H),(T, T)} The outcome will be (H, H) if both coins are heads, (H, T) if the first coin is heads and the second tails, (T, H) if the first is tails and the second heads, and (T, T) if both coins are tails. 22