Abstract
We give formulas for calculating in polynomial time the number of ancestral reconstructions for a tree with binary leaf- and root labels for each number of 0 -> 1 and 1 -> 0 arcs. For trees of fixed degree, the corresponding numbers of 0 -> 0 and 1 -> 1 arcs can be deduced. We calculate intervals for the relative cost of 0 -> 1 and 1 -> 0 transitions over which the same labelings remain the cheapest.