Reference articles on history, science, culture and more
Surprise meSurprise meSubscribe
Encyclopedia

Bijective proof

Technique for proving sets have equal size

Wikipedia contributorsAdapted for Fathomly · View authors
1 min read
Source updated August 15, 2026

In combinatorics, bijective proof is a proof technique for proving that two sets have equally many elements, or that the sets in two combinatorial classes have equal size, by finding a bijective function that maps one set one-to-one onto the other. This technique can be useful as a way of finding a formula for the number of elements of certain sets, by corresponding them with other sets that are easier to count. Additionally, the nature of the bijection itself often provides powerful insights into each or both of the sets.

01Basic examples

Proving the symmetry of the binomial coefficients

The symmetry of the binomial coefficients states that

{n \choose k}={n \choose n-k}.

This means that there are exactly as many combinations of k things in a set of size n as there are combinations of n − k things in a set of size n.

The key idea of the bijective proof may be understood from a simple example: selecting k children to be rewarded with ice cream cones, out of a group of n children, has exactly the same effect as choosing instead the n − k children to be denied ice cream cones.

02Other examples

Problems that admit bijective proofs are not limited to binomial coefficient identities. As the complexity of the problem increases, a bijective proof can become very sophisticated. This technique is particularly useful in areas of discrete mathematics such as combinatorics, graph theory, and number theory.

The most classical examples of bijective proofs in combinatorics include:

Watch videos about Bijective proofExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Bijective proof”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.

Continue exploring

Related topics

Binomial theorem

In elementary algebra, the binomial theorem describes the algebraic expansion of powers of a binomial. According to the theorem, the power ⁠ ( x + y ) n {\displaystyle \textstyle (x+y)^{n}} ⁠ expands into a polynomial with terms of the form ⁠ a x k y m {\displaystyle \textstyle ax^{k}y^{m}} ⁠, where the exponents ⁠ k {\displaystyle k} ⁠ and ⁠ m {\displaystyle m} ⁠ are nonnegative integers satisfying ⁠ k + m = n {\displaystyle k+m=n} ⁠ and the coefficient ⁠ a {\displaystyle a} ⁠ of each term is a specific positive integer depending on ⁠ n {\displaystyle n} ⁠ and ⁠ k {\displaystyle k} ⁠.

Schröder-Bernstein theorem

In set theory, the Schröder-Bernstein theorem states that, if there exist injective functions f : A → B and g : B → A between the sets A and B, then there exists a bijective function h : A → B. In terms of the cardinality of the two sets, this classically implies that if |A| ≤ |B| and |B| ≤ |A|, then |A| = |B|; that is, A and B are equipotent. This is a useful feature in the ordering of cardinal numbers.

Double counting (proof technique)

In combinatorics, double counting, also called counting in two ways, is a combinatorial proof technique for showing that two expressions are equal by demonstrating that they are two ways of counting the size of one set. In this technique, which van Lint & Wilson call "one of the most important tools in combinatorics", one describes a finite set from two perspectives leading to two distinct expressions for the size of the set.