Combinatorial proof

From Wikipedia for FEVERv2
Jump to navigation Jump to search

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

Combinatorial proof_unordered_list_0

  • 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.Combinatorial proof_item_0_0
  • 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.Combinatorial proof_item_0_1

The term "combinatorial proof" may also be used more broadly to refer to any kind of elementary proof in combinatorics. Combinatorial proof_sentence_1

However, as writes in his review of (a book about combinatorial proofs), these two simple techniques are enough to prove many theorems in combinatorics and number theory. Combinatorial proof_sentence_2

Example Combinatorial proof_section_0

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

The benefit of a combinatorial proof Combinatorial proof_section_1

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. Combinatorial proof_sentence_4

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 −1). Combinatorial proof_sentence_5

The second proof is based on the observation that there are 2 −1 proper subsets of the set {1, 2, ..., k}, and (2 −1) functions from the set {1, 2, ..., n} to the family of proper subsets of {1, 2, ..., k}. Combinatorial proof_sentence_6

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}. Combinatorial proof_sentence_7

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. Combinatorial proof_sentence_8

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. Combinatorial proof_sentence_9

The difference between bijective and double counting proofs Combinatorial proof_section_2

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 n different trees that can be formed from a given set of n nodes. Combinatorial proof_sentence_10

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. Combinatorial proof_sentence_11

They also mention but do not describe the details of a fifth bijective proof. Combinatorial proof_sentence_12

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 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. Combinatorial proof_sentence_13

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. Combinatorial proof_sentence_14

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. Combinatorial proof_sentence_15

If there are Tn n-node trees, then there are nTn trees with two designated nodes. Combinatorial proof_sentence_16

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. Combinatorial proof_sentence_17

By finding a bijection between trees with two labeled nodes and pseudoforests, Joyal's proof shows that Tn = n. Combinatorial proof_sentence_18

Finally, the fourth proof of Cayley's formula presented by Aigner and Ziegler is a double counting proof due to Jim Pitman. Combinatorial proof_sentence_19

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. Combinatorial proof_sentence_20

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! Combinatorial proof_sentence_21

possible sequences of this type. Combinatorial proof_sentence_22

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! Combinatorial proof_sentence_23

possible sequences. Combinatorial proof_sentence_24

Equating these two different formulas for the size of the same set of edge sequences and cancelling the common factor of n! Combinatorial proof_sentence_25

leads to Cayley's formula. Combinatorial proof_sentence_26

Related concepts Combinatorial proof_section_3

Combinatorial proof_unordered_list_1

  • 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.Combinatorial proof_item_1_2
  • 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.Combinatorial proof_item_1_3

Credits to the contents of this page go to the authors of the corresponding Wikipedia page: proof.