Combinatorics: Combinations without Replacement
When you think of combinations, the first thing that comes to mind might be a “combination lock”. Unfortunately, that is actually a very bad example of what a combination really is! As we talked about the past few days, in permutations, the order does matter, but in combinations, the order does not matter. As you know though, the order in which you enter numbers in a combination lock makes all the difference, so if we wanted to be more accurate (at least from a mathematician’s perspective), we should rename “combination locks” to be called “permutation locks”!
Let’s reconsider our example from yesterday, where you have a four different marketing campaign strategies that you are considering for an upcoming product launch. In the context of permutations, the order of those decisions matter. But today, let’s assume that you are going to make a big marketing blast and do all of those strategies at the same time. Then how many different outcomes are there? Simple, one – you do everything at the same time!
Now let’s assume that you want to make a big splash, but don’t have the budget or time to actually do all four strategies at the same time. Instead, you can only do two. The easiest way to think about combinations without replacement is to first compute the number of permutations without replacement and then reduce that value by the number of ways in which the choices could be ordered. Yesterday we calculated that there are 12 different permutations without replacement when I had four options and two choices. So how many ways could our two choices be made, with replacement? We already know the answer from yesterday, it is P(2, 2) = 2! / (2 – 2)! = 2! = 2 * 1 / 1 = 2. That means that the number of combinations without replacement is 12 / 2 = 6.
We can put all of this together into a general form, again denoting n as the number of options and k the number of choices. We calculated the outcomes today as P(n, k) / P(k, k). Because P(k, k) is the same as k!, we can write this as P(n, k) / k! = n! / (n – k)! * k!, which is commonly denoted C(n, k). In the first example we talked about today, there are 4 options (n = 4) and 4 choices (k = 4), so 4! / (4 – 4)! * 4! = 4! / 0! * 4! = 1. In the second example, there are 4 options (n = 4) and 2 choices (k = 4), so 4! / (4 – 2)! * 2! = 4! / 2! * 2! = 6.
Tomorrow I’ll wrap up our conversation on combinatorics by discussing combinations with replacement.