Counting

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'.

Conditions and key results

Before multiplying, verify that every partial choice has the stated number of continuations. Before adding, make alternatives disjoint. Permutations apply when order matters; combinations apply when only the selected subset matters. Inclusion–exclusion is required when categories overlap, because direct addition double-counts intersections.

A reliable strategy

1. Describe one valid outcome precisely and decide whether order or repetition matters.
2. Partition into disjoint cases or express the outcome as a sequence of choices.
3. Apply the sum, product, complement, bijection, or inclusion–exclusion rule with its conditions visible.
4. Check the count on a smaller version by listing outcomes and confirm no object is omitted or counted twice.

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.

Common mistakes

Verification and reasonableness

• List all outcomes for a tiny analogous case and compare with the formula.
• Reverse the construction: every counted sequence should decode to one valid object and vice versa.
• Estimate magnitude and check that adding a restriction never increases the count.

Practice

1. How many binary strings of length five exist?
2. How many three-person committees can be chosen from eight people?
3. Among 100 students, 60 study French, 45 study Spanish, and 20 study both. How many study at least one?

Further deduction

A useful identity illustrates bijective proof: $\binom nr=\binom n{n-r}$. Choosing the $r$ members of a committee uniquely determines the $n-r$ people left out, and choosing the excluded group uniquely determines the committee. This one-to-one correspondence proves equality without factorial algebra. Another diagnostic is to count the same set in two ways; agreement can prove an identity, while disagreement usually signals that one construction omits objects or represents some object more than once.

Related topics

• Pigeonhole Principle
• Set Operations
• Probability