Bijective proof

In combinatorics, double counting, also called two-way counting, is a proof technique that involves counting the size of a set in two ways in order to show that the two resulting expressions for the size of the set are equal. Such a proof is sometimes called a bijective proof, when it depends on showing the existence of a bijective mapping. That is, we may consider what we are doing to be taking a finite set X and counting it by method A and then method B; or we may also take two sets X and Y and count them both, then show by means of a bijection f from X to Y that the results are the same. The abstract difference in presentation can usually be absorbed in the freedom to count in various ways.

Example

For instance, consider the number of ways in which a committee can be formed from a total of n people:

Method 1: There are two possibilities for each person - they may or may not be on the committee. Therefore there are a total of 2 × 2 × ... × 2 (n times) = 2ⁿ possibilities.

Method 2: The size of the committee must be some number between 0 and n. The number of ways in which a committee of r people can be formed from a total of n people is ⁿC_r (this is a well known result; see binomial coefficient). Therefore the total number of ways is ⁿC_r summed over r = 0, 1, 2, ... n.

Equating the two expressions gives

Handshaking lemma

An example of a theorem that is commonly proved with a double counting argument is the theorem that every graph contains an even number of vertices of odd degree. Let d(v) be the degree of vertex v. Every edge of the graph is incident to exactly two vertices, so by counting the number of edges incident to each vertex, we have counted each edge exactly twice. 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.

Another meaning

Double counting is also a fallacy in which, when counting events or occurrences in probability or in other areas, a solution counts events two or more times, resulting in an erroneous number of events or occurrences which is higher than the true result. For example, what is the probability of seeing a 5 when throwing a pair of dice? The erroneous argument goes as follows: The first die shows a 5 with probability 1/6; the second die shows a 5 with probability 1/6; therefore the probability of seeing a 5 is 1/6 + 1/6 = 1/3. However, the correct answer is 11/36, because the erroneous argument has double-counted the event where both dice show fives.

See also

• combinatorial principles
• inclusion-exclusion principle