CS/Math 240: Introduction to Discrete Mathematics 5/3/2011Lecture 26 : Permutations and CombinationsInstructor: Dieter van Melkebeek Scribe: Dalibor Zelen´yDRAFTLast time we started talking about counting. The general setting is that we are given a descrip-tion of a finite set, and our goal is to find the set’s cardinality. This has applications for examplein program analysis and discrete probability theory.We saw some basic counting strategies, namely the bijection rule, the union rule, and theproduct rule. We also saw extensions of the bijection rule and the product rule. Today we describea general kind of a problem that captures all the counting problems we discussed last time, andgive an example where we count the number of ways to get various hands in poker. After that,we discuss the binomial theorem which is an important ingredient in many counting proofs. Atthe end of lecture, we discuss a generalization of the sum rule from last time and use the binomialtheorem to prove its correctness.26.1 Permutations and CombinationsWe can characterize the counting problems we discussed last time in the context of the followingproblem. We have a bowl with n distinct balls, and we draw a ball from the bowl k times. We wantto count the number of ways we can draw the balls, subject to the following kinds of restrictions.1. Replacement: In some variations, we can draw the same ball twice, which we think of asputting the ball back in the bowl after we draw it, i.e., replacing it. In other variations, theball is discarded after it is drawn.2. Ordering: In some settings, the order in which we pick the balls matters, whereas in othersettings it does not matter.We summarize the number of ways to draw the balls in each of the four variations of the problemin Table 26.1.With replacement?Ordering matters?Yes NoYes nkn!(n − k)!Non + k − 1k − 1nkTable 26.1: Number of ways to pick one of n balls k times with different kinds of rules.First consider the situation when the order in which we draw the balls matters, and when wereplace a ball after it is drawn. This way, there are n balls in the bowl for each draw, so there aren options for each draw. It follows that there are a total of nkways to draw the balls. You canshow this more rigorously by combining the bijection rule with the product rule if you wish.1Lecture 26: Permutations and Combinations 26.1. Permutations and CombinationsNow consider the situation when order matters but when we do not replace a ball that wasdrawn. In that case, there are n balls to choose from in the first draw, n − 1 balls to choose from inthe second draw, and in general there are n−i options after i draws. Thus, the total number of waysto draw k balls in this case is n· (n−1) · · · (n −k +1). We can multiply this by 1 =(n−k)(n−k−1)···2·1(n−k)(n−k−1)···2·1to get an expression in terms of factorials:n · (n − 1) · · · (n − k + 1) = n · (n − 1) · · · (n − k + 1) ·(n − k)(n − k − 1) · · · 2 · 1(n − k)(n − k − 1) · · · 2 · 1=n!(n − k)!.If we do not replace the balls and disregard the ordering, we are picking a k-element subset ofthe set of n balls, and we saw last time that the number of ways to do this isnk. Another way tothink about it is that there is a (k!)-to-1 relationship b etween the number of ways to pick k ballsin the setting when order matters (all k! ways of picking k balls when order matters correspondto the same subset consisting of k balls), and our generalized bijection rule tells us that, in thatcase, the number of ways to pick k balls when order doesn’t matter is (n!/(n − k)!)/k!, and this isexactly whatnkis.Here we also remark that there are many names for the quantitynk. Some of the names arecombination, binomial, or binomial coefficient.Finally, consider the situation when we replace the balls after being drawn, and when orderingdoes not matter. This i s exactly the situation we were facing in our first example in Lecture 25.There, we had to pick 12 bagels out of 5 kinds (so n = 5 and k = 12). Replacing each bagel afterit is drawn means that we can pick multiple bagels of the same kind.Recall that we found a bijection between the ways to pick the bagels and the set of sequencesof binary strings of length 16 with exactly 4 ones in them. The number of ze ros between each pairof ones (or between an end of a string and the 1 nearest to that end) indicated how many bagelsof some kind we picked. This idea generalizes. There is a bijection between the number of ways topick k balls out of n with replacement and without caring about the order in which the balls arepicked, and the number of binary strings of length n + k − 1 with exactly n − 1 ones. The numberof such strings is the same as the number of (n − 1)-element subsets of a domain of size n + k − 1,i.e.,n+k−1n−1by the bijection rule.26.1.1 Example: Counting Poker HandsLet’s get some more practice with our counting rules. Consider a deck of cards that’s used forplaying poker. The cards have 4 different suits: spades, clubs, hearts, and diamonds. For each suit,there are 13 cards, one for each of the values 2 through 10, jack (J), queen (Q), king (K), and ace(A). This means that there are a total of 4 · 13 = 52 cards.A poker hand consists of 5 of those 52 cards. Since there is only one card for each suit-valuepair, the dealer gives a player those 5 cards by drawing from the deck without replacement. Theorder in which the cards are drawn does not matter, so there are525= 2598960 different possiblehands.Example 26.1: A four-of-a-kind is a hand with four cards with the same value, one for each suit,and an additional card.There are 13 ways to pick which value will be present in all suits. Since order doesn’t matter,this fully determines four of the five cards in the hand. We can pick the last card any way we want.Bu the generalized product rule, there are now 12 choices for the value and 4 values for the suit.Thus, the total number of four-of-a-kind hands is 13 · 12 · 4 = 624. ⊠2Lecture 26: Permutations and Combinations 26.1. Permutations and CombinationsWe are not going to discuss discr ete probability in this course, but let’s at least mention itnow. The discrete probability of an event with a certain property happening is the number ofevents that have the property divided by the total number of possible events. There are 624events (hands) of the type