  In this paper we consider two aspects of the inverse problem of how to
construct merge trees realizing a given barcode. Much of our investigation
exploits a recently discovered connection between the symmetric group and
barcodes in general position, based on the simple observation that death order
is a permutation of birth order. The first important outcome of our study is a
clear combinatorial distinction between the space of phylogenetic trees (as
defined by Billera, Holmes and Vogtmann) and the space of merge trees. Generic
BHV trees on $n+1$ leaf nodes fall into $(2n-1)!!$ distinct strata, but the
analogous number for merge trees is equal to the number of maximal chains in
the lattice of partitions, i.e., $(n+1)!n!2^{-n}$. The second aspect of our
study is the derivation of precise formulas for the distribution of tree
realization numbers (the number of merge trees realizing a given barcode) when
we assume that barcodes are sampled using a uniform distribution on the
symmetric group. We are able to characterize some of the higher moments of this
distribution, thanks in part to a reformulation in terms of Dirichlet
convolution. This characterization provides a type of null hypothesis,
apparently different from the distributions observed in real neuron data and
opens the door to doing more precise science.
