Chapter 15 of 30

Counting Principles

How many passwords can a hacker try? How many test cases does a nested loop generate? How many different 8-bit patterns can a register hold? How many relations exist on a 4-element set? Counting questions like these are everywhere in computer science, from estimating the running time of an algorithm to judging whether a password policy is strong enough.

Listing everything and counting by hand stops working almost immediately: there are already 65536 relations on a 4-element set. Instead we use a few simple counting principles that let us count huge sets without listing them. This chapter covers the five basic rules (sum, product, subtraction, division and complement), the bijection principle, and tree diagrams. Later chapters build on them: Permutations & Combinations, Pigeonhole Principle and Inclusion-Exclusion Principle.

Combinatorics is the art of counting without listing. Almost every counting argument is a careful combination of two ideas: add when you split into separate cases (OR), multiply when you build in independent steps (AND).

Every number in this chapter was checked by brute-force enumeration with the Python program shown later.


The Sum Rule (OR)

Sum rule: if a task can be done in one of n1 ways or in one of n2 ways, and no way belongs to both groups, then it can be done in n1 + n2 ways. In set form: if A ∩ B = ∅, then |A ∪ B| = |A| + |B|.

It extends to any number of pairwise disjoint cases: |A1 ∪ … ∪ Ak| = |A1| + … + |Ak|.

Example. A student must choose one elective from three lists: 6 from AI, 4 from Systems, 5 from Theory, with no course on two lists. The number of choices is 6 + 4 + 5 = 15.

Example (code). How many times does count++ run?

for (i = 0; i < 10; i++) count++;
for (j = 0; j < 20; j++) count++;

The loops run one after the other, so each increment comes from the first loop or the second: 10 + 20 = 30.

The word to watch for is "disjoint". If the cases overlap, the sum rule over-counts, and we need the subtraction rule below.


The Product Rule (AND)

Product rule: if a procedure consists of a first step that can be done in n1 ways, followed by a second step that can be done in n2 ways for each way of doing the first step, then the whole procedure can be done in n1 · n2 ways. In set form: |A × B| = |A| · |B|.

It extends to k steps: n1 · n2 · … · nk. The essential condition is that the number of choices at each step does not depend on the earlier choices (the choices themselves may change, the count may not).

Example (code). Nested loops multiply:

for (i = 0; i < 10; i++)
    for (j = 0; j < 20; j++)
        for (k = 0; k < 5; k++)
            count++;

Each run is a choice of i (10 ways), then j (20 ways), then k (5 ways): 10 · 20 · 5 = 1000.

Classic product-rule results

Object

Steps

Count

Bit strings of length n

2 choices for each of n positions

2n (256 for n = 8)

Strings of length n over an alphabet of size k

k choices per position

kn

Subsets of an n-element set

each element is in or out

2n

Functions from an m-set to an n-set

n choices of image for each of m elements

nm

One-to-one functions from an m-set to an n-set (m ≤ n)

n, then n − 1, …, then n − m + 1 choices

n(n − 1)…(n − m + 1)

Relations on an n-element set

each of n2 ordered pairs is in or out

2n²

Boolean functions of n variables

output 0 or 1 for each of 2n input rows

22ⁿ (16 for n = 2, 256 for n = 3)

Palindromes of length n over k letters

only the first ⌈n/2⌉ positions are free

k⌈n/2⌉ (16 binary palindromes of length 7)

For example, from {1, 2, 3} to {a, b, c, d} there are 43 = 64 functions, of which 4 · 3 · 2 = 24 are one-to-one (see Functions for the definitions).

Worked example: number of divisors

How many positive divisors does 720 have? Factorise: 720 = 24 · 32 · 51. Every divisor is 2a · 3b · 5c with 0 ≤ a ≤ 4, 0 ≤ b ≤ 2, 0 ≤ c ≤ 1, and different exponent triples give different divisors (unique factorisation). Choose a (5 ways), b (3 ways), c (2 ways): 5 · 3 · 2 = 30 divisors. In general, n = p1e1 … pkek has (e1 + 1)(e2 + 1)…(ek + 1) divisors.

Odd divisors are those with a = 0: 1 · 3 · 2 = 6.

Worked example: a restricted first step

How many 4-digit numbers have all digits different? The first digit cannot be 0 (9 choices: 1–9). The second can be any digit except the first (9 choices, now including 0). Then 8, then 7. Total 9 · 9 · 8 · 7 = 4536.

Notice the trick: we handled the most restricted position first. If we had started from the last digit, the number of choices for the first digit would depend on whether 0 was already used, and the product rule would not apply directly.


When the Product Rule Needs Help: Splitting into Cases

Problem. How many 3-digit even numbers have distinct digits?

Try the product rule starting from the last digit: it must be one of 0, 2, 4, 6, 8 (5 ways). Now count the choices for the first digit. If the last digit is 0, the first digit can be any of 1–9 (9 ways); if the last digit is 2, 4, 6 or 8, the first digit can be any of 1–9 except that one (8 ways). So 5 · 9 · 8 would be wrong. The count for step 2 depends on step 1, so we split into cases (sum rule) and use the product rule inside each case:

Case 1: last digit 0          first: 9 (1–9)     middle: 8    →  1 · 9 · 8 =  72
Case 2: last digit 2, 4, 6, 8  first: 8 (1–9, not last)  middle: 8  →  4 · 8 · 8 = 256
                                                             total     328

This "split into cases until the product rule applies, then add" pattern is the workhorse of exam counting problems.


Tree Diagrams

When the steps really do depend on each other in an irregular way, draw a tree: each branch is a choice, and each leaf is one outcome. Count the leaves.

Example. Teams A and B play a best-of-three series: the first to win 2 games wins the series. In how many ways can the series unfold?

                     start
               /               \
             A                   B
          /     \             /     \
        AA       AB         BA       BB
      (A wins)  /   \      /   \   (B wins)
              ABA   ABB  BAA   BAB
           (A wins) (B)  (A)  (B wins)

Leaves: AA, ABA, ABB, BAA, BAB, BB. So 6 ways. The product rule alone fails here because some branches stop after 2 games and others continue to 3. A best-of-five series, by the same method, can unfold in 20 ways.


The Subtraction Rule (Overlapping OR)

Subtraction rule: if a task can be done in n1 ways or in n2 ways, then the number of ways is n1 + n2 minus the number of ways common to both. In set form: |A ∪ B| = |A| + |B| − |A ∩ B|.

The elements of A ∩ B are counted once in |A| and once in |B|, so we subtract them once. (The general version for three or more sets is the subject of Inclusion-Exclusion Principle.)

Example. How many 8-bit strings start with 1 or end with 00?

  • Start with 1: the other 7 bits are free → 27 = 128.

  • End with 00: the other 6 bits are free → 26 = 64.

  • Both (start with 1 and end with 00): 5 bits free → 25 = 32.

Answer: 128 + 64 − 32 = 160.

Example. How many integers from 1 to 1000 are divisible by 7 or 11? Multiples of 7: ⌊1000/7⌋ = 142. Multiples of 11: ⌊1000/11⌋ = 90. Multiples of both, i.e. of 77: ⌊1000/77⌋ = 12. Answer: 142 + 90 − 12 = 220.


The Complement Rule

Complement rule: the number of objects with a property = (total number of objects) − (number without the property). In set form: |A| = |U| − |U − A|.

Use it whenever the question says "at least one". "At least one" usually splits into many messy cases, while "none" is a single clean product.

Example. How many 4-digit PINs (leading zeros allowed) contain at least one repeated digit? Total PINs: 104 = 10000. PINs with all digits different: 10 · 9 · 8 · 7 = 5040. Answer: 10000 − 5040 = 4960.

Example (passwords). A password has 6 to 8 characters, each an uppercase letter or a digit, and must contain at least one digit. For length k there are 36k strings, of which 26k have no digit. By the complement rule and then the sum rule over the three lengths:

(36^6 − 26^6) + (36^7 − 26^7) + (36^8 − 26^8)
=  1,867,866,560  +  70,332,353,920  +  2,612,282,842,880
=  2,684,483,063,360

The Division Rule

Division rule: if a set of N arrangements can be divided into groups so that every group contains exactly d arrangements that we regard as the same, then there are N / d different outcomes. Equivalently, if a function from A onto B is exactly d-to-1, then |B| = |A| / d.

In the language of Equivalence Relations & Partitions: we count the classes of an equivalence relation in which every class has the same size d.

Example (round table). In how many ways can 5 people sit around a round table, if two seatings are the same when one is a rotation of the other? Seat them in a row first: 5 · 4 · 3 · 2 · 1 = 120 orders. Each circular seating corresponds to exactly 5 row orders (start reading at any of the 5 seats). So there are 120 / 5 = 24 seatings. In general (n − 1)!.

Example (unordered pairs). How many times does count++ run?

for (i = 1; i <= n; i++)
    for (j = i + 1; j <= n; j++)
        count++;

Each run corresponds to a pair i < j. There are n(n − 1) ordered pairs (i, j) with i ≠ j, and each unordered pair {i, j} appears in exactly 2 of them. So the count is n(n − 1)/2 (45 for n = 10). This is the quantity C(n, 2) of the next chapter.

Warning: the division rule needs every group to have exactly d members. For colourings of a necklace, the pattern "all beads red" has only one rotation, not n, so naive division gives a wrong (often non-integer) answer.


The Bijection Principle

If there is a bijection (one-to-one correspondence) between two finite sets, they have the same size. This lets us count an awkward set by matching it with an easy one.

  • Subsets ↔ bit strings. Subset T of {x1, …, xn} ↔ the bit string whose i-th bit is 1 iff xi ∈ T. Hence 2n subsets. This is exactly how bitmask DP and for mask in range(1 << n) enumerate subsets.

  • Relations ↔ 0/1 matrices. A relation on an n-set ↔ its n × n matrix, hence 2n² relations, as used in Properties of Relations.


Checking the Counts by Program

For small cases, brute force is the best way to catch a counting mistake. The program below lists every object and compares the size with the formula.

from itertools import product

# 1. Product rule: 8-bit strings
bits8 = list(product("01", repeat=8))
print("8-bit strings              :", len(bits8), "  formula 2^8 =", 2 ** 8)

# 2. Subtraction rule: start with 1 OR end with 00
either = [s for s in bits8 if s[0] == "1" or s[-2:] == ("0", "0")]
print("start 1 or end 00          :", len(either), "  formula 128 + 64 - 32 =", 128 + 64 - 32)

# 3. Product rule with a restricted first choice: 4-digit numbers, distinct digits
four = [n for n in range(1000, 10000) if len(set(str(n))) == 4]
print("4-digit, distinct digits   :", len(four), "  formula 9*9*8*7 =", 9 * 9 * 8 * 7)

# 4. Case split + product rule: 3-digit even numbers, distinct digits
even3 = [n for n in range(100, 1000) if n % 2 == 0 and len(set(str(n))) == 3]
print("3-digit even, distinct     :", len(even3), "  formula 9*8 + 4*8*8 =", 9 * 8 + 4 * 8 * 8)

# 5. Product rule on prime exponents: divisors of 720 = 2^4 * 3^2 * 5
divs = [d for d in range(1, 721) if 720 % d == 0]
print("divisors of 720            :", len(divs), "  formula 5*3*2 =", 5 * 3 * 2)

# 6. Division rule: 5 people around a round table (rotations are the same)
def canonical(seating):
    """Rotate the seating so that person 0 is first."""
    i = seating.index(0)
    return seating[i:] + seating[:i]
from itertools import permutations
tables = {canonical(p) for p in permutations(range(5))}
print("round-table seatings of 5  :", len(tables), "  formula 5!/5 =", 120 // 5)

# 7. Complement: 4-character PINs over digits with at least one repeated digit
pins = list(product(range(10), repeat=4))
repeat = [p for p in pins if len(set(p)) < 4]
print("4-digit PINs with a repeat :", len(repeat), "  formula 10^4 - 10*9*8*7 =", 10 ** 4 - 10 * 9 * 8 * 7)

Output:

8-bit strings              : 256   formula 2^8 = 256
start 1 or end 00          : 160   formula 128 + 64 - 32 = 160
4-digit, distinct digits   : 4536   formula 9*9*8*7 = 4536
3-digit even, distinct     : 328   formula 9*8 + 4*8*8 = 328
divisors of 720            : 30   formula 5*3*2 = 30
round-table seatings of 5  : 24   formula 5!/5 = 24
4-digit PINs with a repeat : 4960   formula 10^4 - 10*9*8*7 = 4960

The round-table check uses the division rule in reverse: it maps every row order to a canonical rotation (person 0 first) and counts the distinct results, which are exactly the equivalence classes.


Which Rule Do I Use?

Situation in the question

Rule

Operation

"either … or …", separate non-overlapping cases

Sum rule

Add

Build the object step by step, choice count fixed at each step

Product rule

Multiply

"or" with overlapping cases

Subtraction rule

Add, then subtract the overlap

"at least one", "not all"

Complement rule

Total minus the opposite

Some arrangements are "the same" in groups of equal size

Division rule

Divide by the group size

Choices depend on earlier choices irregularly

Cases or a tree diagram

Add over cases / count leaves


Common Mistakes

  • Adding overlapping cases. "Start with 1 or end with 00" is not 128 + 64.

  • Multiplying when the number of choices depends on earlier steps. Fill the most restricted position first, or split into cases.

  • Forgetting the leading-zero restriction for numbers (but not for PINs or strings, where 0 in front is allowed).

  • Mixing up ordered and unordered. Choosing a president and a vice-president from 10 people: 10 · 9 = 90 (ordered). Choosing a 2-person committee: 90 / 2 = 45 (unordered).

  • Counting "at least one" directly by "choose the special one, then anything for the rest". This counts objects with several special items many times. Use the complement.

  • Using the division rule when groups have different sizes (necklaces, symmetric patterns).


Practice and GATE-Style Questions

Q1. A variable name in a language must be 1 to 3 characters long. The first character is a letter (upper or lower case) or an underscore; later characters may also be digits. Ignoring reserved words, how many names are possible?

First character: 52 + 1 = 53 choices. Later characters: 53 + 10 = 63. By length (sum rule) and position (product rule): 53 + 53 · 63 + 53 · 632 = 53 + 3339 + 210357 = 213749.

Q2. How many 5-letter strings over the English alphabet contain at least one vowel (a, e, i, o, u)?

Complement: 265 − 215 = 11,881,376 − 4,084,101 = 7,797,275.

Q3. How many positive divisors does 23 · 34 · 72 have? How many of them are even?

All: (3 + 1)(4 + 1)(2 + 1) = 60. Even divisors need the exponent of 2 to be 1, 2 or 3: 3 · 5 · 3 = 45.

Q4. In how many ways can a best-of-five series (first to 3 wins) unfold?

Split by the final score. 3–0: the winner takes all three games, 2 ways (A or B). 3–1: the winner wins game 4 and exactly 2 of the first 3, so 2 · 3 = 6. 3–2: the winner wins game 5 and exactly 2 of the first 4, so 2 · 6 = 12. Total 20.

Q5. How many binary strings of length 10 either start with 11 or end with 0?

Start with 11: 28 = 256. End with 0: 29 = 512. Both: 27 = 128. Answer: 256 + 512 − 128 = 640.

Q6. Interview: a 4-digit OTP is sent by SMS, and an attacker gets 3 attempts. What is the chance of guessing it, and how does the product rule suggest improving it?

There are 104 OTPs, so 3 distinct guesses succeed with probability 3/10000 = 0.03%. Each extra digit multiplies the space by 10 (product rule), so a 6-digit OTP gives 3/106. Limiting attempts matters as much as length: allowing a million attempts would make even a 6-digit code trivial.


Summary

  • Sum rule: disjoint cases add. Product rule: sequential independent steps multiply.

  • Subtraction rule: |A ∪ B| = |A| + |B| − |A ∩ B| for overlapping cases.

  • Complement rule: "at least one" = total − "none".

  • Division rule: if every outcome is counted exactly d times, divide by d (round tables, unordered pairs).

  • Bijection principle: count an easy set that matches the hard one (subsets ↔ bit strings).

  • When choice counts depend on earlier choices, split into cases or draw a tree.

  • Standard results: 2n bit strings and subsets, nm functions, n(n − 1)…(n − m + 1) injections, (e1 + 1)…(ek + 1) divisors.

Before multiplying, ask "does the number of choices at this step ever change?"; before adding, ask "can an object be counted in two cases?". Those two questions prevent most counting errors.