Bijection
Also known as: one-to-one correspondence, bijective function
A bijection is a function that pairs every element of one set with exactly one element of another set, with nothing left unmatched on either side. Because the pairing is perfect, two finite sets linked by a bijection must have the same number of elements.
A function f from set A to set B is a bijection when it is both injective (one-to-one) and surjective (onto). Injective means no two elements of A map to the same element of B; surjective means every element of B gets hit by something in A. Put together, each element of A has exactly one partner in B and each element of B has exactly one partner in A — a perfect matching. Every bijection has an inverse function that undoes it, which is another way to recognize one.
Simple examples make the idea concrete. The function f(x) = 2x + 1 from the real numbers to the real numbers is a bijection, since every real output comes from exactly one input. The function f(x) = x² from the real numbers to the real numbers is not: it is neither injective (2 and −2 both map to 4) nor surjective (nothing maps to −1). Restricting the domain to x ≥ 0 and the codomain to y ≥ 0 makes it a bijection.
In competition math, bijections are a counting tool rather than an object of study. If a set is hard to count directly, you find a bijection to a set that is easy to count, and the answer transfers. A classic case: the number of ways to distribute 10 identical candies among 4 children corresponds one-to-one with arrangements of 10 stars and 3 bars in a row, so the count is C(13, 3). Another: the subsets of an n-element set correspond exactly with length-n strings of 0s and 1s, giving 2ⁿ subsets. The work lies in describing the correspondence and checking that it really is one-to-one and onto.
The AMC 8 and AMC 12 both reward this technique in their combinatorics and probability problems, where a well-chosen bijection can turn a messy case-by-case count into a single binomial coefficient. Recognizing when to reach for one is a large part of getting through counting problems quickly.
Key takeaways
- A bijection is a function that is both injective (one-to-one) and surjective (onto).
- Two finite sets connected by a bijection have exactly the same number of elements.
- Every bijection has an inverse function; functions that are not bijections do not.
- f(x) = 2x + 1 on the reals is a bijection; f(x) = x² on the reals is not.
- In combinatorics, bijections let you count a difficult set by counting an equivalent easy one, as in stars and bars.