Added to Favorites

Related Searches

Nearby Words

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. We describe a finite set X from two perspectives leading to two distinct expressions. Through the two perspectives, we demonstrate that each is to equal |X|.## Examples

### Forming committees

For instance, consider the number of ways in which a committee can be formed from n people, with from 0 through to n members:### 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### Sum of consecutive integers

Suppose we have an (n + 1)×(n + 1) square of points. The number of points on the diagonal is exactly n + 1, and clearly the number of points S that are strictly above the diagonal equals the number of points strictly below the diagonal, so the total number of points in the square is n + 1 + 2S. On the other hand, the total number of points in the square is (n + 1)^{2}, so
## Further examples

## See also

## References

The process necessarily provides a bijective mapping from the set to itself. This free bijection may very well be non-trivial; in certain theorems, the bijective mapping is more relevant than the expressions' equivalence.

Method 1: There are two possibilities for each person - they may or may not be on the committee. Therefore there are 2 × 2 × ... × 2 (n times) = 2^{n} 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 k people can be formed from n people is the binomial coefficient

- $\{n\; choose\; k\}.$

Equating the two expressions gives

- $sum\_\{k=0\}^n\; \{n\; choose\; k\}\; =\; 2^n.$

- $sum\_v\; d(v)\; =\; 2e,$

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.

- $(n+1)^2\; =\; n+1+2S$,

- $n(n+1)\; =\; 2S$,

- $S\; =\; sum\_\{k=1\}^n\{k\}\; =\; frac\{n(n+1)\}\{2\}.$

- The third proof of the formula for Catalan numbers.
- Proof of Sperner's lemma.

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)

This article is licensed under the GNU Free Documentation License.

Last updated on Thursday October 02, 2008 at 21:01:25 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

This article is licensed under the GNU Free Documentation License.

Last updated on Thursday October 02, 2008 at 21:01:25 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

Copyright © 2014 Dictionary.com, LLC. All rights reserved.