15. Combinatorics & Counting

Level: Intermediate You'll use this for: password/keyspace sizing, hash collision estimation, and any "how many possible X" question.

Permutations vs. combinations

• Permutations (order matters): arranging n items in n! ways; choosing k ordered items from n: P(n,k) = n!/(n-k)!
• Combinations (order doesn't matter): choosing k unordered items from n: C(n,k) = n!/(k!(n-k)!)

from math import factorial, comb, perm
perm(10, 3)   # 720  -- ordered arrangements of 3 from 10
comb(10, 3)   # 120  -- unordered groups of 3 from 10

Where P(n,k) and C(n,k) actually come from

Permutations, built from the fundamental counting principle. To arrange 3 items chosen (in order) from 10: the 1st pick has 10 options, the 2nd pick has 9 remaining, the 3rd has 8 remaining — multiply:

P(10,3) = 10 × 9 × 8 = 720

Written as factorials, this is "10! but stop after 3 terms," which is
exactly what dividing by the leftover tail (7!) achieves:
  10! / 7!  =  (10×9×8×7×6×5×4×3×2×1) / (7×6×5×4×3×2×1)  =  10×9×8  =  720
  and 7 = 10 - 3, so this is P(n,k) = n! / (n-k)!

Combinations = permutations, with duplicate orderings divided back out. C(10,3) counts the same picks as P(10,3), but treats {A,B,C} and {B,A,C} etc. as the same group. Each group of 3 can be internally reordered 3! = 6 ways, so every distinct group got counted 6 times over in P(10,3):

C(10,3) = P(10,3) / 3! = 720 / 6 = 120
        = n! / (n-k)! / k! = n! / (k!(n-k)!)     <- matches the formula above

That's the whole derivation: combinations are permutations with the "which order" duplicates divided away.

def keyspace(alphabet_size, length):
    return alphabet_size ** length

lower_only = keyspace(26, 8)          # 26^8 ≈ 2.09 * 10^11
mixed_case_digits_symbols = keyspace(95, 12)  # 95^12 ≈ 5.4 * 10^23

The pigeonhole principle

If you put n+1 items into n boxes, at least one box holds 2+ items. Trivial-sounding, but it's the proof that hash collisions are mathematically guaranteed once you hash more items than the output space size — a hash function mapping an unbounded input space to a fixed-size (say, 256-bit) output space must have collisions somewhere; the only question is how hard they are to find (Ch. 26's birthday paradox sharpens this into a concrete number).

Real-life engineering ties

• SWE: estimating combinatorial test-case explosion, counting valid states in a state machine.
• AI: hyperparameter search space sizing (grid search over k parameters, each with m values, is m^k combinations — the combinatorial explosion that justifies random/Bayesian search instead).
• Network: counting possible subnet allocations, VLAN ID space (12-bit VLAN tags = 2^12 = 4096 possible VLANs, a real capacity limit).
• Security: keyspace-size calculations underlie every brute-force time estimate (Ch. 26); counting attack paths through a system (attack-graph enumeration) is a permutations/combinations problem.

More real-life examples:

• Lottery odds (e.g., choosing 6 numbers from 49) are a pure C(n,k) combinations calculation — a concrete, intuitive way to build number sense for the same formula used in password-keyspace reasoning.
• QA teams facing combinatorial explosion in configuration testing (e.g., 5 browsers x 4 OSes x 3 screen sizes = thousands of combinations) use pairwise (combinatorial) testing, which mathematically guarantees covering all pairs of parameter values with far fewer test cases than the full combinatorial product.
• API key and session token generators size their random identifier space (e.g., 128-bit UUIDs) using the same pigeonhole/collision reasoning as password entropy, making accidental collisions between two independently generated tokens astronomically unlikely.
• NIST's 2017 password guidance (SP 800-63B) explicitly moved away from complexity rules (mandatory symbols/digits) toward length-based entropy reasoning, citing exactly the "complexity rules reduce real entropy" effect covered in Ch. 23's common mistake.

Common mistake

Confusing "order matters" (permutation) with "order doesn't matter" (combination) — e.g., a 4-digit PIN is a permutation problem (order matters: 1234 ≠ 4321, and repeats are allowed: 10^4), while "choose 4 servers out of 10 to take offline for maintenance" is a combination problem.