6.1: The Fundamental Theorem

We start with a basic rule that goes by the audacious name of The Fundamental Theorem of Counting.¹ It goes like this:

Example: Jane is ordering a new Lamborghini. She has twelve different paint colors to choose from (including Luscious Red and Sassy Yellow), three different interiors (Premium Leather, Bonded Leather, or Vinyl), and three different stereo systems. She must also choose between automatic and manual transmission, and she can get power locks & windows (or not). How many different configurations does Jane have to choose from? Put another way, how many different kinds of cars could come off the line for her?

The key is that every one of her choices is independent of all the others. Choosing an Envious Green exterior doesn’t constrain her choice of transmission, stereo, or anything else. So no matter which of the 12 paint colors she chooses, she can independently choose any of the three interiors, and no matter what these first two choices were, she can freely choose any of the stereos, etc. It’s a mix-and-match. Therefore the answer is:

\[12 \times 3 \times 3 \times 2 \times 2 = 432\ \text{choices}.\]

Here’s an alternate notation you’ll run into for this, by the way:

\[\prod_{i=1}^k{n_i}\] which is just a shorter way of writing \[n_1 \times n_2 \times n_3 \times \cdots \times n_k.\]

As mentioned in section 5, the \(\Sigma\) notation is essentially a loop with a counter, and it says to add up the expression to the right of it for each value of the counter. The \(\Pi\) notation is exactly the same, only instead of adding the expressions together for each value of the counter, we’re multiplying them. (The reason mathematicians chose the symbols \(\Sigma\) (sigma) and \(\Pi\) (pi) for this, by the way, is that “sigma" and “pi" start with the same letter as “sum" and “product," respectively.)

We can actually get a lot of leverage just with the fundamental theorem. How many different PINs are possible for an ATM card? There are four digits, each of which can be any value from 0 to 9 (ten total values), so the answer is:

\[10 \times 10 \times 10 \times 10 = 10,000\ \text{different PINs}.\]

So a thief at an ATM machine frantically entering PINs at random (hoping to break your account before you call and stop your debit card) would have to try about 5,000 of them on average before cracking the code.

What about middle school bullies who are trying to break into your locker? Well, most combination locks are opened by a three-number sequence, each number of which is anything from 0 to 39. So there are:

\[40 \times 40 \times 40 = 64,000\ \text{different combinations}.\]

That’s probably slightly overstated, since I’ll bet consecutive repeat numbers are not allowed (Master probably doesn’t manufacture a lock with a combination of 17–17–23, for example.) But it does seem at least as secure as a PIN number.

Every car in the state of Virginia must be issued its own license plate number. That’s a lot of cars. How many different license plate combinations are available?

This one requires a bit more thought, since not all licenses numbers have the same number of characters. In addition to “SED4756" and “PXY1927" you can also have “DAWG" or “LUVME" or even “U2". How can we incorporate these?

The trick is to divide up our set into mutually exclusive subsets, and then add up the cardinalities of the subsets. If only 7 characters fit on a license plate, then clearly every license plate number has either 1, 2, 3, 4, 5, 6, or 7 characters. And no license plate has two of these (i.e., there is no plate that is both 5 characters long and 6 characters long). Therefore they’re mutually exclusive subsets, and safe to add. This last point is often not fully appreciated, leading to errors. Be careful not to cavalierly add the cardinalities of non-mutually-exclusive sets! You’ll end up double-counting items.

So we know that the number of possible license plates is equal to:

the # of 7-character plates +
the # of 6-character plates +
the # of 5-character plates +
\(\cdots\) +
the # of 1-character plates.

Very well. We can now figure out each one separately. How do we know how many 7-character plates there are? Well, if every character must be either a letter or a digit, then we have 26 + 10 = 36 choices for each character. This implies \(36^7\) different possible 7-character license plates. The total number of plates is therefore: \[36^7 + 36^6 + 36^5 + 36^4 + 36^3 + 36^2 + 36 = \text{80,603,140,212 plates}\]

which is about ten times the population of the earth, so I think we’re safe for now.

Here’s an interesting thought experiment to test your intuition about numbers. Look at the above calculation, and ask yourself: “what if the state of Virginia decided, for purposes of consistency, that all license plates had to have the full 7 characters? Would that significantly reduce the total number of possible plates?" My first inclination would be to say “yes," because we’re adding seven things in that equation, and if we mandated 7-character plates for everyone we’d eliminate 6 out of the 7. Surely we’d be in danger of running out of license plates to give to all the cars! But in fact the new total number of plates would turn out to be: \[36^7 = \text{78,364,164,096 plates}.\]

Wow. We’ve hardly lost anything by scrapping all the less-than-7-character plates. Turns out that in comparison with the 7-character plates, all the other lengths were a drop in the bucket. This is a powerful illustration of exponential growth. When you modify the exponent, going from something like \(36^6\) to \(36^7\), you get astronomically larger very, very quickly. This is a good thing to know when all you want is an approximation of some quantity. How many passwords are possible in a system that mandates 6-10 characters per password? Well, you can pretty much ignore all the 6-9 character passwords and just count the 10-character passwords, because there are so many more of those.

One last tweak to the license plate example before we move on. Suppose (again, for the sake of consistency) that Virginia outlawed personalized plates and gave everyone a randomly generated 7-character plate. Furthermore, the last four characters of the plate had to be digits instead of letters, so that something like “" would be impossible. Now how many possible plates would there be?

In this case, not each of the \(k\) parts of \(n\) have an equal number of choices. \(n_1\) through \(n_3\) are still 36, but now \(n_4\) through \(n_7\) are just 10. So this gives us: \[36 \times 36 \times 36 \times 10 \times 10 \times 10 \times 10 =\ \text{466,560,000 plates}\]

or only about .006 times as many as before. Better stick with alphanumeric characters for all seven positions.

A simple trick

Sometimes we have something difficult to count, but we can turn it around in terms of something much easier. Often this involves counting the complement of something, then subtracting from the total.

For instance, suppose a certain website mandated that user passwords be between 6-10 characters in length — every character being an uppercase letter, lowercase letter, digit, or special character (*, #, @, % or &) — but it also required each password to have at least one digit or special character. How many passwords are possible?

Without the “at least one digit or special character" part, it’s pretty easy: there are 26 + 26 + 10 + 5 = 67 different choices for each character, so we have \[67^{10} + 67^9 + 67^8 + 67^7 + 67^6 = \text{1,850,456,557,795,600,384 strings}.\]

But how do we handle the “at least one" part?

One way would be to list all the possible ways of having a password with at least one non-alpha character. The non-alpha could appear in the first position, or the second, or the third, \(\dots\), or the tenth, but of course this only works for 10-digit passwords, and in any event it’s not like the other characters couldn’t also be non-alpha. It gets messy really fast.

There’s a simple trick, though, once you realize that it’s easy to count the passwords that don’t satisfy the extra constraint. Ask yourself this question: out of all the possible strings of 6-10 characters, how many of them don’t have at least one non-alpha character? (and are therefore illegal, according to the website rules?)

It turns out that’s the same as asking “how many strings are there with 6-10 alphabetic (only) characters?" which is of course: \[52^{10} + 52^9 + 52^8 + 52^7 + 52^6 = \text{147,389,519,403,536,384 (illegal) passwords}.\]

Now, all we have to do is subtract to get \[\begin{aligned} \text{total # of strings -- # of illegal passwords} & = \text{# of legitimate passwords} \\ \text{1,850,456,557,795,600,384 -- 147,389,519,403,536,384} &= \text{1,708,735,865,301,022,720}\end{aligned}\] legitimate passwords. Looks like we don’t lose much by requiring the non-alpha character.

The lesson learned is that if counting the elements in some set involves accounting for a lot of different sticky scenarios, it’s worth a try to count the elements not in the set instead, and see if that’s easier.

---

1. How many other “Fundamental Theorems” of math do you know? Here are a few: the Fundamental Theorem of Arithmetic says that any natural number can be broken down into its prime factors in only one way. The Fundamental Theorem of Algebra says that the highest power of a polynomial is how many roots (zeroes) it has. The Fundamental Theorem of Linear Algebra says that the row space and the column space of a matrix have the same dimension. The Fundamental Theorem of Calculus says that integration and differentiation are the inverse of each other.