[FOM] Counting arguments
urquhart at cs.toronto.edu
Tue Oct 28 16:09:40 EST 2003
I think it is rather trivially true that
any probabilistic argument in finite
combinatorics can be rewritten as
a counting argument. This is because
probability in finite spaces is simply
the ratio of two finite cardinalities.
Bela Bollobas puts it succinctly in his book
"Graph Theory" p. 123.
It should be noted that we never
use more than the convenient *language*
of probability theory, since all the
probability arguments we need can be
replaced by *counting* the numbers of
objects in various sets.
However, from the heuristic point of view,
the language of probability theory is extremely
helpful. Joel Spencer puts it rather well in
his "Ten Lectures on the Probabilistic Method"
When presented with the probabilistic method,
the probabilist J. Doob remarked: "Well, this
is very nice, but it's really just a counting
argument." With the advantage of hindsight I
respectfully disagree. As we shall see, ...,
notions of probability permeate the probabilistic
method. To reduce the arguments to counting,
although it is technically feasible, would be
to remove the heart of the argument.
This matter of heuristic suggestiveness is very important
for mathematical practice, though I don't think we can
say much about it with current tools of mathematical logic.
More information about the FOM