Permutations and Combinations

Order matters means arrange them and the count is bigger; order does not matter means choose them and you divide the arrangements by the reshuffles.

Choosing 2 players from 5 gives 10 unordered teams but 20 ordered lineups, because every team of 2 reshuffles into 2 orders and permutations count each reshuffle separately

Why Does This Exist?

Feature selection, top $k$ rankings, and shuffled splits all ask one question: how many ways can you pick $k$ things from $n$ ? Get it wrong and your "exhaustive" subset search skips most subsets, or your shuffle baseline uses the wrong denominator. The trap is that two nearly identical questions have answers differing by a factor of $k!$ , and English hides which one you asked.

Counting and basic probability gives the multiplication rule this page builds on. This page settles the order question: when to count every arrangement and when to divide the reshuffles away.

The one idea you need first

Sampling without replacement means each pick removes that item from later picks: first pick has $n$ options, the next has $n - 1$ , then $n - 2$ . That shrinking product is where both formulas come from.

Think of It Like This

Picking a team versus posting a lineup

You coach 5 players and need 2 on the court. If you only care who plays, Alice plus Ben is one team. If you must post a lineup with positions, Alice at point plus Ben at wing differs from Ben at point plus Alice at wing: one team, two lineups.

Every team of 2 reshuffles into exactly $2! = 2$ lineups. So count the lineups first (easy, it is just sequential picks), then divide by the reshuffles per team to get the teams. That division is the entire difference between the two formulas, and forgetting it overcounts by $k!$ every time.

How It Actually Works

Picking an ordered lineup of $k$ from $n$ multiplies the shrinking options:

P(n, k) = n \times (n-1) \times \cdots \times (n-k+1) = \frac{n!}{k!/(n-k)!} = \frac{n!}{(n-k)!}

In plain words: $P$ counts arrangements, and order matters. The symbol $n!$ means factorial: $n$ down to 1 multiplied together.

Choosing an unordered set divides away the $k!$ reshuffles of each set:

C(n, k) = \binom{n}{k} = \frac{P(n,k)}{k!} = \frac{n!}{k!(n-k)!}

In plain words: $C$ counts sets, and order does not matter. $\binom{n}{k}$ reads " $n$ choose $k$ ."

Worked example

Choose 2 features from 5 candidates.

Permutations: $P(5,2) = 5 \times 4 = 20$ ordered pairs. First slot has 5 options, second has 4.

Combinations: $C(5,2) = 20 / 2! = 20 / 2 = 10$ sets. Each pair reshuffles 2 ways, so divide by 2.

Sanity check by listing around one member: pairs containing feature A are AB, AC, AD, AE, just 4. By symmetry each feature sits in 4 pairs, giving $5 \times 4 / 2 = 10$ , since every pair got counted at both ends. The division by 2 is doing real work.

Watch Out For

Counting permutations when the task wants combinations

The symptom is a subset search priced $k!$ times too high: "all pairs of 50 features" quoted as $50 \times 49 = 2{,}450$ model fits when unordered pairs need only $1{,}225$ . The fix is the lineup test: if swapping two picked items changes nothing about the result, you want combinations, so divide by $k!$ . Rankings, passwords, and PINs keep order; teams, subsets, and feature sets do not.

Mixing up sampling with and without replacement

With replacement (a die rolled twice), the options never shrink: $6 \times 6 = 36$ . Without replacement (two cards dealt), they do: $52 \times 51$ . The symptom is a denominator that is slightly off, like pricing bootstrap samples with the without-replacement formula. Bootstrap resamples with replacement, so repeats are allowed and $n^k$ applies. Name the replacement rule before reaching for a formula.

The Quick Version

Permutations count arrangements: $P(n,k) = n!/(n-k)!$ , and order matters.
Combinations count sets: $C(n,k) = n!/(k!(n-k)!)$ , and order does not matter.
The two differ by exactly $k!$ , the reshuffles of each chosen set.
Choosing 2 of 5 gives 20 ordered pairs but only 10 sets.
Rankings and passwords keep order; teams and feature subsets divide it away.
Replacement decides whether the options shrink between picks.