Counting

A proof-oriented treatment of sum, product, bijection, complement, and inclusion–exclusion counting strategies.

A counting structure records choices once so cases are neither missed nor repeated. A branching choice tree ends in distinct outcomes. Following one path records one complete sequence of choices, which helps prevent omissions and duplicate cases.

Precise definition

Counting determines the cardinality $|S|$ of a finite set without necessarily listing every element. If disjoint alternatives have sizes $a$ and $b$, the sum rule gives $a+b$ choices. If a process makes successive independent-in-the-counting-sense choices with $a$ and $b$ options for every first choice, the product rule gives $ab$ outcomes.

Notation and mathematical language

Use $|A|$ for cardinality, $A^c$ for a complement relative to a stated universe, $n!$ for $n(n-1)\cdots1$, $P(n,r)=n!/(n-r)!$, and $\binom nr=n!/[r!(n-r)!]$. Inclusion–exclusion begins $|A\cup B|=|A|+|B|-|A\cap B|$.

Conceptual picture

A counting argument succeeds when each valid object is represented exactly once. A decision tree visualizes the product rule; disjoint boxes visualize the sum rule; a bijection transfers a count from a difficult set to an easier set of the same size. Complement counting replaces 'at least one' with total minus 'none'.

Fully worked example

Interpretation and application

Counting supports probability denominators, password-space estimates, resource allocation, and combinatorial proofs. A large nominal password space does not alone establish security: user behaviour and attack models matter, but the count still gives a precise upper limit on possible strings under stated rules.