Rule of product

In simplest terms, the rule of product states that the number of ways to do something multiplied by the number of ways to do another thing is the total number of ways to do both. Here's a more formal definition involving sets:

The cardinality of the Cartesian product of finite sets $A_1, ... A_n$ is the product of their individual cardinalities: $$|A_1 \times ... \times A_n| = |A_1| * ... * |A_n|$$

⚠ In keeping with the whole "number of ways to do a thing" metaphor, imagine each set above as the set of all the different ways to do its associated "thing."

If you can still remember what a Cartesian product is, then you'll know $A_1 \times ... \times A_n$ is a set of $n$-tuples (essentially sequences). Therefore, $|A_1 \times ... \times A_n|$ is equal to the number of different sequences (in the order $ a_1, ... a_n$) that can be made from the elements of $A_1, ... A_n.$

For example, imagine you have a closet of $2$ hats $\set{\text{top hat}, \text{baseball cap}}$, $3$ shirts $\set{\text{red}, \text{green}, \text{blue}}$, and $1$ pair of pants $\set{\text{jeans}}.$ You can only wear $1$ of each type of clothing. How many unique outfits can you make? Well, according to the rule of product, you can make exactly $2 * 3 * 1 = 6.$ One such outfit would be $(\text{baseball cap}, \text{red}, \text{jeans}).$

Now, here's a computing example. How many unique $4$-bit binary strings are there? To calculate the number of possible strings of length $n$, where each character is chosen from a finite alphabet $\sum$, by the rule of product: $|\sum^n| = \underbrace{|\sum \times ... \times \sum|}_{n \, \text{times}} = \underbrace{|\sum| * ... * |\sum|}_{n \, \text{times}}$

In this case, $\sum = \set{0, 1}$, meaning $|\sum| = 2$, and we already know $n = 4$ because we're focused on $4$-bit (length $4$) binary strings. So, there are $|\set{0, 1}^4| = 2 * 2 * 2 * 2 = 16$ binary strings of length $4.$ One such binary string would be $1001.$ The general formula for the number of unique binary strings of length $n$ is $2^n.$

Even for strings where the alphabets vary among characters, it's still possible to count how many exist. Let's say a password string must be $4$ letters followed by $3$ numbers (decimal digits). By the rule of product, there are $26 * 26 * 26 * 26 * 10 * 10 * 10 = 26^4 * 10^3 = 456,976,000$ possible passwords, where the alphabet for letters is $\set{a, ... z}$ and the alphabet for numbers is $\set{0, ... 9}.$ One such password would be $abcd123.$

Contents

Generalized rule of product

The generalized rule of product is simply a rewording of the rule of product that may make counting some sets more intuitive:

Imagine that it takes $k$ decisions to fully specify an item. The set which contains every possible item that can be specified is $S.$ If the following statements are true:

There are $n_1$ choices for the $1$st decision.
For every way you can make the $1$st decision, there are $n_2$ choices for the $2$nd decision.
For every way you can make the first $2$ decisions, there are $n_3$ choices for the $3$rd decision.
For every way you can make the first $(k - 1)$ decisions, there are $n_k$ choices for the $k$th decision.

This means the number of choices for each decision does not depend on what previous decisions were made, and therefore: $$|S| = n_1 * ... * n_k$$

Let's go back to the example where you must count how many unique outfits can be made from a closet of $2$ hats $\set{\text{top hat}, \text{baseball cap}}$, $3$ shirts $\set{\text{red}, \text{green}, \text{blue}}$, and $1$ pair of pants $\set{\text{jeans}}.$ When a type of clothing (whether it's the hat, shirt, or pants) is specified for an outfit, the number of options you have for the other types of clothing that have yet to be chosen for the outfit are unaffected. Therefore, according to the generalized rule of product, the number of unique outfits you can make is precisely $2 * 3 * 1 = 6.$

Pretend that, in a contest between $10$ people, the top $3$ get $1$st, $2$nd, and $3$rd place trophies. How many ways are there to give out these $3$ trophies, such that nobody gets more than $1$ trophy? Well, initially, $10$ people are eligible for $1$st place, then, whoever wins the $1$st place trophy cannot receive another trophy, so you have $9$ choices for $2$nd place. After that, $8$ choices for $3$rd place. The result given by the generalized rule of product is $10 * 9 * 8 = 720.$ (This is a $3$-permutation.)z

Here's a really simple example. How many ways can $4$ people sit together on a bench? You've got $4$ choices for the leftmost person, $3$ for the next, $2$ after that, and then $1$ more choice for the rightmost person. In total, that's $4 * 3 * 2 * 1 = 24$ ways to sit together. Curiously, that is equal to $4!$ exactly. That's because it is actually a permutation.

Logic & Proofs

Integer • Rational number • Inequality • Real number • Theorem • Proof • Statement • Proof by exhaustion • Universal generalization • Counterexample • Existence proof • Existential instantiation • Axiom • Logic • Truth • Proposition • Compound proposition • Logical operation • Logical equivalence • Tautology • Contradiction • Logic law • Predicate • Domain • Quantifier • Argument • Rule of inference • Logical proof • Direct proof • Proof by contrapositive • Irrational number • Proof by contradiction • Proof by cases • Summation • Disjunctive normal form

Set Theory

Set • Element • Empty set • Universal set • Subset • Power set • Cartesian product • String • Binary string • Empty string • Set operation • Set identity • Set proof

Functions

Function • Floor function • Ceiling function • Inverse function

Algorithms

Algorithm • Pseudocode • Command • Asymptotic notation • Time complexity • Atomic operation • Brute-force algorithm

Relations

Relation • Reflexive relation • Symmetric relation • Transitive relation • Relation composition • Equivalence relation • Equivalence class

Number Theory

Integer division • Linear combination • Division algorithm • Modular arithmetic • Prime factorization • Greatest common divisor • Least common multiple • Primality test • Factoring algorithm • Euclid's theorem • Prime number theorem • Euclidean algorithm

Induction

Proof by induction • Fibonacci sequence • Proof by strong induction • Well-ordering principle • Sequence • Factorial • Recursive definition

Combinatorics

Rule of product • Rule of sum • Bijection rule • Permutation • Combination • Complement rule • Experiment • Outcome • Sample space • Event • Probability • Probability distribution • Uniform distribution • Multiset • Sixfold way • Inclusion-exclusion principle • Pigeonhole principle

Graph Theory

Graph • Walk • Subgraph • Regular graph • Complete graph • Empty graph • Cycle graph • Hypercube graph • Bipartite graph • Component • Eulerian circuit • Eulerian trail • Hamiltonian cycle • Hamiltonian path • Tree • Huffman tree • Substring • Forest • Path graph • Star • Spanning tree • Weighted graph • Minimum spanning tree • Greedy algorithm • Prim's algorithm

Recursion

Recursion • Recursive algorithm • Correctness proof • Divide-and-conquer algorithm • Sorting algorithm • Merge sort