The Fundamental Principle of Counting
We often care to count the number of possible outcomes for multiple events.
Example 1. Consider purchasing a lunch with the following components:
How many lunch outcomes are possible?
Three approaches to counting suggest themselves. We might make a list. But this process can be error prone. Other representations are more systematic: we can build a tree, or imagine a (hyper)-volume. Each strategy converges on the same answer: 12 possible lunches.
Can we generalize? Yes, with the help of the fundamental principle of counting (aka the rule of multiplication). For any event with possible outcomes, and another event with possible outcomes, the number of possible outcomes for composite event is .
How does counting work for a repeating event? For an event with possibilities occurs times, there are possible outcomes.
Example 2. How many numbers can be represented by a byte (8 bits)?
Each bit has two possible assignments: zero or one. For eight such “bit events”, we have possible outcomes.
Example 3. A trifecta bet guesses which horse will place first, which second, and which third. How many such bets are possible in a 9-horse race?
Each medal has nine possible assignments. For three such “medal events”, we have possible outcomes.
This answer is completely wrong. To understand why, consider the lottery machine:
- In Example 2, a single value (e.g., 0) can freely be assigned to multiple bits. Every time you draw a bit from the “possibility machine”, it is replaced when the next bit is drawn. Sampling with replacement means that each event is exactly the same.
- In Example 3, a single horse (e.g., Secretariat) cannot be assigned multiple medals. Every time you draw a horse from the “possibility machine”, it cannot be drawn for subsequent events. Sampling without replacement means that each event has diminishing numbers of possibilities.
Definition 4. A permutation is a list of outcomes drawn without replacement.
For the trifecta bet, how many permutations exist? Well, 9 different horses that earn the gold. Given that one horse won the gold, 8 different horses that can earn the silver. Then there are 7 different horses that can earn bronze. Thus, there are possible trifecta bets.
Similar to how exponentiation is defined as repeated multiplication, a factorial is defined as slowly-decrementing multiplication.
But we only want . How can we get rid of the other terms? By division, of course!
Why did we use the number 6? Because if three of our nine horses place, six do not place. So a more general way to write this equation,
More generally, if you have n items and want to find the number of ways k items can be ordered:
Equation 5: Permutation.
In contrast to permutations, for combinations, order doesn’t matter. A permutation is a list, a combination is a set.
A boxed trifecta bet requires correctly which three horses will place first, second and third (order doesn’t matter). A trifecta bet selects a permutations; a boxed trifecta bet selects a combination.
Imagine only four horses in the race. That’s possible trifecta bets. But how many boxed trifecta bets are possible?
Combinations treat duplicates as a single entry. For example, and are equivalent for a boxed trifecta bet. We can identify four groups, with six equivalent permutations each:
In general, how many winner duplicates exist? How many ways can we shuffle winners? Well, if you have k winners and are wondering how many permutations exist for that entire set… that’s !
Equation 6: Combination.
For an example of combinations used to solve a real problem, I recommend this post.
The Fourth Way: Stars and Bars
Example 7. You have cookies to give to kids. How many possible ways are there to do so?
In the case of medals and horses, we claimed four solutions: , , , and . But there is an important difference: horse-less medals are impossible, but cookie-less children are not! So we need to account for situations like , with one child getting all of the cookies.
We can use the traditional bins-as-containers metaphor to visualize outcomes (top row). Or we can instead visualize bin boundaries (bottom row). This visualization strategy is called stars and bars.
How many kid-cookie outcomes are possible? The answer becomes apparent only if we use stars and bars (bottom row). Every possible shuffling of the stars in those squares produces a valid event. That is, .
How many objects are possible in general? There are stars (kids). Since bars represent bin boundaries, there are bars. Thus:
Equation 8: Multi-Combination.
The Fourfold Way
Every example we have seen differentiates possibilities and outcomes. We will use the metaphor of balls for outcomes (something concrete) and bins for possibilities (something to “clothe” outcomes).
Equation 9. An event is a function that maps outcomes to possibilities:
This function can be compactly represented as .
Functions require every element of the domain to map to the codomain. Event functions require no unrealized outcomes. That is: every outcomes manifests a possibility. Every ball is given a bin.
We saw previously that combinations and permutations don’t allow events like and . A single horse cannot win multiple medals. Multiply-realized possibilities are not allowed.
Recall the definitions of injective, surjective and bijective functions. This requirement is the injective property. Sampling without replacement is the same thing as injectivity.
Tuple, permutation, combination, and multi-combination. This is the fourfold way. The Way can be made more general by counting situations where the possibilities are unlabeled, and the event function meets the surjection property. But for details on the more complete twelvefold way, I recommend this post.
Towards a Rosetta Stone
Now, consider all possible functions for 4 bins and 3 balls:
What do the equations above have to do with this shape? Well, each way of counting corresponds with a different subset of this broader shape:
I leave it to the interested reader to ponder, how such a jagged shape can be represented by these four relatively clean formulae.
Until next time.