The Bijection Principle

Combinatorics · Axiom Academy

LESSON The Bijection Principle A powerful counting technique: instead of counting set A directly, find a bijection to set B and count B instead The Bijection Principle states that if there exists a bijection (one-to-one and onto function) between sets A and B, then these sets have the same cardinality. A function f: A → B is a bijection if it is: One-to-one (Injective): Different elements in A map to different elements in B Onto (Surjective): Every element in B is mapped to by some element in A This means every element in A pairs with exactly one unique element in B, and vice versa. Think of it as a perfect matching between the two sets. 2. Why Bijections Are Powerful The beauty of the Bijection Principle is that it lets us count a simpler set instead of the original set. Often, we can find a creative bijection between a complicated set and one that's much easier to count. Example: Binary Strings and Subsets Consider the question: How many subsets does an n-element set have? This can be hard to count directly. But notice that each subset of 1, 2, ..., n corresponds to a binary string of length n, where the i-th bit is 1 if element i is in the subset, and 0 otherwise. Lattice Paths and Bit Sequences Consider paths on a grid from (0,0) to (m,n) using only right (R) and up (U) moves. How many such paths exist?

This is the written version of the interactive lesson above. See the full Combinatorics course.