Combinations Are Just Permutations That Forgot Their Order

The more I learn about counting, the more I notice that the same number keeps showing up in completely different contexts. You count subsets — you get some number. You count binary strings with a fixed number of ones — same number. You count paths on a grid — same number again.

That's not a coincidence. It's a sign that these objects are secretly the same thing, just wearing different costumes. And the tool that reveals the connection is the combination — or "n choose k" — which turns out to be one of the most versatile expressions in all of combinatorics.

In the previous post, we built up from complement counting to permutations to anagrams. This post picks up right where that left off: we'll see how the quotient rule applies to physical symmetry, then derive combinations from permutations, and then discover that subsets, binary strings, and grid paths are all counted by the exact same formula.

Symmetry makes counting harder — and the quotient rule fixes it

Here's a fun problem: you have four different colors of pipe cleaners — red, blue, green, yellow — and you want to make a square. How many different squares can you make?

The answer depends on what "different" means. If you hang each square on a wall like a portrait (fixed orientation), every arrangement is unique. That gives you 4! = 24 squares.

But if you treat them as physical objects you can pick up, rotate, and flip — then some of those 24 "portraits" are actually the same square.

A square has 8 symmetry orientations: 4 rotations (0, 90, 180, 270 degrees) times 2 flips (front and back). Every unique physical square appears as exactly 8 different portraits. So the number of truly different squares is 24 / 8 = 3.

This is the quotient rule from the previous post, applied to geometry instead of letters. Expand to an easier set (portraits), count it, divide by the category size (symmetries).

A cleverer way to see it

There's an alternate approach that avoids the division entirely. Fix one color — say red goes on the bottom. Now you only need to decide what goes on the opposite side (top). There are 3 choices: blue, green, or yellow.

Once you've chosen the top and bottom, the remaining two sides can be swapped by flipping the square. So they don't create new squares. That gives you exactly 3.

Both approaches agree. The quotient-rule method is more systematic (and generalizes to any shape), while the direct method requires more geometric insight but avoids big numbers.

Generalizing to other shapes

For a hexagon with 6 different colored sides, there are 6 rotations and 2 flips = 12 symmetry orientations. The number of unique hexagons would be 6! / 12 = 720 / 12 = 60.

The pattern: total arrangements divided by symmetry orientations. It works for any regular polygon as a physical pipe-cleaner object.

The big shift: from sequences to subsets

Everything we've counted so far — strings, permutations, anagrams — has involved order. Position 1 matters, position 2 matters, and so on. Two sequences are different if their elements are in a different order.

But sometimes order doesn't matter. You just care about which elements are chosen, not the arrangement.

Picking 7 people from a class of 50 to go on a field trip as a group — you don't care who was "picked first." It's just a set of 7 people. That's a combination.

Picking 7 people where each goes on a different day of the week — now the order matters (Monday person vs. Tuesday person). That's a permutation.

The notation for combinations is C(n, k), often written as "n choose k." It counts the number of k-element subsets of a set with n elements.

Deriving the formula: permutations with the order divided out

Here's how to compute C(n, k). The trick is to connect it to something we already know: P(n, k).

Consider picking 7 students from 50 for different days of the week. That's P(50, 7) — a permutation problem.

But we can break that process into two steps:

1. Choose which 7 students go (a combination: C(50, 7) ways)
2. Arrange those 7 students across the days (a permutation of 7: 7! ways)

Since both methods count the same set:

Solving for C(n, k):

That's the combination formula. The k! in the denominator is exactly the "forgetting the order" step — it divides out all the ways you could arrange the k chosen elements.

A concrete example

The numerator is P(50, 7). Dividing by 7! = 5,040 strips away the ordering. The result is 99,884,400.

Try different values:

Notice how C(n, k) is always smaller than P(n, k) — because combinations collapse all k! orderings of the same subset into one.

The key question: does order matter?

The hardest part of counting problems isn't the formula — it's recognizing which formula applies. Here's the mental model that clicked for me:

Permutation = sequence. If elements have roles, positions, or labels that make their arrangement matter, use P(n, k).

Combination = subset. If you're just choosing a group and the arrangement is irrelevant, use C(n, k).

Quick examples

The leader/scribe/treasurer/presenter problem is a permutation because changing who gets which role creates a different outcome — even if the same 4 people are chosen. The conference problem is a combination because the 4 people just go together as a group.

Binary strings and subsets are the same thing

Here's where things get really satisfying. It turns out that C(n, k) doesn't just count subsets — it also counts fixed-density binary strings (binary strings of length n with exactly k ones).

And the reason is a beautiful bijection.

The bijection

Take the set {1, 2, 3, 4} and consider all 2-element subsets. There are C(4, 2) = 6 of them:

The rule: position i gets a 1 if i is in the subset, and a 0 if it isn't. That's it.

This works for any n and k. Every k-element subset maps to exactly one binary string with k ones, and vice versa. Since it's a bijection, both sets have the same size: C(n, k).

Counting binary strings directly

You can also arrive at C(n, k) without knowing about the bijection — just by counting the binary strings on their own.

How many length-8 binary strings have exactly 3 ones?

Method 1: Choose positions. Start with 8 positions. Choose 3 of them to be ones. That's C(8, 3).

Method 2: Anagrams. A string with 3 ones and 5 zeros is really just an anagram of "00000111." We know from the previous post that the number of anagrams is:

And that's exactly C(8, 3) = 56.

This is what I really like about combinatorics — three completely different ways of thinking about the same problem (subsets, binary strings, anagrams) all converge on the same formula. That convergence isn't an accident; it's telling you something deep about the structure.

A subtle point about "order"

Here's a question that tripped me up: if combinations count things where "order doesn't matter," why do they also count binary strings, where the order of 0s and 1s clearly matters?

The resolution: in the binary string, the order of the bits matters for determining which string it is. But the order in which you chose the positions for the ones doesn't matter. You're choosing a subset of positions — and that's the unordered part.

So C(8, 3) counts the number of ways to choose 3 positions from 8. Once you've chosen them, the string is determined. The "combination" is about the choosing, not about the final string.

Grid paths: the same formula in disguise

Suppose you're navigating a 6-by-3 grid of city blocks, starting at the bottom-left corner and trying to reach the top-right corner. You can only move right or up — no backtracking.

To get from bottom-left to top-right, you must make exactly 6 moves to the right and 3 moves up — 9 moves total. Every path is just a different ordering of these 9 moves.

One path might be: R, U, R, U, U, R, R, R, R, R — wait, that's only right if... let me think. Actually: R, R, U, R, U, U, R, R, R. Each path is an anagram of "RRRRRRRRR" — no, let me be precise: 6 R's and 3 U's.

This is exactly a fixed-density binary string of length 9 with 3 ones (if U = 1, R = 0). Or equivalently, we're choosing which 3 of the 9 steps are "up" moves.

Try different grid sizes:

Notice something: C(9, 3) = C(9, 6) = 84. This is the symmetry property of combinations — choosing 3 items to include is the same as choosing 6 items to exclude. Choosing which 3 of 9 steps go up is equivalent to choosing which 6 go right.

Generalizing

For an m-by-n grid, you need m right moves and n up moves, for a total of m + n steps. The number of paths is:

The grid path problem, subsets, binary strings, and anagrams — they're all the same counting problem in different clothing. Each time you encounter one, you can translate it into whichever form makes it easiest to solve.

Everything connects back to the quotient rule

Looking back at this post and the previous one, the quotient rule keeps doing the heavy lifting:

• Anagrams: expand by coloring identical letters, count permutations, divide by internal symmetries
• Geometric shapes: count all orientations, divide by rotational/reflectional symmetry
• Combinations: count permutations (ordered selections), divide by k! (the number of orderings per subset)

The pattern is always: count a bigger set where everything is distinguishable, then divide out the redundancy. It's one idea powering four different counting techniques.

A few things I'm taking away

• Combinations count subsets (unordered selections), while permutations count sequences (ordered arrangements) — the dividing line is whether order matters
• The combination formula C(n, k) = n! / (k!(n-k)!) is just P(n, k) with the k! orderings divided out
• When deciding between permutation and combination, ask: "if I rearrange the chosen elements, do I get a different outcome?" — if yes, it's a permutation; if no, it's a combination
• Subsets and fixed-density binary strings are the same thing via a natural bijection: elements in the subset correspond to positions of ones in the string
• Fixed-density binary strings are also anagrams of a word made of k ones and (n-k) zeros — three perspectives, one formula
• Grid paths on an m-by-n grid are equivalent to choosing which n of the (m+n) total steps are "up" moves — another disguised combination
• The symmetry property C(n, k) = C(n, n-k) makes intuitive sense: choosing k items to include is the same as choosing n-k items to exclude
• Physical symmetry counting (squares, hexagons) uses the same quotient rule as anagrams — total arrangements divided by orientations per unique object
• The quotient rule is the thread connecting anagrams, geometric symmetry, combinations, and binary strings — it's one idea in four costumes
• Naming something ("n choose k") is a real step forward, even before you can compute the number — having notation lets you reason about structure

That last point — about naming things before computing them — stuck with me. In math and in programming, giving something a name is often the first step toward understanding it. You can't manipulate what you can't refer to. The formula matters, but the name came first.