Skip to content
Tutorials Center
My learning

Topics

Lesson 31 of 68 ยท Counting

Counting Principles

Learn the sum rule, product rule, inclusion-exclusion and the pigeonhole principle, and verify each counting argument by brute force in Python.

Combinatorics is the art of counting without listing. How many passwords of length 8 exist? How many ways can a tournament bracket unfold? How many of the first thousand numbers are divisible by 3 or 5? Listing every case works for tiny problems, but real questions have billions of answers, so we need rules that turn a description into a number.

This lesson covers the four basic tools: the sum rule, the product rule, inclusion-exclusion and the pigeonhole principle. Every later counting lesson (permutations, combinations, binomial coefficients) is built on them. Because counts are easy to get wrong by one, we will check each formula against a brute-force enumeration in Python. That habit, "compute the formula, then count the slow way on a small case", is the best defence against double counting.

Four basic tools

Sum rule Either this or that, with no overlap.
Product rule This and then that.
Inclusion-exclusion Fix the overlap you counted twice.
Pigeonhole More items than boxes forces a shared box.
1 / 2

The sum rule

If a task can be done in one of several mutually exclusive ways, with n1 ways for the first kind, n2 for the second and so on, the total is n1 + n2 + .... Mutually exclusive means no outcome belongs to two groups.

Example: you can travel to a city by one of 3 trains, 4 buses or 2 flights. Since a single trip uses just one of them, there are 3 + 4 + 2 = 9 ways. In set language, if A and B are disjoint, then |A โˆช B| = |A| + |B|.

The product rule

If a procedure has several steps, the first with n1 outcomes, the second with n2 outcomes (whatever the first choice was) and so on, the total number of outcomes is n1 ยท n2 ยท .... This is the Cartesian product idea again: a choice at each stage forms a tuple.

Example: a license plate has 3 letters followed by 4 digits. There are 26 options for each letter and 10 for each digit, so the count is 26ยณ ยท 10โด = 175,760,000. If letters must be distinct, the choices shrink as you go: 26 ยท 25 ยท 24 ยท 10โด. The number of options at each step may depend on earlier steps as long as the count of options does not.

Python Sum and product rules, checked by brute force

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.

Notice what happened to the distinct-letter plates: instead of listing the allowed ones, the formula multiplied a shrinking sequence of options, and the brute force agrees.

Inclusion-exclusion

When groups overlap, adding their sizes counts the overlap twice. For two sets,

|A โˆช B| = |A| + |B| - |A โˆฉ B|

For three sets, add the singles, subtract the pairwise overlaps, then add back the triple overlap:

|A โˆช B โˆช C| = |A| + |B| + |C| - |A โˆฉ B| - |A โˆฉ C| - |B โˆฉ C| + |A โˆฉ B โˆฉ C|

The pattern generalizes to any number of sets: include singles, exclude pairs, include triples, exclude quadruples, and so on, alternating signs. Example: how many integers from 1 to 100 are divisible by 2, 3 or 5? Let A, B and C be the multiples of 2, 3 and 5. Then |A| = 50, |B| = 33, |C| = 20; the pairwise overlaps are multiples of 6, 10 and 15 (16, 10, 6), and the triple overlap is the multiples of 30 (3). The answer is 50 + 33 + 20 - 16 - 10 - 6 + 3 = 74.

Counting the complement is often easier: the numbers not divisible by any of 2, 3, 5 are 100 - 74 = 26.

Python Inclusion-exclusion versus counting directly

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.

Notice that the program multiplies the divisors to get the overlaps. That is valid only because 2, 3 and 5 share no factors; for numbers like 4 and 6 you would use the least common multiple (see GCD, LCM and the Euclidean Algorithm).

The pigeonhole principle

If you put more than k pigeons into k holes, some hole contains at least two pigeons. It sounds trivial, but it proves surprising facts without constructing anything:

  • In any group of 13 people, at least two were born in the same month.
  • Among any 5 integers, two have the same remainder when divided by 4, because there are only 4 possible remainders.
  • Among any 27 English words, two begin with the same letter, because there are only 26 letters.

The generalized version says: if n objects go into k boxes, some box holds at least โŒˆn/kโŒ‰ objects. With 100 people and 12 months, some month has at least โŒˆ100/12โŒ‰ = 9 birthdays.

The principle proves existence, not which pair. Using it requires choosing the boxes cleverly: the art is deciding what the pigeons and holes are. Python can confirm small cases exhaustively.

Python Verifying pigeonhole claims exhaustively

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 first line prints 792 (the number of 5-element subsets) and True. The second shows that with only 4 numbers you can dodge every collision, so the bound 5 is tight.

Putting the rules together

Real problems mix the rules. A typical recipe:

  1. Split the task into stages, or into disjoint cases.
  2. Count each stage or case with the product rule.
  3. Add the cases with the sum rule.
  4. If cases overlap, use inclusion-exclusion; if the complement is smaller, count that and subtract.
  5. Test the formula against a brute-force count on a small instance.

Example: how many 4-bit strings contain at least one 1? The complement is the single string 0000, so the answer is 2โด - 1 = 15. When "at least one" appears, think about the complement first.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. A menu offers 5 soups, 3 salads and 4 desserts. A meal is one soup, one salad and one dessert. How many meals are possible?

    Three stages in sequence, so multiply: 5 x 3 x 4 = 60. Adding would apply only if you chose just one item from the menu.
  2. 2. How many integers from 1 to 60 are divisible by 4 or by 6?

    Multiples of 4: 15. Multiples of 6: 10. Multiples of both (multiples of 12): 5. By inclusion-exclusion, 15 + 10 - 5 = 20.
  3. 3. You want to guarantee that two of your socks match, drawing from a drawer with 3 colors. What is the minimum number of socks you must draw?

    With 3 colors as holes, drawing 4 socks forces two into the same color. Three socks could be one of each color.
  4. 4. How many binary strings of length 6 have at least one 0?

    Count the complement: only 111111 has no 0. So the answer is 2^6 - 1 = 63.
  5. 5. Why does the sum rule require the cases to be mutually exclusive?

    If some outcome belongs to two groups, adding the group sizes counts it twice. Inclusion-exclusion subtracts that overlap.

Summary

  • The sum rule adds the sizes of disjoint cases; the product rule multiplies the number of choices over successive stages.
  • Inclusion-exclusion corrects for overlap: add singles, subtract pairs, add triples, and so on.
  • Counting the complement ("at least one") is often easier than counting directly.
  • The pigeonhole principle guarantees a shared box when there are more objects than boxes, and the generalized form gives โŒˆn/kโŒ‰.
  • Always test a counting formula on a small case with brute force.

Next: Permutations and Combinations, where ordering and repetition decide which formula applies.