MULTIPLICATION RULE

Tags: #◇Computer Science #◇STT101A #◇Conceptual #◇Multiplication Rule

---

◇Overview

In combinatorics, the Multiplication Rule (Rule of Product) states that if an operation can be broken into a sequence of $k$ ordered steps where Step $1$ has $n_1$ choices, Step $2$ has $n_2$ choices, ..., and Step $k$ has $n_k$ choices, the total number of ways to perform the entire operation is $n_1 \times n_2 \times \cdots \times n_k$.

◇Key Definitions

• Rule of Product: $|A_1 \times A_2 \times \cdots \times A_k| = n_1 \cdot n_2 \cdots n_k$.
• Sampling With Replacement: Each of the $r$ steps has $n$ choices, giving $n \times n \times \cdots \times n = n^r$ ordered tuples.
• Sampling Without Replacement: Step 1 has $n$ choices, Step 2 has $n-1$ choices, ..., Step $r$ has $n - r + 1$ choices, giving $P(n, r) = n(n-1)\cdots(n-r+1)$.

◇Worked Example

Problem: An IPv4 subnet host identifier has $8$ bits, each of which can be 0 or 1. How many total $8$-bit strings exist, and how many usable host addresses remain after excluding the network address (all 0s) and broadcast address (all 1s)?

Solution:

• By the Multiplication Rule across $8$ bit positions: $2^8 = 256$ total addresses.
• Subtracting the $2$ reserved addresses leaves $2^8 - 2 = 254$ usable host addresses.

◇References & Navigation

• Previous Topic: ◇Multiplicative Rule
• Next Topic: ◇Generalized Multiplication
• Related Notes: ◇Conditional Probability, ◇Independent Events