Combinatorics: Permutations with Replacement

This is part 2 of our series on Combinatorics, previous segments are available in our archives.

Back when we were talking about game theory, one of the scenarios we talked about was that your company (e.g., Doug’s Desserts) needs to make a decision as whether to raise your price, lower your price, or keep your price the same. Suppose you have 3 other competitors (let’s call them A, B, and C) that sell the same product as you, and they face the same three decisions. Also, you know from your past experience, that your company is the leader in the space and then each of the other companies always react to your pricing decisions in the same order, A then B and then C.

So how many different scenarios could happen? We could count them all out by hand of course…

Doug’s Desserts A B C
Raise Raise Raise Raise
Raise Raise Raise Maintain
Raise Raise Raise Lower
Raise Raise Maintain Raise

 

…but that gets harder and harder as the number of options grows. This problem is an example of a permutation with replacement. Let’s start at the beginning to think through the number of outcomes. Doug’s Desserts first makes a choice between 3 options, then Company A makes a choice between the same 3 options. In other words, for each of the 3 options Doug’s Desserts could choose, Company A could choose any of the same 3 options, meaning there are 3 * 3 = 9 possible outcomes. Next, Company B makes a choice between the same 3 options. In other words, for each of the 9 outcomes we computed for Doug’s Desserts and Company A, Company B could choose 3 options, meaning there are 9 * 3 = 27 outcomes. Finally, Company C makes a choice between the same 3 options. In other words, for each of the 27 outcomes we computed for Doug’s Desserts, Company A, Company B, Company C could choose 3 options, meaning there are 27 * 3 = 81 outcomes.

You can now see the pattern – each time a new choice is made, we multiply the previous result by the number of options. Let’s denote n as the number of options, n = 3 in this example, and k as the number of times the choice is being made, k = 4 in this example. Then we can generalize the concept of permutations with replacement: when there are n options being chosen k times, each time with replacement of the options, there are n^k different outcomes. In this example, that means, 3^4 = 3 * 3 * 3 * 3 = 81.

Tomorrow I’ll talk about the scenario of permutations where the options are not allowed to be replaced.