  We investigate the number of permutations that occur in random labellings of
trees. This is a generalisation of the number of subpermutations occurring in a
random permutation. It also generalises some recent results on the number of
inversions in randomly labelled trees. We consider complete binary trees as
well as random split trees a large class of random trees of logarithmic height
introduced by Devroye in 1998. Split trees consist of nodes (bags) which can
contain balls and are generated by a random trickle down process of balls
through the nodes.
  For complete binary trees we show that asymptotically the cumulants of the
number of occurrences of a fixed permutation in the random node labelling have
explicit formulas. Our other main theorem is to show that for a random split
tree, with high probability the cumulants of the number of occurrences are
asymptotically an explicit parameter of the split tree. For the proof of the
second theorem we show some results on the number of embeddings of digraphs
into split trees which may be of independent interest.
