Counting seems simple until the number of cases explodes. How many 8-character passwords exist? How many possible answer keys does a 20-question multiple-choice exam have? Listing them one by one is impractical. We need principles.
Two of them underlie all of combinatorics: the Sum Rule (SR) and the Product Rule (PR).
Why SR and PR? #
Counting is a central operation in computing and engineering:
- Security and cryptography: the size of the space of passwords or keys determines the resistance to brute-force attacks. Quantifying that space is always an application of the PR.
- Software testing: techniques such as pairwise testing use SR and PR to choose a reduced set of cases that covers all combinations of pairs of parameters.
- Data structures: the number of indices of a multidimensional array \(A[n_1][n_2]\cdots[n_k]\) is \(n_1 \cdot n_2 \cdots n_k\), a direct Cartesian product.
- Network protocols: the IPv4 (\(2^{32}\)) and IPv6 (\(2^{128}\)) address spaces come from the PR applied to sequences of bits.
- Algorithm analysis: estimating the complexity of exhaustive algorithms, the probability of collisions in hash tables, and the sizing of search spaces in AI (Artificial Intelligence) all rely on counting with SR and PR.
This article develops the two principles formally, applies them in graded examples, and shows how to recognize which one to use in each situation.
The Intuition: “or” Is a Sum, “and” Is a Product #
Consider a store with 4 math books and 3 Portuguese books.
- In how many ways can we choose one book (a math book or a Portuguese book)? \(4 + 3 = 7\)
- In how many ways can we choose one of each (a math book and a Portuguese book)? \(4 \times 3 = 12\)
This intuition is the core of the two principles. The diagram below turns it into a decision guide that can be applied to any counting problem:
flowchart TD
A["How to count?"] --> B{"Mutually
exclusive
alternatives?"}
B -->|"Yes: 'or'"| C["Sum Rule
|A₁| + |A₂| + …"]
B -->|"No: 'and'"| D{"Independent
stages?"}
D -->|Yes| E["Product Rule
|A₁| × |A₂| × …"]
D -->|No| F["Complement
or PIE"]
C --> G["⚠️ Non-disjoint
sets? → PIE"]
Sum Rule #
If \(A \cap B = \emptyset\), then \(|A \cup B| = |A| + |B|\).
Extension: for pairwise disjoint sets \(A_1, A_2, \ldots, A_n\):
$$|A_1 \cup \cdots \cup A_n| = |A_1| + \cdots + |A_n|$$Application: when the choices are mutually exclusive, that is, they cannot occur simultaneously.
The SR requires pairwise disjoint sets. If there are common elements, naively adding the sizes counts those elements more than once. The fix is the Inclusion-Exclusion Principle (PIE):
$$|A \cup B| = |A| + |B| - |A \cap B|$$Example: in a class, 18 students play soccer and 12 play volleyball; 5 play both sports. The total number of players is \(18 + 12 - 5 = 25\), not \(18 + 12 = 30\). The PIE is covered in detail in the article on cardinality.
Cartesian Product and Product Rule #
Also known as the rule of product. If a task is carried out in independent stages, with \(|A_1|\) ways for the 1st stage, \(|A_2|\) for the 2nd, …, \(|A_k|\) for the \(k\)th, then the total number of ways to carry out the task is:
$$|A_1 \times A_2 \times \cdots \times A_k| = |A_1| \cdot |A_2| \cdots |A_k|$$Application: when the choices are sequential and independent, that is, each stage does not interfere with the others.
Worked Examples #
The examples below progressively increase in complexity. In each one, we identify the applicable principle before calculating, and this habit avoids mistakes and makes the reasoning verifiable.
Passwords with and without repetition #
Problem: a lock has 8 available symbols. How many 2-symbol passwords exist: (a) with repeated symbols allowed; (b) with the two symbols necessarily distinct?
Principle: PR in both cases, since the password is formed in two sequential stages (choose the 1st symbol, then the 2nd), and in each stage the number of options is constant regardless of the symbol chosen before.
(a) With repetition: each position has 8 options, with no restriction between them:
$$8 \times 8 = 64 \text{ passwords}$$(b) Without repetition: the 1st position still has 8 options, but the 2nd has only 7 (any symbol except the one already chosen):
$$8 \times 7 = 56 \text{ passwords}$$Check by complement: of the 64 passwords with repetition, we remove the 8 where both positions have the same symbol (AA, BB, …): \(64 - 8 = 56\). ✓
Python: itertools.product and itertools.permutations
itertools.product and itertools.permutations
The itertools module in the standard library implements the Cartesian
product directly, making the PR observable in code. The example below uses
the case of 2-symbol passwords over an 8-character alphabet:
import itertools
symbols = "ABCDEFGH" # 8 symbols
# PR with repetition: Cartesian product 8 × 8 = 64 pairs
with_rep = list(itertools.product(symbols, repeat=2))
print(len(with_rep)) # 64
# PR without repetition: each position excludes the symbol already used → 8 × 7 = 56
without_rep = list(itertools.permutations(symbols, 2))
print(len(without_rep)) # 56itertools.product(A, B, C, ...) generates \(|A| \times |B| \times |C| \times \cdots\)
tuples, exactly the PR. itertools.permutations(S, k) generates
arrangements (r-permutations) of \(k\) distinct elements of \(S\) (distinct by position in \(S\), not by value), corresponding to the PR applied to
stages without repetition. The function name anticipates a formal concept: a
permutation is an ordered selection of distinct elements. The
next article covers this
topic in detail.
Application: brute force and the password space
An attacker who tries every 8-character password from an alphabet of 95 printable symbols faces \(95^8 \approx 6.6 \times 10^{15}\) combinations, more than 6 quadrillion attempts. Forbidding repetition would reduce this space to \(95 \times 94 \times \cdots \times 88\), but human users choose passwords that are far from random, which reduces the effective space: that is why NIST SP 800-63B recommends comparing chosen passwords against lists of common, expected, or compromised values. The PR is the tool that formalizes this reasoning in password policies and attack cost estimates.
Flag with 3 stripes of different colors #
Problem: a flag has 3 horizontal stripes; there are 5 colors available and each stripe must have a color different from the others. How many distinct flags can be created?
Principle: PR, since the assembly is done in 3 sequential stages (top, middle, and bottom stripe), and in each stage the number of available colors decreases predictably.
| Stage | Stripe | Available options |
|---|---|---|
| 1st | Top | 5 (any of the 5 colors) |
| 2nd | Middle | 4 (any except the one used on the top stripe) |
| 3rd | Bottom | 3 (any except the two already used) |
The number of options in the 2nd stage is always 4, regardless of which color was chosen in the 1st: this constancy is exactly what validates the use of the PR.
Multiple-choice exam #
Problem: an exam has 20 questions. How many distinct answer keys are possible if each question is true or false? And if each question has 5 choices?
Principle: PR, since each question is a stage independent of the others. The answer given to any question does not change the options of the others.
True or false: each of the 20 questions has 2 options (T or F):
$$\underbrace{2 \times 2 \times \cdots \times 2}_{20\text{ times}} = 2^{20} = 1{,}048{,}576 \text{ answer keys}$$5 choices per question: the structure is identical, only each stage now has 5 options:
$$5^{20} \approx 9.5 \times 10^{13} \text{ answer keys}$$That is more than 95 trillion possible answer keys. Even trying one per second, it would take about 3 million years to exhaust them.
Application: generating test cases
Imagine a system with \(k\) configuration parameters, each of which can take \(n\) values. Testing all possible combinations (the strategy called exhaustive coverage or full factorial) requires \(n^k\) test cases, exactly by the PR. For \(k = 10\) parameters with \(n = 5\) values each, that is already \(5^{10} \approx 10\) million tests.
In practice, empirical research from NIST indicates that most defects are caused by the interaction of one or two parameters, with a smaller fraction requiring three or more. Pairwise testing (also known as all-pairs testing) takes advantage of this: instead of covering all \(n^k\) combinations, we choose a smaller subset of tests such that, for each pair of parameters, all \(n^2\) combinations of values for that pair appear at least once. So-called covering arrays achieve this with only \(O(n^2 \log k)\) cases, a drastic reduction compared to full factorial.
3-digit numbers with distinct digits from \(\{1,2,3,4,5,6\}\) #
Problem: how many 3-digit numbers with distinct digits can be formed using only digits from \(\{1,2,3,4,5,6\}\)?
Principle: PR, since we fill the 3 positions sequentially; in each position the number of options decreases by 1 because the chosen digit is not repeated.
| Position | Options | Justification |
|---|---|---|
| Hundreds | 6 | any of the 6 digits |
| Tens | 5 | any except the hundreds digit |
| Units | 4 | any except the two already used |
Since 0 does not belong to the set, all the numbers formed are automatically valid 3-digit numbers: there is no risk of a leading zero.
3-digit numbers with distinct digits from \(\{0,1,\ldots,9\}\) #
Problem: how many 3-digit numbers (between 100 and 999) have all distinct digits, using digits from \(\{0,1,\ldots,9\}\)?
Principle: PR, with the same structure as the previous example, but now 0 is available and cannot occupy the hundreds position (otherwise the number would have fewer than 3 digits).
| Position | Options | Justification |
|---|---|---|
| Hundreds | 9 | digits 1 to 9 (zero excluded) |
| Tens | 9 | digits 0 to 9 except the hundreds digit (zero is an option again) |
| Units | 8 | digits 0 to 9 except the two already used |
Check by complement: we count all arrangements of 3 distinct digits (including those that start with zero) and subtract the invalid ones:
$$\underbrace{10 \times 9 \times 8}_{\text{all arrangements with distinct digits}} - \underbrace{1 \times 9 \times 8}_{\text{start with 0}} = 720 - 72 = 648 \checkmark$$The complement method always follows the same structure, useful when counting the invalid cases is simpler than counting the valid ones directly:
flowchart LR
A["Total
no restriction"] -->|"− Invalid cases
(easier to count)"| B["Result
only the valid cases"]
Selection in a room #
Problem: in a room there are 5 men, 6 women, and 4 children. In how many ways can we choose: (a) a single person; (b) one person of each type?
This example is instructive because the two sub-problems, with similar statements, require different principles.
(a) A single person, by the Sum Rule:
Choosing “either a man, or a woman, or a child”: the three categories are mutually exclusive (no one belongs to two groups simultaneously). By the SR:
$$5 + 6 + 4 = 15 \text{ ways}$$(b) One of each type, by the Product Rule:
Now we want “a man and a woman and a child”: three independent choices in distinct groups. Whom we choose from the group of men does not interfere with whom we can choose among the women. By the PR:
$$5 \times 6 \times 4 = 120 \text{ ways}$$
SQL: UNION ALL (SR) vs CROSS JOIN (PR)
UNION ALL (SR) vs CROSS JOIN (PR)
The distinction “or is a sum, and is a product” has a direct counterpart in SQL. We use minimal tables to make the result visible:
CREATE TABLE men (name TEXT);
CREATE TABLE women (name TEXT);
CREATE TABLE children (name TEXT);
INSERT INTO men VALUES ('Bruno'), ('Carlos');
INSERT INTO women VALUES ('Ana'), ('Diana');
INSERT INTO children VALUES ('Edu'), ('Fabi');SR, a single person (UNION ALL):
SELECT name FROM men
UNION ALL
SELECT name FROM women
UNION ALL
SELECT name FROM children;name
------
Bruno
Carlos
Ana
Diana
Edu
Fabi
(6 rows: 2 + 2 + 2)PR, one of each type (CROSS JOIN):
SELECT m.name AS man,
w.name AS woman,
c.name AS child
FROM men m
CROSS JOIN women w
CROSS JOIN children c;man | woman | child
-------|--------|--------
Bruno | Ana | Edu
Bruno | Ana | Fabi
Bruno | Diana | Edu
Bruno | Diana | Fabi
Carlos | Ana | Edu
Carlos | Ana | Fabi
Carlos | Diana | Edu
Carlos | Diana | Fabi
(8 rows: 2 × 2 × 2)UNION ALL stacks the rows of disjoint tables, adding the cardinalities.
CROSS JOIN generates all possible combinations (pairs, triples, and so
on), multiplying the cardinalities. This
correspondence shows up whenever a relational schema needs to enumerate
combinations among independent entities.
Divisors of \(N = 2^3 \times 3^2 \times 5^4\) #
Problem: how many positive divisors does \(N = 2^3 \times 3^2 \times 5^4\) have?
Key observation: by the Fundamental Theorem of Arithmetic, every divisor of \(N\) necessarily has the form \(2^\alpha \cdot 3^\beta \cdot 5^\gamma\), where the exponents satisfy:
$$\alpha \in \{0,1,2,3\}, \quad \beta \in \{0,1,2\}, \quad \gamma \in \{0,1,2,3,4\}$$Principle: PR, since choosing \(\alpha\), \(\beta\), and \(\gamma\) are three stages independent of each other. Any combination within the ranges above produces a valid divisor, distinct from all the others.
| Stage | Choice | Options |
|---|---|---|
| 1st | \(\alpha\) (exponent of 2) | 4 values: 0, 1, 2, 3 |
| 2nd | \(\beta\) (exponent of 3) | 3 values: 0, 1, 2 |
| 3rd | \(\gamma\) (exponent of 5) | 5 values: 0, 1, 2, 3, 4 |
Generalization: if \(N = p_1^{a_1} \cdots p_k^{a_k}\) is the prime factorization of \(N\), the number of positive divisors is:
$$(a_1+1)(a_2+1)\cdots(a_k+1)$$The factor \((a_i + 1)\) counts the possible values for the exponent of \(p_i\): from \(0\) to \(a_i\), there are \(a_i + 1\) integers. Zero is included because a divisor may not contain that prime. For example, 9 is a divisor of \(N\) and corresponds to \(\alpha = 0, \beta = 2, \gamma = 0\).
Python: checking the formula against brute force
For small \(N\) it is possible to confirm the result by enumerating all the divisors directly and comparing with the formula:
from math import prod
N = 2**3 * 3**2 * 5**4 # 45,000
# Brute force: list every d that divides N
divisors = [d for d in range(1, N + 1) if N % d == 0]
print(len(divisors)) # 60
# PR formula: product of (exponent + 1)
exponents = [3, 2, 4] # exponents of 2, 3, and 5
print(prod(e + 1 for e in exponents)) # 60For large \(N\) (as in cryptography, where the primes have hundreds of digits) brute force is infeasible, but the formula remains fast: it takes only \(k\) multiplications, one per prime factor, that is, \(O(k)\), provided the factorization is known. Finding that factorization for large \(N\) is, in itself, a computationally hard problem, and it is precisely on this hardness that the security of RSA (Rivest-Shamir-Adleman) rests, a classic asymmetric encryption algorithm, used in digital signatures and in HTTPS certificate authentication (key exchange via RSA existed in older versions of TLS, but was removed in TLS 1.3).
Summary Table #
| Principle | Typical situation | Keyword | Operation |
|---|---|---|---|
| Sum | Mutually exclusive choices | “or” | Sum |
| Product | Sequential stages | “and” | Product |
Exercises #
Exercise 1: Round trip
For a Rio-Belo Horizonte-Rio trip I can use a train, a bus, or a plane. In how many ways can I choose the transportation if I do not want to use the same mode on the return as on the way out?
Answer
Outbound: 3 options. Return: 2 options (excluding the outbound one). By the PR: \(3 \times 2 = \mathbf{6}\) ways.
Exercise 2: 4-letter words
How many 4-letter words with different letters can be formed from an alphabet of 26 letters?
Answer
By the PR, 4 sequential stages with no repeated letter: 1st letter: 26 options; 2nd: 25 (any except the 1st); 3rd: 24; 4th: 23. \(26 \times 25 \times 24 \times 23 = \mathbf{358{,}800}\) words.
Exercise 3: Integers with distinct digits
How many integers between 100 and 999 have distinct digits?
Answer
1st digit: 9 options (1 to 9); 2nd: 9 options (0 to 9, except the 1st); 3rd: 8 options. \(9 \times 9 \times 8 = \mathbf{648}\)
Exercise 4: At least two equal digits
How many 4-digit natural numbers have at least two equal digits?
Answer
By complement:
- Total number of 4-digit numbers: \(9 \times 10^3 = 9{,}000\)
- With all digits distinct: \(9 \times 9 \times 8 \times 7 = 4{,}536\)
- With at least two equal: \(9{,}000 - 4{,}536 = \mathbf{4{,}464}\)
Exercise 5: Numbers with digit restrictions
How many 3-digit numbers with distinct digits, greater than 390, can be formed with \(\{0,1,2,3,4,5,6,7,8,9\}\)?
Answer
Splitting into cases:
- Starts with 4 to 9 (6 digits): \(6 \times 9 \times 8 = 432\)
- Starts with 3: to exceed 390, the 2nd position must be 9 (1 option); 3rd position: 7 options, the digits \(\{1,2,4,5,6,7,8\}\) (excluding 0, since it would form 390, which does not satisfy the restriction, and 3 and 9, already used). Hence, \(1 \times 1 \times 7 = 7\)
Total: \(432 + 7 = \mathbf{439}\)
Exercise 6: Divisors of \(M = a^m \cdot b^n \cdot c^p\)
How many divisors does \(M = a^m \cdot b^n \cdot c^p\) have (with \(a, b, c\) distinct primes)?
Answer
Each divisor has the form \(a^\alpha b^\beta c^\gamma\) with \(0 \leq \alpha \leq m\), \(0 \leq \beta \leq n\), \(0 \leq \gamma \leq p\):
$$(m+1)(n+1)(p+1) \text{ divisors}$$Next Steps #
The sum and product rules are the foundation, but they have a limitation: they require the number of options at each stage to be independent of the earlier choices (or, when there is dependence, that the count of remaining options stay constant). When this condition is no longer satisfied, the analysis must be refined.
The natural next step is to count sequences without repetition in which all the elements of a set are used, the domain of permutations. After that, we will see how to count groupings where order does not matter (combinations) and how to handle additional restrictions that mix SR and PR in more elaborate ways.
