Additionally, the nature of the bijection itself often provides powerful insights into each or both of the sets.
The symmetry of the binomial coefficients states that 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.
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.
The most classical examples of bijective proofs in combinatorics include: