Counting Principle

Precise definition

The fundamental counting principle says: if a process has stages with $n_1,n_2,\ldots,n_k$ choices and every choice at one stage leaves the stated number of choices at the next, then there are $n_1n_2\cdots n_k$ outcomes. Disjoint alternative cases are added rather than multiplied.

Notation and mathematical language

An outcome must be defined precisely enough to decide whether order and repetition matter. A tree diagram represents branches; the number of leaves is the count. If later options depend on earlier choices, use branch-specific products and add the terminal counts.

Conceptual picture

Multiplication counts ordered sequences of compatible choices. Each valid outcome must correspond to exactly one route through the stages. This one-to-one requirement prevents both omissions and double counting.

Conditions and key results

The method does not assume probabilistic independence; it is a combinatorial statement about numbers of continuations. In probability, dividing favourable counts by total counts additionally requires equally likely elementary outcomes.

A reliable strategy

1. Describe one complete outcome and decide order, repetition, and restrictions.
2. Break its construction into stages and count legal choices after each possible earlier choice.
3. Multiply along a branch and add genuinely disjoint branches.
4. Check by listing a small analogue or constructing a reversible encoding of counted outcomes.

Fully worked example

Interpretation and application

Counting principles build sample spaces for codes, schedules, genetics, and surveys. A uniform probability model must be justified; counting alone does not make real-world categories equally likely.

Common mistakes

Verification and reasonableness

• List outcomes for a shorter code or smaller digit set.
• Verify each object maps to exactly one counted branch.
• Check that adding a restriction does not increase the count.

Practice

1. How many outfits use 4 shirts and 3 pants?
2. How many length-4 binary strings?
3. Does multiplication require probabilistic independence?

Further deduction

Complement counting is often shorter. To count length-$n$ strings over an alphabet of size $m$ that use at least one special symbol, subtract strings avoiding it: $m^n-(m-1)^n$. The total and complement must be built from the same outcome space. This avoids overlapping cases based on the first or second occurrence.

When repetitions are forbidden, continuation counts decrease: arranging $r$ distinct objects selected from $n$ gives $n(n-1)\cdots(n-r+1)=n!/(n-r)!$. If order is later ignored, every selected subset has $r!$ arrangements, so dividing yields $\binom nr$. These formulas derive from the staged principle rather than replace it.

A decision tree is a proof device when every root-to-leaf path represents exactly one outcome. If later choices depend on earlier ones, branches can have unequal sizes and the simple product of constant counts no longer applies globally; sum the leaf counts or partition into cases with constant continuation counts. Labeling paths also reveals whether two construction histories represent the same final object, the key question before dividing by a symmetry factor.

Related topics

• Fundamental Counting Principle
• Permutations
• Combinations