Combinatorics & Counting: The Mathematics of How Many

The multiplication principle: the rule beneath every count

Almost every counting formula in mathematics is one idea applied repeatedly: if a first choice can be made in a ways and a second, independent choice can then be made in b ways, the whole sequence of choices can happen in a·b ways. A five-course tasting menu with 4 starters, 3 soups, 5 mains, 2 desserts and 3 drinks has 4·3·5·2·3 = 360 possible orders — nobody has to write out 360 menus to know that. This is the multiplication principle, and factorials, permutations and combinations are all shortcuts for applying it many times without the bookkeeping.

Permutations: when order matters

A permutation is an ordered arrangement. Arranging all n distinct objects in a row has n choices for the first slot, n-1 for the second (one is used up), n-2 for the third, and so on down to 1 — the product is n factorial, written n!. Arranging only k of the n objects stops the product k steps early:

n! = n · (n-1) · (n-2) · … · 2 · 1        (0! = 1, by convention)

P(n,k) = n! / (n-k)!   — ordered arrangements of k items chosen from n

example: 3 medals awarded to 8 sprinters
P(8,3) = 8! / 5! = 8 · 7 · 6 = 336 possible podiums

Combinations: when order doesn't matter

A combination is an unordered selection — a committee, a hand of cards, a subset. Every group of k items can be arranged in k! different orders, so if you count ordered arrangements P(n,k) and then divide out the k! orderings you counted redundantly, you are left with the number of distinct groups:

C(n,k) = P(n,k) / k! = n! / (k! · (n-k)!)   — read "n choose k"

example: a 5-card poker hand from a 52-card deck
C(52,5) = 52! / (5! · 47!) = 2,598,960 possible hands

C(n,k) is also called a binomial coefficient, because it is exactly the coefficient of the x^k term when you expand (1+x)^n — a fact known as the binomial theorem. Stacking every C(n,k) for a fixed n in a row, and stacking every n as a new row, produces Pascal's triangle: each entry is the sum of the two entries above it, since choosing k items from n either includes one particular item (leaving C(n-1,k-1) ways to fill the rest) or excludes it (leaving C(n-1,k) ways).

Repetition, and the pigeonhole principle

Two extensions come up constantly. If choices can repeat — a 4-digit PIN, a DNA codon of 3 bases from {A,C,G,T} — the multiplication principle applies directly with no division: n^k total sequences (10,000 PINs, 4³ = 64 codons). If instead you are distributing identical items into distinct bins (say, 10 identical stickers among 4 kids), the count is a "stars and bars" combination, C(n+k-1, k-1), because you are really choosing where to place k-1 dividers among n+k-1 slots.

The pigeonhole principle is combinatorics' favourite existence proof: if you place more than n items into n bins, at least one bin holds two or more items — no formula needed, just a comparison of totals. It sounds trivial and proves surprisingly deep results, from guaranteeing two people in London share a birthday-plus-hour combination to bounding compression algorithms: you cannot losslessly compress every possible file, because there are more input files than shorter output files to map them to.

Where the count actually matters

These formulas are the arithmetic underneath probability (a probability is usually favourable-count divided by total-count), cryptographic key-space estimates, hash-collision bounds, and algorithm complexity analysis, where counting the number of possible inputs or states bounds how fast a brute-force search can possibly be. The simulation on this page lets you change n and k and watch the count explode — factorials grow so fast that C(60,30), a modestly sized committee problem, already exceeds the number of atoms in a human body.

Frequently asked questions

Try it live

Everything above runs in your browser — open Combinatorics & Counting and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.