6.1 Principles of Counting

Principles of Counting

Counting in combinatorics often relies on three foundational principles:

1. The Bijection Principle states that if there’s a one-to-one correspondence between two sets $A$ and $B$ (i.e., $f:A\to B$), then they have the same number of elements, such that
   $|A|=|B|.$
2. The Multiplication Principle states that given a sequence of $k$ independent choices with $n_1$ options for the first, $n_2$ for the second, and so on, then the number of possible sequences is
   $N=n_1\times n_2\times \cdots \times n_k.$
3. The Division Principle states that if each element of an unordered set $B$ corresponds to exactly $m$ ordered arrangements in set $A$ (i.e., an $m$-to-$1$ mapping $f:A\to B$, then  
   $|B|=\frac{|A|}{m}.$

Intuition

Let’s rephrase these principles in an easy to understand language, so the latter notes in this section become easier to understand:

1. Bijection rule: This principle allows you to count a tricky set by pairing it with an easier-to-count set. It’s the backbone of many combinatorial proofs and combinatorial identities.

2. Multiplication rule: This rule applies when you’re counting ordered sequences of choices. You multiply because each choice expands the number of possible outcomes.

3. Division rule: Converts an ordered count into an unordered count. You divide because multiple ordered arrangements correspond to the same unordered group.