A NEW PROOF OF CAYLEYS FORMULA FOR COUNTING LABELED TREES

We give a new proof of Cayley's formula, which states that the number of labeled trees on n nodes is n(n-2). This proof uses a difficult com binatorial identity, and it could equally well be regarded as a proof of this identity that uses Cayley's formula. The proof proceeds by cou nting labeled rooted trees with n vertices and j improper edges, where an improper edge is one whose endpoint closer to the root has a large r label than some vertex in the subtree rooted on the edge. (C) 1995 A cademic Press, Inc.