Discrete Math and Proof

Counting and combinatorics

How many ways: permutations and combinations

~11 minLesson 13 of 19Written by Claude Opus 4.8

A café offers 5 breads, 4 fillings, and 3 sauces. How many sandwiches are possible? You could write them all out - or you could multiply: $5 \times 4 \times 3 = 60$ . Combinatorics is the discipline of finding the size of a set without ever building the set. It is where probability finds its denominators, and where algorithms meet their worst case: the very same $n!$ and $2^{n}$ that look tidy on paper are exactly what make brute force impossible in practice.

The one-line idea

Counting is multiplication and addition in disguise. Whenever something is built by a sequence of independent choices, the option counts multiply. Whenever it falls into one of several mutually exclusive cases, the counts add. Almost every formula in this lesson is those two rules applied until the pattern earns a name.

Two rules that generate everything

The rule of product. If a task is a sequence of $k$ independent stages, and stage $i$ can be done in $n_{i}$ ways regardless of the earlier choices, then the number of ways to do the whole task is the product:

total = n_{1} \times n_{2} \times \dots \times n_{k} .

The sandwich is three independent stages, so $5 \times 4 \times 3 = 60$ . A 4-character password over a 26-letter alphabet is $2 6^{4}$ . The key word is independent: choosing the bread must not shrink your filling options, or the clean product breaks.

The rule of sum. If the possibilities split into cases that never overlap, you add the cases. With $A$ and $B$ disjoint, $∣ A \cup B ∣ = ∣ A ∣ + ∣ B ∣$ . A committee that is "a math major or a physics major" (no double majors) has $∣ math ∣ + ∣ physics ∣$ candidates. Product builds one thing from many parts; sum picks one option among alternatives.

Order matters, or it doesn't

Everything specializes from one question: when you pick items, does their order count as different?

Start with arranging all $n$ distinct items in a row. The first slot has $n$ choices, the next $n - 1$ , and so on down to $1$ - the rule of product gives the factorial:

n! = n \cdot (n - 1) \cdot (n - 2) \dots 2 \cdot 1, 0! = 1.

Now pick only $k$ of the $n$ and keep them in order. You stop the product after $k$ factors, which is a permutation:

P (n, k) = n (n - 1) \dots (n - k + 1) = \frac{n !}{( n - k )!} .

If order does not matter - a set, not a sequence - then every group of $k$ items has been counted $k!$ times, once per ordering. Divide it out to get the combination, read " $n$ choose $k$ ":

(k n) = \frac{n !}{k ! ( n - k )!}, so P (n, k) = (k n) \cdot k! .

That last equation is the whole relationship: arranging = choosing, then ordering. The machine below makes it physical. Pick $n$ and $k$ , toggle whether order matters, and press Count: it reveals every valid output one at a time, and the running tally lands exactly on the formula.

Choose-vs-arrange machine. Toggle order, then press Count.

n =4k =2

pool of n =ABCD

Unordered - selectionsC(4, 2)

C(4, 2) = 4!2! (4−2)!=242 · 2= 6

each set has 2! = 2 orderings → ordered would be 6 × 2 = 12

counted 6 of 6 outputs

ABACADBCBDCD

Each tile is one valid output. Unordered lists every distinct set; Ordered expands each set into all k! of its orderings - one group per row. Watch the ordered count be exactly k! times the unordered one.

The aha: ordering is a multiplier of exactly k!

Toggle between the two modes with

n = 4, k = 2

and the grid stops hiding it: 6 unordered selections, 12 ordered arrangements - every set of two split into its

2! = 2

orderings. That is why

(k n)

P (n, k)

with the

k!

divided back out. Combinations are permutations that forgot their order. Once you see the

k!

factor, you never again confuse "how many teams" (a combination) with "how many finishing orders" (a permutation).

The same three counts, in code

from math import factorial, comb, perm
from itertools import permutations, combinations

n, k = 5, 2
perm(n, k)      # 20  -> ordered:   n! / (n-k)!
comb(n, k)      # 10  -> unordered: n! / (k!(n-k)!)
comb(n, k) * factorial(k) == perm(n, k)   # True  -> P = C * k!

list(combinations("ABCDE", 2))   # 10 sets:  AB AC AD ... DE
list(permutations("ABCDE", 2))   # 20 ordered pairs: AB BA AC CA ...

The same three counts, in code

Pascal's triangle and the binomial theorem

The combinations obey one beautiful recurrence. To pick $k$ items from $n$ , fix your eye on the last item: either you take it (now pick $k - 1$ from the remaining $n - 1$ ) or you leave it (pick all $k$ from the other $n - 1$ ). Those two cases are disjoint, so by the rule of sum:

(k n) = (k - 1 n - 1) + (k n - 1) .

Stack the $(k n)$ in a pyramid and that identity says every number is the sum of the two directly above it. That is Pascal's triangle. Click any cell below to see the two parents that add up to it - and read off, at the edge of each row, that it always begins and ends with $(0 n) = (n n) = 1$ .

Pascal's triangle. Click a number to see its two parents.

Click any number. Each interior one is the sum of the two above it - that is the identity C(n,k) = C(n−1,k−1) + C(n−1,k).

Row $n$ of the triangle is more than pretty. Those numbers are exactly the coefficients when you expand a binomial to the $n$ -th power - the binomial theorem:

(a + b)^{n} = k = 0 \sum n (k n) a^{n - k} b^{k} .

Why? Expanding $(a + b)^{n}$ means picking either $a$ or $b$ from each of the $n$ factors; the term $a^{n - k} b^{k}$ appears once for every way to choose which $k$ factors donate a $b$ - and that count is $(k n)$ . So $(a + b)^{4} = a^{4} + 4 a^{3} b + 6 a^{2} b^{2} + 4 a b^{3} + b^{4}$ , reading row 4: $1, 4, 6, 4, 1$ .

One row, and the number of subsets

Set

a = b = 1

in the binomial theorem and the left side becomes

2^{n}

while the right becomes the sum of a whole row:

k = 0 \sum n (k n) = 2^{n} .

This is a counting identity you can read two ways. A set of

n

elements has

2^{n}

subsets - each element is independently in or out, the rule of product on

n

two-way choices. Grouping those subsets by how many elements they contain gives

(0 n) + (1 n) + \dots + (n n)

. Both count the same subsets, so they must be equal. Every row of Pascal's triangle sums to a power of two.

Pigeonhole, and why brute force hits a wall

One last principle, almost insultingly simple yet startlingly powerful. The pigeonhole principle: if you place $n$ items into $m$ boxes and $n > m$ , then some box holds at least two items. More sharply, some box holds at least $⌈ n / m ⌉$ of them. It sounds trivial, but it proves that any two of the 8+ million people in New York share a birthday-count pattern, that any lossless compressor must expand some inputs, and that a hash table with more keys than buckets must collide.

Combinatorics is also the bearer of bad news. The counts we built don't just grow - they explode. Arranging $n$ things is $n!$ ways; considering every subset is $2^{n}$ . At $n = 20$ that is already $2.4 \times 1 0^{18}$ permutations. This is the exact reason brute force is a trap, and the reason whole fields of algorithms exist to avoid enumerating what combinatorics counts.

Growth you cannot outrun with hardware

n!

and

2^{n}

outpace every polynomial and shrug off faster chips. Doubling your computer's speed lets a

2^{n}

search handle exactly one more item; an

n!

search, often less than that. That is why "just try all of them" fails past small

n

, and why the interesting question is never "can we enumerate?" but "can we avoid enumerating?" - the driving question of the next several lessons.

Check yourself

You line up 3 of 5 books on a shelf; swapping two books makes a different lineup. This is counted by:

How many 2-person teams can be formed from 5 people, where order within a team does not matter?

State n!, P(n,k), and C(n,k) - and how the two selection counts relate.

Try to state it, then check.

Lock it in

Counting is multiplication and addition in disguise: a sequence of independent choices multiplies (rule of product), mutually exclusive cases add (rule of sum).
Arranging all $n$ items is $n!$ ; ordered picks are $P (n, k) = \frac{n !}{( n - k )!}$ ; unordered picks are $(k n) = \frac{n !}{k ! ( n - k )!}$ , related by $P (n, k) = (k n) \cdot k!$ .
Pascal's recurrence $(k n) = (k - 1 n - 1) + (k n - 1)$ builds the triangle, whose row $n$ holds the binomial coefficients and sums to $2^{n}$ - the number of subsets of an $n$ -element set.
The pigeonhole principle: put $n$ items in $m$ boxes with $n > m$ and some box holds at least $⌈ n / m ⌉$ of them.
$n!$ and $2^{n}$ outgrow every polynomial and shrug off faster hardware - the exact reason brute force is a trap. Reach for combinations when order is ignored, permutations when it counts.

Primary source

For the rigorous version - proofs, bijective counting, and the sum/product rules built from set theory - work through the counting unit of MIT's 6.042J Mathematics for Computer Science (Fall 2010), the canonical discrete-math course for programmers. For intuition-first practice with permutations and combinations, drill Khan Academy's Counting, permutations, and combinations unit.

Ask your teacher

Combinatorics is precisely why brute force explodes. Trying every ordering of

n

items is

n!

work - the wall that backtracking (Lesson 44) spends its whole life pruning - and trying every subset is

2^{n}

, the combinatorial heart of why P vs NP (Lesson 101) is hard: a verifier checks one certificate in polynomial time, yet a blind search may face

2^{n}

of them. The same counts run straight through machine learning (Lesson 60), where a probability is a favorable-count divided by a total-count - and those counts are the binomials you just built. Ask me why

n!

eventually dwarfs

2^{n}

, how Stirling's approximation tames

n!

, or how counting subsets connects to entropy and information.