FUNDAMENTAL PRINCIPLE OF COUNTING

Tags: #◇Computer Science #◇STT101A #◇Conceptual #◇Fundamental Principle of Counting

---

◇Overview

The Fundamental Principle of Counting (Basic Multiplication Principle / Rule of Product) states that if a sequential process consists of $k$ stages where Stage 1 has $n_1$ possible outcomes, and for each outcome of the preceding stages Stage $i$ has $n_i$ possible outcomes, then the total number of distinct composite outcomes is the product:
$N = n_1 \times n_2 \times \cdots \times n_k$

◇Key Definitions

• Two-Stage Rule of Product: If task $A$ can be performed in $m$ ways and for each of those ways task $B$ can be performed in $n$ ways, the sequence $(A, B)$ can be performed in $m \times n$ ways.
• Cartesian Product Interpretation: For finite sets $A_1, A_2, \dots, A_k$, $|A_1 \times A_2 \times \cdots \times A_k| = |A_1| \cdot |A_2| \cdots |A_k|$.
• Tree Diagram Uniformity: Every node at depth $i-1$ must have the same branching factor $n_i$ (even if the specific set of options changes, as in sampling without replacement where $n_1 = n, n_2 = n-1, \dots$).

◇Worked Example

Problem: Philippine license plates in a certain format consist of $3$ uppercase English letters ($26$ possibilities each) followed by $4$ digits ($0$–$9$, $10$ possibilities each).

1. If repetition of letters and digits is allowed: $26^3 \times 10^4 = 17,576 \times 10,000 = 175,760,000$.
2. If no letter or digit may be repeated: $(26 \times 25 \times 24) \times (10 \times 9 \times 8 \times 7) = 15,600 \times 5,040 = 78,624,000$.

◇References & Navigation

• Previous Topic: ◇Counting Techniques
• Next Topic: ◇Counting by Cases
• Related Notes: ◇Mutually Exclusive Events, ◇Permutations