16. The sum and product rules

Combinatorics is the science of counting: computing the number of possibilities without having to list them one by one. At OSN it appears as direct math problems, and as part of programming problems whose answer is too large to compute with a loop.

Two rules are the foundation of everything.

The sum rule

If a choice can be made in a ways or in b ways, and the two groups do not overlap, then there are a + b ways in total.

The key word is or, and the condition is no overlap.

Example: on the table there are 3 kinds of cake and 4 kinds of fried snacks. If Budi takes one food item, there are 3 + 4 = 7 choices.

The product rule

If an activity consists of two steps, the first step can be done in a ways and the second step in b ways (whatever the result of the first step), then there are a × b ways in total.

The key word is and, and the condition is that the number of ways for the second step does not depend on the choice made in the first step.

Example: Budi takes one cake and one fried snack: 3 × 4 = 12 pairs.

The tree diagram shows why the results are multiplied: every first branch splits again into as many branches as there are second choices.

                 pick a cake
        /            |            \
    cake A        cake B        cake C
    / | | \      / | | \       / | | \
   g1 g2 g3 g4  g1 g2 g3 g4   g1 g2 g3 g4

There are 3 branches at the first level, each producing 4 branches, so there are 3 × 4 = 12 leaves.

The most common mistake with these two rules is not miscounting, but picking the wrong rule. One question decides it:

Am I choosing one among several groups (sum), or taking one from each group (product)?

Combining the two

A license plate consists of one letter (A–Z) followed by three digits (0–9), and digits may repeat. How many plates are there?

26 × 10 × 10 × 10 = 26,000.

What if digits may not repeat?

26 × 10 × 9 × 8 = 18,720. After one digit is used, the next choices decrease — this is the early form of permutations (Chapter 17).

How many passwords of length 4 from lowercase letters a–z must contain at least one letter a?

Here it is easier to count the opposite:

• all passwords: 26⁴ = 456,976
• those that do not contain a at all: 25⁴ = 390,625
• the answer: 456,976 − 390,625 = 66,351

This technique is called the complement, and it is used very often: counting "at least one" is almost always easier through "none at all".

The reason counting directly is harder: "at least one a" means there can be one a, two, three, or four — four groups that have to be counted and then added, and those groups easily overlap if you are not careful. Whereas "no a at all" is only one computation: every position freely chooses from 25 letters.

A small example that can be checked by hand: passwords of length 3 from the 4 letters a b c d, at least one a. In total 4³ = 64, those without a 3³ = 27, so the answer is 64 − 27 = 37. Listing all thirty-seven words directly one by one can be done, but takes much longer — and for length 10 it is already impossible.

Other forms that also use the complement:

When the groups overlap

The sum rule is only valid when the two groups have no members in common. If they overlap, what is used is inclusion-exclusion:

|A ∪ B| = |A| + |B| − |A ∩ B|

Example: of the numbers 1 to 100, how many are divisible by 3 or 5?

• divisible by 3: ⌊100/3⌋ = 33
• divisible by 5: ⌊100/5⌋ = 20
• divisible by 15 (both): ⌊100/15⌋ = 6
• the answer: 33 + 20 − 6 = 47

Without subtracting the intersection, numbers like 15, 30, and 45 are counted twice.

Two things need to be understood from that computation. First, the number of numbers from 1 to n divisible by p is n / p with integer division — exactly the / operation in C++ for positive numbers, with no loop needed. Second, the intersection "divisible by 3 and divisible by 5" is not 3 × 5 in every case, but their LCM (Chapter 15). For 3 and 5 it happens to be the same because they are coprime, but for 4 and 6 the intersection is the multiples of 12, not 24.

For three sets, the pattern continues:

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

The signs alternate: single terms are added, pairwise terms are subtracted, triple terms are added again. The reason can be traced on one number that is in all three sets at once: it is counted 3 times by the single terms, subtracted 3 times by the pairwise terms, then added 1 time by the triple term — a total of 1, exactly as it should be.

Example: from 1 to 100, how many are divisible by 2, 3, or 5?

50 + 33 + 20 − 16 − 10 − 6 + 3 = 74

with 16 = ⌊100/6⌋, 10 = ⌊100/10⌋, 6 = ⌊100/15⌋, and 3 = ⌊100/30⌋.

Checking counts with a program

This is the habit that sets careful contestants apart: every combinatorics formula can be tested with an enumerating program for small cases.

// formula: 26 * 10 * 9 * 8
long long rumus = 26LL * 10 * 9 * 8;

// direct enumeration
long long cacah = 0;
for (int h = 0; h < 26; h++)
    for (int a = 0; a < 10; a++)
        for (int b = 0; b < 10; b++)
            for (int c = 0; c < 10; c++)
                if (a != b && a != c && b != c) cacah++;

cout << rumus << " " << cacah << "\n";   // must be equal

If the two differ, the formula is wrong — and it is better to find out now than during the contest.

OSN problem patterns

Homework

Most common mistakes

OSN tips

Turn the problem into a single sentence "how many ways are there to choose ...". If that sentence says "then", use the product rule; if it says "or", use the sum rule. Most mistakes on combinatorics problems come from choosing wrongly between those two words.

Count by hand first for the smallest cases. For N = 1, N = 2, and N = 3, the answer can often be enumerated one by one on paper. Your formula must match on all three before it is trusted for N = 10¹⁸.

Check the formula with an enumerating program. Write a brute force that enumerates all possibilities for small N, then compare it with your formula. This is the fastest way to find a mistake that is off by a factor — and the only way that can be trusted when contest time is running out.

The complement is almost always easier than direct counting. The phrase "at least one" is the cue: count everything, then subtract those that have none. For "at least one a and at least one b", the complement is two overlapping sets, and their intersection has to be added back once — that is inclusion-exclusion.

Combinatorics answers explode, so a modulo is almost always required. Once there is a % MOD, all the habits of Chapter 14 apply: take the remainder at every step, use long long, and wrap subtractions with + MOD.

Modular subtraction without adjustment is a bug waiting to happen. The complement formula always contains a subtraction, and its intermediate result can be negative. The standard form:

hasil = ((semua - tanpa) % MOD + MOD) % MOD;

Pay attention to whether order counts. "A pair (x, y)" usually means ordered — (1, 2) and (2, 1) are different. "Choosing two people" usually does not. OSN problems state it, but the sentence is easy to miss, and the answer differs by exactly a factor of two.

Summary

• The sum rule for "or" on groups that do not overlap; the product rule for "and" in steps.
• If the groups overlap, use inclusion-exclusion: |A ∪ B| = |A| + |B| − |A ∩ B|, with alternating signs for three or more sets.
• The intersection "divisible by p and q" is the multiples of LCM(p, q), not always p × q.
• "At least one" is almost always easier through the complement: the total minus "none at all".
• The number of numbers 1 to n divisible by p is n / p with integer division.
• Every counting formula can and should be checked with direct enumeration on small data, exactly like the comparison tester in Chapter 10.

OSN-style exercises

All three are solved with a formula, not enumeration. Before typing, work out N = 1 and N = 2 by hand, then make sure your formula matches.

The skeletons for all three are in exercises/16/osn/.

Problem 1 — Colored Flag

A flag consists of N stripes lined up from left to right. Each stripe is colored with one of the K available colors. Two adjacent stripes may not have the same color; stripes that are further apart may.

Count how many different flags can be made, then output the remainder when divided by 1,000,000,007.

Input format. One line containing two integers N and K.

Output format. One line containing the number of flags modulo 1,000,000,007.

Constraints.

• 1 ≤ N ≤ 10¹⁸
• 1 ≤ K ≤ 10⁹

Sample input

3 3

Sample output

12

Explanation. The first stripe may be any color: 3 choices. The second stripe may be any color except the color of the first stripe: 2 choices. The third stripe may be any color except the color of the second stripe: 2 choices. In total 3 × 2 × 2 = 12.

Note the case K = 1: the only valid flag is a flag with a single stripe.

The skeleton: exercises/16/osn/01-bendera-warna.cpp

Problem 2 — Password With Two Required Letters

A system accepts passwords of exactly N letters, and the letters that may be used are the first K letters of the alphabet. The extra rule: the password must contain at least one letter a and at least one letter b.

Count how many valid passwords there are, then output the remainder when divided by 1,000,000,007.

Input format. One line containing two integers N and K.

Output format. One line containing the number of passwords modulo 1,000,000,007.

Constraints.

• 1 ≤ N ≤ 10¹⁸
• 2 ≤ K ≤ 26

Sample input

2 3

Sample output

2

Explanation. The letters are a, b, and c. Of the nine two-letter words, the only ones containing both a and b are ab and ba.

The skeleton: exercises/16/osn/02-sandi-dua-huruf.cpp

Problem 3 — Pairs Summing to a Multiple of K

Count how many ordered pairs (x, y) with 1 ≤ x, y ≤ N there are such that x + y is divisible by K. The pairs (1, 2) and (2, 1) are considered different, and x may equal y.

Input format. One line containing two integers N and K.

Output format. One line containing the number of pairs.

Constraints.

• 1 ≤ N ≤ 10⁹
• 1 ≤ K ≤ 10⁶

Sample input

5 3

Sample output

9

Explanation. The pairs are (1,2), (2,1), (1,5), (5,1), (2,4), (4,2), (3,3), (4,5), and (5,4). Checking every pair one by one takes N² = 10¹⁸ steps, so what must be grouped is the remainders, not the numbers.

The skeleton: exercises/16/osn/03-pasangan-kelipatan.cpp

Stuck or already done? Open the homework solutions page.