Combinatorics

Combinatorics is all about counting: how many ways can you arrange, select, or group objects under certain rules? This sounds simple, but surprisingly subtle patterns and formulas arise. The best way to master combinatorics is to focus on why the formulas make sense, not just memorize them.

Let’s start by seeing how the fundamental principles work and how each formula is built from scratch.

Fundamental Counting Principles

Before we jump into fancy formulas, we need two basic ideas: the Multiplication Principle and the Addition Principle.

Multiplication Principle

Suppose you want to perform several actions in sequence, and each step is independent of the previous ones. This independence means the choices for each step do not affect the others. Then by the multiplication principle we can count the total number of ways to perform the sequence.

If the first action can be done in \(n_1\) ways, and the second in \(n_2\) ways (regardless of how you did the first), then the whole sequence can be done in \(n_1 \cdot n_2\) ways.

Imagine picking a shirt (3 options) and then pants (2 options). For every shirt, you can pick any pants: 3 shirts times 2 pants equals 6 different combinations.

We can generalize this to multiple actions where if you have \(k\) choices, each with \(n\_i\) options, we can simply multiply them to get the total number of different combinations:

Addition Principle

If there are several different ways to do something, and you can only do one at a time (the sets of options don’t overlap) or more formally, if tasks A and B are mutually exclusive, then if task A can be done in \(n_1\) ways and task B in \(n_2\) ways, there are \(n\_1 + n\_2\) possible outcomes.

Imagine you can take bus (3 routes) or train (2 routes) to work, but not both: \(3+2=5\) options to get to work.

Permutations

The idea of a permutation is about rearranging objects in some order. Commonly, we just want this to be some random order. We denote such a random permutation of a set with \(n\) objects as:

However, in combinatorics we want to count how many different ways we can arrange the objects. So note, we care about the order of the objects, which is why we call it a permutation. Suppose you have \(n\) distinct objects, and you want to arrange all of them in a row. Then the first question is how many different arrangements (or permutations) are possible? This is commonly also called a full permutation.

We can build an arrangement step-by-step:

• The first spot: \(n\) choices (any object).
• Second spot: \(n-1\) choices (one is used up).
• Third spot: \(n-2\) choices.
• …
• Last spot: \(1\) choice (only one object remains).

Obviously as we take each object, the number of choices shrinks by 1 each time as we do not allow for any repeated objects. So the total number of arrangements is:

This follows from the multiplication principle, since each choice is independent of the others.

Partial Permutations

Partial permutations are when you want to arrange only a subset of the objects, not all of them. This is useful when you have more objects than spots to fill. This is sometimes also referred to as a k-permutation where \(k\) is the number of spots you want to fill. Suppose you have \(n\) distinct objects, but want to arrange only \(k\) of them in some order. We can derive the formula step-by-step just like before:

• First spot: \(n\) choices
• Second spot: \(n-1\) (since we can’t repeat)
• …
• \(k\)-th spot: \(n - (k-1)\) choices

So, here our reordering is just cut short at \(k\) spots instead of \(n\). The total arrangements are then again by the multiplication principle:

This is just the first \(k\) factors of \(n!\), so we want to express this in terms of factorials and remove the unnecessary terms. The last term is \((n-k)!\), which is the product of all the numbers from \(1\) to \(n-k\). So we can write:

Permutations With Repetition

What if you can use the same object multiple times in your arrangement? This is called permutations with repetition as we allow for repetitions. Here’s how to think about it:

• For each spot: \(n\) choices (since after picking, you “replace” it).
• \(k\) spots: \(n \cdot n \cdot \dots \cdot n = n^k\)

Permutations of Indistinguishable Objects

Suppose that rather then all objects being distinct like in a set, some objects are indistinguishable, so like in a multiset. This means that swapping two identical objects does not create a new arrangement. For example the word “BALLOON” has 7 letters, but the two L’s and two O’s are indistinguishable swapping them does not create a new arrangement (word).

We can still count the arrangements, but we need to adjust our formula to account for these indistinguishable objects. In general if you have \(n\) objects, divided into groups \(k\) of indistinguishable objects of sizes \(n_1, n_2, \ldots, n_k\), where \(n_1 + n_2 + \ldots + n_k = n\). To count the arrangements, we can think of it like this:

• We start with \(n\) objects, and arrange them as if they were all distinct: \(n!\).
• But then we have to account for the indistinguishable groups. For each group of size \(n_i\), swapping those objects does not create a new arrangement, so we divide by \(n_i!\) for each group.

This results in the formula where \(S\) is the multiset of objects and \(k\) is the number of distinct groups:

Combinations

For permutations, we cared about order: how many ways to arrange objects. But what if we just want to select objects, and order doesn’t matter? This is where combinations come in.

Suppose you have \(n\) distinct objects, and you want to select \(k\) of them, with no repeats, and the order is irrelevant. So the arrangement “ABC” is considered the same as “CAB”.

To count combinations, we can use the idea of partial permutations but adjust for the fact that order doesn’t matter.

• We start by counting all the ways to arrange \(k\) of them in order: \(P(n, k) = \frac{n!}{(n-k)!}\).
• But for combinations, order doesn’t matter! Every group of \(k\) elements can be arranged among themselves in \(k!\) ways, but all those are really the same selection. Or in other words, every unique group is counted \(k!\) times (one for each order).

So, to count each group once, we must divide by \(k!\):

This results in the binomial coefficient, often read as “n choose k” or \(\binom{n}{k}\) as we are choosing \(k\) objects from \(n\) and we don’t care about the order. You can find out more about the binomial coefficient on the binomial coefficient page.

Combinations With Repetition

Suppose you can select distinct objects with replacement (each object can be chosen multiple times), and order still doesn’t matter. This is a bit tricker but the idea is similar to combinations without replacement. Think of it as having 3 chores for students to do after school, and you have 10 students to choose from. Each student can do any number of chores, including none. If you are very unlucky, you might end up with all 3 chores assigned to the same student.

So if you have \(n\) distinct objects and want to choose \(k\) of them, allowing repeats, we can use a classic combinatorial trick called the stars and bars method.

The idea is to think of the \(k\) selections as \(k\) indistinguishable stars, and we need to place them into \(n\) distinguishable boxes (the objects). The key is that we can have empty boxes (some objects may not be chosen). We can think of it as having \(k\) stars (choices) and \(n-1\) bars (dividers between boxes). Arranging the stars and bars in a line gives a unique selection. So there are \(k + n - 1\) positions and we choose \(k\) of them to put stars (or equivalently, \(n-1\) to put bars):

A A B | C | D | E

A | B B C | D | E

Inclusion-Exclusion Principle

When you want to count the number of elements in the union of overlapping sets, you can’t just add the sizes of the sets as there is an overlap that gets counted more than once for the objects that belong to both sets. The inclusion-exclusion principle corrects this.

For two sets:

Adding \(|A|\) and \(|B|\) counts any element in both sets twice—so subtract \(|A \cap B|\) once. We call it the inclusion-exclusion principle because we include the sizes of both sets, then exclude the size of their intersection to avoid double-counting. We can also extend this to three sets and more. For three sets:

We first add the sizes of all three sets, then subtract the sizes of each pairwise intersection (since they were counted twice), and finally add back the size of the triple intersection (since it was subtracted too many times). For \(n\) sets, the formula generalizes to:

This alternating sum accounts for overlaps at all levels, correcting for double-counting. This formula is often also referred to as the sieve method, as it “sieves out” the overlaps to get the correct count.

Pigeonhole Principle

The piegonhole principle is a simple but powerful counting argument that is used in many proofs. It states that if you have more items than containers, at least one container must hold more than one item. The reasoning is straightforward: if you try to put \(n\) items into \(k\) containers and \(n > k\), then at least one container must contain at least \(\lceil n/k \rceil\) items, because if each container could hold at most one item, you would only be able to place \(k\) items in total.

The name comes from the idea of pigeons and pigeonholes: if you have 10 pigeons and only 9 pigeonholes, at least one pigeonhole must contain at least 2 pigeons.

Derangements

A derangement is a permutation where no object appears in its original position. So in a way you can think of it as a very specific type of permutation where we want to avoid any objects being in their original place. This is often denoted as \(!n\) for \(n\) objects.

Suppose you want to count the number of ways \(n\) letters can be placed into \(n\) addressed envelopes so that no letter is in the correct envelope.

Let \(A_i\) be the set of arrangements where letter \(i\) is in the right envelope. We want the total number not in any \(A_i\) (i.e., in none of the \(A_i\)).

By inclusion-exclusion:

where \(n!\) is the total number of permutations and the sum accounts for the overlaps of arrangements where at least one letter is in the correct envelope by alternating adding and subtracting the arrangements that fix at least one letter in its correct position matching the principle of inclusion-exclusion.

De Morgan’s Laws for Counting

De’Morgan’s Laws are common rules in set theory that help us understand how to manipulate unions and intersections of sets. They are particularly useful when dealing with complements of sets:

With regards to counting these laws help us calculate the number of outcomes not in a union or intersection. This is often handy with inclusion-exclusion.

Urn Model

The urn model is a metaphor for almost every combinatorics scenario. It helps visualize how to count arrangements, selections, and distributions of objects. Think of an urn containing \(n\) distinct balls, and you want to draw \(k\) balls under various conditions such as with or without replacement, and whether order matters or not etc. This is also a very useful model to visualize basic probability theory concepts as drawing balls from an urn behaves just like drawing a sample from a laplace distribution if the balls are drawn with with replacement.

We can then summarize the 4 main cases in a table:

Or we can summarize the different types of combinatorial problems in a table: