Bijective proof

In combinatorics, bijective proof is a proof technique that finds a bijective function (that is, a one-to-one and onto function) f : A → B between two finite sets A and B, or a size-preserving bijective function between two combinatorial classes, thus proving that they have the same number of elements, |A| = |B|. One place the technique is useful is where we wish to know the size of A, but can find no direct way of counting its elements. By establishing a bijection from A to some B solves the problem if B is more easily countable. Another useful feature of the technique is that the nature of the bijection itself often provides powerful insights into each or both of the sets. In combinatorics, bijective proof is a proof technique that finds a bijective function (that is, a one-to-one and onto function) f : A → B between two finite sets A and B, or a size-preserving bijective function between two combinatorial classes, thus proving that they have the same number of elements, |A| = |B|. One place the technique is useful is where we wish to know the size of A, but can find no direct way of counting its elements. By establishing a bijection from A to some B solves the problem if B is more easily countable. Another useful feature of the technique is that the nature of the bijection itself often provides powerful insights into each or both of the sets.