Combinatorial proof

Last updated May 24, 2023

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

A proof by double counting. A combinatorial identity is proven by counting the number of elements of some carefully chosen set in two different ways to obtain the different expressions in the identity. Since those expressions count the same objects, they must be equal to each other and thus the identity is established.
A bijective proof. Two sets are shown to have the same number of members by exhibiting a bijection, i.e. a one-to-one correspondence, between them.

The term "combinatorial proof" may also be used more broadly to refer to any kind of elementary proof in combinatorics. However, as Glass (2003) writes in his review of Benjamin & Quinn (2003) (a book about combinatorial proofs), these two simple techniques are enough to prove many theorems in combinatorics and number theory.

Example

An archetypal double counting proof is for the well known formula for the number ${\tbinom {n}{k}}$ of k-combinations (i.e., subsets of size k) of an n-element set:

{\binom {n}{k}}={\frac {n(n-1)\cdots (n-k+1)}{k(k-1)\cdots 1}}.

Here a direct bijective proof is not possible: because the right-hand side of the identity is a fraction, there is no set obviously counted by it (it even takes some thought to see that the denominator always evenly divides the numerator). However its numerator counts the Cartesian product of k finite sets of sizes n, n − 1, ..., n − k + 1, while its denominator counts the permutations of a k-element set (the set most obviously counted by the denominator would be another Cartesian product k finite sets; if desired one could map permutations to that set by an explicit bijection). Now take S to be the set of sequences of k elements selected from our n-element set without repetition. On one hand, there is an easy bijection of S with the Cartesian product corresponding to the numerator $n(n-1)\cdots (n-k+1)$ , and on the other hand there is a bijection from the set C of pairs of a k-combination and a permutation σ of k to S, by taking the elements of C in increasing order, and then permuting this sequence by σ to obtain an element of S. The two ways of counting give the equation

n(n-1)\cdots (n-k+1)={\binom {n}{k}}k!,

and after division by k! this leads to the stated formula for ${\tbinom {n}{k}}$ . In general, if the counting formula involves a division, a similar double counting argument (if it exists) gives the most straightforward combinatorial proof of the identity, but double counting arguments are not limited to situations where the formula is of this form.

Here is a simpler, more informal combinatorial proof of the same identity:

{\binom {n}{k}}k!(n-k)!=n!

Suppose that n people would like to enter a museum, but the museum only has room for k people. First choose which k people from among the n people will be allowed in. There are ${\tbinom {n}{k}}$ ways to do this by definition. Now order the k people into a single-file line so that they may pay one at a time. There are k! ways to permute this set of size k. Next, order the n − k people who must remain outside into a single-file line so that later they can enter one at a time, as the others leave. There are (n − k)! ways to do this. But now we have ordered the entire group of n people, something which can be done in n! ways. So both sides count the number of ways to order the n people. Division yields the well-known formula for ${\tbinom {n}{k}}$ .

The benefit of a combinatorial proof

Stanley (1997) gives an example of a combinatorial enumeration problem (counting the number of sequences of k subsets S₁, S₂, ... S_k, that can be formed from a set of n items such that the intersection of all the subsets is empty) with two different proofs for its solution. The first proof, which is not combinatorial, uses mathematical induction and generating functions to find that the number of sequences of this type is (2^k −1)ⁿ. The second proof is based on the observation that there are 2^k −1 proper subsets of the set {1, 2, ..., k}, and (2^k −1)ⁿ functions from the set {1, 2, ..., n} to the family of proper subsets of {1, 2, ..., k}. The sequences to be counted can be placed in one-to-one correspondence with these functions, where the function formed from a given sequence of subsets maps each element i to the set {j | i ∈ S_j}.

Stanley writes, “Not only is the above combinatorial proof much shorter than our previous proof, but also it makes the reason for the simple answer completely transparent. It is often the case, as occurred here, that the first proof to come to mind turns out to be laborious and inelegant, but that the final answer suggests a simple combinatorial proof.” Due both to their frequent greater elegance than non-combinatorial proofs and the greater insight they provide into the structures they describe, Stanley formulates a general principle that combinatorial proofs are to be preferred over other proofs, and lists as exercises many problems of finding combinatorial proofs for mathematical facts known to be true through other means.

The difference between bijective and double counting proofs

Stanley does not clearly distinguish between bijective and double counting proofs, and gives examples of both kinds, but the difference between the two types of combinatorial proof can be seen in an example provided by Aigner & Ziegler (1998), of proofs for Cayley's formula stating that there are n^n − 2 different trees that can be formed from a given set of n nodes. Aigner and Ziegler list four proofs of this theorem, the first of which is bijective and the last of which is a double counting argument. They also mention but do not describe the details of a fifth bijective proof.

The most natural way to find a bijective proof of this formula would be to find a bijection between n-node trees and some collection of objects that has n^n − 2 members, such as the sequences of n − 2 values each in the range from 1 to n. Such a bijection can be obtained using the Prüfer sequence of each tree. Any tree can be uniquely encoded into a Prüfer sequence, and any Prüfer sequence can be uniquely decoded into a tree; these two results together provide a bijective proof of Cayley's formula.

An alternative bijective proof, given by Aigner and Ziegler and credited by them to André Joyal, involves a bijection between, on the one hand, n-node trees with two designated nodes (that may be the same as each other), and on the other hand, n-node directed pseudoforests. If there are T_nn-node trees, then there are n²T_n trees with two designated nodes. And a pseudoforest may be determined by specifying, for each of its nodes, the endpoint of the edge extending outwards from that node; there are n possible choices for the endpoint of a single edge (allowing self-loops) and therefore nⁿ possible pseudoforests. By finding a bijection between trees with two labeled nodes and pseudoforests, Joyal's proof shows that T_n = n^n − 2.

Finally, the fourth proof of Cayley's formula presented by Aigner and Ziegler is a double counting proof due to Jim Pitman. In this proof, Pitman considers the sequences of directed edges that may be added to an n-node empty graph to form from it a single rooted tree, and counts the number of such sequences in two different ways. By showing how to derive a sequence of this type by choosing a tree, a root for the tree, and an ordering for the edges in the tree, he shows that there are T_nn! possible sequences of this type. And by counting the number of ways in which a partial sequence can be extended by a single edge, he shows that there are n^n − 2n! possible sequences. Equating these two different formulas for the size of the same set of edge sequences and cancelling the common factor of n! leads to Cayley's formula.

Related concepts

The principles of double counting and bijection used in combinatorial proofs can be seen as examples of a larger family of combinatorial principles, which include also other ideas such as the pigeonhole principle.
Proving an identity combinatorially can be viewed as adding more structure to the identity by replacing numbers by sets; similarly, categorification is the replacement of sets by categories.

Related Research Articles

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 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 combinatorial mathematics, the theory of combinatorial species is an abstract, systematic method for deriving the generating functions of discrete structures, which allows one to not merely count these structures but give bijective proofs involving them. Examples of combinatorial species are graphs, permutations, trees, and so on; each of these has an associated generating function which counts how many structures there are of a certain size. One goal of species theory is to be able to analyse complicated structures by describing them in terms of transformations and combinations of simpler structures. These operations correspond to equivalent manipulations of generating functions, so producing such functions for complicated structures is much easier than with other methods. The theory was introduced, carefully elaborated and applied by Canadian researchers around André Joyal.

In combinatorial mathematics, the Catalan numbers are a sequence of natural numbers that occur in various counting problems, often involving recursively defined objects. They are named after the French-Belgian mathematician Eugène Charles Catalan.

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, 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.

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, Cayley's formula is a result in graph theory named after Arthur Cayley. It states that for every positive integer $, the number of trees on labeled vertices is .$

In the mathematical field of graph theory, Kirchhoff's theorem or Kirchhoff's matrix tree theorem named after Gustav Kirchhoff is a theorem about the number of spanning trees in a graph, showing that this number can be computed in polynomial time from the determinant of a submatrix of the Laplacian matrix of the graph; specifically, the number is equal to any cofactor of the Laplacian matrix. Kirchhoff's theorem is a generalization of Cayley's formula which provides the number of spanning trees in a complete graph.

In proving results in combinatorics several useful combinatorial rules or combinatorial principles are commonly recognized and used.

In combinatorial mathematics, the Prüfer sequence of a labeled tree is a unique sequence associated with the tree. The sequence for a tree on n vertices has length n − 2, and can be generated by a simple iterative algorithm. Prüfer sequences were first used by Heinz Prüfer to prove Cayley's formula in 1918.

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

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.

<span class="mw-page-title-main">Ordered Bell number</span> Number of weak orderings

In number theory and enumerative combinatorics, the ordered Bell numbers or Fubini numbers count the number of weak orderings on a set of n elements. Starting from n = 0, these numbers are

<span class="mw-page-title-main">Handshaking lemma</span> Every graph has evenly many odd vertices

In graph theory, a branch of mathematics, the handshaking lemma is the statement that, in every finite undirected graph, the number of vertices that touch an odd number of edges is even. For example, if there is a party of people who shake hands, the number of people who shake an odd number of other people's hands is even. The handshaking lemma is a consequence of the degree sum formula, also sometimes called the handshaking lemma, according to which the sum of the degrees equals twice the number of edges in the graph. Both results were proven by Leonhard Euler (1736) in his famous paper on the Seven Bridges of Königsberg that began the study of graph theory.

<span class="mw-page-title-main">Pseudoforest</span> Graph with one cycle per component

In graph theory, a pseudoforest is an undirected graph in which every connected component has at most one cycle. That is, it is a system of vertices and edges connecting pairs of vertices, such that no two cycles of consecutive edges share any vertex with each other, nor can any two cycles be connected to each other by a path of consecutive edges. A pseudotree is a connected pseudoforest.

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 combinatorics, the Schröder–Hipparchus numbers form an integer sequence that can be used to count the number of plane trees with a given set of leaves, the number of ways of inserting parentheses into a sequence, and the number of ways of dissecting a convex polygon into smaller polygons by inserting diagonals. These numbers begin

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

Aigner, Martin; Ziegler, Günter M. (1998), Proofs from THE BOOK , Springer-Verlag, pp. 141–146, ISBN 3-540-40460-0 .

Benjamin, Arthur T.; Quinn, Jennifer J. (2003), Proofs that Really Count: The Art of Combinatorial Proof, Dolciani Mathematical Expositions, vol. 27, Mathematical Association of America, ISBN 978-0-88385-333-7 .

Glass, Darren (2003), Read This: Proofs that Really Count, Mathematical Association of America .

Stanley, Richard P. (1997), Enumerative Combinatorics, Volume I, Cambridge Studies in Advanced Mathematics, vol. 49, Cambridge University Press, pp. 11–12, ISBN 0-521-55309-1 .

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.