Skip to main content

Counting by Structure, Not by Guessing

What This Concept Is​

Combinatorial counting is not "plug numbers into a formula you remember." It is the act of describing a finite set so precisely that the number of its elements becomes forced. The formula is a consequence of the description. If the description is imprecise or silently ambiguous, no formula can rescue it.

The most common structural moves are:

  • product rule: build an object step by step through independent choices. If step $i$ has $n_i$ options and the steps do not interfere, the total is $\prod_i n_i$.
  • sum rule: split the target set into disjoint cases and add. If cases overlap, naive addition fails and must be repaired (see inclusion-exclusion).
  • division rule: count a larger representation and quotient by overcounting symmetry. If every object appears exactly $k$ times in the larger count, the true count is (larger) $/ k$.
  • bijection: count a difficult set by matching it exactly to an easier one. A correspondence is valid only when it is both injective and surjective.

The point is not the formula. The point is the model: naming the set, naming the equivalence, naming the construction. You should be able to hand another person your model and have them reconstruct the count without being told which formula to invoke.

This module treats counting as a discipline of set specification. Every later technique -- binomial identities, inclusion-exclusion, stars and bars, generating functions, graph proofs -- refines one of these four moves.

There is a deeper principle hiding here, often credited to Gian-Carlo Rota: "a counting problem is a set together with an equivalence relation." When the equivalence is trivial (every object is its own class), you are in pure product-rule territory. When equivalence classes have equal size $k$, division applies. When classes differ in size, neither addition nor division works -- you must either split cases or find a weighted counting argument (which generating functions will formalize in cluster 3). Recognizing which regime you are in is the entire game.

Why It Matters Here​

Every later counting technique in this module is a refinement of these four moves. Inclusion-exclusion is a repair for non-disjoint sums. Stars and bars is a bijection. Generating functions encode repeated product-rule choices. Graph proofs often become counting arguments by reinterpreting edges, paths, or degrees.

Downstream the pipeline: Semester 2's algorithm analysis depends on counting paths, subproblems, and branches; Semester 3's data-structure reasoning depends on counting nodes, keys, and comparisons; Semester 4's database work uses counting to reason about cardinality estimation and join selectivity; Semester 5's concurrency literature counts interleavings.

If the structural setup is wrong, the arithmetic being correct does not save you. A precise count off the wrong set is just confidently wrong.

This module also conditions you for estimation discipline. Even when an exact count is out of reach, a correct structural model yields tight upper and lower bounds. "Every object belongs to at least one class of size $\le M$" and "every class has size $\ge m$" together pin the total to within a factor of $M/m$ -- often good enough for algorithm-analysis order-of-magnitude work in Semester 2.

Concrete Examples​

Example 1. How many length-$5$ passwords over ${a, b, c, d}$ contain exactly two as?

Do not start with a memorized formula. Start with structure:

  1. choose the two positions occupied by a: $\binom{5}{2}$ ways.
  2. fill the remaining three positions with any non-a letter: $3$ choices each, so $3^3$.

The two stages are independent once the positions are fixed, so the product rule applies:

$$\binom{5}{2} \cdot 3^3 = 10 \cdot 27 = 270.$$

The formula appears because the model is correct, not the other way around.

Example 2. How many ways are there to seat $6$ distinguishable people around a round table, where rotations are considered the same arrangement?

Naively, $6!$ orderings. But each circular arrangement corresponds to $6$ different linear orderings (one for each starting seat). That is exact symmetry: every circular arrangement is represented exactly $6$ times. Apply the division rule:

$$\frac{6!}{6} = 5! = 120.$$

If reflections are also considered the same, divide by an additional factor of $2$, giving $60$. The key discipline: name the equivalence before computing.

Example 3: bijective counting. How many lattice paths from $(0,0)$ to $(m,n)$ using only right-steps $R$ and up-steps $U$?

Every path is a sequence of $m + n$ steps, of which exactly $m$ are $R$ and $n$ are $U$. The path is therefore uniquely determined by which positions in the sequence are $R$ (the rest are $U$). This is a bijection between lattice paths and $m$-subsets of ${1, 2, \ldots, m+n}$. By the subset count:

$$#\text{paths} = \binom{m+n}{m}.$$

No coordinate geometry required. The bijection converted a geometric question into a subset-count question. This is the move you want to practice until it is reflex.

Example 4: complementary counting. How many $5$-card poker hands (from $52$ cards) contain at least one ace?

Direct counting (by number of aces) gives four cases that must be summed. The complement is instantly easier: count hands with no ace and subtract. The set without aces lives in the $48$ non-ace cards:

$$#\text{hands with} \ge 1\text{ ace} = \binom{52}{5} - \binom{48}{5} = 2{,}598{,}960 - 1{,}712{,}304 = 886{,}656.$$

This is a typical "at least one" tell: the complement is always a single case with no overlap accounting needed.

Common Confusion / Misconceptions​

  • Mixing positions with objects. Learners often multiply by too many factors because they count the same arrangement several times under different construction orders. If the same final object can be built two ways, you have double counted.
  • Sum with overlapping cases. If your cases share objects, addition double-counts. Either refactor the cases to be disjoint, or use inclusion-exclusion to correct.
  • Division without exact symmetry. The division rule requires every object in the larger set to appear the same number of times. If some appear $k$ times and others $k'$ times, division is invalid and you must split first.
  • Treating similar objects as distinct. Counting distinct arrangements of RRB as $3! = 6$ is wrong if the two Rs are identical; the real count is $3$.
  • Silent "at least one" traps. "How many ways contain at least one X" is rarely a product-rule problem: the events at each stage are not independent. Usually you must use the complement or inclusion-exclusion.
  • Skipping the small-case sanity check. If $n = 1$ or $n = 0$ produces a nonsensical number (e.g., negative, fractional, or larger than $n!$), your model is broken. Always push the formula to the smallest case.

How To Use It​

Before computing, ask these questions in order:

  1. What exact set am I counting? Write it in words.
  2. Can I construct each object by a finite sequence of choices? (product rule candidate)
  3. Are my cases disjoint? (sum rule precondition)
  4. Am I counting each object once, or many times? (division rule candidate)
  5. Would a bijection to a simpler set make the structure clearer? (bijection candidate)
  6. Can I check my answer on a small instance by full enumeration? (sanity check)
  7. Does my answer pass a trivial upper/lower bound sanity test?

Use that checklist before touching factorials or binomial coefficients. If you skip it, you are guessing.

Two-way audit. Whenever possible, count the same set two different ways and check that the results agree. Two counts that agree are one consistency check; a single count and a formula agreeing is not. Competitive problem-solvers (Putnam, USAMO) train this reflex because it catches off-by-one errors that no amount of careful algebra will.

Transfer / Where This Shows Up Later​

  • Semester 2 algorithm analysis: runtime bounds are counting problems in disguise. The product rule counts paths through a recursion tree; the sum rule counts loop iterations split by case.
  • Semester 3 data structures: hash table load factor, BST node count, and heap levels are all counting setups. The division rule underlies amortized analysis of resized arrays.
  • Semester 4 databases: query planners estimate result sizes via counting models; selectivity estimation is a product rule on independent predicates.
  • Semester 5 concurrency: counting interleavings of $n$ threads with $k$ instructions each uses multinomial thinking (next concept). Lock-ordering proofs are bijection arguments between execution schedules.
  • Semester 6 distributed systems: failure-domain analysis counts the number of simultaneous failures a quorum survives; it is a product / bijection combination on subsets.
  • Semester 7 architecture: capacity plans count the number of distinct placement patterns for $k$ services on $n$ hosts, respecting anti-affinity; the division rule removes symmetric placements that are operationally identical.

Check Yourself​

  1. When is the product rule valid? State the independence condition formally.
  2. Why can the sum rule fail if cases overlap? Give a concrete two-set example where the overlap matters.
  3. What does the division rule correct? What has to be true for it to apply exactly?
  4. Construct a counting problem that is naturally solved by bijection rather than by product rule. Describe the target set you biject to.
  5. You count a set and get $7.5$. What mistake did you almost certainly make?
  6. Without computing, predict which of $\binom{10}{3}$ and $P(10, 3)$ is larger and by what ratio. Verify.
  7. Describe a situation where the product rule fails because the stages interfere. Give a concrete two-stage example.

Mini Drill or Application​

For each problem, name the first counting move you would try and justify it in one sentence. Then compute:

  1. Count length-$8$ binary strings.
  2. Count $4$-card poker hands (from $52$) containing at least one ace. (Hint: easier by complement.)
  3. Count circular seatings of $6$ people around a round table (rotations identical, reflections distinct).
  4. Count subsets of ${1,2,\ldots,n}$ with even size by relating them to another set (bijection).
  5. Count the number of distinct necklaces using $3$ red and $2$ blue beads, where rotations are identical.
  6. How many length-$10$ binary strings have more 1s than 0s? (Hint: use a symmetry/complement bijection with strings that have fewer 1s.)
  7. Count the number of ways to place $4$ non-attacking rooks on a $4 \times 4$ board (rooks attack in rows and columns). Confirm the model reduces to counting permutations.

Read This Only If Stuck​