6.1 Counting Principles: Addition, Multiplication, Inclusion-Exclusion, and the Pigeonhole Principle

"How many configurations does a system have?" sounds like simple arithmetic. The real difficulty lies in first defining what counts as a valid state, determining whether steps are independent, and identifying whether two sets of solutions overlap. If the model is wrong, no matter how fast the formula computes, it yields meaningless results.

Counting Starts with Defining Objects

An authorization system has:

• 5 roles;
• 20 resources;
• 3 operations: read, write, execute.

If each role–resource–operation combination is independently allowed or denied, there are:

5×20×3 = 300 boolean decisions
state count = 2³⁰⁰

If the product specifies that each role–resource pair must be assigned one of three predefined packages (read-only, read-write, or no permission) then the total becomes:

3^(5×20) = 3¹⁰⁰

Both numbers can be correct, depending on the model of the system state. The first step in any counting problem is always to clearly define the objects and the constraints.

Addition Principle: Summing Mutually Exclusive Options

If a task can be completed through a set of mutually exclusive options A₁,...,A_k:

|A₁ ∪ ... ∪ A_k| = |A₁| + ... + |A_k|

For example, a request might enter from one of three mutually exclusive sources:

Web entry: 120 test cases
CLI entry: 40 test cases
Scheduled task: 15 test cases

Total: 120 + 40 + 15 = 175 cases

"Mutually exclusive" must not be omitted. If the same test case could belong to both the Web and scheduled task categories, simply adding the counts would result in overcounting.

Multiplication Principle: Sequential Choices Multiplied

If constructing an object through k stages, and for every valid prefix, stage i offers the same n_i choices, then:

n₁n₂...n_k

Three independent deployment dimensions:

4 regions × 3 instance types × 2 storage backends = 24 combinations

If a region does not support a particular storage backend, the number of choices at that stage depends on prior decisions and cannot be directly 4×3×2. In such cases, choices can be categorized and summed, or the allowed pairing relationships can be enumerated instead.

The multiplication principle does not require probabilistic independence; it is a counting rule for constructing objects. For the simple product above, each prefix must have the stated number of continuations.

Complement Counting: Count All, Then Subtract the Bad Cases

A decimal string of length 8, allowing leading zeros, has 10⁸ total possibilities. The number of strings containing at least one digit 7 is:

Total - Strings with no 7
= 10⁸ - 9⁸

"At least one" is often well-suited to the complement method. While you could count directly by categorizing based on the position of the first occurrence of 7, that approach is more prone to missing cases or double-counting.

Inclusion-Exclusion Principle Correction for Overlap

For two finite sets:

|A∪B| = |A| + |B| - |A∩B|

For three sets:

|A∪B∪C| = |A| + |B| + |C|
         - |A∩B| - |A∩C| - |B∩C|
         + |A∩B∩C|

When we initially add the individual sets, elements that belong to two sets are counted twice. After subtracting the pairwise intersections, elements in all three sets are subtracted too many times, so we must add them back.

Example: Counting integers from 1 to 100 divisible by 2 or 5:

⌊100/2⌋ + ⌊100/5⌋ - ⌊100/10⌋
= 50 + 20 - 10
= 60

The complexity of inclusion-exclusion grows rapidly with the number of sets. When the constraints have a special structure, dynamic programming, generating functions, or specialized solvers may be more appropriate.

Division Principle: Each object is counted equally multiple times

If a counting process counts each target object exactly k times, for a positive integer k, then:

Target count = process count / k

Selecting an unordered pair of 2 people from n individuals. Choosing the first person and then the second person gives n(n-1) possibilities, but each pair {a,b} is counted once by (a,b) and once by (b,a):

n(n-1)/2

Division is only valid when each target object is exactly repeated k times; if the repetitions are uneven, simple division would be incorrect.

Double Counting: Counting the Same Set from Two Directions

In a meeting, count all handshake events. If the number of handshakes made by person i is d_i:

Σ d_i = 2|E|

The left side counts by participants, so each handshake appears once at each endpoint. The right side counts events, each contributing 2. This is the Handshake Theorem, which will reappear in the chapter on graph theory.

Double counting is often used to prove identities. Choose a set of objects and count them in two different ways. The results must be equal.

The Pigeonhole Principle: Insufficient Capacity Guarantees Collision

If N≥0 objects are placed into k≥1 boxes, at least one box must contain:

⌈N/k⌉

objects.

Example: A hash function mapping more than 2⁶⁴ distinct inputs to a 64-bit output will necessarily produce a collision. The pigeonhole principle only proves that a collision exists; it does not indicate how easily such a collision can be found, nor does it imply that the hash function is insecure. Security concerns also depend on the computational cost of collision search and the specific attack model.

“Among 366 people, at least two share a birthday” requires a model with only 365 dates. Including February 29 raises the guaranteed threshold to 367. This compares month and day, not birth year; high probability and logical certainty are different conclusions.

Software state space cannot be measured solely by parameter count

Three parameters:

browser ∈ {Chrome, Firefox, Safari}
auth ∈ {password, passkey}
region ∈ {CN, EU, US}

The unconstrained Cartesian product yields:

3×2×3 = 18

Suppose this example product’s deployment policy excludes the single combination Safari/passkey/CN and permits all others. Then 18−1=17 states are valid. This is a sample product rule, checked here by Python 3 standard-library enumeration:

from itertools import product

states = list(product(("Chrome", "Firefox", "Safari"),
                      ("password", "passkey"), ("CN", "EU", "US")))
def allowed(state):
    return state != ("Safari", "passkey", "CN")

valid = [state for state in states if allowed(state)]
print(len(states), len(valid))  # 18 17
print(sum(i % 2 == 0 or i % 5 == 0 for i in range(1, 101)))  # 60

Test design must also distinguish:

• Whether a configuration is reachable;
• Whether different configurations exhibit equivalent behavior;
• Whether state transition paths are within the coverage objective;
• Whether concurrent scheduling introduces new ordering spaces.

Counting provides scale, not an automatically valid test suite.

Completion Check

1. Calculate the number of alphanumeric strings of length 6 that contain at least one uppercase letter, and specify the character set;
2. Use the inclusion-exclusion principle to compute how many numbers between 1 and 500 are divisible by 3 or 7;
3. Prove that among any 13 integers, at least two are congruent modulo 12;
4. List all constraints for a three-dimensional configuration matrix, then compute the number of reachable states;
5. Provide an example of a dependency selection where a direct multiplication approach would lead to an error.

References

• MIT Mathematics for Computer Science