v1 · padrão canônico

Lesson 36 — Fundamental Counting Principle

FCP: if a task has k independent stages with n₁, n₂, …, nₖ options each, the total number of possible sequences is the product. Additive principle, factorial, and applications.

Used in: High school year 1 (age 15) · Equiv. Math A Japanese · Equiv. Class 10 German

N = n_1 \times n_2 \times \cdots \times n_k

The Fundamental Counting Principle: if a task divides into $k$ independent stages, with $n_i$ choices at the $i$ -th stage, the total number of possible sequences is the product $n_1 \times n_2 \times \cdots \times n_k$ . The connector "AND" between stages generates multiplication; the connector "OR" between mutually exclusive alternatives generates addition.

Choose your door

Rigorous notation, full derivation, hypotheses

Rigorous statement and additive principle

Multiplicative Principle (FCP)

"If you have $m$ ways to do one thing and $n$ ways to do another, then there are $m \cdot n$ ways to do both things." — OpenStax College Algebra 2e, §11.5

Formal justification: the set of all sequences is the Cartesian product $E_1 \times E_2 \times \cdots \times E_k$ , and $|A \times B| = |A| \cdot |B|$ (proved by induction). The FCP is exactly this theorem.

Additive Principle

Connector between stages	Operation
"AND" — sequential independent stages	multiplication
"OR" — mutually exclusive alternatives	addition

"The Addition Principle states that if there are $m$ outcomes in event $A$ and $n$ outcomes in event $B$ , and $A$ and $B$ are mutually exclusive, then there are $m + n$ outcomes in event $A$ or $B$ ." — OpenStax College Algebra 2e, §11.5

Factorial

Tree of possibilities

A decision tree with $k$ levels represents the FCP graphically: each node at level $i$ generates $n_i$ children. The total number of leaves is $n_1 \times n_2 \times \cdots \times n_k$ .

Tree with 3 options at the 1st level and 2 at the 2nd level: 6 leaves = 3 × 2. The FCP in action.

Functions and subsets via FCP

Total functions $f: A \to B$ with $|A| = m,\, |B| = n$ : $n^m$ (each element of $A$ has $n$ independent images).
Total subsets of $S$ with $|S| = n$ : $2^n$ (each element is included or excluded).
Injective functions $f: A \to B$ ( $m \leq n$ ): $n \cdot (n-1) \cdots (n-m+1) = \frac{n!}{(n-m)!}$ — basis of arrangement (Lesson 37).

Worked examples

Example— 2· FCP with three stages — vehicle plate

Problem: An old-standard vehicle plate (before Mercosur) consisted of 3 letters followed by 4 numeric digits. Assuming 26 letters and digits 0-9 with repetition allowed, how many distinct plates were possible?

Strategy: 7 independent stages — 3 for letter choice and 4 for digit choice. Apply the FCP.

Solution:

Letters: each of the 3 positions has 26 options. Subtotal: $26^3 = 17\,576$ .
Digits: each of the 4 positions has 10 options. Subtotal: $10^4 = 10\,000$ .
FCP: $26^3 \times 10^4 = 17\,576 \times 10\,000 = 175\,760\,000$ .

Verification: Order of magnitude: $\approx 1.8 \times 10^8$ . Brazil had around 100 million vehicles in 2019 — the space of $1.8 \times 10^8$ plates was sufficient. Consistent with the historical fact that the system worked for decades.

Source. OpenStax College Algebra 2e, §11.5 — license CC-BY 4.0.

Example— 3· Additive principle — mutually exclusive alternatives

Problem: A student wants to go from school to home using public transportation. He can take one of 3 available buses OR one of 2 subway lines that make the trip. In how many ways can he make the trip?

Strategy: Bus and subway are alternative means (exclusive between themselves — he takes one OR the other, not both). Apply the additive principle.

Solution:

The two alternatives are mutually exclusive (the student uses exactly one means of transportation):

$N = 3 + 2 = 5 \text{ ways}$

Caution: if the problem were "take a bus AND then a subway" (two sequential stages), the total would be $3 \times 2 = 6$ . The connector "OR" (alternative) generates sum; the connector "AND" (sequence) generates product.

Source. Book of Proof, 3rd ed., §3.1 — Richard Hammack, license CC-BY-ND.

Example— 5· Password with mixed restrictions — with and without restriction on 1st position

Problem: A system requires passwords of 6 characters formed from lowercase letters (a-z, 26 options) and digits (0-9, 10 options), with repetition allowed. How many passwords are possible if: (a) there is no additional restriction; (b) the password must start with a letter?

Strategy: Apply the FCP directly in (a). For (b), fix the restriction on the first character before multiplying.

Solution:

(a) No restriction: each of the 6 positions accepts any of the $26 + 10 = 36$ alphanumeric characters.

$N_a = 36^6 = 2\,176\,782\,336 \approx 2.2 \times 10^9$

(b) First position must be a letter: the 1st position has 26 options (letters only); the other 5 positions maintain 36 options each.

$N_b = 26 \times 36^5 = 26 \times 60\,466\,176 = 1\,572\,120\,576 \approx 1.6 \times 10^9$

Verification: $N_b / N_a = 26/36 \approx 0.72$ — passwords starting with a letter represent 72% of the total, consistent with $26/36$ of the 36 options being letters.

Source. OpenStax College Algebra 2e, §11.5 — license CC-BY 4.0.

Exercise list

44 exercises · 11 with worked solution (25%)

Application 27Understanding 6Modeling 5Challenge 3Proof 3

Sources for this lesson

OpenStax College Algebra 2e — Jay Abramson et al. · OpenStax · 2022 · EN · CC-BY 4.0 · §11.5 (Counting Principles). Primary source.
Book of Proof, 3rd ed. — Richard Hammack · 2018, 3rd ed. · EN · CC-BY-ND · Chapter 3 (Counting), §3.1 (Multiplication Principle), §3.2 (Lists and Functions). Primary source.
Wikibooks — Elementary Mathematics / Combinatorics — collaborative · PT-BR · CC-BY-SA · FCP, factorial, Brazilian applications.