On Cayley's formula for counting forests (Q912847)

In 1889, A. Cayley stated that (*) \(F(n,s)=sn^{n-s-1}\) where F(n,s) is the number of forests with n labelled vertices that consist of s distinct trees such that s specified vertices belong to distinct trees. When \(s=1\), one obtains Cayley's formula \(F(n,1)=n^{n-2}\) for the number of distinct labelled trees on n vertices. Formula (*) has been proven analytically under the assumption that Cayley's formula already holds. In this note the author proves (*) without assuming Cayley's formula by establishing a recurrence relation for F(n,s).