3
$\begingroup$
  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!

3 Answers 3

4

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.

3

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|$.

  • 0
    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 di$f$fere$n$t ways of cou$n$ting the same thing.2012-11-23
2

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.

  • 3
    Not in the combinatorial context, which is what Tim is talking about.2012-11-01