MATHEMATICS 102, FALL 2002METHODS OF DISCRETE MATHEMATICSNotes on Probability to accompany Apostol, Vol. 2, Chapter 131 Combinatorial analysisThe Cartesian product A × B of sets A and B is the set of ordered pairs a, bwhere a ∈ A, b ∈ B. If A has naelements and B has nbelements, A × B hasnanbelements.Example: a die roll (1 ...6) followed by a coin toss(H or T): there are 6 × 2elements: 1H, 2H,...6H, 1T,...6T.• Principle 1: Multiply for sequential counting. If we are forming a setof n-tuples where there are k1choices for the first element x1, k2for x2,and so on, the number of n-tuples x1x2...xnin the set is k1k2...kn• Principle 2: Divide to correct systematic overcounting. If M differentn-tuples all correspond to the same element in our sample space, countthe n-tuples and then divide by the number of times M that each wasovercounted.• Principle 3: Divide and Conquer. To count the number of elements in aunion of disjoint subsets, count each subset and sum the results.• Principle 4: Subtract off special cases. To count the number of elementsin a difference A−B where B ⊂ A, count each set and take the difference.Classic example of principles 1 and 2: counting the number of k-element sub-sets of an n-element set.First count the k-tuples whose elements are all different:n(n − 1)(n − 2)...(n − k + 1). Then divide by k! to correct for overcounting.2 The carnival game called “Chuck-A-Luck”You pick a number from 1 to 6. Three fair dice are rolled. If any comes upwith your number, you win. What is the probability of winning?Use principle 4, where A is the set S of all possible rolls and B is the setof winning rolls, so P (B) = 1 − P (B0) where B0is the set of losing rolls.The number of losing rolls is 5 x 5 x 5 = 125.The total number of rolls is 6 x 6 x 6 = 216So there are 216-125 = 91 winning rolls, and your chance of winning is 91/216.1Sanity check:• 1 roll with 3 of your number• 15 rolls with 2 of your number (3 places for the other number x 5 choicesfor it)• 75 rolls with 1 of your number (3 places for it, and 5 x 5 pairs of othernumbers for the other two dice)3 × 1 + 15 × 2 + 75 × 1 = 108, which is half of 216.3 Examples from pokerHow many distinct 5-card poker hands can be dealt from a 52-card deck?Answer: Select 5 cards sequentially: the number of ways to do this is 52 ×51 × 50 × 49 × 48But this generates each distinct hand 5! = 120 times.So the number of distinct hands is52!47!5!Some more examples from poker where multiplication leads to the answer:• How many distinct ways are there to get 4 of a kind?13 choices for the rank of the 4, 48 choices for the other card.• A full house (3 of one rank, 2 of another)13 choices for the first rank (with 3 cards), 4 for the suit that is missing.12 choices for the second rank (with 2 cards), 6 for the pair of suits thathave the second rank.• Three of a kind (3 of one rank, the other two do not match)13 choices for the first rank (with 3 cards), 4 for the suit that is missing.48 choices for the fourth card44 choices for the fifth card (because 2 ranks are now excluded)4 Examples from bridge• How many ways are there to select 6 cards from the 13 spades?13!7! 6!• How many distinct hands have 6 spades, 4 hearts, 2 diamonds, 1 club?Apply the same analysis to each suit in turn:13!7! 6!13!9! 4!13!11! 2!13!12! 1!2• How many distinct hands have a 6-4-2-1 distribution?Multiply the preceding number by the numb er of ways to choose the6-card suit, the 4-card suit, etc, which is 24.• How many distinct hands have a 4-4-3-2 distribution?Start with13!9! 4!13!9! 4!13!10! 3!13!11! 2!Now there are 4 ways to select the 2-card suit followed by 3 ways toselect the 3-card suit, so multiply by 12.(Alternative: multiply by 24 as above, but divide by 2 to correct forovercounting)How many distinct hands have a 4-3-3-3 distribution?13!9! 4!13!10! 3!13!10! 3!13!10! 3!Now there are 4 ways to select the 3-card suit, so multiply by 4.(Alternative: multiply by 24 as above, but divide by 6 to correct forovercounting)5 Conditional probabilitySuppose that A and B are events (subsets) of a sample space S. If we know thatevent B has occurred, what is then the probability that A has also occurred?Example: I roll two dice and note that the sum is six. What is the proba-bility that• at least one 2 is showing?Answer: there are 5 pairs in set B: (1,5), (2,4), (3,3), (4,2), and (5,1).Two of them belong to set A so the probability is25• at least one 3 is showing?Answer: there are 5 pairs in set B: (1,5), (2,4), (3,3), (4,2), and (5,1).Only one of them belongs to set A so the probability is155.1 Definition of conditional probabilitySuppose that P (B) > 0Then P (A|B) “the probability of A, given B,” isP (A|B) = P (A ∩ B)/P (B)Many simply problems in conditional probability can be analyzed by ar-ranging the probabilities into a rectangular array where the rows and columnscorrespond to mutually exclusive events and each cell gives the probability forthe intersection of the “row” and “column” events.35.2 Example: the “bearded man” problemAt an airport with severe terrorism problems, security personnel have estab-lished the following:• Of male passengers with explosives in their shoes, 60% have beards.• Of male passengers with no explosives in their shoes, 5% have beards.• 20% of male passengers have explosives in their shoes.What is the probability that a bearded male passenger has explosives inhis shoes?Event A is “explosive shoes” while event A0is “non-explosive shoes”Event B is “bearded” while event B0is “clean-shaven”¿From the given information we can make a tableB B0A .12 .08A0.04 .76Sum .16 84So P (A ∩ B) = .12, P (B) = .16, andP (A|B) = P (A ∩ B)/P (B) = .12/.16 = 3/4.5.3 The math roommate problem(an enhanced version of Apostol, p. 488. Example 2)The Harvard class of 2006 contains 4n members who room randomly togetherin pairs. Precisely 2n of them are taking a math course(only one per student).There are three versions of the problem, each with a different answer.1. In every math course, each student writes the roommate’s name on oneslip of paper.2. In every math course, each student writes his or her name on one slip ofpaper and the roommate’s name on another.3. In all rooms where at least one person is taking a math course the stu-dents write each roommate’s name on a slip of paper.From all these slips of paper, one is drawn.What is the probability that it has the name of a