  In this paper, we show that calculating the partition function of optimal
medians of binary strings with Hamming distance is \#P-complete for several
weight functions. The case when the weight function is the factorial function
has application in bioinformatics. In that case, the partition function counts
the most parsimonious evolutionary scenarios on a star tree under several
models in bioinformatics. The results are extended to binary trees and we show
that it is also \#P-complete to calculate the most parsimonious evolutionary
scenarios on an arbitrary binary tree under the substitution model of
biological sequences and under the Single Cut-or-Join model for genome
rearrangements.
