The Fundamental Counting Principle
This is the third article in So You Think You Can Count: A Series on Combinatorics.
Every field of math seems to have it’s own fundamental principle or theorem. We have the fundamental theorem of arithmetic (every integer greater than 1 can be uniquely expressed as a product of primes), the fundamental theorem of calculus (part 1 and 2), the fundamental theorem of linear algebra (with about a bazillion parts), etc. So it’s natural to assume there’s a fundamental principle of counting as well. There most definitely is, and we often refer to it as the product principle.
In the simplest sense, the product principle states that if you have two tasks (let’s be creative and call them task #1 and task #2) with m ways to do task #1 and n ways to do task #2, then there are m·n ways to do tasks #1 and #2 sequentially.
That’s a bit abstract, so let’s take a minute to ground ourselves in an example. Imagine you’re making a whole bunch of sandwich cookies for a party. You’re a bit of an overachiever, so you’ve made sugar cookies, peanut butter cookies, lemon shortbread, and double chocolate cookies. You’ve also made several fillings: raspberry jam, buttercream frosting, and chocolate frosting. If we want to know how many distinct combinations we can make, we first need to choose a cookie flavor(task #1), and then we need to choose a filling (task #2). There are 4 choices for task #1 and 3 choices for task #2. So by the product principle, there are 4·3=12 distinct sandwich cookies we can make. If you don’t believe me yet, let’s create a decision tree to visualize it.
We can see that there are 4 paths we can take in choosing a cookie. For each of those paths, there are 3 more paths based on the filling we want. See if you can convince yourself that this really does capture every possible combination of cookies and fillings.
What if we’re dealing with more than two tasks? Does the product principle still apply? Yes! The general product principle states the following:
Given k tasks where the iᵗʰ task can be done in nᵢ ways, there are n₁·n₂·…·nₖ ways to do the sequence of k tasks.
To see what this is saying, let’s come back to our cookie example, but this time let’s go a little wild and crazy. Suppose our top and bottom cookies no longer need to match. Before we do the math, take a minute and see if you can get an intuitive sense of how this new requirement (or lack thereof) will affect the number of possible cookie combinations.
Ok, time to test our hypotheses. We now have three decisions to make: there are 4 options for the bottom cookie, 3 options for a filling, and 4 options for the top cookie. By the product principle, this gives us 4·3·4=36 possible cookie combinations. So, we went from having 12 distinct sandwich cookies with matching tops and bottoms to 36 distinct sandwich cookies with potentially mismatched tops and bottoms. Notice though that this 36 includes the 12 original cookies we counted before. If you’re having some trouble wrapping your head around this, try drawing a decision tree for the mismatched cookies like we did above.
Let’s take a look at one more example (because you can never have too many examples, am I right?). Let’s say we’re making a sandwich. There are 3 kinds of bread to choose from, 4 kinds of meat/protein, 3 types of cheese, 5 different sauces/spreads, and 6 veggies. If we assume we’re just picking one item from each category (I know, that’s a rather bold assumption, but bear with me here), then how many different sandwich combinations can we make? Drawing a decision tree will get out of hand pretty quickly (go ahead and try it), so we definitely need to lean on the product principle. We have 3 choices at our first decision, 4 at the second, 3 at the third, 5 at the fourth, and 6 at the fifth. This means that by the product principle, there are 3·4·3·5·6=1080 distinct sandwich combinations. So how is that helpful? I guess now we know you could eat a sandwich every day for several years without ever repeating a combination… great.
No, but really. How is this helpful? The fundamental principle of counting is fundamental for a reason. It forms the foundation for us to work with more complex counting situations. As we continue on with this series, we’ll use the product principle constantly to count things like passwords, rearrangements of words, license plates, etc. If we step back and look at the field of combinatorics as a whole, the product principle functions in much the same way that we think about basic arithmetic, it’s so fundamental that you eventually don’t even realize you’re using it, it simply becomes second nature.
Have thoughts or questions about the product principle? Toss them in the comments and let’s have a conversation about it!
