קולוקוויום במדעי המחשב - Cayley's Formula: A Page from THE BOOK

Abstract:

Cayley's formula from the 19th century (for counting the number of labeled trees on a given finite set) is one of the oldest and most celebrated results in graph theory.  An apparently new proof of this formula of N. Dershowitz and the speaker is going to be published in a forthcoming issue of the American Mathematical Monthly. This new proof  seems to be the simplest and shortest among the many different known proofs of this formula. In this talk the new proof will be presented, as well as the long process that led to it through many years of teaching Cayley's Formula in our course on discrete mathematics. I shall also  use this opportunity to say a few words about  the nature and content of this course (to which the discovery of the new proof is strongly connected).

The talk will be self-contained, and no knowledge will be assumed beyond mathematical induction and some very fundamental notions of naive set theory.