Skip to content
Tutorials Center
My learning

Topics

Lesson 5 of 36 ยท Counting Principles

The Sum Rule

Learn the sum rule of counting: when a task can be done in one of several disjoint ways, add the counts. Includes casework, common mistakes and Python checks.

The sum rule is the simplest counting principle and the one you use most without noticing. It handles "either-or" situations: you may do this or that, never both at once.

Sum rule. If a task can be done in one of m ways, or in one of n ways, and no way appears in both lists, then there are m + n ways in total. It extends to any number of disjoint options: add them all.

A first example

A cafe sells 4 kinds of tea and 3 kinds of coffee. You order one drink. Since a drink is either tea or coffee and never both, there are 4 + 3 = 7 choices.

The important phrase is "never both". If a drink could be classified as both, adding would double-count it. In set language, the sum rule is |A โˆช B| = |A| + |B| when A โˆฉ B = โˆ….

Python Sum rule with disjoint sets

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Casework

Most uses of the sum rule are casework: split a hard problem into cases that cover everything and never overlap, count each case, and add.

Example: how many numbers from 1 to 100 are divisible by 10 or end in the digit 7? Numbers divisible by 10 end in 0, so a number cannot be in both groups. That makes the groups disjoint: there are 10 multiples of 10 and 10 numbers ending in 7 (7, 17, ..., 97), giving 20.

For a case split to be valid you need two checks:

  1. Exhaustive: every object falls into some case.
  2. Exclusive: no object falls into two cases.
Python Casework by last digit

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Splitting by a feature

A very useful trick is to split by a property of the object itself. How many binary strings of length 4 start with 1 or have exactly one 1? These overlap (1000 fits both), so the sum rule does not apply directly. You can repair it by choosing cases that do not overlap: strings that start with 1 (8 of them), plus strings that start with 0 and have exactly one 1 (3 of them, since the single 1 sits in positions 2-4). Total 11.

Python Repairing an overlap by choosing better cases

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

When overlaps are unavoidable, you need the more general tool from the inclusion-exclusion chapter.

Sum rule with many cases

Suppose a password has length 1, 2 or 3 and uses only lowercase letters. A password of length 1 is a different kind of object from one of length 2, so the cases are disjoint. The total is 26 + 26^2 + 26^3 = 26 + 676 + 17,576 = 18,278.

flowchart TD
    P["Password"] --> L1["Length 1: 26"]
    P --> L2["Length 2: 676"]
    P --> L3["Length 3: 17576"]
    L1 --> T["Total = 18278"]
    L2 --> T
    L3 --> T

Each length is a separate case; the product rule counts inside each case.

Python Passwords of length 1 to 3

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The most common error is adding counts for overlapping cases. Before you add, ask: "could one object be in two cases?" If yes, redefine the cases or use inclusion-exclusion.

Sum rule and the product rule together

Real problems mix both rules: add across alternatives, multiply across steps. You will use the product rule next, then see how both combine in complement and casework.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. A shop has 6 red shirts and 5 blue shirts. You pick one shirt. How many choices?

    A shirt is red or blue, not both, so add: 6 + 5 = 11.
  2. 2. What must be true before you may simply add counts of cases?

    Cases must cover everything and not overlap, otherwise you miss or double-count objects.
  3. 3. How many strings of length 1 or 2 over {a, b, c}?

    3 + 3^2 = 12.
  4. 4. Numbers 1 to 30 divisible by 2 or 3: can you just add 15 + 10?

    Multiples of 6 are in both sets, so the cases overlap and need inclusion-exclusion.

Summary

  • Sum rule: for disjoint options, the total number of ways is the sum of the counts.
  • Casework means splitting into exhaustive, exclusive cases and adding.
  • If cases overlap, redefine them or use inclusion-exclusion.
  • It pairs with the product rule in almost every real problem.

Next: The Product Rule