FACTOID # 27: If you're itching to live in a trailer park, hitch up your home and head to South Carolina, where a whopping 18% of residences are mobile homes.
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 


FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:



(* = Graphable)



Encyclopedia > Double counting


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. 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|. Combinatorics is a branch of mathematics that studies finite collections of objects that satisfy specified criteria. ... In mathematics, a set can be thought of as any well-defined collection of distinct things considered as a whole. ...

Such a proof is sometimes called a bijective proof because the process necessarily provides a bijective mapping between two sets. Each of the two sets is closely related to its respective expression. This free bijective mapping may very well be non-trivial; in certain theorems, the bijective mapping is more relevant than the expressions' equivalence. In mathematics, a bijection, bijective function, or one-to-one correspondence is a function that is both injective (one-to-one) and surjective (onto), and therefore bijections are also called one_to_one and onto. ... In mathematics, a bijection, bijective function, or one-to-one correspondence is a function that is both injective (one-to-one) and surjective (onto), and therefore bijections are also called one_to_one and onto. ...


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) = 2n 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 nCr (this is a well known result; see binomial coefficient). Therefore the total number of ways is nCr summed over r = 0, 1, 2, ... n. In mathematics, particularly in combinatorics, the binomial coefficient of the natural number n and the integer k is defined to be the natural number and (Here, for a natural number m, m! denotes the factorial of m. ...

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 One major problem that has plagued graph theory since its inception is the lack of consistency in terminology. ...

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. In mathematics, any integer (whole number) is either even or odd. ...

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. The word probability derives from the Latin probare (to prove, or to test). ...

See also

  Results from FactBites:
Precision Weighing Balances - Parts Counting Scales Balances (894 words)
Counting scale are your answer to bad counts and customer complaints about shortages.
Sartorius CB counting scales are accurate, fast and affordable and the unique sample dial is a turn for the better.
This unit features 1 in 400,000 internal count, a huge 16.7" x 20.7" stainless steel platform, an operates on either AC adapter or the internal rechargeable battery allow you to move the scale to the job and not be restricted [Read More....]
Double counting - Wikipedia, the free encyclopedia (119 words)
Double counting (proof technique), a proof technique in combinatorics whereby one set is counted in two different ways
Double counting (fallacy), a fallacy in combinatorics and probability theory whereby objects are counted more than once
Double counting (accounting), an error in accounting whereby a transaction is counted more than once
  More results at FactBites »



Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m