Sheldon ross a first course in probability pdf download

Citation preview

1 of 848

Tenth Edition

2 of 848

Tenth Edition Sheldon Ross University of Southern California

Director, Portfolio Management: Deirdre Lynch Courseware Portfolio Manager: Suzanna Bainbridge Courseware Portfolio Management Assistant: Morgan Danna Content Producer: Tara Corpuz Managing Producer: Scott Disanno Producer: Jon Wooding Product Marketing Manager: Yvonne Vannatta Product Marketing Assistant: Jon Bryant Field Marketing Manager: Evan St. Cyr Senior Author Support/Technology Specialist: Joe Vetere Manager, Rights and Permissions: Gina Cheselka Cover Design: Studio Montage Production Coordination, Composition, and Illustrations: Integra Software Services Pvt. Ltd. Manufacturing Buyer: Carol Melville, LSC Communications Cover Image: Adrienne Bresnahan/Moment/Getty Images Copyright © 2019, 2014, 2010 by Pearson Education, Inc. All Rights Reserved. Printed in the United States of America. This publication is protected by copyright, and permission should be obtained from the publisher prior to any prohibited reproduction, storage in a retrieval system, or transmission in any form or by any means, electronic, mechanical, photocopying, recording, or otherwise. For information regarding permissions, request forms and the appropriate contacts within

3 of 848

the Pearson Education Global Rights & Permissions department, please visit www.pearsoned.com/permissions/. Credits and acknowledgments borrowed from other sources and reproduced, with permission, in this textbook appear on page 506 within text. PEARSON, ALWAYS LEARNING, and MYLAB are exclusive trademarks owned by Pearson Education, Inc. or its affiliates in the U.S. and/or other countries. Unless otherwise indicated herein, any third-party trademarks that may appear in this work are the property of their respective owners and any references to third-party trademarks, logos or other trade dress are for demonstrative or descriptive purposes only. Such references are not intended to imply any sponsorship, endorsement, authorization, or promotion of Pearson’s products by the owners of such marks, or any relationship between the owner and Pearson Education, Inc. or its affiliates, authors, licensees or distributors. Library of Congress Cataloging-in-Publication Data Names: Ross, Sheldon M., author. Title: A first course in probability / Sheldon Ross (University of Southern California). Other titles: Probability Description: Tenth edition. | Boston: Pearson, 2018. | Includes index. Identifiers: LCCN 2018006823 | ISBN 9780134753119 | ISBN 0134753119 Subjects: LCSH: Probabilities—Textbooks. Classification: LCC QA273 .R83 2018 | DDC 519.2—dc23 LC record available at https://lccn.loc.gov/2018006823 1 18 ISBN-10:  0-13-475311-9 ISBN-13: 978-0-13-475311-9

4 of 848

For Rebecca

Preface x 1 Combinatorial Analysis 1 1.1 Introduction 1 1.2 The Basic Principle of Counting 2 1.3 Permutations 3 1.4 Combinations 5 1.5 Multinomial Coefficients 9 1.6 The Number of Integer Solutions of Equations 12 Summary 15 Problems 15 Theoretical Exercises 18 Self-Test Problems and Exercises 20 2 Axioms of Probability 22 2.1 Introduction 22 2.2 Sample Space and Events 22 2.3 Axioms of Probability 26 2.4 Some Simple Propositions 29 2.5 Sample Spaces Having Equally Likely Outcomes 33 2.6 Probability as a Continuous Set Function 44 2.7 Probability as a Measure of Belief 48 Summary 49 Problems 50 Theoretical Exercises 55 Self-Test Problems and Exercises 56 3 Conditional Probability and Independence 58 3.1 Introduction 58

5 of 848

3.2 Conditional Probabilities 58 3.3 Bayes’s Formula 64 3.4 Independent Events 78 3.5 P(ꞏ|F) Is a Probability 95 Summary 102 Problems 103 Theoretical Exercises 113 Self-Test Problems and Exercises 116 4 Random Variables 119 4.1 Random Variables 119 4.2 Discrete Random Variables 123 4.3 Expected Value 126 4.4 Expectation of a Function of a Random Variable 128 4.5 Variance 132 4.6 The Bernoulli and Binomial Random Variables 137 4.6.1 Properties of Binomial Random Variables 142 4.6.2 Computing the Binomial Distribution Function 145 4.7 The Poisson Random Variable 146 4.7.1 Computing the Poisson Distribution Function 158 4.8 Other Discrete Probability Distributions 158 4.8.1 The Geometric Random Variable 158 4.8.2 The Negative Binomial Random Variable 160 4.8.3 The Hypergeometric Random Variable 163 4.8.4 The Zeta (or Zipf) Distribution 167 4.9 Expected Value of Sums of Random Variables 167 4.10 Properties of the Cumulative Distribution Function 172 Summary 174 Problems 175 Theoretical Exercises 182 Self-Test Problems and Exercises 186

6 of 848

5 Continuous Random Variables 189 5.1 Introduction 189 5.2 Expectation and Variance of Continuous Random Variables 193 5.3 The Uniform Random Variable 197 5.4 Normal Random Variables 200 5.4.1 The Normal Approximation to the Binomial Distribution 207 5.5 Exponential Random Variables 211 5.5.1 Hazard Rate Functions 215 5.6 Other Continuous Distributions 218 5.6.1 The Gamma Distribution 218 5.6.2 The Weibull Distribution 219 5.6.3 The Cauchy Distribution 220 5.6.4 The Beta Distribution 221 5.6.5 The Pareto Distribution 223 5.7 The Distribution of a Function of a Random Variable 224 Summary 227 Problems 228 Theoretical Exercises 231 Self-Test Problems and Exercises 233 6 Jointly Distributed Random Variables 237 6.1 Joint Distribution Functions 237 6.2 Independent Random Variables 247 6.3 Sums of Independent Random Variables 258 6.3.1 Identically Distributed Uniform Random Variables 258 6.3.2 Gamma Random Variables 260 6.3.3 Normal Random Variables 262 6.3.4 Poisson and Binomial Random Variables 266 6.4 Conditional Distributions: Discrete Case 267 6.5 Conditional Distributions: Continuous Case 270 6.6 Order Statistics 276

7 of 848

6.7 Joint Probability Distribution of Functions of Random Variables 280 6.8 Exchangeable Random Variables 287 Summary 290 Problems 291 Theoretical Exercises 296 Self-Test Problems and Exercises 299 7 Properties of Expectation 303 7.1 Introduction 303 7.2 Expectation of Sums of Random Variables 304 7.2.1 Obtaining Bounds from Expectations via the Probabilistic Method 317 7.2.2 The Maximum–Minimums Identity 319 7.3 Moments of the Number of Events that Occur 321 7.4 Covariance, Variance of Sums, and Correlations 328 7.5 Conditional Expectation 337 7.5.1 Definitions 337 7.5.2 Computing Expectations by Conditioning 339 7.5.3 Computing Probabilities by Conditioning 349 7.5.4 Conditional Variance 354 7.6 Conditional Expectation and Prediction 356 7.7 Moment Generating Functions 360 7.7.1 Joint Moment Generating Functions 369 7.8 Additional Properties of Normal Random Variables 371 7.8.1 The Multivariate Normal Distribution 371 7.8.2 The Joint Distribution of the Sample Mean and Sample Variance 373 7.9 General Definition of Expectation 375 Summary 377 Problems 378 Theoretical Exercises 385

8 of 848

Self-Test Problems and Exercises 390 8 Limit Theorems 394 8.1 Introduction 394 8.2 Chebyshev’s Inequality and the Weak Law of Large Numbers 394 8.3 The Central Limit Theorem 397 8.4 The Strong Law of Large Numbers 406 8.5 Other Inequalities and a Poisson Limit Result 409 8.6 Bounding the Error Probability When Approximating a Sum of Independent Bernoulli Random Variables by a Poisson Random Variable 418 8.7 The Lorenz Curve 420 Summary 424 Problems 424 Theoretical Exercises 426 Self-Test Problems and Exercises 428 9 Additional Topics in Probability 430 9.1 The Poisson Process 430 9.2 Markov Chains 432 9.3 Surprise, Uncertainty, and Entropy 437 9.4 Coding Theory and Entropy 441 Summary 447 Problems and Theoretical Exercises 447 Self-Test Problems and Exercises 448 10 Simulation 450 10.1 Introduction 450 10.2 General Techniques for Simulating Continuous Random Variables 453 10.2.1 The Inverse Transformation Method 453 10.2.2 The Rejection Method 454 10.3 Simulating from Discrete Distributions 459

9 of 848

10.4 Variance Reduction Techniques 462 10.4.1 Use of Antithetic Variables 463 10.4.2 Variance Reduction by Conditioning 463 10.4.3 Control Variates 465 Summary 465 Problems 466 Self-Test Problems and Exercises 467 Answers to Selected Problems 468 Solutions to Self-Test Problems and Exercises 470 Index 502 Common Discrete Distributions inside front cover Common Continuous Distributions inside back cover

“We see that the theory of probability is at bottom only common sense reduced to calculation; it makes us appreciate with exactitude what reasonable minds feel by a sort of instinct, often without being able to account for it... It is remarkable that this science, which originated in the consideration of games of chance, should have become the most important object of human knowledge.... The most important questions of life are, for the most part, really only problems of probability.” So said the famous French mathematician and astronomer (the “Newton of France”) PierreSimon, Marquis de Laplace. Although many people believe that the famous marquis, who was also one of the great contributors to the development of probability, might have exaggerated somewhat, it is nevertheless true that probability theory has become a tool of fundamental importance to nearly all scientists, engineers, medical practitioners, jurists, and industrialists. In fact, the enlightened individual had learned to ask not “Is it so?” but rather “What is the probability that it is so?”

This book is intended as an elementary introduction to the theory of probability for students in mathematics, statistics, engineering, and the sciences (including

10 of 848

computer science, biology, the social sciences, and management science) who possess the prerequisite knowledge of elementary calculus. It attempts to present not only the mathematics of probability theory, but also, through numerous examples, the many diverse possible applications of this subject.

Chapter 1

presents the basic principles of combinatorial analysis, which are most

useful in computing probabilities. Chapter 2

handles the axioms of probability theory and shows how they can be

applied to compute various probabilities of interest. Chapter 3

deals with the extremely important subjects of conditional probability

and independence of events. By a series of examples, we illustrate how conditional probabilities come into play not only when some partial information is available, but also as a tool to enable us to compute probabilities more easily, even when no partial information is present. This extremely important technique of obtaining probabilities by “conditioning” reappears in Chapter 7

, where we use it to obtain expectations.

The concept of random variables is introduced in Chapters 4 Discrete random variables are dealt with in Chapter 4 variables in Chapter 5

,5

, and 6

.

, continuous random

, and jointly distributed random variables in Chapter 6

.

The important concepts of the expected value and the variance of a random variable are introduced in Chapters 4

and 5

, and these quantities are then determined

for many of the common types of random variables. Additional properties of the expected value are considered in Chapter 7

. Many

examples illustrating the usefulness of the result that the expected value of a sum of random variables is equal to the sum of their expected values are presented. Sections on conditional expectation, including its use in prediction, and on momentgenerating functions are contained in this chapter. In addition, the final section introduces the multivariate normal distribution and presents a simple proof concerning the joint distribution of the sample mean and sample variance of a sample from a normal distribution. Chapter 8

presents the major theoretical results of probability theory. In particular,

we prove the strong law of large numbers and the central limit theorem. Our proof of the strong law is a relatively simple one that assumes that the random variables have a finite fourth moment, and our proof of the central limit theorem assumes Levy’s continuity theorem. This chapter also presents such probability inequalities as Markov’s inequality, Chebyshev’s inequality, and Chernoff bounds. The final section

11 of 848

of Chapter 8

gives a bound on the error involved when a probability concerning a

sum of independent Bernoulli random variables is approximated by the corresponding probability of a Poisson random variable having the same expected value. Chapter 9

presents some additional topics, such as Markov chains, the Poisson

process, and an introduction to information and coding theory, and Chapter 10 considers simulation. As in the previous edition, three sets of exercises are given at the end of each chapter. They are designated as Problems, Theoretical Exercises, and Self-Test Problems and Exercises. This last set of exercises, for which complete solutions appear in Solutions to Self-Test Problems and Exercises, is designed to help students test their comprehension and study for exams.

The tenth edition continues the evolution and fine tuning of the text. Aside from a multitude of small changes made to increase the clarity of the text, the new edition includes many new and updated problems, exercises, and text material chosen both for inherent interest and for their use in building student intuition about probability. Illustrative of these goals are Examples 4n of Chapter 3

, which deals with

computing NCAA basketball tournament win probabilities, and Example 5b of Chapter 4 , which introduces the friendship paradox. There is also new material on the Pareto distribution (introduced in Section 5.6.5 ), on Poisson limit results (in Section 8.5

), and on the Lorenz curve (in Section 8.7

).

I would like to thank the following people who have graciously taken the time to contact me with comments for improving the text: Amir Ardestani, Polytechnic University of Teheran; Joe Blitzstein, Harvard University; Peter Nuesch, University of Lausaunne; Joseph Mitchell, SUNY, Stony Brook; Alan Chambless, actuary; Robert Kriner; Israel David, Ben-Gurion University; T. Lim, George Mason University; Wei Chen, Rutgers; D. Monrad, University of Illinois; W. Rosenberger, George Mason University; E. Ionides, University of Michigan; J. Corvino, Lafayette College; T. Seppalainen, University of Wisconsin; Jack Goldberg; University of Michigan; Sunil Dhar, New Jersey Institute of Technology; Vladislav Kargin, Stanford University; Marlene Miller; Ahmad Parsian; and Fritz Scholz, University of Washington. I would also like to especially thank the reviewers of the ninth and tenth editions:

12 of 848

Richard Laugesen, University of Illinois; Stacey Hancock, Clark University; Stefan Heinz, University of Wyoming; and Brian Thelen, University of Michigan; Mark Ward, Purdue University. I would like to thank the accuracy checker, Stacey Hancock (Montana State University), for her careful review. Finally, I would like to thank the following reviewers for their many helpful comments. Reviewers of the tenth edition are marked with an asterisk. K. B. Athreya, Iowa State University Richard Bass, University of Connecticut Robert Bauer, University of Illinois at Urbana-Champaign Phillip Beckwith, Michigan Tech Arthur Benjamin, Harvey Mudd College Geoffrey Berresford, Long Island University Baidurya Bhattacharya, University of Delaware Howard Bird, St. Cloud State University Shahar Boneh, Metropolitan State College of Denver Jean Cadet, State University of New York at Stony Brook Steven Chiappari, Santa Clara University Nicolas Christou, University of California, Los Angeles James Clay, University of Arizona at Tucson Francis Conlan, University of Santa Clara Justin Corvino, Lafayette College Jay DeVore, California Polytechnic University, San Luis Obispo Scott Emerson, University of Washington Thomas R. Fischer, Texas A & M University Anant Godbole, Michigan Technical University Zakkula Govindarajulu, University of Kentucky Richard Groeneveld, Iowa State University *Stacey Hancock, Clark University Mike Hardy, Massachusetts Institute of Technology

13 of 848

Bernard Harris, University of Wisconsin Larry Harris, University of Kentucky David Heath, Cornell University *Stefan Heinz, University of Wyoming Stephen Herschkorn, Rutgers University Julia L. Higle, University of Arizona Mark Huber, Duke University Edward Ionides, University of Michigan Anastasia Ivanova, University of North Carolina Hamid Jafarkhani, University of California, Irvine Chuanshu Ji, University of North Carolina, Chapel Hill Robert Keener, University of Michigan *Richard Laugesen, University of Illinois Fred Leysieffer, Florida State University Thomas Liggett, University of California, Los Angeles Helmut Mayer, University of Georgia Bill McCormick, University of Georgia Ian McKeague, Florida State University R. Miller, Stanford University Ditlev Monrad, University of Illinois Robb J. Muirhead, University of Michigan Joe Naus, Rutgers University Nhu Nguyen, New Mexico State University Ellen O’Brien, George Mason University N. U. Prabhu, Cornell University Kathryn Prewitt, Arizona State University Jim Propp, University of Wisconsin William F. Rosenberger, George Mason University

14 of 848

Myra Samuels, Purdue University I. R. Savage, Yale University Art Schwartz, University of Michigan at Ann Arbor Therese Shelton, Southwestern University Malcolm Sherman, State University of New York at Albany Murad Taqqu, Boston University *Brian Thelen, University of Michigan Eli Upfal, Brown University Ed Wheeler, University of Tennessee Allen Webster, Bradley University S. R. [email protected]

1.1 Introduction 1.2 The Basic Principle of Counting 1.3 Permutations 1.4 Combinations 1.5 Multinomial Coefficients 1.6 The Number of Integer Solutions of Equations

Here is a typical problem of interest involving probability: A communication system is to consist of 𝑛 seemingly identical antennas that are to be lined up in a linear order.

15 of 848

The resulting system will then be able to receive all incoming signals and will be called functional as long as no two consecutive antennas are defective. If it turns out that exactly 𝑚 of the 𝑛 antennas are defective, what is the probability that the resulting system will be functional? For instance, in the special case where 𝑛 𝑚 2, there are 6 possible system configurations, namely, 0 0 1 0 1 1

1 1 0 0 0 1

1 0 1 1 0 0

4 and

0 1 0 1 1 0

where 1 means that the antenna is working and 0 that it is defective. Because the resulting system will be functional in the first 3 arrangements and not functional in the 3 1 remaining 3, it seems reasonable to take 6 2 as the desired probability. In the case of general 𝑛 and 𝑚, we could compute the probability that the system is functional in a similar fashion. That is, we could count the number of configurations that result in the system’s being functional and then divide by the total number of all possible configurations. From the preceding discussion, we see that it would be useful to have an effective method for counting the number of ways that things can occur. In fact, many problems in probability theory can be solved simply by counting the number of different ways that a certain event can occur. The mathematical theory of counting is formally known as combinatorial analysis.

The basic principle of counting will be fundamental to all our work. Loosely put, it states that if one experiment can result in any of 𝑚 possible outcomes and if another experiment can result in any of 𝑛 possible outcomes, then there are mn possible outcomes of the two experiments.

The basic principle of counting Suppose that two experiments are to be performed. Then if experiment 1 can result in any one of 𝑚 possible outcomes and if, for each outcome of experiment 1, there are 𝑛 possible outcomes of experiment 2, then together there are mn possible outcomes of the two experiments. Proof of the Basic Principle: The basic principle may be proven by enumerating all the possible outcomes of the two experiments; that is,

16 of 848

1, 1 ,

1, 2 ,

. . .,

1, 𝑛

2, 1 ,

2, 2 ,

. . .,

2, 𝑛

𝑚, 2 , . . .,

𝑚, 𝑛

⋮ 𝑚, 1 ,

where we say that the outcome is (𝑖, 𝑗) if experiment 1 results in its 𝑖th possible outcome and experiment 2 then results in its 𝑗th possible outcome. Hence, the set of possible outcomes consists of 𝑚 rows, each containing 𝑛 elements. This proves the result. Example 2a A small community consists of 10 women, each of whom has 3 children. If one woman and one of her children are to be chosen as mother and child of the year, how many different choices are possible?

Solution By regarding the choice of the woman as the outcome of the first experiment and the subsequent choice of one of her children as the outcome of the second experiment, we see from the basic principle that there are 10

3

30 possible

choices. When there are more than two experiments to be performed, the basic principle can be generalized.

The generalized basic principle of counting If 𝑟 experiments that are to be performed are such that the first one may result in any of 𝑛 possible outcomes; and if, for each of these 𝑛 possible outcomes, there are 𝑛 possible outcomes of the second experiment; and if, for each of the possible outcomes of the first two experiments, there are 𝑛 possible outcomes of the third experiment; and if, then there is a total of 𝑛 ⋅ 𝑛 ⋯𝑛 possible outcomes of the 𝑟 experiments. Example 2b A college planning committee consists of 3 freshmen, 4 sophomores, 5 juniors, and 2 seniors. A subcommittee of 4, consisting of 1 person from each class, is to be chosen. How many different subcommittees are possible?

Solution We may regard the choice of a subcommittee as the combined outcome of the four separate experiments of choosing a single representative from each of the classes. It then follows from the generalized version of the basic principle that

17 of 848

there are 3

4

5

2

120 possible subcommittees.

Example 2c How many different 7-place license plates are possible if the first 3 places are to be occupied by letters and the final 4 by numbers?

Solution By the generalized version of the basic principle, the answer is 26 ⋅ 26 ⋅ 26 ⋅ 10 ⋅ 10 ⋅ 10 ⋅ 10 175,760,000. Example 2d How many functions defined on 𝑛 points are possible if each functional value is either 0 or 1?

Solution Let the points be 1,2, . . . ,𝑛. Since 𝑓 𝑖 must be either 0 or 1 for each 𝑖

1,2, . . . ,𝑛,

it follows that there are 2 possible functions. Example 2e In Example 2c , how many license plates would be possible if repetition among letters or numbers were prohibited?

Solution In this case, there would be 26 ⋅ 25 ⋅ 24 ⋅ 10 ⋅ 9 ⋅ 8 ⋅ 7

78,624,000 possible

license plates.

How many different ordered arrangements of the letters 𝑎, 𝑏, and 𝑐 are possible? By direct enumeration we see that there are 6, namely, abc, acb, bac, bca, cab, and cba. Each arrangement is known as a permutation. Thus, there are 6 possible permutations of a set of 3 objects. This result could also have been obtained from the basic principle, since the first object in the permutation can be any of the 3, the second object in the permutation can then be chosen from any of the remaining 2, and the third object in the permutation is then the remaining 1. Thus, there are 3⋅2⋅1

6 possible permutations.

Suppose now that we have 𝑛 objects. Reasoning similar to that we have just used for the 3 letters then shows that there are

18 of 848

𝑛 𝑛

1 𝑛

2 ⋯3 ⋅ 2 ⋅ 1

𝑛!

different permutations of the 𝑛 objects. Whereas 𝑛! (read as “n factorial”) is defined to equal 1 ⋅ 2⋯𝑛 when 𝑛 is a positive integer, it is convenient to define 0! to equal 1. Example 3a How many different batting orders are possible for a baseball team consisting of 9 players?

Solution There are 9!

362,880 possible batting orders.

Example 3b A class in probability theory consists of 6 men and 4 women. An examination is given, and the students are ranked according to their performance. Assume that no two students obtain the same score. a. How many different rankings are possible? b. If the men are ranked just among themselves and the women just among themselves, how many different rankings are possible?

Solution a. (a) Because each ranking corresponds to a particular ordered arrangement of the 10 people, the answer to this part is 10!

3,628,800.

b. (b) Since there are 6! possible rankings of the men among themselves and 4! possible rankings of the women among themselves, it follows from the basic principle that there are 6! 4!

720 24

17,280 possible

rankings in this case. Example 3c Ms. Jones has 10 books that she is going to put on her bookshelf. Of these, 4 are mathematics books, 3 are chemistry books, 2 are history books, and 1 is a language book. Ms. Jones wants to arrange her books so that all the books dealing with the same subject are together on the shelf. How many different arrangements are possible?

Solution There are 4! 3! 2! 1! arrangements such that the mathematics books are first in

19 of 848

line, then the chemistry books, then the history books, and then the language book. Similarly, for each possible ordering of the subjects, there are 4! 3! 2! 1! possible arrangements. Hence, as there are 4! possible orderings of the subjects, the desired answer is 4! 4! 3! 2! 1!

6912.

We shall now determine the number of permutations of a set of 𝑛 objects when certain of the objects are indistinguishable from one another. To set this situation straight in our minds, consider the following example. Example 3d How many different letter arrangements can be formed from the letters 𝑃𝐸𝑃𝑃𝐸𝑅?

Solution We first note that there are 6! permutations of the letters 𝑃 𝐸 𝑃 𝑃 𝐸 𝑅 when the 3𝑃's and the 2𝐸's are distinguished from one another. However, consider any one of these permutations for instance, 𝑃 𝑃 𝐸 𝑃 𝐸 𝑅. If we now permute the 𝑃’s among themselves and the 𝐸’s among themselves, then the resultant arrangement would still be of the form 𝑃𝑃𝐸𝑃𝐸𝑅. That is, all 3! 2! permutations 𝑃 𝑃 𝐸 𝑃 𝐸 𝑅 𝑃 𝑃 𝐸 𝑃 𝐸 𝑅 𝑃 𝑃 𝐸 𝑃 𝐸 𝑅 𝑃 𝑃 𝐸 𝑃 𝐸 𝑅 𝑃 𝑃 𝐸 𝑃 𝐸 𝑅 𝑃 𝑃 𝐸 𝑃 𝐸 𝑅 𝑃 𝑃 𝐸 𝑃 𝐸 𝑅 𝑃 𝑃 𝐸 𝑃 𝐸 𝑅 𝑃 𝑃 𝐸 𝑃 𝐸 𝑅 𝑃 𝑃 𝐸 𝑃 𝐸 𝑅 𝑃 𝑃 𝐸 𝑃 𝐸 𝑅 𝑃 𝑃 𝐸 𝑃 𝐸 𝑅 are of the form 𝑃𝑃𝐸𝑃𝐸𝑅. Hence, there are 6!/ 3! 2!

60 possible letter

arrangements of the letters 𝑃𝐸𝑃𝑃𝐸𝑅. In general, the same reasoning as that used in Example 3d

shows that

there are 𝑛! 𝑛 ! 𝑛 ! ⋯ 𝑛 ! different permutations of 𝑛 objects, of which 𝑛 are alike, 𝑛 are alike, . . . ,𝑛 are alike. Example 3e A chess tournament has 10 competitors, of which 4 are Russian, 3 are from the United States, 2 are from Great Britain, and 1 is from Brazil. If the tournament result lists just the nationalities of the players in the order in which they placed, how many outcomes are possible?

20 of 848

Solution There are 10! 4! 3! 2! 1!

12,600

possible outcomes. Example 3f How many different signals, each consisting of 9 flags hung in a line, can be made from a set of 4 white flags, 3 red flags, and 2 blue flags if all flags of the same color are identical?

Solution There are 9! 4! 3! 2!

1260

different signals.

We are often interested in determining the number of different groups of 𝑟 objects that could be formed from a total of 𝑛 objects. For instance, how many different groups of 3 could be selected from the 5 items 𝐴, 𝐵, 𝐶, 𝐷, and 𝐸? To answer this question, reason as follows: Since there are 5 ways to select the initial item, 4 ways to then select the next item, and 3 ways to select the final item, there are thus 5 ⋅ 4 ⋅ 3 ways of selecting the group of 3 when the order in which the items are selected is relevant. However, since every group of 3–say, the group consisting of items 𝐴, 𝐵, and 𝐶 will be counted 6 times (that is, all of the permutations ABC, ACB, BAC, BCA, CAB, and CBA will be counted when the order of selection is relevant), it follows that the total number of groups that can be formed is 5⋅4⋅3 3⋅2⋅1 In general, as 𝑛 𝑛

1 ⋯ 𝑛

𝑟

10

1 represents the number of different ways that a

group of 𝑟 items could be selected from 𝑛 items when the order of selection is relevant, and as each group of 𝑟 items will be counted 𝑟! times in this count, it follows that the number of different groups of 𝑟 items that could be formed from a set of 𝑛

21 of 848

items is 𝑛 𝑛

1 ⋯ 𝑛 𝑟!

𝑟

1

𝑛! 𝑛 𝑟 ! 𝑟!

Notation and terminology We define

𝑛 , for 𝑟 𝑟

𝑛, by 𝑛 𝑟

𝑛! 𝑛 𝑟 ! 𝑟!

𝑛 (read as “𝑛 choose 𝑟“) represents the number of possible 𝑟

and say that

combinations of 𝑛 objects taken 𝑟 at a time. 𝑛 Thus, represents the number of different groups of size 𝑟 that could be selected 𝑟 from a set of 𝑛 objects when the order of selection is not considered relevant. 𝑛 is the number of subsets of size 𝑟 that can be chosen from a set of 𝑟 𝑛! 𝑛 𝑛 1, which is consistent with size 𝑛. Using that 0! 1, note that 0!𝑛! 𝑛 0 Equivalently,

the preceding interpretation because in a set of size 𝑛 there is exactly 1 subset of size 𝑛 (namely, the entire set), and exactly one subset of size 0 (namely the empty 𝑛 set). A useful convention is to define equal to 0 when either 𝑟 𝑛 or 𝑟 0. 𝑟 Example 4a A committee of 3 is to be formed from a group of 20 people. How many different committees are possible?

Solution There are

20 3

20 ⋅ 19 ⋅ 18 3⋅2⋅1

1140 possible committees.

Example 4b From a group of 5 women and 7 men, how many different committees consisting of 2 women and 3 men can be formed? What if 2 of the men are feuding and refuse to serve on the committee together?

Solution

22 of 848

5 7 possible groups of 2 women, and possible groups of 3 2 3 5⋅4 5 7 . men, it follows from the basic principle that there are 2⋅1 2 3 7⋅6⋅5 350 possible committees consisting of 2 women and 3 men. 3⋅2⋅1 As there are

Now suppose that 2 of the men refuse to serve together. Because a total of 2 5 7 5 out of the 35 possible groups of 3 men contain both of the 2 1 3 feuding men, it follows that there are 35

5 5 2

of the feuding men. Because there are still women, there are 30 ⋅ 10

30 groups that do not contain both 10 ways to choose the 2

300 possible committees in this case.

Example 4c Consider a set of 𝑛 antennas of which 𝑚 are defective and 𝑛

𝑚 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 𝑛 𝑚 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 𝑛

𝑚

1 possible positions–represented in Figure 1.1

by carets–

between the 𝑛

𝑚 functional antennas, we must select 𝑚 of these in which to 𝑛 𝑚 1 put the defective antennas. Hence, there are possible orderings in 𝑚 which there is at least one functional antenna between any two defective ones. Figure 1.1 No consecutive defectives. The figure shows No consecutive defectives A useful combinatorial identity, known as Pascal’s identity, is (4.1) 𝑛 𝑟 Equation (4.1)

𝑛 𝑟

1 1

𝑛

1 𝑟

 1

𝑟

𝑛

may be proved analytically or by the following combinatorial

argument: Consider a group of 𝑛 objects, and fix attention on some particular one of

23 of 848

these objects–call it object 1. Now, there are

𝑛 𝑟

1 groups of size 𝑟 that contain 1

object 1 (since each such group is formed by selecting 𝑟 1 from the remaining 𝑛 1 groups of size 𝑟 that do not contain object 1. 𝑛 1 objects). Also, there are 𝑟 𝑛 follows. As there is a total of groups of size 𝑟, Equation (4.1) 𝑟 𝑛 are often referred to as binomial coefficients because of their 𝑟

The values

prominence in the binomial theorem.

The binomial theorem (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. Proof of the Binomial Theorem by Induction: When 𝑛

1, Equation (4.2)

reduces to 𝑥

for 𝑛

Assume Equation (4.2) 𝑥

𝑦

𝑥

𝑦 𝑥

𝑥

𝑦

𝑥

𝑦 𝑛

1 𝑘

1 𝑘

𝑘

𝑦

1. Now,

𝑛

Letting 𝑖

1  𝑥 𝑦 1

1  𝑥 𝑦 0

𝑦

1 in the first sum and 𝑖

𝑥

𝑦

 𝑥 𝑦 𝑛

1 𝑘

 𝑥 𝑦

𝑘 in the second sum, we find that

24 of 848

𝑥

𝑦

𝑛 𝑖

1  𝑥 𝑦 1

𝑛 𝑖

1  𝑥 𝑦 1 𝑛 𝑖

𝑥

𝑛 𝑖 𝑥

1 1

 𝑥 𝑦 𝑛

𝑦

𝑛

1 𝑖

𝑛  𝑥 𝑦 𝑖

𝑥

1

1 𝑖

 𝑥 𝑦

 𝑥 𝑦

𝑦

𝑦

𝑛  𝑥 𝑦 𝑖 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 𝑥

𝑦

𝑥

𝑦 ⋯ 𝑥

𝑦

Its expansion consists of the sum of 2 terms, each term being the product of 𝑛 factors. Furthermore, each of the 2 terms in the sum will contain as a factor either 𝑥 or 𝑦 for each 𝑖

1, 2, . . . ,𝑛. For example, 𝑥

𝑦

𝑥

𝑦

𝑥 𝑥

𝑥 𝑦

𝑦 𝑥

𝑦 𝑦

Now, how many of the 2 terms in the sum will have 𝑘 of the 𝑥 ’s and 𝑛 𝑦 ’s as factors? As each term consisting of 𝑘 of the 𝑥 ’s and 𝑛

𝑘 of the

𝑘 of the 𝑦 ’s

corresponds to a choice of a group of 𝑘 from the 𝑛 values 𝑥 ,  𝑥 …,  𝑥 , there are such terms. Thus, letting 𝑥

𝑥, 𝑦

𝑥

Example 4d Expand 𝑥

Solution

𝑦 .

𝑦

𝑦, 𝑖

1, . . . ,𝑛, we see that 𝑛  𝑥 𝑦 𝑘

𝑛 𝑘

25 of 848

𝑥

3  𝑥 𝑦 0

𝑦 𝑦

3  𝑥 𝑦 1

3𝑥𝑦

3𝑥 𝑦

3  𝑥 𝑦 2

3  𝑥 𝑦 3

𝑥

Example 4e How many subsets are there of a set consisting of 𝑛 elements?

Solution Since there are

𝑛 subsets of size 𝑘, the desired answer is 𝑘 𝑛 𝑘

1

1

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 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 2 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 1 element is 2

1.

In this section, we consider the following problem: A set of 𝑛 distinct items is to be divided into 𝑟 distinct groups of respective sizes 𝑛 ,𝑛 , . . . ,𝑛 , where

𝑛

𝑛.

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 are

𝑛

𝑛 𝑛

possible choices for the second group; for each choice of the first

two groups, there are

𝑛

𝑛 𝑛

𝑛

possible choices for the third group; and so on.

It then follows from the generalized version of the basic counting principle that there are

26 of 848

𝑛

𝑛 𝑛

𝑛 𝑛

𝑛

⋯

𝑛

𝑛

𝑛

⋯

𝑛

𝑛

𝑛! 𝑛 ! 𝑛 ! 𝑛

𝑛 𝑛

𝑛 𝑛 ! ⋯ 𝑛 ! 𝑛 !

𝑛

𝑛 ⋯ 0! 𝑛 !

𝑛

!

𝑛! 𝑛 ! 𝑛 !⋯𝑛 ! possible divisions. Another way to see this result is to consider the 𝑛 values  1,1, . . . ,1,2, . . . ,2, . . . , 𝑟, . . . ,𝑟, where 𝑖 appears 𝑛 times, for 𝑖

1, . . . ,𝑟. Every permutation of these values

corresponds to a division of the 𝑛 items into the 𝑟 groups in the following manner: Let the permutation 𝑖 ,𝑖 , . . . ,𝑖 correspond to assigning item 1 to group 𝑖 , item 2 to group 𝑖 , and so on. For instance, if 𝑛

8 and if 𝑛

4,𝑛

3, and 𝑛

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 𝑛 items into 𝑟 distinct groups of sizes 𝑛 ,𝑛 , . . . ,𝑛 is the same as the number of permutations of 𝑛 items of which 𝑛 are alike, and 𝑛 are alike, . . . , and 𝑛 are alike, which was shown in 𝑛! Section 1.3 to equal   . 𝑛 !𝑛 !⋯𝑛 !

Notation If 𝑛

𝑛

⋯

𝑛

𝑛, we define

𝑛 𝑛 ,𝑛 , . . . ,𝑛

𝑛 𝑛 ,𝑛 , . . . ,𝑛

Thus,

𝑛 𝑛 ,𝑛 , . . . ,𝑛

by

𝑛! 𝑛 ! 𝑛 !⋯𝑛 !

represents the number of possible divisions of 𝑛 distinct

objects into 𝑟 distinct groups of respective sizes 𝑛 ,𝑛 , . . . ,𝑛 . 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

27 of 848

There are

10! 5! 2! 3!

2520 possible divisions.

Example 5b Ten children are to be divided into an 𝐴 team and a 𝐵 team of 5 each. The 𝐴 team will play in one league and the 𝐵 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?

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 𝐴 or 𝐵 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                 𝑥

𝑥

⋯   



, . . .,

𝑥 𝑛 𝑛 ,𝑛 , . . .,𝑛

 𝑥 𝑥 ⋯𝑥



:

⋯

That is, the sum is over all nonnegative integer-valued vectors 𝑛 ,𝑛 , . . . ,𝑛 ⋯ 𝑛 𝑛. 𝑛 The numbers are known as multinomial coefficients. 𝑛 ,𝑛 , . . . ,𝑛 such that 𝑛

𝑛

Example 5d In the first round of a knockout tournament involving 𝑛

2 players, the 𝑛

28 of 848

players are divided into 𝑛/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 8 8! pair, and a fourth pair is . Thus, the number of possible pairings 2,  2,  2,  2 2 8! when there is no ordering of the 4 pairs is . For each such pairing, there are 2 4! 2 possible choices from each pair as to the winner of that game, showing that 8! 8!2 there are possible results of round 1. [Another way to see this is to 2 4! 4! 8 note that there are possible choices of the 4 winners and, for each such 4 choice, there are 4! ways to pair the 4 winners with the 4 losers, showing that 8! 8 there are 4! possible results for the first round.] 4! 4 4! possible outcomes of round 2, 2! 2! and for each of the outcomes of the first two rounds, there are possible 1! outcomes of round 3. Consequently, by the generalized basic principle of 8! 4! 2! counting, there are   8! possible outcomes of the tournament. Indeed, 4! 2! 1! the same argument can be used to show that a knockout tournament of 𝑛 2 players has 𝑛! possible outcomes. Similarly, for each result of round 1, there are

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, . . . ,𝑛. 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

29 of 848

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 2 matches be 2 plus the rank of the player who beat him, for 𝑘

0,  . . . , 𝑚

1.) In this manner, the result of the

tournament can be represented by a permutation 𝑖 ,𝑖 , . . . ,𝑖 , where 𝑖 is the player who was given rank 𝑗. 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, . . . ,𝑛. Example 5e 𝑥

𝑥

2  𝑥 𝑥 𝑥 2,  0,  0

𝑥

𝑥

2  𝑥 𝑥 𝑥 0,  2,  0

2  𝑥 𝑥 𝑥 0,  0,  2

2  𝑥 𝑥 𝑥 1,  1,  0

2  𝑥 𝑥 𝑥 1,  0,  1

2  𝑥 𝑥 𝑥 0,  1,  1

𝑥

𝑥

2𝑥 𝑥

2𝑥 𝑥

2𝑥 𝑥

* Asterisks denote material that is optional.

An individual has gone fishing at Lake Ticonderoga, which contains four types of fish: lake trout, catfish, bass, and bluefish. If we take the result of the fishing trip to be the numbers of each type of fish caught, let us determine the number of possible outcomes when a total of 10 fish are caught. To do so, note that we can denote the outcome of the fishing trip by the vector 𝑥 , 𝑥 ,  𝑥 ,  𝑥

where 𝑥 is the number of

trout that are caught, 𝑥 is the number of catfish, 𝑥 is the number of bass, and 𝑥 is the number of bluefish. Thus, the number of possible outcomes when a total of 10 fish are caught is the number of nonnegative integer vectors 𝑥 , 𝑥 ,  𝑥 ,  𝑥 to 10.

that sum

30 of 848

More generally, if we supposed there were 𝑟 types of fish and that a total of 𝑛 were caught, then the number of possible outcomes would be the number of nonnegative integer-valued vectors 𝑥 , . . . ,𝑥 such that (6.1) 𝑥

𝑥

. . .

𝑥

𝑛

To compute this number, let us start by considering the number of positive integervalued vectors 𝑥 , . . . ,𝑥 that satisfy the preceding. To determine this number, suppose that we have 𝑛 consecutive zeroes lined up in a row: 0 0 0  . . .  0 0 Note that any selection of 𝑟 Figure 1.2

1 of the 𝑛

1 spaces between adjacent zeroes (see

) corresponds to a positive solution of 6.1

by letting 𝑥 be the

number of zeroes before the first chosen space, 𝑥 be the number of zeroes between the first and second chosen space, . . . , and 𝑥 being the number of zeroes following the last chosen space. Figure 1.2 Number of positive solutions.

For instance, if we have 𝑛

8 and 𝑟

3, then (with the choices represented by dots)

the choice 0.0 0 0 0.0 0 0 corresponds to the solution 𝑥

1, 𝑥

4, 𝑥

3. As positive solutions of (6.1)

correspond, in a one-to-one fashion, to choices of 𝑟

1 of the adjacent spaces, it

follows that the number of differerent positive solutions is equal to the number of different selections of 𝑟 1 of the 𝑛 1 adjacent spaces. Consequently, we have the following proposition. Proposition 6.1

31 of 848

There are

𝑛 𝑟

1 distinct positive integer-valued vectors 𝑥 , 𝑥 , . . . ,𝑥 1

satisfying the equation 𝑥

𝑥

⋯

𝑥

𝑛, 𝑥

0, 𝑖

1, . . . ,𝑟

To obtain the number of nonnegative (as opposed to positive) solutions, note that the number of nonnegative solutions of 𝑥 of positive solutions of 𝑦

⋯

Hence, from Proposition 6.1

𝑦

𝑥 𝑛

⋯

𝑥

𝑛 is the same as the number

𝑟 (seen by letting 𝑦

𝑥

1, 𝑖

1, . . . ,𝑟).

, we obtain the following proposition.

Proposition 6.2 There are

𝑛

𝑟 𝑟

1 1

distinct nonnegative integer-valued vectors 𝑥 ,𝑥 , . . . ,𝑥

satisfying the equation 𝑥 Thus, using Proposition 6.2

𝑥

⋯

𝑥

𝑛

, we see that there are

13 3

286 possible

outcomes when a total of 10 Lake Ticonderoga fish are caught. Example 6a How many distinct nonnegative integer-valued solutions of 𝑥

𝑥

3 are

possible?

Solution There are

3

2 2

1 1

4 such solutions: (0, 3), (1, 2), (2, 1), (3, 0).

Example 6b An investor has $20,000 to invest among 4 possible investments. Each investment must be in units of $1000. If the total $20,000 is to be invested, how many different investment strategies are possible? What if not all the money needs to be invested?

Solution If we let 𝑥 , 𝑖

1, 2, 3, 4, denote the number of thousands invested in investment

𝑖, then, when all is to be invested, 𝑥 ,  𝑥 ,  𝑥 ,  𝑥 are integers satisfying the equation

32 of 848

𝑥

𝑥

Hence, by Proposition 6.2

𝑥

𝑥

20 𝑥 23 3

, there are

0

1771 possible investment

strategies. If not all of the money needs to be invested, then if we let 𝑥 denote the amount kept in reserve, a strategy is a nonnegative integer-valued vector 𝑥 ,  𝑥 ,  𝑥 ,  𝑥 ,  𝑥

satisfying the equation 𝑥

𝑥 Hence, by Proposition 6.2

𝑥

𝑥

𝑥

, there are now

20

24 4

10,626 possible strategies.

Example 6c How many terms are there in the multinomial expansion of 𝑥

𝑥

⋯

𝑥

?

Solution 𝑥

𝑥

⋯

𝑛 𝑛 , . . . ,𝑛

𝑥

 𝑥 ⋯𝑥

where the sum is over all nonnegative integer-valued 𝑛 , . . . ,𝑛 such that 𝑛 𝑟 1 𝑛 ⋯ 𝑛 𝑛. Hence, by Proposition 6.2 , there are such 𝑟 1 terms. Example 6d Let us consider again Example 4c

, in which we have a set of 𝑛 items, of

which 𝑚 are (indistinguishable and) defective and the remaining 𝑛

𝑚 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 𝑥 as the number of functional items to the left of the first defective, 𝑥 as the number of functional items between the first two defectives, and so on. That is, schematically, we have 𝑥  0 𝑥  0⋯𝑥  0 𝑥 Now, there will be at least one functional item between any pair of defectives as long as 𝑥

0, 𝑖

2, . . . ,𝑚. Hence, the number of outcomes satisfying the

condition is the number of vectors 𝑥 , . . . ,𝑥

that satisfy the equation

33 of 848

⋯

𝑥

𝑥 𝑥

But, on letting 𝑦

𝑛

𝑚, 𝑥

1, 𝑦

𝑥 , 𝑖

0, 𝑥

0, 𝑥

2, . . . ,𝑚, 𝑦

0, 𝑖 𝑥

2, . . . , 𝑚 1, we see that this

number is equal to the number of positive vectors 𝑦 , . . . ,𝑦

that satisfy the

equation 𝑦

𝑦

⋯

𝑦 𝑛

, there are

Hence, by Proposition 6.1

agreement with the results of Example 4c

𝑛

𝑚

𝑚 𝑚

1

2

such outcomes, in

.

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 𝑥

⋯

Upon letting 𝑦

𝑥 𝑥

𝑛 1, 𝑦

𝑚, 𝑥 𝑥

1, 𝑖

0, 𝑥

0, 𝑥

2, . . . ,𝑚, 𝑦

2, 𝑖 𝑥

2, . . . , 𝑚 1, we see that

this is the same as the number of positive solutions of the equation 𝑦

Hence, from Proposition 6.1

⋯

𝑦

, there are

𝑛

2𝑚

3

𝑛

2𝑚 𝑚

2

such outcomes.

The basic principle of counting states that if an experiment consisting of two phases is such that there are 𝑛 possible outcomes of phase 1 and, for each of these 𝑛 outcomes, there are 𝑚 possible outcomes of phase 2, then there are nm possible outcomes of the experiment. There are 𝑛!

𝑛 𝑛

1 ⋯3 ⋅ 2 ⋅ 1 possible linear orderings of 𝑛 items. The quantity 0!

is defined to equal 1. Let 𝑛 𝑖

𝑛! 𝑛 𝑖 ! 𝑖!

34 of 848

when 0

𝑖

𝑛, and let it equal 0 otherwise. This quantity represents the number of

different subgroups of size 𝑖 that can be chosen from a set of size 𝑛. It is often called a binomial coefficient because of its prominence in the binomial theorem, which states that

𝑥

𝑦

𝑛  𝑥 𝑦 𝑖

For nonnegative integers 𝑛 , . . . ,𝑛 summing to 𝑛, 𝑛 𝑛 ,𝑛 , . . .,𝑛

𝑛! 𝑛 !𝑛 !⋯𝑛 !

is the number of divisions of 𝑛 items into 𝑟 distinct nonoverlapping subgroups of sizes 𝑛 ,𝑛 . . . ,𝑛 . These quantities are called multinomial coefficients.

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:

35 of 848

“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. When all letters are used, 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 𝐴 and 𝐵 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 one another? 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?

36 of 848

12. How many 3 digit numbers 𝑥𝑦𝑧, with 𝑥,  𝑦,  𝑧 all ranging from 0 to 9 have at least 2 of their digits equal. How many have exactly 2 equal digits. 13. How many different letter permutations, of any length, can be made using the letters M O T T O. (For instance, there are 3 possible permutations of length 1.) 14. 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? 15. Consider a group of 20 people. If everyone shakes hands with everyone else, how many handshakes take place? 16. How many 5-card poker hands are there? 17. 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? 18. 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? 19. 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? 20. 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? 21. 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? 22. 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?

37 of 848

23. Consider the grid of points shown at the top of the next column. Suppose that, starting at the point labeled 𝐴, you can go one step up or one step to the right at each move. This procedure is continued until the point labeled 𝐵 is reached. How many different paths from 𝐴 to 𝐵 are possible? Hint: Note that to reach 𝐵 from 𝐴, you must take 4 steps to the right and 3 steps upward.

24. In Problem 23

, how many different paths are there from 𝐴 to 𝐵

that go through the point circled in the following lattice?

25. 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? 26. a. Show b. Simplify

𝑛  2 3 𝑘 𝑛  𝑥 𝑘

38 of 848

27. Expand 3𝑥

𝑦 .

28. The game of bridge is played by 4 players, each of whom is dealt 13 cards. How many bridge deals are possible? 29. Expand 𝑥

2𝑥

3𝑥

.

30. If 12 people are to be divided into 3 committees of respective sizes 3, 4, and 5, how many divisions are possible? 31. If 8 new teachers are to be divided among 4 schools, how many divisions are possible? What if each school must receive 2 teachers? 32. Ten weight lifters are competing in a team weight-lifting 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? 33. 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? * 34. 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? * 35. 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? * 36. We have $20,000 that must be invested among 4 possible opportunities. Each investment must be integral in units of $1000, and there are minimal investments that need to be made if one is to invest in these opportunities. The minimal investments are $2000, $2000, $3000, and $4000. 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? * 37. Suppose that 10 fish are caught at a lake that contains 5 distinct types of fish.

39 of 848

a. How many different outcomes are possible, where an outcome specifies the numbers of caught fish of each of the 5 types? b. How many outcomes are possible when 3 of the 10 fish caught are trout? c. How many when at least 2 of the 10 are trout?

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 𝑚 possible outcomes. If the first experiment results in outcome 𝑖, then the second experiment can result in any of 𝑛 possible outcomes, 𝑖

1, 2, . . . ,𝑚.

What is the number of possible outcomes of the two experiments? 3. In how many ways can 𝑟 objects be selected from a set of 𝑛 objects if the order of selection is considered relevant? 𝑛 4. There are different linear arrangements of 𝑛 balls of which 𝑟 are black 𝑟 and 𝑛

𝑟 are white. Give a combinatorial explanation of this fact.

5. Determine the number of vectors 𝑥 , . . . ,𝑥 , such that each 𝑥 is either 0 or 1 and 𝑥

𝑘

6. How many vectors 𝑥 , . . . ,𝑥 are there for which each 𝑥 is a positive integer such that 1

𝑥

𝑛 and 𝑥

𝑥

⋯

𝑥 ?

7. Give an analytic proof of Equation (4.1)

.

8. Prove that 𝑛

𝑛 0

𝑚 𝑟

⋯

𝑚 𝑟

𝑛 1 𝑛 𝑟

𝑚 𝑟

1

𝑚 0

Hint: Consider a group of 𝑛 men and 𝑚 women. How many groups of size 𝑟 are possible? 9. Use Theoretical Exercise 8 2𝑛 𝑛

to prove that 𝑛 𝑘

10. From a group of 𝑛 people, suppose that we want to choose a committee of

40 of 848

𝑘, 𝑘

𝑛, one of whom is to be designated as chairperson. a. By focusing first on the choice of the committee and then on the choice 𝑛  𝑘 possible choices. of the chair, argue that there are 𝑘 b. By focusing first on the choice of the nonchair committee members and 𝑛   𝑛 𝑘 1 then on the choice of the chair, argue that there are 𝑘 1 possible choices. c. By focusing first on the choice of the chair and then on the choice of 𝑛 1 the other committee members, argue that there are 𝑛  possible 𝑘 1 choices. d. Conclude from parts (a), (b), and (c) that 𝑛 𝑛 𝑘  𝑛 𝑘 1 𝑘 𝑘 1

e. Use the factorial definition of

𝑛 

𝑛 𝑘

1 1

𝑚 to verify the identity in part (d). 𝑟

11. The following identity is known as Fermat’s combinatorial identity: 𝑛 𝑘

𝑖 𝑘

1  𝑛 1

𝑘

Give a combinatorial argument (no computations are needed) to establish this identity. Hint: Consider the set of numbers 1 through 𝑛. How many subsets of size 𝑘 have 𝑖 as their highest numbered member? 12. Consider the following combinatorial identity: 𝑘 

𝑛 𝑘

𝑛⋅2

a. Present a combinatorial argument for this identity by considering a set of 𝑛 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 𝑘 and its chairperson? ii. How many possible selections are there of a chairperson and the other committee members?

41 of 848

b. Verify the following identity for 𝑛 𝑛  𝑘 𝑘

1,  2,  3,  4,  5: 2

𝑛 𝑛

1

For a combinatorial proof of the preceding, consider a set of 𝑛 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 𝑘 people? ii. How many different selections are there in which the chairperson and the secretary are the same? (ANSWER: 𝑛2 ) iii. How many different selections result in the chairperson and the secretary being different? c. Now argue that 𝑛  𝑘 𝑘 13. Show that, for 𝑛

2

𝑛 𝑛

3

0, 1

𝑛 𝑖

0

Hint: Use the binomial theorem. 14. From a set of 𝑛 people, a committee of size 𝑗 is to be chosen, and from this committee, a subcommittee of size 𝑖,𝑖

𝑗, 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: 𝑛 𝑗

𝑗 𝑖

𝑛  2 𝑖

c. Use part (a) and Theoretical Exercise 13

 𝑖

𝑛

to show that

.

42 of 848

𝑛 𝑗

𝑗   𝑖

1

0 𝑖

𝑛

15. Let 𝐻 𝑛 be the number of vectors 𝑥 , . . . ,𝑥 for which each 𝑥 is a positive integer satisfying 1

𝑥

𝑛 and 𝑥

𝑥

⋯

𝑥 .

𝑗  𝑘

1

a. Without any computations, argue that 𝑛 𝐻 𝑛 𝐻 𝑛

𝐻

Hint: How many vectors are there in which 𝑥

𝑗?

b. Use the preceding recursion to compute 𝐻 5 . Hint: First compute 𝐻 𝑛 for 𝑛

1, 2, 3, 4, 5.

16. Consider a tournament of 𝑛 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 who tied for first place, the next group being those who tied for the next-best position, and so on. Let 𝑁 𝑛 denote the number of different possible outcomes. For instance, 𝑁 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 𝑛

3.

b. With 𝑁(0) defined to equal 1, argue, without any computations, that 𝑁 𝑛

𝑛  𝑁 𝑛 𝑖

𝑖

Hint: How many outcomes are there in which 𝑖 players tie for last place? c. Show that the formula of part (b) is equivalent to the following: 𝑁 𝑛

𝑛  𝑁 𝑖 𝑖

d. Use the recursion to find 𝑁(3) and 𝑁(4).

17. Present a combinatorial explanation of why 18. Argue that

𝑛 𝑟

𝑛 𝑟,  𝑛 𝑟

43 of 848

𝑛 𝑛 ,𝑛 , . . .,𝑛

𝑛 1 1, 𝑛 , .   .   . , 𝑛

𝑛

𝑛 𝑛 ,𝑛

1 1, .   .   . , 𝑛

𝑛 1 𝑛 ,𝑛 , . . .,𝑛

⋯

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 𝑛 identical balls be distributed into 𝑟 urns so that the 𝑖th urn contains at least 𝑚 balls, for each 𝑖 𝑛

1, . . . ,𝑟? Assume that

𝑚.

𝑥

𝑛

𝑟 𝑘

* 21. Argue that there are exactly

𝑛 ⋯

𝑥

1 𝑟 𝑘 𝑥 𝑛

solutions of

for which exactly 𝑘 of the 𝑥 are equal to 0. * 22. Consider a function 𝑓 𝑥 , . . . ,𝑥

of 𝑛 variables. How many different

partial derivatives of order 𝑟 does 𝑓 possess? * 23. Determine the nu mber of vectors 𝑥 , . . . ,𝑥

such that each 𝑥 is a

nonnegative integer and 𝑥

𝑘

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?

.

44 of 848

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. 𝐴 and 𝐵 will not serve together? c. 𝐶 and 𝐷 will serve together or not at all? d. 𝐸 must be an officer? e. 𝐹 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 𝑛 𝑛 𝑟 𝑛 𝑟 8. Consider 𝑛-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 𝑖 times, 𝑖

0, . . . ,𝑛?

9. Consider three classes, each consisting of 𝑛 students. From this group of 3 𝑛 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

45 of 848

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? 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 𝑥 , . . . ,𝑥 such that each 𝑥 is a positive integer and 𝑥

where 𝑘

𝑘

𝑛.

15. A total of 𝑛 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 𝑆

1, 2, . . . ,20 contain at least

one of the elements 1, 2, 3, 4, 5? 17. Give an analytic verification of 𝑛 𝑘 𝑘 𝑛 2 2

𝑘

𝑛

𝑘 2

,    1

𝑘

𝑛

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?

46 of 848

20. Verify the identity . . .

, 

𝑛! 𝑥 !𝑥 !⋯𝑥 !

𝑟

a. by a combinatorial argument that first notes that 𝑟 is the number of different 𝑛 letter sequences that can be formed from an alphabet consisting of 𝑟 letters, and then determines how many of these letter sequences have letter 1 a total of 𝑥 times and letter 2 a total of 𝑥 times and ... and letter 𝑟 a total of 𝑥 times; b. by using the multinomial theorem.

21. Simplify 𝑛

𝑛 2

𝑛 3

…

1

𝑛 𝑛

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

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 to discuss the concept of the sample space and the events of an experiment.

47 of 848

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 of the determination of the sex of a newborn child, then 𝑆 𝑔, 𝑏 where the outcome 𝑔 means that the child is a girl and 𝑏 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 𝑆 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: 𝑆 ℎ, ℎ , ℎ, 𝑡 , 𝑡, ℎ , 𝑡, 𝑡 The outcome will be (ℎ, ℎ) if both coins are heads, (ℎ, 𝑡) if the first coin is heads and the second tails, (𝑡, ℎ) if the first is tails and the second heads, and (𝑡, 𝑡) if both coins are tails. 4. If the experiment consists of tossing two dice, then the sample space consists of the 36 points 𝑆 𝑖, 𝑗 :  𝑖, 𝑗 1, 2, 3, 4, 5, 6 where the outcome 𝑖, 𝑗 is said to occur if 𝑖 appears on the leftmost die and 𝑗 on the other die. 5. If the experiment consists of measuring (in hours) the lifetime of a transistor, then the sample space consists of all nonnegative real numbers; that is, 𝑥:  0 𝑥 ∞ 𝑆 Any subset 𝐸 of the sample space is known as an event. In other words, an event is a set consisting of possible outcomes of the experiment. If the outcome of the experiment is contained in 𝐸, then we say that 𝐸 has occurred. Following are some examples of events.

48 of 848

𝑔 , then 𝐸 is the event that the child is a girl.

In the preceding Example 1, if 𝐸 Similarly, if 𝐹

𝑏 , then 𝐹 is the event that the child is a boy.

In Example 2, if 𝐸

all outcomes in 𝑆 starting with a 3

then 𝐸 is the event that horse 3 wins the race. In Example 3, if 𝐸

ℎ, ℎ , ℎ, 𝑡 , then 𝐸 is the event that a head appears on the

first coin. In Example 4, if 𝐸

1, 6 , 2, 5 , 3, 4 , 4, 3 , 5, 2 , 6, 1 , then 𝐸 is the event that

the sum of the dice equals 7. In Example 5, if 𝐸

𝑥:  0

𝑥

5 , then 𝐸 is the event that the transistor does not

last longer than 5 hours. For any two events 𝐸 and 𝐹 of a sample space 𝑆, we define the new event 𝐸 ∪ 𝐹 to consist of all outcomes that are either in 𝐸 or in 𝐹 or in both 𝐸 and 𝐹. That is, the 𝑔 is event 𝐸 ∪ 𝐹 will occur if either E or 𝐹 occurs. For instance, in Example 1, if 𝐸 the event that the child is a girl and 𝐹

𝑏 is the event that the child is a boy, then

𝐸∪𝐹

𝑔, 𝑏

is the whole sample space 𝑆. In Example 3, if 𝐸 first coin lands heads, and 𝐹

𝑡, ℎ , ℎ, ℎ

ℎ, ℎ , ℎ, 𝑡

is the event that the

is the event that the second coin lands

heads, then 𝐸∪𝐹

ℎ, ℎ , ℎ, 𝑡 , 𝑡, ℎ

is the event that at least one of the coins lands heads and thus will occur provided that both coins do not land tails. The event 𝐸 ∪ 𝐹 is called the union of the event 𝐸 and the event 𝐹. Similarly, for any two events 𝐸 and 𝐹, we may also define the new event EF, called the intersection of 𝐸 and 𝐹, to consist of all outcomes that are both in 𝐸 and in 𝐹. That is, the event EF (sometimes written 𝐸 ∩ 𝐹) will occur only if both 𝐸 and 𝐹 occur. For instance, in Example 3, if 𝐸 occurs and 𝐹

ℎ, ℎ , ℎ, 𝑡 , 𝑡, ℎ

ℎ, 𝑡 , 𝑡, ℎ , 𝑡, 𝑡

is the event that at least 1 head

is the event that at least 1 tail occurs, then 𝐸𝐹

ℎ, 𝑡 , 𝑡, ℎ

49 of 848

is the event that exactly 1 head and 1 tail occur. In Example 4, if 1, 6 , 2, 5 , 3, 4 , 4, 3 , 5, 2 , 6, 1

𝐸 and 𝐹

1, 5 , 2, 4 , 3, 3 , 4, 2 , 5, 1

is the event that the sum of the dice is 7 is the event that the sum is 6, then the

event EF does not contain any outcomes and hence could not occur. To give such an event a name, we shall refer to it as the null event and denote it by Ø. (That is, Ø refers to the event consisting of no outcomes.) If 𝐸𝐹 Ø, then 𝐸 and 𝐹 are said to be mutually exclusive. We define unions and intersections of more than two events in a similar manner. If 𝐸 , 𝐸 , ... are events, then the union of these events, denoted by

∪

𝐸 , is defined

to be that event that consists of all outcomes that are in 𝐸 for at least one value of 𝑛

1, 2, .... Similarly, the intersection of the events 𝐸 , denoted by

∩

𝐸 , is

defined to be the event consisting of those outcomes that are in all of the events 𝐸 , 𝑛 1, 2, ... . Finally, for any event 𝐸, we define the new event 𝐸 , referred to as the complement of 𝐸, to consist of all outcomes in the sample space 𝑆 that are not in 𝐸. That is, 𝐸 will occur if and only if 𝐸 does not occur. In Example 4, if event 𝐸

1, 6 , 2, 5 , 3, 4 , 4, 3 , 5, 2 , 6, 1 , then 𝐸 will occur when the sum of the

dice does not equal 7. Note that because the experiment must result in some outcome, it follows that 𝑆

Ø.