Six Ways of Looking at Burtin's Lemma

In an article in this MONTHLY in 1953 Metropolis and Ulam asked for the expected number of components of the graph induced by a purely random mapping of a set of n points into itself [7]. This problem was solved one year later by L. Kruskal [6]. In 1955, L. Kac [4] computed the probability that this random graph is connected, that is, that the number of components is 1. In 1981, S. Ross [9] treated the same questions for more general random mappings in which the function values are independent and identically distributed but not necessarily uniform. The fundamental lemma of [9] had been proved earlier by the young Russian mathematician Y. D. Burtin, several months before his death in 1977 [2, Prop. 1]: