Minimally colored trees

Each edge in a weighted colored tree has a nonnegative weight corresponding to the colors of its incident vertices. The sum of these weights is the weight of the tree. Algorithms of O(n) are known to find minimal colorings, that is, to assign colors from a given finite set to the vertices of a tree so as to minimize the weight of the tree. In this paper generating functions are used to find the number of minimal colorings and the average weight of each edge over such colorings, also using O(n) operations. Applications to evolutionary trees are given.