Combinatorial proof
Encyclopedia
In mathematics
, the term combinatorial proof is often used to mean either of two types of proof
of an identity
in enumerative combinatorics
that either states that two sets of combinatorial configurations, depending on one or more parameters, have the same number of elements (for all values of the parameters), or gives a formula for the number of one such set of configurations in terms of the parameters:
The restriction on the counting methods in double counting is to avoid that any (non combinatorial) argument showing that X and Y have the same size could trivially be turned into a double counting argument, by saying on one hand X has as many elements as X, and on the other hand it has (by the given argument) as many elements as Y. In a sense a double counting argument then always corresponds to a bijective proof, since the bijections from S to the sets counted by the two numbers found can be composed to give a bijection between those sets. The distinction with a bijective proof comes from the circumstance that the introduction of an intermediate set S may be needed to make the bijections obvious, and that the bijection established by double counting may not correspond directly to the identity to be proved, for instance if it requires simplification to obtain the latter.
An archetypal double counting proof is for the well known formula for the number
of k-combination
s (i.e., subsets of size k) of an n-element set:
Here a direct bijective proof is not possible, because the right-hand side of the identity being 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, , ..., , while its denominator counts the permutations of a k-element set (the set most obviously counted 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 without repetition of elements selected from our n-element set. On one hand there is an easy bijection of S with the Cartesian product corresponding to the numerator
, and on the other hand there is a bijection from the set of pairs of a k-combination C 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
and after division by k! this leads to the stated formula for
. 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.
The term "combinatorial proof" may also be used more broadly to refer to any kind of elementary proof
in combinatorics. However, as writes in his review of (a book about combinatorial proofs), these two simple techniques are enough to prove many of the important theorems in combinatorics and number theory.
gives an example of a combinatorial enumeration problem (counting the number of sequences of k subsets S1, S2, ... Sk, that can be formed from a set of n items such that the subsets have an empty common intersection) with two different proofs for its solution. The first proof, which is not combinatorial, uses mathematical induction
and generating function
s to find that the number of sequences of this type is (2k −1)n. The second proof is based on the observation that there are 2k −1 proper subsets of the set {1, 2, ..., k}, and (2k −1)n 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 ∈ Sj}.
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.
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 nn − 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
pseudoforest
s. If there are Tn n-node trees, then there are n2Tn 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 nn possible pseudoforests. By finding a bijection between trees with two labeled nodes and pseudoforests, Joyal's proof shows that Tn = nn − 2.
Finally, the fourth proof of Cayley's formula presented by Aigner and Ziegler is a double counting proof due to Jim Pitman, presented in more detail in Double counting (proof technique)#Counting trees. 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 Tnn! 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 nn − 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.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, the term combinatorial proof is often used to mean either of two types of proof
Mathematical proof
In mathematics, a proof is a convincing demonstration that some mathematical statement is necessarily true. Proofs are obtained from deductive reasoning, rather than from inductive or empirical arguments. That is, a proof must demonstrate that a statement is true in all cases, without a single...
of an identity
Identity (mathematics)
In mathematics, the term identity has several different important meanings:*An identity is a relation which is tautologically true. This means that whatever the number or value may be, the answer stays the same. For example, algebraically, this occurs if an equation is satisfied for all values of...
in enumerative combinatorics
Enumerative combinatorics
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...
that either states that two sets of combinatorial configurations, depending on one or more parameters, have the same number of elements (for all values of the parameters), or gives a formula for the number of one such set of configurations in terms of the parameters:
- A bijective proofBijective proofIn combinatorics, bijective proof is a proof technique that finds a bijective function f : A → B between two sets A and B, 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...
, which exhibits a bijectionBijectionA bijection is a function giving an exact pairing of the elements of two sets. A bijection from the set X to the set Y has an inverse function from Y to X. If X and Y are finite sets, then the existence of a bijection means they have the same number of elements...
, i.e. a one-to-one correspondence, between the two sets, or (in the case of a formula) between the given set and a set obviously counted by the formula.
- A proof by double countingDouble counting (proof technique)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...
. Some combinatorial set S, often different from the ones in question, is counted in two different ways, and from the equality of the numbers so found the desired identity is deduced. The two ways of counting S must each be by establishing a bijection of S with a set obviously counted by the number found.
The restriction on the counting methods in double counting is to avoid that any (non combinatorial) argument showing that X and Y have the same size could trivially be turned into a double counting argument, by saying on one hand X has as many elements as X, and on the other hand it has (by the given argument) as many elements as Y. In a sense a double counting argument then always corresponds to a bijective proof, since the bijections from S to the sets counted by the two numbers found can be composed to give a bijection between those sets. The distinction with a bijective proof comes from the circumstance that the introduction of an intermediate set S may be needed to make the bijections obvious, and that the bijection established by double counting may not correspond directly to the identity to be proved, for instance if it requires simplification to obtain the latter.
An archetypal double counting proof is for the well known formula for the number
of k-combinationCombination
In mathematics a combination is a way of selecting several things out of a larger group, where order does not matter. In smaller cases it is possible to count the number of combinations...
s (i.e., subsets of size k) of an n-element set:
Here a direct bijective proof is not possible, because the right-hand side of the identity being 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
Cartesian product
In mathematics, a Cartesian product is a construction to build a new set out of a number of given sets. Each member of the Cartesian product corresponds to the selection of one element each in every one of those sets...
of k finite sets of sizes n, , ..., , while its denominator counts the permutations of a k-element set (the set most obviously counted 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 without repetition of elements selected from our n-element set. On one hand there is an easy bijection of S with the Cartesian product corresponding to the numerator
, and on the other hand there is a bijection from the set of pairs of a k-combination C 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 equationand after division by k! this leads to the stated formula for
. 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.The term "combinatorial proof" may also be used more broadly to refer to any kind of elementary proof
Elementary proof
In mathematics, an elementary proof is a mathematical proof that only uses basic techniques. More specifically, the term is used in number theory to refer to proofs that make no use of complex analysis. For some time it was thought that certain theorems, like the prime number theorem, could only be...
in combinatorics. However, as writes in his review of (a book about combinatorial proofs), these two simple techniques are enough to prove many of the important theorems in combinatorics and number theory.
The benefit of a combinatorial proof
gives an example of a combinatorial enumeration problem (counting the number of sequences of k subsets S1, S2, ... Sk, that can be formed from a set of n items such that the subsets have an empty common intersection) with two different proofs for its solution. The first proof, which is not combinatorial, uses mathematical induction
Mathematical induction
Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers...
and generating function
Generating function
In mathematics, a generating function is a formal power series in one indeterminate, whose coefficients encode information about a sequence of numbers an that is indexed by the natural numbers. Generating functions were first introduced by Abraham de Moivre in 1730, in order to solve the general...
s to find that the number of sequences of this type is (2k −1)n. The second proof is based on the observation that there are 2k −1 proper subsets of the set {1, 2, ..., k}, and (2k −1)n 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 ∈ Sj}.
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 , of proofs for Cayley's formula stating that there are nn − 2 different treesTree (graph theory)
In mathematics, more specifically graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree...
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 nn − 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
Prüfer sequence
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...
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
André Joyal
André Joyal is a professor of mathematics at the Université du Québec à Montréal who works on category theory. Joyal was born in Drummondville . He has three children and lives in Montreal.- Main research :...
, 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
Directed graph
A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...
pseudoforest
Pseudoforest
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...
s. If there are Tn n-node trees, then there are n2Tn 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 nn possible pseudoforests. By finding a bijection between trees with two labeled nodes and pseudoforests, Joyal's proof shows that Tn = nn − 2.
Finally, the fourth proof of Cayley's formula presented by Aigner and Ziegler is a double counting proof due to Jim Pitman, presented in more detail in Double counting (proof technique)#Counting trees. 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 Tnn! 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 nn − 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 principlesCombinatorial principlesIn proving results in combinatorics several useful combinatorial rules or combinatorial principles are commonly recognized and used.The rule of sum, rule of product, and inclusion-exclusion principle are often used for enumerative purposes. Bijective proofs are utilized to demonstrate that two sets...
, 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, categorificationCategorificationIn mathematics, categorification refers to the process of replacing set-theoretic theorems by category-theoretic analogues. Categorification, when done successfully, replaces sets by categories, functions with functors, and equations by natural isomorphisms of functors satisfying additional...
is the replacement of sets by categories.