EECS 70 Discrete Mathematics and Probability TheorySpring 2014 Anant Sahai Note 11CountingAs we saw in our discussion for uniform discrete probability, being able to count the number of elements ofa set is critical to being able to do probability calculations. You might think that counting is something thatyou learned how to do before you even started to go to school as a kid, and in a sense, you’re right. However,we need ways to count sets fast in a way that reveals how the size changes as we vary certain parameters.In this section we introduce simple techniques that will allow us to count the total number of outcomes fora variety of probabilistic experiments (including coin flips).We start by considering a simple scenario. We pick k elements out of an n element set S = {1, 2, ·· · , n}one at a time. We wish to count the number of different ways to do this, taking into account the order inwhich the elements are picked. For example, when k = 2, picking 1 and then 2 is considered a differentoutcome from picking 2 followed by 1. Another way to ask the question is this: we wish to form an orderedsequence of k distinct elements, where each element is picked from the set S. How many different suchordered sequences are there?If we were dealing cards, the set would be S = {1, ··· , 52}, where each number represents a card in a deckof 52 cards. Picking an element of S in this case refers to dealing one card. Note that once a card is dealt,it is no longer in the deck and so it cannot be dealt again. So the hand of k cards that are dealt consists of kdistinct elements from the set S.For the first card, it is easy to see that we have 52 distinct choices. But now the available choices for thesecond card depend upon what card we picked first. The crucial observation is that regardless of which cardwe picked first, there are exactly 51 choices for the second card. So the total number of ways of choosingthe first two cards is 52 × 51. Reasoning in the same way, there are exactly 50 choices for the third card, nomatter what our choices for the first two cards. It follows that there are exactly 52 × 51 × 50 sequences ofthree cards. In general, the number of sequences of k cards is 52 · 51 · ··(52 − (k − 1)).This is an example of the first rule of counting:First Rule of Counting: If an object can be made by a succession of k choices, where there are n1waysof making the first choice, and for every way of making the first choice there are n2ways of making thesecond choice, and for every way of making the first and second choice there are n3ways of making thethird choice, and so on up to the nk-th choice, then the total number of distinct objects that can be made inthis way is the product n1· n2· n3··· nk.Here is another way of picturing the first rule of counting. Consider the following tree:EECS 70, Spring 2014, Note 11 1It has branching factor n1at the root, n2at every node at the second level,..., nkat every node at the k-thlevel. Each node at level k + 1 (a leaf node) represents one possible way of making the object by making asuccession of k choices. So the number of distinct objects that can be made is equal to the number of leavesin the tree. Moreover, the number of leaves in the tree is the product n1·n2·n3··· nk. For example, if n1= 2,n2= 2, and n3= 3, then there are 12 leaves (i.e., outcomes).Counting SetsConsider a slightly different question. We would like to pick k distinct elements of S = {1, 2, ·· · , n} (i.e.without repetition), but we do not care about the order in which we picked the k elements. For example,picking elements 1, . . . , k is considered the same outcome as picking elements 2, . . . , k and picking 1 as thelast (kthelement). Now how many ways are there to choose these elements?When dealing a hand of cards, say a poker hand, it is often more natural to count the number of distincthands (i.e., the set of 5 cards dealt in the hand), rather than the order in which they were dealt. As we’veseen in the section above, if we are considering order, there are 52 · 51 · 50 · 49 · 48 =52!47!outcomes. But howmany distinct hands of 5 cards are there? Here is another way of asking the question: each such 5 card handis just a subset of S of cardinality 5. So we are asking how many 5 element subsets of S are there?Here is a clever trick for counting the number of distinct subsets of S with exactly 5 elements. Create a bincorresponding to each such 5 element subset. Now take all the sequences of 5 cards and distribute them intothese bins in the natural way. Each sequence gets placed in the bin corresponding to the set of 5 elementsin the sequence. Thus if the sequence is (2, 1, 3, 5, 4), then it is placed in the bin labeled {1, 2, 3, 4, 5}. Howmany sequences are placed in each bin? The answer is exactly 5!, since there are exactly 5! different waysto order 5 cards.Recall that our goal was to compute the number of 5 element subsets, which now corresponds to the numberof bins. We know that there are52!47!5 card sequences, and there are 5! sequences placed in each bin. Thetotal number of bins is therefore52!47!5!.This quantityn!(n−k)!k !is used so often that there is special notation for it:nk, pronounced n choose k. Thisis the number of ways of picking k distinct elements from S, where the order of placement does not matter.Equivalently, it’s the number of ways of choosing k objects out of a total of n objects, where the order of thechoices does not matter.The trick we used above is actually our second rule of counting:Second Rule of Counting: Assume an object is made by a succession of choices, and the order in which thechoices is made does not matter. Let A be the set of ordered objects and let B be the set of unordered objects.If there exists a k to 1 function f from A to B, we can count the number of ordered objects (pretending thatthe order matters) and divide by k (the number of ordered objects per unordered objects) to obtain |B|, thenumber of unordered objects.EECS 70, Spring 2014, Note 11 2Note that we are assuming the number of ordered objects is the same for every unordered object; the rulecannot be applied otherwise. Here is another way of picturing the second rule of counting:The function f simply places the ordered outcomes into bins corresponding to the unordered outcomes. Inour poker hand example, f will map 5! elements in the domain of the function (the set of ordered 5 cardoutcomes) to one element in the range (the set of
View Full Document
Unlocking...