Elem Discrete Math II
Elem Discrete Math II MATH 232
Popular in Course
Popular in Mathematics (M)
This 7 page Class Notes was uploaded by Henderson Lind II on Tuesday September 8, 2015. The Class Notes belongs to MATH 232 at University of Oregon taught by Frank Anderson in Fall. Since its upload, it has received 9 views. For similar materials see /class/187179/math-232-university-of-oregon in Mathematics (M) at University of Oregon.
Reviews for Elem Discrete Math II
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 09/08/15
Lecture 3 Some Probability Recall that a die die is the singular of dice is cube with dots on each of its six faces with from 1 to 6 dots on each face Check Figure 1 on page 192 if you are unsure of what a die is Suppose that we toss such a die over and over many times recording how many dots show after each toss So we ll wind up with a scrambled list of the numbers 1 2 3 4 5 6 What do we expect to nd with this list If our list includes the results of many tosses say 1000 then we probably would expect to see that each of the six numbers shows up essentially the same number of times as any other number Of course this requires that our die be a fair one that is one that is not loaded to favor one or two faces Assuming that our expectation is met then we d likely say something like The probability of any one number showing is 16 Here we want to try to make this notion of probability more precise in some particularly simple settings You will undertake a more extensive study of probability next term when you get into Chapter 9 The typical setup that we shall deal with is one where we perform some experiment such as tossing a die and recording or noting the outcome The totality of outcomes is called the sample space and is usually denoted by the capital Greek letter 9 In this introduction we will assume that the sample space 9 is nite Then each subset E of Q is called an event For example suppose our experiment is tossing a single die Then our sample space is Q 1 2 34 5 6 Of the 26 events the subsets of Q a couple of them is the simple event E the outcome is a 4 4 and the event E w E Q l w is even 2 4 6 Given such an experiment and sample space 9 we would like to have some way of measuring the likelihood that for some event E an experiment will have an outcome in E Probability is a technique to provide such a measure So a probability function P for such an experiment is a function that assigns to each event E a real number PE on the interval 01 In particular we require that PE 0 iff the event E is impossible and we require that PE 1 iff the event is certain For example if for some outcome a probability function P assigns PE 12 then this is stating that the probability for that particular probability function an experiment will have an outcome an that falls in E is probably 12 More later So exactly what does determine what functions are probability functions The requirements are simple Let Q be a nite set the sample space Then a function P de ned on the power set 730 to the real interval 01 is a probability function on 9 if it satis es the two axioms P1 PQ 1 P2 If E and F are disjoint events then PE U F PE Before we see some more speci c examples of sample spaces and probability functions let s list four key properties of probability functions that we will use extensively First though if Q is a sample space and E is an event in this space then the complement E0 of E is the set E0 Q E so E and E0 are disjoint and Q E U E We are now going to restate the Theorem given on page 191 of the text but we will omit the proof However we expect you to expend a little effort to follow and understand its proof 7 it is not only fun in its own right but it illustrates some very important properties of sets and probability functions Theorem 31 Let P be a probability function on a nite sample space 9 Then a 130 0 b PEc17 PE for every event E in Q C PE U F PE PF 7 PE O F for every pair of events E and F d For every pairwise disjoint set of events E1 E2 En PE1 U E2 U U E PE1 PE2 PEn Here is one of the great advantages of having only a nite sample space 9 For then each single outcome to E Q is an event and each event E Q Q is the disjoint union of its elements Hence by d of the Theorem the probability of an event E is simply the sum of the probability of its elements For in nite sample spaces the Theorem is still correct and all events will be the disjoint unions of their elements but for such sample spaces those unions are not likely to be nite In fact they can be quite ugly so that in these cases we need a more delicate notion of probability Example 31 Suppose that our experimen 7 is to choose two cards without repetition from a standard 52 card bridge deck Assuming that our deck is fair with no marked or otherwise funny cards then we usually choose the probability function that says that the probability of drawing any two cards is the same as drawing any other two in which case we say that any two pairs are equally likely Now the total number of possible pairs of two cards is simply the number of two card sets in the deck namely the number 52 52 7 1326 lt 2 gt 2l50l Since we assume that drawing any pair is equally likely by Axiom P1 the sum of these 1326 equal probabilities must be 1 That is if too is the pair consisting of say the ace of hearts and the ace of spades then by the equally likely assumption 2 Pw 1326Pw0 1 UJEQ So for any pair to of cards we have P 7 P 7 71 w 7 we 7 1326 Therefore in this setting we know the probability of drawing any one pair and so the task of nding the probability PE of any event boils down to counting the number of elements in E I This important fact deserves a formal statement so here it is Equally Likely Probabilities Let Q be a nite sample space and let P be an equally likely probability function on 9 Then for each event E Q Q Example 32 Let s return to the equally likely setup we had in Example 31 Here the sample space of all possible two card draws has 1326 elements So rst say we nd the probability that if we draw two cards we ll get a pair of aces That is we want PE where E is the event of two aces Well to count E is easy There are 4 aces and we want two of them so there are exactly 4 4 lt2 6 such pairs Thus the probability of drawing two aces is E 7 000452 101 1326 1309 So being so lucky would be very remote Next let s ask for the probability of drawing a pair of clubs This time let F1 be the event consisting of all pairs of clubs We are looking for F1 purl Well the number of clubs is 13 so the number of pairs of clubs the size of F1 is 13 1F1127s lFll 78 PF 7700588 1 1m 1326 so the desired probability is That is assuming a fair deck we would expect to draw a pair of clubs about 6 of the time Next let s ask for drawing two cards of the same suit Since each suit contains exactly 13 cards the number of pairs of any one suit is the same as the number of pairs of clubs that is 78 If we let F1 F2 F3 F4 be the four events of two clubs diamonds hearts and spades then these four events are pairwise disjoint and each has the same probability PF1 00588 Now we are looking for the probability of the disjoint union F of these four events and by part d of the Theorem we have U F2 U F3 U F4 4PF1 4 x 00588 0235 In other words you d expect to draw two cards of the same suit about 23 of the time Finally let s turn that around and nd the probability that if we draw two cards we get cards of different suits Of course now that s pretty easy Our event this time is simply the set F0 So by part b of the Theorem we have PF0 17 PF17 0235 0765 Thus we d expect to draw two cards of different suits slightly more than 75 of the time I Achtung Next we d particularly like to call your attention to Example 5 of Section 52 on pages 1923 Here the event is to roll a pair of dice in the example one black and one red If the goal is to record the value of the red and the value of black die on each roll as an ordered pair then the appropriate sample space has the 36 elements listed in display a at the top of page 193 But often if not usually the focus is on the sum of the two dice Since the possible sums are the numbers 234 1112 these 11 numbers make an appropriate sample space But here is the rub If we work with the 36 element sample space of display a then the probability of any one of these 36 outcomes equals that of any other that is this probability is equally likely On the other hand however if is our interest is in the sums then using the 11 element sample space makes sense But here the events are not equally likely The probability of rolling a 2 is just 0028 while the probability of rolling a 7 is 0167 In either case we still have that the probability of any event is the sum of the probabilities of its individual outcomes but the probabilities of these outcomes need not be equal for different outcomes This is no big deal use whatever sample space is most appropriate But please be warned that by changing sample spaces you may very well loose or gain equal likelihood Let s nish by checking out some more challenges that you should see if you can answer Again if necessary we can discuss them in class Example 33 Suppose that we roll a single fair die over and over Then the probability of rolling any value is 16 Say for instance we toss the die ve times Then an appropriate sample space would be the set S D5 of all 5 sequences d1 d2d3d4 15 with each d in the set D 1 2 3 4 5 6 of outcomes for a single toss Then the sample space satis es 5 7776 Okay let s see what we can do with this a What s the probability of rolling a 1 on the rst two tosses Hint This corresponds to the event E 1 m E D So 64 and PE b What is the probability of rolling a 1 on the second toss but not on the rst Hint Here the event would be F d11 E S 2 g 11 g 6 and 9lt E D The answer is that 5 PF 536 g 6 Why c What is the probability of rolling the rst 1 on the second toss and the rst 2 on the fourth toss d What is the probability of rolling at least one 1 in the 5 tosses I Remark Those of you who know a little probability will wonder why we attacked the last problem the way we did Recognizing that rolling a die and then rolling it again are two indepen dent experiments render the questions of this last Example quite easy Unfortunately this course is organized so that this one little excursion into the subject here in Section 52 is not really a course in probability so much as an important example of the value of knowing how to count things If you d like to explore this further check out Section 91 of the text Lecture 2 Counting Subsets Let S be a set with lSl n Last time we learned how to count k permutations in S that is ordered subsets of k elements of S But how about counting the number of k element unordered subsets That task will be the focus of this Lecture We begin though with a familiar but related question How many subsets does S have That is what is the number l73Sl of elements in the power set 73S of the n element set S As you saw see page 142 of the text If lSln then 73Sl2 Let lSl n and let 1 g r g n Then the number of k element subsets of the n set S is denoted by the binomial coef cient 71 k The reason for the name will be clear a bit later But for now let s see how to evaluate it and put it to use So let T Q S be a k element subset of S Then there are Pk k kl permutations of T But each of the Pn k permutations of S is rst the choice of some k element set T of S followed by a permutation of T So by the product Rule the number of k permutations of S must satisfy nl nik 7 Pnk ltZgtPkk and Pnk so solving Example 21 Recall rst that 0 1 So if S is an n set then the number of empty subsets and of course we know that this one subset is just 0 And the number of n sets of S is and of course that one n element subset of S is just S itself Also since the power set 73S is the disjoint union of the k element subsets of S for k O 1 2 n we have the interesting formula ms 2 k2 Finally the above formula for fails whenever k lt 0 or k gt n but in those cases 0 whenever k lt 0 or k gt n Example 22 Suppose a group G consists of 24 students 15 juniors and 9 seniors We want to form an executive committee consisting of 7 of these students The number of different ways to create that committee is just the number of 7 element subsets of the 24 element set G that is 24 24 lt7 7 W 7346104 Wow On the other hand if the by laws require that this committee must have 4 juniors and 3 seniors then by the Product Rule the number of possible committees is 15 9 lt4 lt3 1365 x 84 114 660 Example 23 Before worrying about this example you should master Example 10 of Section 51 on page 187 of the text This is one of the premier illustrations of this general counting procedure Okay With that behind us let s play a slightly different game Suppose now we select 4 cards at random from a standard 52 card bridge deck We ask rst how many different hands are possible Since here order is not an issue the solution is easy namely lt52 52 7 52515049 7 270725 4 4814 4321 7 Here are a couple of more speci c questions a How many of these 270 thousand some hands consist of 3 cards of one suit and 1 of another One natural way to attack this problem is rst to specify the suits so say we start by asking for 3 clubs and 1 diamond Well there are 13 clubs of which we need 3 and 13 diamonds of which we need 1 So the number of such club diamond hands is 13 13 169 3 lt 1 And of coursethe same number applies to any pair of suits But there are 4 suits so there are 4 ways to choose the dominant suit and then 3 ways to choose the lesser suit Then by the Product Rule there are 4 3 12 ways to choose the two suits one dominant Finally by the Union Rule the total number of such 4 card hands is 4 3 13 13 lt1gtlt1gtlt3gtlt1gti2028 b How many of all of these 4 card hands consist of two pair Again suppose we begin with a speci c case say a pair of 8 s and a pair of 9 s The deck holds exactly 4 cards of each denomination and we want 2 of each So there are exactly 3 lt3 pairs of pairs involving just 8 s and 9 s Finally there are 13 different denominations hence 123 ways to choose two denominations so by the Union Rule the number of such 4 card handsis 13 4 4 lt2gtlt2gtlt2gt 78x6x62808 Here are a couple of examples that we will not solve now Instead we urge you to View these as challenges and take them on If nesessary7 we can discuss them in class Example 34 How many different 8 letter words are there that use exactly 5 as and 3 b s Hint You could think of how many ways you could distribute these letters in a row of 8 blanks Example 35 Draw 35 cards from a standard 52 card deck a In how many way can you wind up with no aces b In how many way can you wind up with exactly 2 aces c In how many way can you wind up with at least one ace Example 36 This time craw the cards in order 7 a rst7 second7 third7 etc a How many ways can you hit an ace on the rst draw On the second but not the rst b In how many ways will you get no aces or kings on the ve draws How many with at least one ace or king
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'