Before revision:  This paper presents dynamic-programming algorithms and proofs for exact inference in hierarchical clustering at small but useful scales. We are able to compute the partition function, MAP hierarchical clustering , and marginal probabilities of sub-hierarchies and clusters.
After revision:  This paper presents dynamic-programming algorithms and proofs for exact inference in hierarchical clustering based on a novel trellis data structure, and we prove that we can exactly compute the partition function, MAP hierarchical clustering , and marginal probabilities of sub-hierarchies and clusters.