The Combinatorics Toolbox: Counting Techniques

ABSTRACT

This module covers the operational mechanics of counting. The goal is to transform word problems into mathematical expressions by identifying the underlying constraints of the set.

The Four Fundamental Rules

The “Bread and Butter” of counting. Use these to break down complex problems into smaller parts.

• Sum Rule

  • When to use: When you have a choice between mutually exclusive tasks (OR).
  • Core Logic: If Task A has $n$ ways and Task B has $m$ ways, and they cannot happen together, total = $n+m$.

• Product Rule

  • When to use: When a procedure consists of a sequence of tasks (AND).
  • Core Logic: The fundamental counting principle; multiply the number of ways for each independent step.1

• Quotient Rule

  • When to use: When your counting method overcounts identical outcomes (Symmetry).
  • Core Logic: Total = (Total with overcounting) / (Number of times each item is repeated).

• Power Rule

  • When to use: For sequences where repetition is allowed (e.g., bit strings or passwords).
  • Core Logic: $n^k$ (choosing from $n$ items $k$ times).

Permutations & Combinations

The core logic of selection. The “Golden Rule” here is: Does order matter?

Advanced Selection Strategies

Specialized “patterns” for tricky constraints.

Arrangement & Distribution

• Anagram Counting: Using permutations of multisets to find arrangements of words with repeating letters.
• Binary Strings: Techniques for counting bit patterns (0s and 1s) under specific constraints (e.g., “no two 0s adjacent”).
• Stars and Bars: The go-to method for distributing 2$n$ identical objects into 3$k$ distinct bins.4

Logical Filters

• Inclusion Exclusion: A technique to calculate the size of the union of multiple sets by accounting for their intersections.5
  • Essential for problems involving “at least one” or “none of the following.”