One way to define probability is as the ratio of the number of favorable outcomes to the total number of outcomes. This seemingly "simple" definition hides the complexity involved in setting up the calculation for probability.

The complexity lies in the phrase "number of". This branch of mathematics that deals with how to count things is known as combinatorics, and it is fundamental to understanding probability. In this article, we will build intuition on answering the question "How many ways to choose a subset of things from a set". However, to get to our main question, we need to answer a series of other questions that will lead us there.

How Many Ways to Arrange K Things?

The setup for this question is that you have K items. Let's assume K is 3, and the items in question are 3 cats: Spark, Winston, and Miller. We want to know how many different arrangements we can have of our 3 cats. By brute force, we could list the arrangements, but a smarter way would be to compute the permutations.

Since we care about arrangements, "Spark, Winston, Miller" and "Miller, Winston, Spark" are different arrangements. When we care about the order of items, the result is called permutations (ABC ≠ BAC). When we don't care about the order, the result is called combinations (ABC = BAC). For a combination, ABC, BAC, and CAB are just a single combination of the same 3 items.

To calculate the permutations, imagine 3 empty spots, where each of the 3 cats can be placed.

• For the first spot, we have 3 cats to pick from.
• For any of the 3 cats picked for the first spot, we have 2 cats left to pick for the next spot.
• For the last spot, only 1 cat is left.

This results in 3×2×1=63 \times 2 \times 1 = 63×2×1=6 permutations.

This can be generalized: the total number of ways to arrange K items is:

K!=K×(K−1)×(K−2)×…×1

How to Arrange K Items from a Total of N Items? (N≥K)

Let's say we have 5 cats and want to find out how many ways we can pick and arrange 3 cats from these 5. Using the same logic:

• We have 5 choices for the first spot.
• 4 choices for the second spot (since 1 cat is already placed).
• 3 choices for the third spot.

So, the total number of ways to pick and arrange 3 cats out of 5 is 5×4×3 = 60

This can be generalized: to find the number of ways to arrange K items from N total items, we calculate:

N×(N−1)×(N−2)×…×(N−K+1)

Expressed as a formula:

N! / (N - K)!

How to Choose K Items from a Total of N Items? (Combinations)

If we want to know how many ways there are to choose K items from N items (combinations), where order doesn't matter:

We start with the total permutations N! / (N - K)!​. However, since order doesn't matter, we divide by the number of ways to arrange K items, which is K!:

Combinations = N! / (N-K)! * K!

Summary

• Permutations: Number of ways to arrange K items from N => N! / (N - K)!
• Combinations: Number of ways to choose K items from N (where order doesn't matter) is => N! / (N-K)! * K!

These concepts form the basis for understanding probability and counting in combinatorics, encapsulated in the binomial coefficient N Choose K, which represents the number of ways to choose K unordered outcomes from N possibilities.