nLab bijective proof




In enumerative combinatorics, a “bijective proof” refers to a basic method of counting the number of structures of a certain type supported on a finite set of underlying points, by analyzing structure in two different ways. It is really a special case of “categorification”: an identity a=ba = b where aa and bb are natural number expressions is proved by taking underlying cardinalities of a bijection ABA \cong B between sets of structures, hence the name. (If taking cardinalities is an example of “decategorifying”, then going the other way from a=ba = b to ABA \cong B would be “categorifying” or promoting an equation to an isomorphism.)

In some sense this is what the theory of species is all about: formalizing the operations adhering to bijective proofs. Often bijective proofs give an impression of elegance or enlightenment: rather than prove natural number or polynomial identities through acts of symbolic manipulation, one sees the identity by drawing pictures of structures that the two sides of the identity are counting.


For the moment we’ll just jot down some possible examples for illustrating the method; these are to be filled in later, or to be linked to other nLab articles where the bijective proof is given.

Binomial identity

See for now binomial theorem.

qq-binomial identity

For more details, see the Wikipedia article.

Algebraically, one may introduce the qq-binomial coefficients (nk) q\binom{n}{k}_q by introducing a qq-affine plane (or quantum affine plane, to be connected with quantum affine algebra) and its associated (non-commutative) algebra

k[x,y] q=kx,y/(yx=qxy)k[x, y]_q = k\langle x, y \rangle/(y x = q x y)

where qkq \in k is a parameter, and then writing (x+y) n= k=0 n(nk) qx ky nk(x + y)^n = \sum_{k = 0}^n \binom{n}{k}_q x^k y^{n-k}.

However, an illuminating combinatorial interpretation of the qq-binomial coefficients is that they count points in a Grassmannian consisting of kk-dimensional linear subspaces of an nn-dimensional vector space 𝔽 q n\mathbb{F}_q^n over a finite field 𝔽 q\mathbb{F}_q of cardinality qq. This interpretation can be used to provide a bijective proof of the qq-Pascal identity

(nk) q=(n1k) q+q nk(n1k1) q.\binom{n}{k}_q = \binom{n-1}{k}_q + q^{n-k}\binom{n-1}{k-1}_q.

For, if we choose a standard affine hyperplane H={x n=1}H = \{x_n = 1\} in 𝔽 q n\mathbb{F}_q^n, then any linear kk-plane WW in 𝔽 q n\mathbb{F}_q^n either intersects HH in an affine (k1)(k-1)-plane in the affine (n1)(n-1)-space, or intersects HH in the empty set, i.e., WW is contained in the linear space {x n=0}\{x_n = 0\}. The number of WW satisfying the latter condition is (n1k) q\binom{n-1}{k}_q, and the number of WW satisfying the former is in bijection with the number of (k1)(k-1)-dimensional affine subspaces of 𝔽 q n1\mathbb{F}_q^{n-1}, which is q n1q^{n-1} times the number of linear subspaces (n1k1) q\binom{n-1}{k-1}_q divided by q k1q^{k-1}, the number of translations which stabilize a given affine subspace. (Maybe to be rewritten later.)

Counting trees: Cayley’s theorem

Cayley’s theorem, here not to be confused with Cayley’s observation that every group (monoid) is a subgroup (submonoid) of a permutation group (endofunction monoid), says that the number of tree structures on an nn-element set {x 1,,x n}\{x_1, \ldots, x_n\} is n n2n^{n-2}.

There are many proofs of this fact in the literature. One, due to Gilbert Labelle and made popular by André Joyal, proceeds by establishing a bijection between trees equipped with a pair (x i,x j)(x_i, x_j) of nodes (allowing x i=x jx_i = x_j) and the number of endofunctions on X={x 1,,x n}X = \{x_1, \ldots, x_n\}.

On the one hand, such a structure (T,x i,x j)(T, x_i, x_j) on XX can be identified with a linearly ordered set (the path PP from x ix_i to x jx_j in TT) together with, for each node yy along that path, a rooted tree structure T yT_y consisting of nodes xXx \in X for which the shortest path in TT from xx to PP ends at yy. (As a subgraph of TT, this naturally forms a tree T yT_y rooted at yy.) Thus, such a structure (T,x i,x j)(T, x_i, x_j) on XX determines and is determined by an equivalence relation EE on XX, a rooted tree structure on each equivalence class, and a linear ordering of the set X/EX/E of equivalence classes.

On the other hand, each endofunction on XX, say f:XXf: X \to X, has an eventual image or stable set stab(f)= n0f n(X)stab(f) = \bigcap_{n \geq 0} f^n(X), on which ff acts by a permutation (i.e., bijectively). For each ystab(f)y \in stab(f), there is a rooted tree T yT_y which consists of all xXx \in X for which the set of iterates x,f(x),f 2(x),x, f(x), f^2(x), \ldots first lands in stab(f)stab(f) at yy. Thus an endofunction on XX determines and is determined by an equivalence relation EE on XX, a rooted tree structure on each equivalence class, and a permutation on the set X/EX/E of equivalence classes.

Since the number of permutations on X/EX/E is equinumerous with the number of linear orderings of X/EX/E, we conclude that the set of “bipointed tree” structures on XX is equinumerous with the set of endofunctions on XX. Thus the number of bipointed tree structures (T,x i,x j)(T, x_i, x_j) on XX is n nn^n, and therefore the number of tree structures TT on XX is n n2n^{n-2}.

Vandermonde identity

Stirling number identities

Polynomial identities

One method for proving polynomial identities (equations p=qp = q between polynomials p,q[x 1,,x k]p, q \in \mathbb{C}[x_1, \ldots, x_k] in several variables) is first to give a bijective proof for the special case in which natural numbers m im_i are substituted for the variables x ix_i, and then reason that there are enough natural numbers that the polynomial identity must hold generally.

More formally, two polynomials are equal, p(x 1,,x k)=q(x 1,,x k)p(x_1, \ldots, x_k) = q(x_1, \ldots, x_k), if p(m 1,,m k)=q(m 1,,m k)p(m_1, \ldots, m_k) = q(m_1, \ldots, m_k) for all choices of natural numbers m im_i. Relatedly, the set k k\mathbb{N}^k \subseteq \mathbb{C}^k is Zariski-dense (i.e., the closure of k\mathbb{N}^k in k\mathbb{C}^k equipped with the Zariski topology is all of k\mathbb{C}^k).

This is intuitively obvious of course. As a public service, we prove a more general result.


Suppose BB is an infinite subset of an integral domain AA. Then a polynomial p(x 1,,x k)A[x 1,,x k]p(x_1, \ldots, x_k) \in A[x_1, \ldots, x_k] is uniquely determined by its values it takes at arguments b 1,,b kBb_1, \ldots, b_k \in B.


It suffices to show that if p(b 1,,b k)=0p(b_1, \ldots, b_k) = 0 for every choice of b iBb_i \in B, then p=0p = 0. We prove this by induction on kk. The case k=0k = 0 is trivial.

Assuming the assertion as induction hypothesis for case kk, suppose pA[x 1,,x k,x k+1]p \in A[x_1, \ldots, x_k, x_{k+1}] satisfies p(b 1,,b k,b)=0p(b_1, \ldots, b_k, b) = 0 for all choices b iBb_i \in B and bBb \in B. Then by induction, for each fixed bBb \in B the polynomial p(x 1,,x k,b)A[x 1,,x k]p(x_1, \ldots, x_k, b) \in A[x_1, \ldots, x_k] is identically zero. Thus if FF is the field of fractions of A[x 1,,x k]A[x_1, \ldots, x_k], and if we regard pp as an element of the Euclidean domain F[x k+1]F[x_{k+1}] under the obvious embedding

A[x 1,,x k,x k+1]A[x 1,,x k][x k+1]F[x k+1],A[x_1, \ldots, x_k, x_{k+1}] \cong A[x_1, \ldots, x_k][x_{k+1}] \hookrightarrow F[x_{k+1}],

then pp has infinitely many roots bb in AA and thus in FF, forcing pp to be identically zero.

Last revised on August 26, 2018 at 12:15:59. See the history of this page for a list of all contributions to it.