On the sub-permutations of pattern avoiding permutations

There is a deep connection between permutations and trees. Certain sub-structures of permutations, called sub-permutations, bijectively map to sub-trees of binary increasing trees. This opens a powerful tool set to study enumerative and probabilistic properties of sub-permutations and to investigate the relationships between ‘local’ and ‘global’ features using the concept of pattern avoidance.First, given a pattern μμ, we study how the avoidance of μμ in a permutation ππ affects the presence of other patterns in the sub-permutations of ππ. More precisely, considering patterns of length 3, we solve instances of the following problem: given a class of permutations KK and a pattern μμ, we ask for the number of permutations π∈Avn(μ)π∈Avn(μ) whose sub-permutations in KK satisfy certain additional constraints on their size.Second, we study the probability for a generic pattern to be contained in a random permutation ππ of size nn without being present in the sub-permutations of ππ   generated   by the entry 1≤k≤n1≤k≤n. These theoretical results can be useful to define efficient randomized pattern-search procedures based on classical algorithms of pattern-recognition, while the general problem of pattern-search is NP-complete.