Combinatorics: Permutations without Replacement
Yesterday, I talked about how to count permutations when the same set of options is available at each step of the process. Today, I’ll talk about how to count the outcomes when each choice is only allowed to be made once.
Suppose you are ready to launch a new product and are trying to figure out the best strategy on how to announce it to the general public. You’ve identified four different marketing strategies that you are considering to undertake:
- Send a press release and schedule interviews with the news media
- Run an online marketing campaign
- Run a TV / radio marketing campaign
- Sponsor and speak at an industry conference
From your experiences in marketing, you believe that the order in which you undertake these initiatives matters. In other words, you think that the outcome that would come about by running an online marketing campaign before sponsoring and speaking at an industry conference would be different than if the conference happened before the online marketing campaign.
So how many different outcomes do you have to consider? This is an example of permutations without replacement. There are four different strategies to consider, which we will denote as n. When thinking about what to do first, you have four choices. When thinking about what to do second, you only have three choices left (since we aren’t going to do the same marketing strategy twice). At the time you are making the choice of what to do third, you have two strategies remaining. Finally, the strategy to do last is determined by your previous choices as there is only one option left. Putting this together, you have 4 * 3 * 2 * 1 = 24 different outcomes to consider.
The calculation of the product of integers that we just made happens so frequently that it has its own special name and mathematical notation. It is called a factorial and denoted with as an “!” after a number. It is shorthand to mean, take the product of each integer less than or equal to the number. For example, 4! = 4 * 3 * 2 * 1 = 24, exactly what we computed above. More generally then, if we are going to undertake all n of our marketing strategies, then we have to consider n! different outcomes.
But what if you can’t do all of the marketing strategies because you just don’t have the time or budget. Instead, you can only choose 2 of the 4 options. Let’s denote the number of selections you’ll make as k, k = 2 in this example. You can choose from 4 strategies for the first step and 3 strategies for the second step, but then you stop there. So you have 4 * 3 = 12 outcomes to consider. Notice how the only difference between this outcome and the one earlier is that 2 * 1 is no longer in the formula. We can rewrite the formula (and it will be clear why soon) as 4 * 3 * 2 * 1 / 2 * 1 = 4 * 3 = 12. In other words, we have a total of n! outcomes, but need to reduce that value by the number of choices we are able to make, which is (n – k)!
Putting both of these examples, we can write one, general formula how to compute permutations with replacement: n! / (n – k)!, commonly denoted P(n, k). In the first example we talked about, there are 4 options (n = 4) and 4 choices (k = 4), so 4! / (4 – 4)! = 4! / 0! = 24 . In the second example, there are 4 options (n = 4) and 2 choices (k = 2), so 4! / (4 – 2)! = 4! / 2! = 12.
Now that we know about how to count when order does, matter, tomorrow, I’ll talk about combinations, where order does not matter.
 0! = 1, by convention.