Supplemental Notes: Counting and ProbabilityEconomics 310 Fall 2011Counting and ProbabilityEarly problems in the history of probability often involved games of chance where theprobabilities for basic outcomes were clear but the probabilities of interesting events weredifficult to calculate because of the large numb er of basic outcomes for events of interest.A number of these problems can be formulated as problems of drawing k objects with andwithout replacement out of a set of n while being or not being concerned with the ordering.Solving them requires counting the ways in which you can do this. As an example weconsider the case where we have n = 4 objects, labeled A, B, C, and D, and wish to drawk = 2. Recall that n! = n × (n − 1) × (n − 2) × · · · × 1 is called n factorial.Result 1 (ordered, with replacement) The total number of ways k objects can be drawn outof a set of n with replacement is nk.For the first draw there are n choices, for the second one there are again n choices and so on.In the example, the set of outcomes is {AA, AB, AC, AD, BA, BB, BC, BD, CA, CB, CC,CD, DA, DB, DC, DD}, with sixteen elements.Result 2 (ordered, without replacement) The total number of ways k objects can be drawnout of a set of n without replacement is n×(n − 1) ×(n− 2) × . . . × (n−k + 1) = n!/(n −k)!.For the first draw there are n choices, for the s ec ond one there are n−1 choices and so on. Inthe example the set of outcomes is {AB, AC, AD, BA, BC, BD, CA, CB, CD, DA, DB, DC},with twelve elements.Result 3 (unordered, without replacement) The total number of ways k objects can bedrawn out of a set of n without replacement is n!/(k !(n − k)!).The total number of ways k objects can be drawn out of a set of n in order withoutreplacement is n!/(n − k)! by Result 2. If we do not care about the ordering, we have totake account of the number of different ways we can order k objects. This is k!, by Result2 again, so we have to divide this into the n!/(n − k)! to ge t nk!≡n!k!(n − k)!.The left hand side notation is read as “n choose k.” In our example, the set of outcomes is{AB, AC, AD, BC, BD, CD}, with six elements.Example 1: How many bridge hands of 13 cards can be formed from a 52-card deck? Sincethe order does not matter, Result 3 is relevant. The number is 5213!=52!13!(52 − 13)!= 635, 013, 559, 600.1Result 4 (unordered, with replacement) The total number of ways k objects can be drawnout of a set of n with replacement is (n + k − 1)!/(k!(n − 1)!).This one is me ss ier than the others. Reformulate the problem as follows: put k objects inn bins, allowing for more than one object per bin. We can describ e the result by the knumbers or by a sequence of n − 1 zeros and k ones, where a zero indicates that we havefinished with one of the n bins, and one indicates one of the objects in that particular bin.For example, with n = 3 bins and k = 2 objects we could have the following outcome: (2,3)which would be coded as 0101: 0 (because the first bin is em pty), 1 (because there is anobject in the second bin), 0 (bec ause there is no additional object in the second bin), 1because there is an object in the third bin. We do not record the last 0 because it wouldalways end in a zero. In the same example (2,2) would be coded as 0110: 0 because thefirst bin is empty, 1 because there is an object in the second bin, 1 because there is a secondobject in this bin, 0 because there is no additional object in this bin.Now the problem is one of choosing a set of k ones out of a set of n + k − 1 which can bedone in (n + k − 1)!/(k!(n − 1)!) different ways.In the example the set is {AA, AB, AC, AD, BB, BC, BD, CC, CD, DD}, with ten ele-ments.Example 2: Isaac Newton and Samuel Pepys debated the following question: is the prob-ability of tossing at least one six in six tosses with a fair die smaller than, equal to, or largerthan the probability of tossing at least two sixes in twelve tosses?Consider the probability of the first event. There are 66different outcom es for the six tosses.Each has probability 1/66. The question is how many of the 66outcomes are favorable, thatis, how many have at least one six. It is easier to answer the opposite: how many outcomeshave no six at all. There are five possibilities for each toss in that case, so 56have no six.Hence the probability of at least one six isP r(at least one six) = 1 − P r(no six) = 1 − 56/66≈ 0.665.Consider the probability of the second event. There are 612different outcomes, again eachwith the same probability 1/612. How many have at least two sixes is 612minus the numberthat have at most one six. At most one six is either no six or exactly one six. The numberof outcomes with no six is 512. The event of exactly one six can be partitioned into twelveevents depending on the location of the six. The number of outcomes with a six in the firsttoss is 511. Hence the number of outcomes with a single six is 12 · 511. Hence the probabilityof at least two sixes isP r(at least two sixes) = 1 − P r(no six) − P r(one six)= 1 − 512/612− 12 · 511/612≈ 0.619.Hence, at least two sixes in twelve tosses is les s likely than at least one six in six tosses.Example 3: Suppose there are 25 people with dogs at a park, and suppose they all chooserandomly from a set of n breeds of dogs. How large should n be to ensure the chances of2everybody having a different breed of dog is at least 0.5? (As n increases this probabilityclearly goes up.)The number of ways 25 people can choose from n types of dogs is n25. All these outcomesare equally likely, with probability 1/n25. The number of ways they can pick with a differentdog breed for everybody is n!/(n − 25)!. Now we want to know n such thatn!/(n − 25)!n25≥ 0.5, and(n − 1)!/(n − 1 − 25)!(n − 1)25< 0.5.At n = 442:n!/(n − 25)!n25= 0.5008,and(n − 1)!/(n − 1 − 25)!(n − 1)25= 0.49996.Hence n = 442 is the