Counting Principles
Learning Objectives
-
State and apply the sum rule for disjoint alternatives
-
State and apply the product rule for independent stages
-
Recognise the structural correspondence: sum rule \(\leftrightarrow\) disjunction, product rule \(\leftrightarrow\) conjunction
-
Decompose a counting problem into cases (sum rule) or stages (product rule)
-
Compute the cardinality of a Cartesian product of finite sets
-
Combine the rules to solve mixed counting problems
Counting Structured Situations
The previous lesson taught us how to count the elements of combined sets — unions, intersections, complements, differences. We now turn to a different family of counting questions: how many arrangements, choices, or outcomes does a structured situation produce?
Two simple but powerful rules suffice to handle a great many such questions: the sum rule, which counts when we face a choice between mutually exclusive alternatives; and the product rule, which counts when we make a sequence of independent choices. These rules are the foundation of elementary combinatorics, and they connect directly to the logical connectives we have been studying.
The Sum Rule
Suppose a task can be performed in one of two ways:
by Method 1, in any of \(m\) distinct manners, or
by Method 2, in any of \(n\) distinct manners,
where the two methods are mutually exclusive — no manner of performing the task counts as both Method 1 and Method 2. Then the total number of distinct manners in which the task can be performed is:
\[m + n\]
More generally, if a task can be performed by any one of \(k\) mutually exclusive methods, with \(n_1, n_2, \ldots, n_k\) distinct manners of performing each, then the total number of manners is:
\[n_1 + n_2 + \cdots + n_k\]
The Sum Rule as Disjoint Union
The sum rule is the disjoint union theorem of the previous lesson, applied to a counting situation. Let \(A\) be the set of manners of performing the task by Method 1 and \(B\) the set of manners by Method 2. Mutual exclusivity means \(A \cap B = \emptyset\). The total number of manners is the cardinality of \(A \cup B\), which by the disjoint union theorem is \(|A| + |B| = m + n\).
The sum rule is therefore not a new principle but a familiar one in different language. It is most useful when a counting problem naturally splits into cases — situations that share no overlap and exhaust all possibilities.
Sum Rule — Examples
A library has \(120\) novels and \(85\) volumes of poetry on its featured shelf. A reader wishes to borrow either a novel or a volume of poetry. The number of choices is \(120 + 85 = 205\).
A pizzeria offers \(8\) vegetarian pizzas and \(12\) non-vegetarian pizzas. A customer ordering one pizza has \(8 + 12 = 20\) options.
A traveller from Bucharest to Cluj may take the train (\(4\) daily departures) or the plane (\(3\) daily departures). The total number of daily travel options is \(4 + 3 = 7\). The two methods are mutually exclusive: a single journey is either by train or by plane, not both.
The Product Rule
Suppose a task is performed in two stages, performed in sequence:
Stage 1 can be carried out in \(m\) distinct manners, and
regardless of the outcome of Stage 1, Stage 2 can then be carried out in \(n\) distinct manners.
Then the total number of distinct manners in which the task can be performed is:
\[m \cdot n\]
More generally, for a task performed in \(k\) stages, where Stage \(i\) can be carried out in \(n_i\) distinct manners regardless of the outcomes of the earlier stages, the total number of manners is:
\[n_1 \cdot n_2 \cdots n_k\]
The Independence Condition
The phrase “regardless of the outcome of Stage 1” expresses an essential condition: the number of manners available at Stage 2 must not depend on what was chosen at Stage 1. If the choice at Stage 1 changes the number of options at Stage 2, the product rule does not apply directly.
For example, choosing a card from a deck (52 options) and then choosing a second different card (51 options regardless of which first card was chosen) gives \(52 \cdot 51\) ordered pairs. But choosing two specific items from a constrained list, where the first choice eliminates certain options at the second stage in a non-uniform way, requires more care.
Product Rule — Examples
A licence plate consists of \(2\) letters followed by \(3\) digits, with repetition allowed. With \(26\) letters and \(10\) digits, the number of possible licence plates is \(26 \cdot 26 \cdot 10 \cdot 10 \cdot 10 = 676{,}000\).
A restaurant menu offers \(4\) starters, \(6\) main courses, and \(3\) desserts. A complete meal consisting of one starter, one main course, and one dessert can be assembled in \(4 \cdot 6 \cdot 3 = 72\) ways.
A student has \(5\) different shirts and \(3\) different pairs of trousers. The number of distinct shirt-and-trousers combinations is \(5 \cdot 3 = 15\).
Cartesian Product
The Cartesian product of two sets \(A\) and \(B\), written \(A \times B\), is the set of all ordered pairs \((a, b)\) with \(a \in A\) and \(b \in B\):
\[A \times B \;=\; \{(a, b) \mid a \in A \text{ and } b \in B\}\]
An ordered pair \((a, b)\) is distinct from \((b, a)\) when \(a \neq b\); the order matters. The Cartesian product extends to any finite number of sets: \(A_1 \times A_2 \times \cdots \times A_k\) is the set of ordered \(k\)-tuples \((a_1, a_2, \ldots, a_k)\) with \(a_i \in A_i\) for each \(i\).
Cardinality of a Cartesian Product
For finite sets \(A_1, A_2, \ldots, A_k\):
\[|A_1 \times A_2 \times \cdots \times A_k| \;=\; |A_1| \cdot |A_2| \cdots |A_k|\]
In particular, for two sets, \(|A \times B| = |A| \cdot |B|\).
The Cartesian Product as Independent Stages
The cardinality formula for Cartesian products is the product rule in set-theoretic clothing. Constructing an ordered pair \((a, b) \in A \times B\) is a two-stage process: choose \(a \in A\) (\(|A|\) options), then independently choose \(b \in B\) (\(|B|\) options). The total number of pairs is \(|A| \cdot |B|\) by the product rule.
This perspective is one of the most useful tools in counting: a counting problem can often be transformed into the cardinality of a Cartesian product, after which the formula gives the answer immediately.
Sum and Product Rules: The Logical Correspondence
The two counting principles correspond exactly to the two main binary connectives of propositional logic:
Logic | Counting | Reading |
|---|---|---|
\(\lor\) (disjunction) | Sum rule (\(+\)) | “A or B” (mutually exclusive cases) |
\(\land\) (conjunction) | Product rule (\(\cdot\)) | “A and B” (independent stages) |
This is more than an analogy. When a counting problem is framed as “how many ways to do this or that?”, the disjoint union of the cases gives the sum. When framed as “how many ways to do this and then that?”, the Cartesian product of the stages gives the product. Identifying which connective governs the situation is often the decisive step in solving a counting problem.
Combining the Two Rules — Worked Example
A code consists of a single letter followed by either two digits or three digits. How many distinct codes are possible? (\(26\) letters and \(10\) digits available; repetitions allowed.)
The code is constructed in stages, but the second part of the code admits two mutually exclusive forms. We organise the count accordingly.
Method by sum and product rules. Let:
\(A_1\) = set of codes with one letter and two digits
\(A_2\) = set of codes with one letter and three digits
The two sets are disjoint (a code has either two digits or three, not both). By the product rule:
\[|A_1| \;=\; 26 \cdot 10 \cdot 10 \;=\; 2600 \qquad |A_2| \;=\; 26 \cdot 10 \cdot 10 \cdot 10 \;=\; 26000\]
By the sum rule:
\[|A_1 \cup A_2| \;=\; |A_1| + |A_2| \;=\; 2600 + 26000 \;=\; 28600\]
Hence \(28{,}600\) distinct codes are possible.
Connection to Computer Science
Counting principles are part of the everyday work of computer security. To estimate how hard it is to guess a password, one applies the product rule: a password of length \(k\) drawn from an alphabet of \(N\) symbols admits \(N^k\) possibilities. Increasing the length or expanding the alphabet multiplies the number of possibilities, which is why longer and more varied passwords are recommended.
Exercise 1
For each problem, compute the answer and identify which counting principle applies.
Exercise 2
Apply the sum or product rule.
Exercise 3
Decide whether each statement is true.
Critical Examination
A student is asked: in a class of \(20\) students, in how many ways can a president and a vice-president be chosen, the two roles being held by different students?
The student writes:
The president can be any of the \(20\) students, and the vice-president can also be any of the \(20\) students. By the product rule, the answer is \(20 \cdot 20 = 400\).
What has gone wrong?
Analysis
The student has applied the product rule but ignored the constraint that the two roles must be held by different students.
The product rule, as stated in this lesson, requires that the number of manners at each stage be the same regardless of the choices made at earlier stages. In this problem, choosing the president eliminates that student from the pool available for vice-president. The number of options at the second stage is therefore not \(20\) but \(19\) — whichever student became president, exactly one student is now ineligible for vice-president.
Crucially, although the identity of the ineligible student depends on who was chosen as president, the number of available options at the second stage is always \(19\). The independence condition required by the product rule is therefore satisfied for the count, even though it would not be satisfied for the identity. This is the precise sense in which the product rule applies:
\[\text{number of (president, vice-president) pairs} \;=\; 20 \cdot 19 \;=\; 380\]
The student’s answer of \(400\) overcounts by \(20\): the \(20\) pairs in which the same student plays both roles, which were forbidden by the problem.
The methodological lesson: when applying the product rule, count carefully the number of options available at each stage given the choices at the previous stages. If this count varies in a way that makes the independence condition fail, the product rule does not apply in its simple form, and the problem requires further analysis — sometimes by splitting into cases (sum rule) or by other methods. When in doubt, write out a small example by hand to verify that the count behaves as expected.
Summary
The sum rule: if a task can be performed by one of \(k\) mutually exclusive methods, with \(n_1, n_2, \ldots, n_k\) manners respectively, the total number of manners is \(n_1 + n_2 + \cdots + n_k\). It is the disjoint union theorem in counting language.
The product rule: if a task is performed in \(k\) independent stages, with \(n_1, n_2, \ldots, n_k\) manners at each stage (independent of the earlier choices), the total number of manners is \(n_1 \cdot n_2 \cdots n_k\).
The Cartesian product \(A_1 \times A_2 \times \cdots \times A_k\) is the set of ordered \(k\)-tuples drawn from these sets; its cardinality is \(|A_1| \cdot |A_2| \cdots |A_k|\), which is the set-theoretic statement of the product rule.
The logical correspondence: the sum rule mirrors disjunction (mutually exclusive cases joined by “or”); the product rule mirrors conjunction (independent stages joined by “and”).
The two rules combine: many problems decompose into stages (product) and cases (sum), in which case both rules apply within a single solution.
The product rule requires the independence condition: the number of options at each stage must not depend on the choices made at earlier stages. When this fails, the simple product formula does not apply.