Counting Principles
Reference · Counting & Combinatorics · Always free
Master the sum rule, product rule, and other fundamental counting techniques
Overview
Why Counting Matters
Combinatorics is the mathematics of counting. It answers questions like "How many passwords are possible?" or "How many ways can we schedule tasks?" These techniques are essential in computer science for analyzing algorithms, probability, and cryptography.
Definition
The Product Rule (Multiplication Principle)
If a task can be broken into a sequence of steps where step 1 can be done in n₁ ways, step 2 in n₂ ways, ..., and step k in nₖ ways, then the total number of ways to complete the task is n₁ × n₂ × ... × nₖ.
Key requirement: the number of ways for each step must be independent of the choices in previous steps.
Example
Product Rule: License Plates
A license plate has 3 letters followed by 4 digits. How many plates are possible?
Letters: 26 choices each × 3 positions = 26³ Digits: 10 choices each × 4 positions = 10⁴
Total = 26³ × 10⁴ = 17,576 × 10,000 = 175,760,000 plates.
Definition
The Sum Rule (Addition Principle)
If a task can be done in one of several mutually exclusive ways, where way 1 can be done in n₁ ways, way 2 in n₂ ways, etc., then the total number of ways is n₁ + n₂ + ... + nₖ.
Key requirement: the ways must be mutually exclusive (no overlap).
Example
Sum Rule: Choosing a Representative
A committee must choose a representative from either the math department (8 members) or the CS department (12 members). No one is in both.
Total choices = 8 + 12 = 20 people.
Definition
The Subtraction Rule (Inclusion-Exclusion)
If ways are NOT mutually exclusive, use the subtraction rule: |A ∪ B| = |A| + |B| - |A ∩ B|
This avoids double-counting elements that fall in both categories.
Example
Subtraction Rule: Bit Strings
How many 8-bit strings start with 1 or end with 00?
Start with 1: fix first bit, 7 remaining bits = 2⁷ = 128. End with 00: fix last two bits, 6 remaining bits = 2⁶ = 64. Both (start with 1 AND end with 00): 5 free bits = 2⁵ = 32.
Total = 128 + 64 - 32 = 160 strings.
Note
The Division Rule
If a task can be done in n ways, but for every way there are d identical outcomes (due to symmetry), then the number of distinct outcomes is n/d.
Example: Seating 4 people around a circular table. Linear arrangements: 4! = 24. But rotations are the same, so divide by 4: 24/4 = 6 distinct arrangements.