Counting: The Fourfold Way

Part Of: Statistics, Algebra sequences
Content Summary: 1100 words, 11 min read

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:

Burger $b \in \{ Chicken, Beef \}$
Side $s \in \{ Fries, Chips \}$
Drink $d \in \{ Fanta, Coke, Sprite \}$

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.

Permutation_ Trees of Events (1)

Can we generalize? Yes, with the help of the fundamental principle of counting (aka the rule of multiplication). For any event $A$ with $a$ possible outcomes, and another event $B$ with $b$ possible outcomes, the number of possible outcomes for composite event $A \cup B$ is $a*b$ .

How does counting work for a repeating event? For an event with $n$ possibilities occurs $k$ times, there are $k^n$ 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 $2^8 = 256$ possible outcomes.

Permutations

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 $9^3 = 729$ possible outcomes.

This answer is completely wrong. To understand why, consider the lottery machine:

powerball

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 $9 \times 8 \times 7 = 504$ possible trifecta bets.

Permutation_ 9 perm 3

Similar to how exponentiation is defined as repeated multiplication, a factorial is defined as slowly-decrementing multiplication.

$9! = 9 \times 8 \times 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1$

But we only want $9 \times 8 \times 7$ . How can we get rid of the other terms? By division, of course!

$9 \times 8 \times 7 = \dfrac{9 \times 8 \times 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1}{6 \times 5 \times 4 \times 3 \times 2 \times 1} = \dfrac{9!}{6!}$

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,

$\dfrac{9!}{9-3!}$

More generally, if you have n items and want to find the number of ways k items can be ordered:

Equation 5: Permutation. $P(n, k) = \dfrac{n!}{(n-k)!}$

Combinations

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 $P(4,3) = \dfrac{4!}{4-3!} = 24$ possible trifecta bets. But how many boxed trifecta bets are possible?

Combinations treat duplicates as a single entry. For example, $abc$ and $acb$ are equivalent for a boxed trifecta bet. We can identify four groups, with six equivalent permutations each:

Permutation_ 4 choose 3

In general, how many winner duplicates exist? How many ways can we shuffle $k$ winners? Well, if you have k winners and are wondering how many permutations exist for that entire set… that’s $P(k,k)$ !

Equation 6: Combination. $C(n, k) = \dfrac{P(n,k)}{P(k,k)} = \dfrac{P(n,k)}{k!} = \dfrac{n!}{(n-k)! k!}$

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 $k=3$ cookies $a, b, c, d$ to give to $n=4$ kids. How many possible ways are there to do so?

In the case of medals and horses, we claimed four solutions: $\{ a, b, c\}$ , $\{ a, b, d\}$ , $\{ a, c, d\}$ , and $\{ b, c, d\}$ . 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 $\{ a, a, a\}$ , 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.

Combinatorics_ Stars and Bars (2)

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, $\binom{6}{3}$ .

How many objects are possible in general? There are $n$ stars (kids). Since bars represent bin boundaries, there are $n-1$ bars. Thus:

Equation 8: Multi-Combination. $C(n, k) = \binom{n+(k-1)}{k}$

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).

Combinatorics_ Possibilities vs Outcomes

Equation 9. An event is a function that maps outcomes to possibilities:

$Event : Outcomes \rightarrow Possibilities$ .

Combinatorics_ Events as Functions (2)

This function can be compactly represented as $bbd$ .

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 $aab$ and $ccc$ . 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.

Combinatorics_ Fourfold Way