[FOM] Counting arguments

Alasdair Urquhart 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"
p. 2:

	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 mailing list