Combinatorics - Harvard University

1 Chapter 1. Combinatorics Copyright 2009 by David Morin, (Version 4, August 30, 2009). This file contains the first three chapters (plus some appendices) of a potential book on Probability and Statistics. It does not assume knowledge of calculus. The first three chapters are titled Com- binatorics, Probability, and Distributions. And Appendix B gives a nice little introduction to the natural logarithm, e. Future chapters on statistics will be added in the summer of 2010. Combinatorics is the study of how to count things. By things we mean the various combinations, permutations, subgroups, etc., that can be formed from a given set of objects or events. For example, how many different committees of three people can be chosen from five people? How many different full-house hands are there in poker? How many different outcomes are possible if you flip a coin four times?

2 Knowing how to count such things is critical for an understanding of probability, because when calculating the probability of a given event, we invariably need to count the number of ways that this event can happen. The outline of this chapter is as follows. In Section we introduce the concept of factorials, which will be ubiquitous in our study of probability. In Section we learn how to count the number of possible permutations (that is, the number of possible orderings). of a set of objects. In Section we learn how to count the number of possible subgroups that can be formed from a set of objects. We consider both the case where the order of the objects matters, and the case where it doesn't matter. For example, the poker question posed above is one where the order of the objects (the cards) doesn't matter. In Section we learn how to count the number of possible outcomes of a repeated experiment, where each repetition has an identical set of possible results.

3 Examples include rolling dice or flipping coins. Finally, in Section we look at the coin-flipping example in more detail, and we see how it relates to a set of numbers called the binomial coefficients. Having learned how to count all these things, we'll then see in Chapter 2 how the results can be used to calculate probabilities. It turns out that it's generally a trivial step to obtain a probability once you've counted the relevant things, so the bulk of the work we'll need to do will be in the present chapter. Factorials Before getting into the discussion of actual Combinatorics , we'll first need to look at a certain quantity that comes up again and again. This quantity is called the factorial. We'll see throughout this chapter that when dealing with a situation that involves an integer N , we often need to consider the product of the first N integers.

4 This product is called N. 1. 2 CHAPTER 1. Combinatorics . factorial, and it is denoted by the shorthand notation, N! .1 For the first few integers, we have: 1! = 1. 2! = 1 2=2. 3! = 1 2 3=6. 4! = 1 2 3 4 = 24. 5! = 1 2 3 4 5 = 120. 6! = 1 2 3 4 5 6 = 720 ( ). As N increases, N ! gets very big very fast. For example, 10! = 3, 628, 800, and 20! . 1018 . In Chapter 3 we'll make good use of an approximate formula for N !, called Stirling's formula. This formula will make it clear what we mean by the statement, N ! gets very big very fast.. We should add that 0! is defined to be 1. Of course, 0! doesn't make much sense, because when we talk about the product of the first N integers, it is understood that we start with 1. Since 0 is below this starting point, it is unclear what 0! actually means. However, there's no need to think too hard about trying to make sense out of it, because as we'll see below, if we simply define 0!

5 To be 1, then a number of formulas turn out to be very nice. Having defined N !, we can now start counting things. There are two main things we'll need to know how to count, and the results for both of these involve N !. These two things are (1) the permutations (the orderings) of N objects , and (2) the number of ways of choosing subgroups from N objects, for example, the number of different committees of three people that can be chosen from five people. Let's look at each of these in turn. Permutations A permutation of a set of objects is a way of ordering them. For example, if we have three people, Alice, Bob, and Carol, then one permutation of them is Alice, Bob, Carol. Another permutation is Carol, Alice, Bob. And another is Bob, Alice, Carol. The goal of this section is to learn how to count the number of possible permutations.

6 We'll do this by starting off with the very simple case where we have just one object. Then we'll consider two objects, then three, and so on, until we see a pattern. As we'll find throughout this book, this is invariably a good strategy when trying to figure something out: Start with small numbers, and then gradually increase until you see a pattern. One object If we have only one object, then there is clearly only one way to order it. There is no ordering to be done. A list of one object simply consists of that one object, and that's that. If we use the notation where PN stands for the number of permutations of N objects, then we have P1 = 1. Two objects With two objects, things aren't completely trivial like they were in the one-object case, but they're still very simple. If we label our two objects as 1 and 2, then we can order them in two ways: 1 I'm not sure why someone long ago picked the exclamation point for this notation.

7 But just remember that it has nothing to do with the more common grammatical use of the exclamation point for emphasis. So try not to get too excited when you see N! ! PERMUTATIONS 3. 12 or 21. So we have P2 = 2. At this point, you might be thinking that this result, along with the previous P1 = 1 result, implies that PN = N for any number N . This would imply that there should be three different ways to order three objects. Well, not so fast.. Three objects Things get more interesting with three objects. If we call them 1, 2, and 3, then we can list out the possible orderings. (If you haven't already looked at the table below, you should cover it up with your hand and try to list out all the permutations yourself. We'll even add on this extra sentence here to make this parenthetical remark a little longer, so that you don't have any excuse for saying that you already looked at it!)

8 The permutations are: 123 213 312. 132 231 321. Table So we have P3 = 6. Note that we've grouped these six permutations into three subgroups (the three columns), according to which number comes first. It isn't necessary to group them this way, but we'll see below that this method of organization has definite advantages. It will simplify how we think about the case where the number of objects is a general number N. Remark: There's no need to use the numbers 1,2,3 to represent the three objects. You can use whatever symbols you want. For example, the letters A,B,C work fine, as do the letters H,Q,Z. You can even use symbols like , , . Or you can mix things up with ,W,7 if you want to be unconventional. The point is that the numbers/letters/symbols/whatever simply stand for three different things, and they need not have any meaningful properties except for their different appearances when you write them down on the paper.

9 However, there is certainly something simple about the numbers 1,2,3,.., or the letters A,B,C,.., so we'll generally work with these. In any event, it's invariably a good idea to be as economical as possible and not write down the full names, such as Alice, Bob, and Carol. Of course, with these three particular names, there's some logic in going with A,B,C.. Four objects The pattern so far is P1 = 1, P2 = 2, and P3 = 6. Although you might be able to guess the general rule from these three results, it will be easier to see the pattern if we look at the next case with four objects. Taking a cue from the above list of six permutations of three objects, let's organize the permutations of four object according to which number starts the list. (Again, you should cover up the following table with your hand and try to list out all the permutations yourself.)

10 We end up with: 1234 2134 3124 4123. 1243 2143 3142 4132. 1324 2314 3214 4213. 1342 2341 3241 4231. 1423 2413 3412 4312. 1432 2431 3421 4321. Table 4 CHAPTER 1. Combinatorics . If we look at the last column, where all the permutations start with 4, we see that if we strip off the 4, we're simply left with the six permutations of the three numbers 1,2,3. that we listed above. A similar thing happens with the column of permutations that start with 3. If we strip off the 3, we're left with the six permutations of the numbers 1,2,4. Likewise for the columns of permutations that start with 2 or 1. The 24 permutations listed above can therefore be thought of as four groups (the four columns), each consisting of six permutations. Five objects For five objects, you probably don't want to write down all the permutations, because it turns out that there are 120 of them.