Combinatorics and Counting

Counting arrangements where order matters versus selections where it does not. Picking 2 letters from A, B, C gives 6 ordered pairs but only 3 unordered ones.

Picking 2 letters from A, B and C makes 6 ordered pairs but only 3 unordered pairs, because ignoring order divides the count by 2 factorial

Why Does This Exist?

A classifier with 10 labels makes a top-3 prediction list. How many such lists exist? A team picks 2 members out of 5 for a review. How many possible pairs? A password allows 4 characters from 26 letters with repetition. How large is the search space? Every one of these is a counting question, and in machine learning the answers size hypothesis spaces, normalise probabilities, and tell you whether brute force is hopeless.

Without counting you cannot do discrete probability at all. A probability like "a random pair contains A" is a ratio of two counts: favourable outcomes over total outcomes. The denominator is combinatorics. That is why this page sits before probability: probability foundations divides counts, and this page produces them.

This page covers the two rules that produce every finite count: multiplying choices along a sequence, and dividing out order when it does not matter. The full catalogue of the two formulas lives in permutations and combinations. Adding up counts term by term uses summation and product notation.

The one idea you need first

A set is a collection of distinct items, and its size is the number of items in it. Counting asks for the size of a set of outcomes: all pairs, all lists, all passwords. The multiplication principle says if step one has $m$ options and step two has $n$ options, the sequence has $m \times n$ options.

Think of It Like This

Assigning labeled chairs versus picking a team

Ten volunteers arrive and there are 3 labeled chairs in a row: chair 1, chair 2, chair 3. Filling them in order gives $10 \times 9 \times 8 = 720$ seatings, because each seated volunteer removes one option from the next chair. The labels matter: moving Ana from chair 1 to chair 3 is a different seating.

Now send the chairs away and just pick 3 volunteers for a team. The same trio chosen in any order is one team, and each team can be seated in $3 \times 2 \times 1 = 6$ ways. So the number of teams is $720 / 6 = 120$ . Picking divides out the seating arrangements.

Where the analogy stops: chairs assume every volunteer fits every chair. If some assignments are forbidden, multiply-then-divide overcounts and you must count valid assignments directly.

How It Actually Works

Two operations build every count.

Permutations count ordered arrangements. Picking $k$ items from $n$ in order gives $P(n, k) = n \times (n-1) \times \cdots \times (n-k+1)$ , which equals $n! / (n-k)!$ . Order matters: AB and BA are different outcomes. In plain words: $n!$ means the product of all integers from 1 to $n$ , so $3! = 3 \times 2 \times 1 = 6$ .

Combinations count unordered selections. Picking $k$ items from $n$ ignoring order gives $C(n, k) = P(n, k) / k!$ , also written $\binom{n}{k}$ and read " $n$ choose $k$ ". Each unordered set of $k$ items can be ordered in $k!$ ways, so dividing removes the ordering. Order does not matter: AB and BA are one outcome.

Worked example

Take the letters A, B, C and pick 2, exactly as the diagram shows.

Ordered: the first letter has 3 options and the second has 2 remaining, so $P(3, 2) = 3 \times 2 = 6$ . They are AB, BA, AC, CA, BC, CB.

Unordered: each pair can be ordered in $2! = 2$ ways, so $C(3, 2) = 6 / 2 = 3$ . They are AB, AC, BC. Each unordered pair in the right panel fuses two ordered pairs from the left.

Scale up to picking 2 from 5. Ordered: $P(5, 2) = 5 \times 4 = 20$ . Unordered: $C(5, 2) = 20 / 2! = 20 / 2 = 10$ . The same divide-by- $k!$ step turns 20 lists into 10 pairs.

Code

The point is the check: math.perm and math.comb in the standard library reproduce the hand counts, so a counting argument can be tested before it becomes a probability.

1import math2
3print(math.perm(3, 2))  # -> 64print(math.comb(3, 2))  # -> 35print(math.perm(5, 2))  # -> 206print(math.comb(5, 2))  # -> 107print(math.perm(5, 2) // math.factorial(2))  # -> 10

Six ordered pairs collapse to 3 unordered ones for 3 letters, and 20 collapse to 10 for 5 items, matching the hand computation. The last line shows the divide-by- $k!$ relationship directly.

Watch Out For

Counting ordered lists when the event ignores order

The symptom is a probability larger than 1 or a count twice as large as it should be. Someone counts $P(5, 2) = 20$ pairs and then divides a favourable count of unordered pairs by 20, mixing an ordered denominator with an unordered numerator.

Fix: decide first whether AB and BA are one outcome or two, then count numerator and denominator the same way. If the event is "the pair contains A", both counts must be unordered: 4 favourable pairs out of $C(5, 2) = 10$ , giving 0.4.

Sampling with replacement counted as without

The symptom is a password or token-sequence space far smaller than reality. With repetition allowed, each of $k$ positions has all $n$ options, giving $n^k$ . Without repetition it is $P(n, k)$ . For 4 characters from 26 letters that is $26^4 = 456{,}976$ with repetition versus $26 \times 25 \times 24 \times 23 = 358{,}800$ without.

Fix: ask whether one option can be reused before choosing a formula. Passwords, PINs, and token sequences reuse symbols, so they use $n^k$ .

The Quick Version

Ordered arrangements use $P(n, k) = n! / (n-k)!$ . AB and BA count separately.
Unordered selections use $C(n, k) = P(n, k) / k!$ . AB and BA fuse into one.
From A, B, C, picking 2 gives 6 ordered pairs and 3 unordered pairs.
Picking 2 from 5 gives 20 permutations and 10 combinations.
Probabilities divide counts, so numerator and denominator must treat order the same way.
Repetition allowed means $n^k$ , which is larger than $P(n, k)$ .