Bijective proof

Last updated February 28, 2024

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.

Basic 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$ .

A bijective proof

The key idea of the 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.

More abstractly and generally,^[1] the two quantities asserted to be equal count the subsets of size $k$ and $n - k$ , respectively, of any $n$ -element set $S$ . Let $A$ be the set of all $k$ -element subsets of $S$ , the set $A$ has size ${\tbinom {n}{k}}.$ Let $B$ be the set of all $n-k$ subsets of $S$ , the set B has size ${\tbinom {n}{n-k}}$ . There is a simple bijection between the two sets $A$ and $B$ : it associates every $k$ -element subset (that is, a member of $A$ ) with its complement, which contains precisely the remaining $n - k$ elements of $S$ , and hence is a member of $B$ . More formally, this can be written using functional notation as, $f : A \to B$ defined by $f (X) = X c$ for $X$ any $k$ -element subset of $S$ and the complement taken in $S$ . To show that f is a bijection, first assume that $f (X 1) = f (X 2)$ , that is to say, $X 1 c = X 2 c$ . Take the complements of each side (in $S$ ), using the fact that the complement of a complement of a set is the original set, to obtain $X 1 = X 2$ . This shows that $f$ is one-to-one. Now take any $n-k$ -element subset of $S$ in $B$ , say $Y$ . Its complement in $S$ , $Y c$ , is a $k$ -element subset, and so, an element of $A$ . Since $f (Y c) = (Y c) c = Y$ , $f$ is also onto and thus a bijection. The result now follows since the existence of a bijection between these finite sets shows that they have the same size, that is, ${\tbinom {n}{k}}={\tbinom {n}{n-k}}$ .

Other 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:

Prüfer sequence, giving a proof of Cayley's formula for the number of labeled trees.
Robinson-Schensted algorithm, giving a proof of Burnside's formula for the symmetric group.
Conjugation of Young diagrams, giving a proof of a classical result on the number of certain integer partitions.
Bijective proofs of the pentagonal number theorem.
Bijective proofs of the formula for the Catalan numbers.

Related Research Articles

<span class="mw-page-title-main">Bijection</span> One-to-one correspondence

A bijection, bijective function, or one-to-one correspondence between two mathematical sets is a function such that each element of the second set is mapped to from exactly one element of the first set. Equivalently, a bijection is a relation between two sets such that each element of either set is paired with exactly one element of the other set.

In mathematics, the binomial coefficients are the positive integers that occur as coefficients in the binomial theorem. Commonly, a binomial coefficient is indexed by a pair of integers $n \geq k \geq 0$ and is written $It is the coefficient of the x k term in the polynomial expansion of the binomial power (1 + x) n; this coefficient can be computed by the multiplicative formula$

In elementary algebra, the binomial theorem (or binomial expansion) describes the algebraic expansion of powers of a binomial. According to the theorem, it is possible to expand the polynomial $(x + y) n$ into a sum involving terms of the form $ax b y c$ , where the exponents $b$ and $c$ are nonnegative integers with $b + c = n$ , and the coefficient $a$ of each term is a specific positive integer depending on $n$ and $b$ . For example, for $n = 4$ ,

In mathematics, a combination is a selection of items from a set that has distinct members, such that the order of selection does not matter. For example, given three fruits, say an apple, an orange and a pear, there are three combinations of two that can be drawn from this set: an apple and a pear; an apple and an orange; or a pear and an orange. More formally, a k-combination of a set S is a subset of k distinct elements of S. So, two combinations are identical if and only if each combination has the same members. If the set has n elements, the number of k-combinations, denoted by $or, is equal to the binomial coefficient$

In mathematics, an injective function (also known as injection, or one-to-one function ) is a function $f$ that maps distinct elements of its domain to distinct elements; that is, $x 1 \neq x 2$ implies $f (x 1) \neq f (x 2)$ . (Equivalently, $f (x 1) = f (x 2)$ implies $x 1 = x 2$ in the equivalent contrapositive statement.) In other words, every element of the function's codomain is the image of at most one element of its domain. The term one-to-one function must not be confused with one-to-one correspondence that refers to bijective functions, which are functions such that each element in the codomain is an image of exactly one element in the domain.

In mathematics, the Erdős–Ko–Rado theorem limits the number of sets in a family of sets for which every two sets have at least one element in common. Paul Erdős, Chao Ko, and Richard Rado proved the theorem in 1938, but did not publish it until 1961. It is part of the field of combinatorics, and one of the central results of extremal set theory.

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 (2001) 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. Since both expressions equal the size of the same set, they equal each other.

In combinatorics, a branch of mathematics, the inclusion–exclusion principle is a counting technique which generalizes the familiar method of obtaining the number of elements in the union of two finite sets; symbolically expressed as

In mathematics, the term combinatorial proof is often used to mean either of two types of mathematical proof:

Sperner's theorem, in discrete mathematics, describes the largest possible families of finite sets none of which contain any other sets in the family. It is one of the central results in extremal set theory. It is named after Emanuel Sperner, who published it in 1928.

In mathematics, and in particular in combinatorics, the combinatorial number system of degree k, also referred to as combinadics, or the Macaulay representation of an integer, is a correspondence between natural numbers N and k-combinations. The combinations are represented as strictly decreasing sequences c_k > ... > c₂ > c₁ ≥ 0 where each c_i corresponds to the index of a chosen element in a given k-combination. Distinct numbers correspond to distinct k-combinations, and produce them in lexicographic order. The numbers less than $correspond to all k -combinations of {0, 1, ..., n - 1}. The correspondence does not depend on the size n of the set that the k -combinations are taken from, so it can be interpreted as a map from N to the k -combinations taken from N; in this view the correspondence is a bijection.$

In mathematics, the Gaussian binomial coefficients are q-analogs of the binomial coefficients. The Gaussian binomial coefficient, written as $or, is a polynomial in q with integer coefficients, whose value when q is set to a prime power counts the number of subspaces of dimension k in a vector space of dimension n over, a finite field with q elements; i.e. it is the number of points in the finite Grassmannian .$

In the mathematical field of enumerative combinatorics, identities are sometimes established by arguments that rely on singling out one "distinguished element" of a set.

In mathematics, Pascal's rule is a combinatorial identity about binomial coefficients. It states that for positive natural numbers n and k,

In graph theory, the Kneser graph $K (n, k)$ (alternatively $KG n, k$ ) is the graph whose vertices correspond to the $k$ -element subsets of a set of $n$ elements, and where two vertices are adjacent if and only if the two corresponding sets are disjoint. Kneser graphs are named after Martin Kneser, who first investigated them in 1956.

In combinatorics, the twelvefold way is a systematic classification of 12 related enumerative problems concerning two finite sets, which include the classical problems of counting permutations, combinations, multisets, and partitions either of a set or of a number. The idea of the classification is credited to Gian-Carlo Rota, and the name was suggested by Joel Spencer.

Enumerative combinatorics is an area of combinatorics that deals with the number of ways that certain patterns can be formed. Two examples of this type of problem are counting combinations and counting permutations. More generally, given an infinite collection of finite sets S_i indexed by the natural numbers, enumerative combinatorics seeks to describe a counting function which counts the number of objects in S_n for each n. Although counting the number of elements in a set is a rather broad mathematical problem, many of the problems that arise in applications have a relatively simple combinatorial description. The twelvefold way provides a unified framework for counting permutations, combinations and partitions.

In the context of combinatorial mathematics, stars and bars is a graphical aid for deriving certain combinatorial theorems. It was popularized by William Feller in his classic book on probability. It can be used to solve many simple counting problems, such as how many ways there are to put $n$ indistinguishable balls into $k$ distinguishable bins.

In combinatorial mathematics, a partial permutation, or sequence without repetition, on a finite set S is a bijection between two specified subsets of S. That is, it is defined by two subsets U and V of equal size, and a one-to-one mapping from U to V. Equivalently, it is a partial function on S that can be extended to a permutation.

In the mathematical study of combinatorics on words, a parameter word is a string over a given alphabet having some number of wildcard characters. The set of strings matching a given parameter word is called a parameter set or combinatorial cube. Parameter words can be composed, to produce smaller subcubes of a given combinatorial cube. They have applications in Ramsey theory and in computer science in the detection of duplicate code.

References

↑ Mazur, David R. (2010), Combinatorics / A Guided Tour, The Mathematical Association of America, p. 28, ISBN 978-0-88385-762-5

External links

"Division by three" – by Doyle and Conway.
"A direct bijective proof of the hook-length formula" – by Novelli, Pak and Stoyanovsky.
"Bijective census and random generation of Eulerian planar maps with prescribed vertex degrees" – by Gilles Schaeffer.
"Kathy O'Hara's Constructive Proof of the Unimodality of the Gaussian Polynomials" – by Doron Zeilberger.
"Partition Bijections, a Survey" – by Igor Pak.
Garsia-Milne Involution Principle – from MathWorld.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Mazur, David R. (2010), Combinatorics / A Guided Tour, The Mathematical Association of America, p. 28, ISBN 978-0-88385-762-5

[1]