Let fn be the number of vertex labeled forests (acyclic graphs) on n vertices. In this paper we study the number-theoretic properties of the sequence (fn : n ≥ 1). First, we find recurrence congruences that relate fn+pk to fn, for all positive integers n and prime powers pk. We deduce that this sequence is ultimately periodic modulo every positive integer, and that every positive integer divides infinitely many terms of this sequence. More generally, we state and prove these results for sequences defined by a weighted generalization of fn, or equivalently, by a special evaluation of the Tutte polynomial of the complete graph Kn.
展开▼
