 Double 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. In this technique, which van Lint & Wilson (2001) call “one of the most important tools in combinatorics,” one describes a finite set X 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.
Contents
Examples
Forming committees
One example of the double counting method counts the number of ways in which a committee can be formed from n people, allowing any number of the people (even zero of them) to be part of the committee. That is, one counts the number of subsets that an nelement set may have. One method for forming a committee is to ask each person to choose whether or not to join it. Each person has two choices – yes or no – and these choices are independent of those of the other people. Therefore there are 2 × 2 × ... × 2 = 2^{n} possibilities. Alternatively, one may observe that the size of the committee must be some number between 0 and n. For each possible size k, the number of ways in which a committee of k people can be formed from n people is the binomial coefficient
Therefore the total number of possible committees is the sum of binomial coefficients over k = 0, 1, 2, ... n. Equating the two expressions gives the identity
a special case of the binomial theorem. The committees counted in this way may also be interpreted as the vertices of a hypercube; a similar double counting method for higher dimensional hypercube features can be used to prove the more general identity
(Garbano, Malerba & Lewinter 2003; Klavžar 2006).
Handshaking lemma
Another theorem that is commonly proved with a double counting argument states that every undirected graph contains an even number of vertices of odd degree. That is, the number of vertices that have an odd number of incident edges must be even. In more colloquial terms, in a party of people some of whom shake hands, an even number of people must have shaken an odd number of other people's hands; for this reason, the result is known as the handshaking lemma.
To prove this by double counting, let d(v) be the degree of vertex v. The number of vertexedge incidences in the graph may be counted in two different ways: by summing the degrees of the vertices, or by counting two incidences for every edge. Therefore
where e is the number of edges. The sum of the degrees of the vertices is therefore an even number, which could not happen if an odd number of the vertices had odd degree. This fact, with this proof, appears in the 1736 paper of Leonhard Euler on the Seven Bridges of Königsberg that first began the study of graph theory.
Counting trees
What is the number T_{n} of different trees that can be formed from a set of n distinct vertices? Cayley's formula gives the answer T_{n} = n^{n − 2}. Aigner & Ziegler (1998) list four proofs of this fact; they write of the fourth, a double counting proof due to Jim Pitman, that it is “the most beautiful of them all.”
Pitman's proof counts in two different ways the number of different sequences of directed edges that can be added to an empty graph on n vertices to form from it a rooted tree. One way to form such a sequence is to start with one of the T_{n} possible unrooted trees, choose one of its n vertices as root, and choose one of the (n − 1)! possible sequences in which to add its n − 1 edges. Therefore, the total number of sequences that can be formed in this way is T_{n}n(n − 1)! = T_{n}n!.
Another way to count these edge sequences is to consider adding the edges one by one to an empty graph, and to count the number of choices available at each step. If one has added a collection of n − k edges already, so that the graph formed by these edges is a rooted forest with k trees, there are n(k − 1) choices for the next edge to add: its starting vertex can be any one of the n vertices of the graph, and its ending vertex can be any one of the k roots other than the root of the tree containing the starting vertex. Therefore, if one multiplies together the number of choices from the first step, the second step, etc., the total number of choices is
Equating these two formulas for the number of edge sequences results in Cayley's formula:
and
As Aigner and Ziegler describe, the formula and the proof can be generalized to count the number of rooted forests with k trees, for any k.
See also
Additional examples
 Vandermonde's identity, another identity on sums of binomial coefficients that can be proven by double counting.
 Square pyramidal number. The equality between the sum of the first n square numbers and a cubic polynomial can be shown by double counting the triples of numbers x, y, and z where z is larger than either of the other two numbers.
 Lubell–Yamamoto–Meshalkin inequality. Lubell's proof of this result on set families is a double counting argument on permutations, used to prove an inequality rather than an equality.
 Proofs of Fermat's little theorem. A divisibility proof by double counting: for any prime p and natural number A, there are A^{p} − A lengthp words over an Asymbol alphabet having two or more distinct symbols. These may be grouped into sets of p words that can be transformed into each other by circular shifts; these sets are called necklaces. Therefore, A^{p} − A = p × (number of necklaces) and is divisible by p.
 Proofs of quadratic reciprocity. A proof by Eisenstein derives another important numbertheoretic fact by double counting lattice points in a triangle.
Related topics
 Bijective proof. Where double counting involves counting one set in two ways, bijective proofs involve counting two sets in one way, by showing that their elements correspond oneforone.
 The inclusionexclusion principle, a formula for the size of a union of sets that may, together with another formula for the same union, be used as part of a double counting argument.
References
 Aigner, Martin; Ziegler, Günter M. (1998), Proofs from THE BOOK, SpringerVerlag. Double counting is described as a general principle on page 126; Pitman's double counting proof of Cayley's formula is on pp. 145–146.
 Euler, L. (1736), "Solutio problematis ad geometriam situs pertinentis", Commentarii Academiae Scientiarum Imperialis Petropolitanae 8: 128–140, http://math.dartmouth.edu/~euler/docs/originals/E053.pdf. Reprinted and translated in Biggs, N. L.; Lloyd, E. K.; Wilson, R. J. (1976), Graph Theory 1736–1936, Oxford University Press.
 Garbano, M. L.; Malerba, J. F.; Lewinter, M. (2003), "Hypercubes and Pascal's triangle: a tale of two proofs", Mathematics Magazine 76 (3): 216–217, doi:10.2307/3219324, JSTOR 3219324.
 Klavžar, Sandi (2006), "Counting hypercubes in hypercubes", Discrete Mathematics 306 (22): 2964–2967, doi:10.1016/j.disc.2005.10.036.
 van Lint, Jacobus H.; Wilson, Richard M. (2001), A Course in Combinatorics, Cambridge University Press, p. 4, ISBN 9780521006019.
Categories:
Wikimedia Foundation. 2010.
Look at other dictionaries:
Double counting — may refer to: Double counting (proof technique), a method in combinatorics that proves two expressions to be equal by demonstrating that they are different ways of counting the same set Double counting (fallacy), a fallacy in combinatorics and… … Wikipedia
Combinatorial proof — 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,… … Wikipedia
Bijective proof — In 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 … Wikipedia
Combinatorial principles — In 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.… … Wikipedia
List of mathematics articles (D) — NOTOC D D distribution D module D D Agostino s K squared test D Alembert Euler condition D Alembert operator D Alembert s formula D Alembert s paradox D Alembert s principle Dagger category Dagger compact category Dagger symmetric monoidal… … Wikipedia
Outline of discrete mathematics — The following outline is presented as an overview of and topical guide to discrete mathematics: Discrete mathematics – study of mathematical structures that are fundamentally discrete rather than continuous. In contrast to real numbers that have… … Wikipedia
List of basic discrete mathematics topics — Discrete mathematics, also called finite mathematics, is the study of mathematical structures that are fundamentally , in the sense of not supporting or requiring the notion of continuity. Most, if not all, of the objects studied in finite… … Wikipedia
List of combinatorics topics — This is a list of combinatorics topics.A few decades ago it might have been said that combinatorics is little more than a way to classify poorly understood problems, and some standard remedies. Great progress has been made since 1960.This page is … Wikipedia
Outline of combinatorics — See also: Index of combinatorics articles The following outline is presented as an overview of and topical guide to combinatorics: Combinatorics – branch of mathematics concerning the study of finite or countable discrete structures. Contents 1… … Wikipedia
BrouwerHilbert controversy — A foundational controversy in twentieth century history of mathematics opposed L. E. J. Brouwer, a supporter of intuitionism, and David Hilbert, the founder of formalism.BackgroundThe background for the controversy was set with David Hilbert s… … Wikipedia