Multiplication Principle

Math for CS · Axiom Academy

Sequential choices and the product rule -- counting strings, passwords, and possibilities When you make a sequence of choices, and each choice is independent, you multiply the number of options at each step. This is equivalent to counting elements in a Cartesian product: |A_1 A_2 A_k| = |A_1| |A_2| |A_k| . Strings are one of the most natural applications of the multiplication principle. Each position in the string is an independent choice from an alphabet. Length 8: 2^8 = 256 (one byte) Length 32: 2^ 32 4.3 (IPv4 address space) Length 256: 2^ 256 1.16 10^ 77 (AES key space) Password security analysis is pure multiplication principle. Each character position is a choice from some character set. Character set: 26 lowercase + 26 uppercase + 10 digits = 62 characters Then apply inclusion-exclusion for the overlaps Many real-world identifiers follow a fixed format where different positions have different character sets. The product rule still works when later choices depend on earlier ones -- you just need to track how the count changes at each step. Second seat: 4 choices (one person already seated)

This is the written version of the interactive lesson above. See the full Math for CS course.