Basic Counting Principles

Math for CS · Axiom Academy

The addition and multiplication principles -- the foundation of all counting The addition principle handles "either/or" situations where you make one choice from multiple categories . The key requirement: the options must be mutually exclusive . If some sections meet both morning and evening, we'd need inclusion-exclusion instead. The multiplication principle handles "and then" situations where you make a sequence of independent choices . A decision tree visualizes a counting problem by branching at each choice point. The number of leaves equals the total count. Decision trees are useful because they make the multiplication principle visible. Each level of the tree is one choice, and the branching factor at each level is the number of options for that choice. Real counting problems often require both principles. The key is identifying which applies at each step. Strings starting with 1: fix first bit, 7 remaining bits free = 2^7 = 128 Strings ending with 00: 6 free bits, last two fixed = 2^6 = 64 Strings starting with 1 AND ending with 00: 2^5 = 32 By inclusion-exclusion: 128 + 64 - 32 = 160 "Choose one from group A or group B" -- add "Choose one from group A and then one from group B" -- multiply If the choices overlap, you need inclusion-exclusion (covered later)

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