Combinatorics: Combinations with Replacement

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

The last type of combination we will talk about is combinations with replacement. One example of this type of counting problem is buying products in a store. For example, you are standing at the counter of my hypothetical bakery, Doug’s Desserts, and want to buy four donuts (i.e., the number of choices you make, where k = 4). My bakery sells three types of donuts: vanilla frosted, glazed, and jelly-filled (i.e., the number of options you have, where n = 3). The question now is, how many ways can you buy four donuts from the three options, given that you can buy as many as you like of each type of donut?

Similar logic applies to the example I discussed when talking about permutations with replacement – four companies each choosing between three options of what to do with their product’s price. In that context of permutations, we made the assumption that the order of the choices matters. For combinations, though, let’s assume that the order doesn’t matter. The question now is, how many different ways can the four companies can make their pricing decision, assuming that they are all setting their price at the same time?

In both of these examples, there are n = 3 options to choose from, and a decision is being made k = 4 times, where all of the options are available each time the decision is being made.

Let’s use the donut example to think about how to solve this problem, as it is easier to visualize. Imagine that you are at the bakery and and that all of the donuts of each type are all on their own tray. So there are a dozen[1] vanilla frosted on one tray (represented by “O” in the table), a dozen jelly-filled on the tray next to it, and a dozen glazed on its own tray as well.

Vanilla Frosted

OOOOOOOOOOOO

Glazed

OOOOOOOOOOOO

Jelly-filled

OOOOOOOOOOOO

 

You like vanilla frosted and really like jelly-filled, but don’t like glazed, so your plan is to choose one vanilla frosted and three jelly-filled. You could imagine the purchasing process being something as follows.

First you stand in front of the tray of vanilla frosted donuts (the tray you are looking at is colored blue)…

Vanilla Frosted

OOOOOOOOOOOO

Glazed

OOOOOOOOOOOO

Jelly-filled

OOOOOOOOOOOO

[You]


and ask for one of those donuts to be put in your bag. Then you move to the next tray of donuts, glazed.

Vanilla Frosted

OOOOOOOOOOOX

Glazed

OOOOOOOOOOOO

Jelly-filled

OOOOOOOOOOOO

[You]

 

Since you don’t want any of these donuts, none are taken from the tray. You move to the last tray of donuts, jelly-filled…

Vanilla Frosted

OOOOOOOOOOOX

Glazed

OOOOOOOOOOOO

Jelly-filled

OOOOOOOOOXXX

[You]


and ask for one of these donuts three times.

If a bystander had been recording the steps you took to buy your donuts, it would have looked like this: (1) donut (2) move to next tray (3) move to next tray (4) donut (5) donut (6) donut. The actual donut chosen doesn’t really matter because this is a combination and order of choices do not matter.

Looking at the purchase this way, no matter which donuts you choose, you are always going to have 4 (i.e., k) “donut” steps and 2 (i.e., n – 1) “move to next tray” steps. This is like saying, we have k + (n -1), 6 in our example, different options of choosing a donut or moving to the next tray, and we want to choose k, 4 in our example, donuts. In other words, this is the same as a combination without replacement, but with slightly modified inputs to the formula we discussed yesterday! The total number of outcomes is C(k + (n – 1), k) = (k + (n – 1))! / (k + (n – 1) – k)! * k! = (k + (n – 1))! / (n – 1)! * k!. Plugging our values in from the example, there are 6! / 2! * 4! = 15 outcomes of how you could select your donuts (or the companies could make their pricing decisions).

Well, that’s it for permutations and combinations. I hope you’ve enjoyed this week on counting the outcomes you could face at your business!

[1] That there are a dozen donuts doesn’t really matter, as long as there are at least four on each tray – because that is how many choices you are making and we are assuming all of the options are available for each choice – the logic is the same.