Note—Derivation from Queueing Theory of an Identity Related to Abel's Generalization of the Binomial Theorem, which is Useful in Graph Theory

Abstract

A well-known theorem of graph theory gives a simple formula for the calculation of the number of spanning trees of a complete graph with n labeled vertices. A well-known proof of this theorem uses a combinatorial identity, related to Abel's generalization of the binomial theorem, that is difficult to prove from first principles. It is the purpose of this note to observe that this identity is an easy consequence of an analysis of the busy period for the single-server queue with Poisson input and constant service times.