define a separable permutation to be a permutation that has a separating tree: a rooted binary tree in which the elements of the permutation appear (in permutation order) at the leaves of the tree, and in which the descendants of each tree node form a contiguous subset of these elements. Each interior node of the tree is either a positive node in which all descendants of the left child are smaller than all descendants of the right node, or a negative node in which all descendants of the left node are greater than all descendants of the right node. There may be more than one tree for a given permutation: if two nodes that are adjacent in the same tree have the same sign, then they may be replaced by a different pair of nodes using a tree rotation operation.
