Distributions on bicoloured binary trees arising from the principle of parsimony

The distribution of binary trees with bicoloured endpoints under the taxonomic principle of parsimony is examined. Part one provides a constructive proof of an expression which describes the distribution of binary trees for a fixed colouring in terms of simple tree-related quantities. The result relies on Menger’s theorem and an invariance property of binary trees. In part two a second invariance property gives the dual distribution, where the tree is fixed and the colourings vary. Applications to taxonomy, and the extension of results to r-colourings (r>2) are outlined briefly.