Counting Principles: Addition, Multiplication & Bijection

June 2026 · 18 min read

Every advanced combinatorics technique ultimately rests on a small set of counting axioms. Before we rush into binomial coefficients or generating functions, we need rock-solid intuition for why we add counts in some situations and multiply in others. This post establishes the four cornerstones you'll use in virtually every CP counting problem.

The Addition Principle (Rule of Sum)

If task A can be done in m ways and task B in n ways, and the two tasks are mutually exclusive (you cannot do both simultaneously), then the number of ways to do "A or B" is m + n.

Example. You have 5 red balls and 3 blue balls. How many ways to pick one ball? The events "pick red" and "pick blue" are mutually exclusive, so the answer is 5 + 3 = 8.

In CP problems, the addition principle typically appears when you split a counting problem into disjoint cases. For instance: "count binary strings of length n that start with 1 or end with 0." Be careful — these two sets might overlap, which takes us into inclusion-exclusion territory (a later module). When they're disjoint, plain addition suffices.

Extending to k sets

If you partition your universe into k disjoint classes C₁, C₂, …, Cₖ, the total count is |C₁| + |C₂| + … + |Cₖ|. This "case analysis" strategy is bread-and-butter in CP:

// Count integers in [1, n] divisible by 2 or 3 but not both
// Case 1: divisible by 2 only  → n/2 - n/6
// Case 2: divisible by 3 only  → n/3 - n/6
// Total = (n/2 - n/6) + (n/3 - n/6)
long long count(long long n) {
    long long d2 = n / 2, d3 = n / 3, d6 = n / 6;
    return (d2 - d6) + (d3 - d6);
}

The Multiplication Principle (Rule of Product)

If task A can be done in m ways and — for each way of doing A — task B can be done in n ways, then doing A then B can be done in m × n ways.

The keyword is independence: the number of choices for B must not depend on which choice was made for A. (If it does, you need a more careful argument — often a sum over the A-choices.)

Multi-step decisions

This extends naturally: if you make k independent decisions with n₁, n₂, …, nₖ choices, the total outcomes are n₁ · n₂ · … · nₖ.

// How many binary strings of length n?
// Each of the n positions has 2 choices → 2^n
long long ans = 1;
for (int i = 0; i < n; i++) ans = ans * 2 % MOD;

Classic CP example — grid paths. Count lattice paths from (0,0) to (m,n) using only right and down steps. You must make m right-steps and n down-steps in some order — that's a sequence of (m+n) steps where you choose m of them to be "right". Answer: C(m+n, m). But why? Because at each of (m+n) positions you independently decide the direction — almost. The constraint that exactly m must be right means we actually need combinations (Post 3), but the multiplication principle tells us without constraint there would be 2^(m+n) paths.

Complementary Counting

Sometimes counting what you want directly is hard, but counting what you don't want is easy. If U is the universe of all outcomes and B is the "bad" set:

|Good| = |U| − |Bad|

Example. Count binary strings of length n that contain at least one '1'.

• Universe: all binary strings of length n → 2ⁿ
• Bad: strings with no '1' → exactly 1 (the all-zero string)
• Answer: 2ⁿ − 1

// Strings of length n over {a..z} with at least one vowel
// Universe = 26^n, Bad = 21^n (consonants only)
long long power(long long b, long long e, long long mod) {
    long long r = 1; b %= mod;
    while (e > 0) {
        if (e & 1) r = r * b % mod;
        b = b * b % mod; e >>= 1;
    }
    return r;
}
long long solve(int n) {
    const long long MOD = 1e9 + 7;
    return (power(26, n, MOD) - power(21, n, MOD) + MOD) % MOD;
}

When to use complementary counting

Use it whenever the problem says "at least one," "not all the same," or any condition whose negation is simpler. Common patterns:

• "At least one element is X" → total minus "no element is X"
• "Not all elements are equal" → total minus "all elements equal"
• "At least two of the same" → total minus "all distinct"

The Bijection Principle

If you can establish a one-to-one correspondence (bijection) between set A and set B, then |A| = |B|. This lets you replace a hard counting problem with an easier equivalent one.

Classic bijections

• Binary strings ↔ Subsets. A binary string of length n corresponds to a subset of {1, …, n}. Bit i is 1 iff element i is in the subset. Both have 2ⁿ elements.
• Grid paths ↔ Sequences. A path from (0,0) to (m,n) using R and D steps corresponds to a binary string of length (m+n) with exactly m ones.
• Parenthesisations ↔ Catalan structures. Valid bracket sequences, binary trees, polygon triangulations, and Dyck paths are all counted by the Catalan numbers — because bijections exist between all these sets.

// Bijection: subsets of {0..n-1} ↔ integers in [0, 2^n - 1]
// Enumerate all subsets using bitmask
for (int mask = 0; mask < (1 << n); mask++) {
    // mask encodes a unique subset
    for (int i = 0; i < n; i++) {
        if (mask >> i & 1) {
            // element i is in this subset
        }
    }
}

Building a bijection argument

To prove that two sets have the same size via bijection:

1. Define a mapping f : A → B.
2. Show f is injective (no two elements of A map to the same element of B).
3. Show f is surjective (every element of B is hit by some element of A).

In contest settings, you usually just describe the mapping clearly and argue informally that it's reversible.

Common Patterns in Competitive Programming

Let's see how these four principles combine in real contest scenarios.

Pattern 1: Counting strings with constraints

Problem. Count strings of length n over {a, b, c} that do not contain "aa" as a substring.

Direct counting with the multiplication principle is tricky because choices are not independent (picking 'a' at position i restricts position i+1). Instead, use a DP recurrence — which is just a structured application of the addition principle over cases:

// dp[i][0] = strings of length i not ending in 'a'
// dp[i][1] = strings of length i ending in 'a'
const int MOD = 1e9 + 7;
long long dp[200001][2];

long long solve(int n) {
    dp[1][0] = 2;  // 'b' or 'c'
    dp[1][1] = 1;  // 'a'
    for (int i = 2; i <= n; i++) {
        dp[i][0] = (dp[i-1][0] + dp[i-1][1]) * 2 % MOD;
        dp[i][1] = dp[i-1][0];  // can only append 'a' after non-'a'
    }
    return (dp[n][0] + dp[n][1]) % MOD;
}

Pattern 2: Counting with overlaps (Inclusion-Exclusion preview)

When sets are not disjoint, the plain addition rule over-counts. For two sets: |A ∪ B| = |A| + |B| − |A ∩ B|. We'll cover the general inclusion-exclusion formula in a later post, but keep this in mind as a natural extension of the addition principle.

Pattern 3: Double counting

Count the same quantity in two different ways to derive an identity or solve a problem. For example, the number of edges in a graph equals ½ Σ deg(v) — counting each edge once from each endpoint.

Practice Problems

Solidify your understanding with these problems, arranged from easier to harder:

1. Codeforces 1462A — Favorite Sequence. A warm-up that uses basic counting and constructive ideas.
2. Codeforces 1312C — Adding Powers of Two. Think in terms of binary representation (bijection with subsets of powers).
3. Codeforces 1569C — Jury Meeting. Complementary counting: total orderings minus bad ones.
4. Codeforces 1353E — K-periodic Garland. DP-based counting with case analysis (addition principle in each transition).
5. AtCoder ABC 215 D — Coprime 2. Use complementary counting over prime factors.
6. Codeforces 1475F — Unusual Matrix. Bijection: the problem reduces to a much simpler check after reframing.

Challenge exercise

Problem. A password is a string of length 8 over digits and lowercase letters (36 chars). How many passwords contain at least one digit and at least one letter?

Compute this modulo 10⁹+7 to get your answer. This is a direct application of complementary counting combined with inclusion-exclusion for two sets.