Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
  1. Does "counting argument" mean a proof of some statements by counting something?
  2. Is "counting argument" same as "double counting"? Or does it include both double counting and bijective proof?

I found some relevant Wikipedia articles Combinatorial proof and Combinatorial principles. But not sure the meaning of counting argument.

Thanks!

share|improve this question
add comment

3 Answers 3

up vote 4 down vote accepted

Counting argument isn’t really a well-defined term, but I’d understand it to mean a proof that two expressions are equal by showing that they are two different ways of counting the same thing. Wikipedia calls this double counting, which I consider a very poorly chosen name: to me double counting refers to counting some things twice and therefore having to correct the total by subtracting the amount of over-counting. I prefer to call it simply counting the same thing in two different ways.

However, I can imagine someone using the term counting argument to include bijective proofs as well as proofs by counting the same thing in two ways.

share|improve this answer
add comment

Counting argument can mean counting the same thing in two different ways to give rise to two different expressions that then have to be equal. For example, we have $\binom{n}{k}=\binom{n}{n-k}$.

Double counting can mean counting the same object twice so that one has to subtract to get the correct number. For example, we have $|A\cup B|=|A|+|B|-|A\cap B|$.

share|improve this answer
    
That's my take on it, though in come contexts (e.g., enumerative combinatorics), double counting can mean proving equality, say a = b, by showing that a and b each represent different ways of counting the same thing. –  amWhy Nov 23 '12 at 0:16
add comment

Tim,

Remember, any set of finite size is trivially countable.

Typically a "counting argument" refers to listing elements of a set in a meaningful way to show that the set is the the same size as the natural numbers or not the same size as the natural numbers.

share|improve this answer
3  
Not in the combinatorial context, which is what Tim is talking about. –  Brian M. Scott Nov 1 '12 at 20:10
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.