Concept

How does the Fundamental Theorem of Counting determine the number of independent choices?

Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk / Chapter 1

"We start with a basic rule that goes by the audacious name of The Fundamental Theorem of Counting. It goes like this: If a whole can be divided into k parts, and there’s nᵢ choices for the iᵗʰ part, then there’s n₁ × n₂ × n₃ × · · · × nₖ ways of doing the whole thing. Example: Jane is ordering a new Lamborghini. She has twelve different paint colors to choose from, three different interiors, and three different stereo systems. She must also choose between automatic and manual transmission, and she can get power locks & windows (or not). The key is that every one of her choices is independent of all the others. Therefore the answer is: 12 × 3 × 3 × 2 × 2 = 432 choices. The Π notation is exactly the same as the Σ notation, only instead of adding the expressions together for each value of the counter, we’re multiplying them: ∏ᵢ₌₁ᵏ nᵢ. 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, so the answer is 10 × 10 × 10 × 10 = 10,000 different PINs. Most combination locks are opened by a three-number sequence, each number of which is anything from 0 to 39. So there are 40 × 40 × 40 = 64,000 different combinations."

Related Ideas

How does the Fundamental Theorem of Counting determine the number of independent choices? | Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk | Bifalgorithm | Bifalgorithm