Skip to content
LearnMathora

Discrete mathematics · 02 · Numbers too big to list · 8 min

The art of counting

How many possible passwords? Poker hands? Tournament brackets? Listing them would outlast the universe — yet three counting principles deliver exact answers in seconds. Combinatorics is counting, weaponized.

Build the intuition

Multiply independent choices

Three shirts, four pants: 12 outfits — choices multiply. An 8-character password from 62 symbols: 62⁸ ≈ 218 trillion. The multiplication principle is one line of arithmetic that routinely produces numbers beyond imagination — and it's why each added password character matters so much.

628≈2.18×101462^8 \approx 2.18 \times 10^{14}

Order matters… or it doesn't

Arranging 5 books on a shelf: 5! = 120 ways (permutations — order counts). Choosing 2 of 5 books to pack: just 10 ways (combinations — order irrelevant). The “choose” formula divides out the redundant orderings. Asking “does order matter?” first is 90% of getting counting problems right.

(nk)=n!k!(n−k)!\binom{n}{k} = \frac{n!}{k!(n-k)!}

Pascal's triangle: counting's family tree

Stack the “n choose k” numbers and each is the sum of the two above — because choosing k from n splits into “took the last item or didn't.” The triangle links counting to algebra (binomial expansions) and probability (coin-flip distributions) — and its rows already silhouette the bell curve.

See it move

InteractiveCounting without listing

number of heads k

6
With 6 coin flips there are 64 possible sequences (2 choices, 6 times: 2^6). The bars count how many land exactly k heads — Pascal's triangle, row 6, and already the outline of a bell curve.

Each bar counts the ways to land exactly k heads in n flips — a Pascal's triangle row, already curving into a bell.

A worked example

Why lottery odds are what they are

  1. Pick 6 numbers from 49. Order doesn't matter — combinations:

  2. Count the tickets:

    (496)=49!6! 43!=13,983,816\binom{49}{6} = \frac{49!}{6!\,43!} = 13{,}983{,}816

  3. One ticket: a 1-in-14-million chance. You're ~50× more likely to be struck by lightning this year. The formula is the consumer warning.

Out in the world

Password policy is combinatorics

Adding one character to a password multiplies the search space by ~62; adding symbols multiplies the base. Security teams literally compute attacker-years via these counts. “Longer beats clever” is a theorem of the multiplication principle.

Common confusion, cleared

“Permutations and combinations are interchangeable.”

Permutations count arrangements (order matters), combinations count selections (it doesn't) — and they differ by a factor of k!, which is enormous. One question separates them: would reshuffling produce a “different” outcome?

“Big counts need big formulas.”

Three principles — multiply choices, arrange (n!), choose (n choose k) — cover a staggering share of problems. Hard counting is mostly careful decomposition into these.

Recap

  • Independent choices multiply — and explode fast.
  • Order matters → permutations (n!); order doesn't → combinations (n choose k).
  • Pascal's triangle organizes the counts and previews probability.